Knapsack Based Public-Key Encryption: Suppose M=(m1, m2, ...,mn) is a binary message E(KM)=<K,M>=∑k;m; Decryption: Given: cipher text Z,N,Y,X Computing N-I mod Y D(=GREEDY(ZN- mod Y,X)
11 Knapsack Based Public-Key • Encryption: Suppose M = (m1 , m2 ,…, mn ) is a binary message – E(K,M) = <K,M> = ki mi • Decryption: Given: cipher text Z, N, Y, X – Computing N-1 mod Y – D(Z) = GREEDY(Z N-1 mod Y, X)
Correctness ZN- modY= <KMeN-I mod y <XNM>N-I Y <XM> mod Y Therefore, greedy on ZN- mod Y is like greedy on <X, M> and hence we can find m 12
12 Correctness Z N-1 mod Y = <K,M> N-1 mod Y = < XN,M>N-1 mod Y = < X,M> mod Y = <X,M> Therefore, greedy on Z N-1 mod Y is like greedy on <X,M> and hence we can find M
Example X=(2,3,6,13,27,52) Y=105 andn=31 2*31mod105=62 3*31mod105=93 6*31mod105=81 13*31mod105=88 27*31mod105=102 52*31mod105=37 K=(62,93,81,88,102,37) 13
13 Example • X = (2,3,6,13,27,52) • Y = 105 and N = 31 – 2*31 mod 105 = 62 – 3*31 mod 105 = 93 – 6*31 mod 105 = 81 – 13*31 mod 105 = 88 – 27*31 mod 105 = 102 – 52*31 mod 105 = 37 • K = (62,93,81,88,102,37)
Example: Encryption °K=(62,9381,8,102,37) ·M=01100011010110l110 Break up in to three sub messages M1=(011000) M2=(110101) M3=(101110 °E(M1)=93+81=174 E(M2)=62+93+88+37=280 E(M3)=62+81+88+102=333
14 Example: Encryption • K = (62,93,81,88,102,37) • M = 011000110101101110 • Break up in to three sub messages – M1 = (011000) – M2 = (110101) – M3 = (101110) • E(M1 ) = 93 + 81 = 174 • E(M2 ) = 62+93 + 88+ 37 = 280 • E(M3 ) = 62+81+ 88+102 = 333
Example: Decryption X=(2,3,6,13,27,52),N1=61 D(MI)=GREEDY(61*174 mod 105) GREEDY(9)=(01000 D(M2)=GREEDY(61* 280 mod 105) GREEDY(70)=(110101 D(M3)=GREEDY(61*333 mod 105) GREEDY(48)=(1011010) M=011000110101010110 15
15 Example: Decryption • X = (2,3,6,13,27,52), N-1 = 61 • D(M1) = GREEDY(61*174 mod 105) = GREEDY(9) = (011000) • D(M2) = GREEDY(61*280 mod 105) = GREEDY(70) = (110101) • D(M3) = GREEDY(61*333 mod 105) = GREEDY(48) = (1011010) • M = 011000110101010110