Knapsack Based Public-Key Encryption: Suppose M=(ml, m2, .,mn) is a binary message E(KM)=<KM>=∑k;m Decryption: Given: cipher textZ,N,Y,X Computing n-modY D(2= 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-I modY <KM>N-I mod Y <XNM>N-I mod Y <XM> mody 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,9381,88,102,37)
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=011000l10101101110 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,36,13,27,52),N1=61 D(M1)=GREEDY(61*174 mod 105) GREEDY(9)=(011000 D(M2)=GREEDY(61 *280 mod 105) GREEDY(70)=(11001) 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