GC Figa

V nasledujúcom texte objasníme spôsob šifrovania s verejným kľúčom, tzv. Merkle-Hellman knapsack problém.
Metóda je založená na obtiažnosti riešenia, tzv. problému naplnenia ruksaku (knapsack problem), ktorý znie takto: máme zbaliť n predmetov, ktorých objemy a1, a2, ..., an poznáme. Priniesli sme si ruksak s objemom S a pýtame sa, či je možné tento ruksak plne využiť. Teda, či je možné číslo S napísať ako súčet niektorých z daných čísiel. To môžeme formulovať ako hľadanie binárneho slova x=x1x2...xn takého, že platí
S=x1a1+x2a2+...+xnan=x*a
Pre naše potreby toľko z teórie stačí. Viac o tejto teórii šifrovania z verejným kľúčom nájdete v odborných publikáciach kryptografického zamerania bez problémov na internete.

Zverejnili sme vektor, ktorým sme zašifrovali správu, tzv. obtiažny knapsack problem v tvare
a=(115984, 5145, 114866, 100746, 122147, 48951, 97390, 60715, 47593, 77092, 16095, 55333, 92982, 58511, 106591, 118611);
Prijatú šifru dešifrujeme takto:
Číslom w násobíme šifru S a zredukujume modulo m.
Potom už riešime ľahký knapsack problém.
m=13031;
v=118611;
w=125534;
a'=(65458, 32766, 16140, 8099, 4087, 1963, 970, 484, 246, 124, 53, 28, 14, 6, 2, 1 );
Príklad.
Dekódovanie 781395.
Najprv vypočítame c'=w*S mod(m)= 38244.
c' = 38244 < 65458 = a(16) ==> p(16) = 0 , c' = 38244 - 0 = 38244
c' = 38244 >= 32766 = a(15) ==> p(15) = 1 , c' = 38244 - 32766 = 5478
c' = 5478 < 16140 = a(14) ==> p(14) = 0 , c' = 5478 - 0 = 5478
c' = 5478 < 8099 = a(13) ==> p(13) = 0 , c' = 5478 - 0 = 5478
c' = 5478 >= 4087 = a(12) ==> p(12) = 1 , c' = 5478 - 4087 = 1391
c' = 1391 < 1963 = a(11) ==> p(11) = 0 , c' = 1391 - 0 = 1391
c' = 1391 >= 970 = a(10) ==> p(10) = 1 , c' = 1391 - 970 = 421
c' = 421 < 484 = a(9) ==> p(9) = 0 , c' = 421 - 0 = 421
c' = 421 >= 246 = a(8) ==> p(8 ) = 1 , c' = 421 - 246 = 175
c' = 175 >= 124 = a(7) ==> p(7) = 1 , c' = 175 - 124 = 51
c' = 51 < 53 = a(6) ==> p(6) = 0 , c' = 51 - 0 = 51
c' = 51 >= 28 = a(5) ==> p(5) = 1 , c' = 51 - 28 = 23
c' = 23 >= 14 = a(4) ==> p(4) = 1 , c' = 23 - 14 = 9
c' = 9 >= 6 = a(3) ==> p(3) = 1 , c' = 9 - 6 = 3
c' = 3 >= 2 = a(2) ==> p(2) = 1 , c' = 3 - 2 = 1
c' = 1 >= 1 = a(1) ==> p(1) = 1 , c' = 1 - 1 = 0

Správa je 1111101101010010 = 64338