Iškrauti kuprinę nėra sunkiau negu ją sudėti. Galbūt netgi lengviau. O dabar panagrinėkime, ką reiškia sudėti ir iškrauti ne kasdienę, bet matematinę kuprinę.

Tegu

$\begin{eqnarray*} W=<w_0, w_1, ..., w_{n-1}> (1) \end{eqnarray*}$

yra natūraliųjų skaičių seka; jos elementus vadinsime svoriais. Pasirinkime skaičius $x_0, x_1, ..., x_{n-1}$ , kurie yra lygūs nuliui arba vienetui. Jei $ x_i = 0 $ , tai svorio $ w_i $ nedėsime į kurpinę, jei $ x_i = 1 $ - dėsime. Dabar raskime, kiek svers mūsų kuprinė. Jos svoris yra skaičius

$\begin{eqnarray*} c = x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n - 1} \cdot w_{n - 1} (2) \end{eqnarray*}$

Taigi sudėti kuprinę iš (1) sistemos svorių reiškia pasirinkti skaičius $x_0, x_1, ..., x_{n-1}$ , kurie lygūs nuliui arba vienetui, ir apskaičiuoti (2) svorį. Tai nesudėtingas skaičiavimo uždavinys.

O kaip su matematinės kuprinės iškraustymu?

Iškraustyti matematinę kuprinę reiškia žinant (1) svorių sistemą ir skaičių $c$ rasti skaičius $x_i \in \lbrace 0, 1 \rbrace$ , kad būtų teisinga (2) lygybė. Kad tai gali būti nelengvas uždavinys, galima pavaizduoti pavyzdžiu.

Tegu yra svorių seka

$\begin{eqnarray*} W = < 25, 27, 35, 48, 59, 67, 75 > \end{eqnarray*}$

ir svoris $ c = 127 $ . Iškraustykite kurpinę, t.y. raskite $x_i \in \lbrace 0, 1 \rbrace$ , kad būtų teisinga lygybė

$\begin{eqnarray*} 127 = 25x_0 + 27x_1 + 35x_2 + 48x_3 + 59x_4 + 67x_5 + 75x_6 \end{eqnarray*}$

Tikriausiai reiks šiek tiek padirbėti tikrinant variantus. Tačiau kartais iškraustyti matematinę kuprinę būna taip pat paprasta, kaip ir sudėti.

Tarkime mūsų svoriai yra tokie:

$\begin{eqnarray*} W = < 1, 2^1, 2^2, 2^3, 2^4, 2^5, 2^6, 2^7, 2^8 > (3) \end{eqnarray*}$

Sistemos svoriai sparčiai didėja: sekantis svoris yra didesnis už visų ankstesnių svorių sumą:

$\begin{eqnarray*} 1 + 2^1 + 2^2 + ... + 2^{m-1} = 2^m - 1 < 2^m \end{eqnarray*}$

Iškraustyti kuprinę nesudėtinga. Pavyzdžiui, tegu svoris yra $ c= 251 $ . Reikia rasti skaičius $x_i \in \lbrace 0, 1 \rbrace$ , kad būtų teisinga lygybė

$\begin{eqnarray*} 251 = x_0 + 2x_1 + 2^2x_2 + ... + 2^8x_8 \end{eqnarray*}$

Kadangi $ 2^7 < 251 < 2^8 $ , tai turi būti $ x_8 = 0, x_7 = 1 $ , t.y.

$\begin{eqnarray*} 251 &=& x_0 + 2x_1 + 2^2x_2 + ... + 2^6x_6 + 2^7 \cdot 1, \\ 123 &=& x_0 + 2x_1 + 2^2x_2 + ... + 2^6x_6. \end{eqnarray*}$

Kadangi $ 2^7 < 123 $ , tai turi būti $ x_6 = 1 $ , taigi

$\begin{eqnarray*} 123 &=& x_0 + 2x_1 + 2^2x_2 + ... + 2^5x_5 + 2^6 \cdot 1, \\ 59 &=& x_0 + 2x_1 + 2^2x_2 + ... + 2^5x_5. \end{eqnarray*}$

Panašiai samprotaudami gauname, kad turi būti

$\begin{eqnarray*} x_5 = 1, x_4 = 1, x_3 = 1, x_2 = 0, x_1 = 1, x_0 = 1 , \end{eqnarray*}$

Taigi

$\begin{eqnarray*} 251 = 1 \cdot 1 + 2^1 \cdot 1 + 2^2 \cdot 0 + 2^3 \cdot 1 + 2^4 \cdot 1 + 2^5 \cdot 1 + 2^6 \cdot 1 + 2^7 \cdot 1. \end{eqnarray*}$

Jeigu su visais $0 \leq m < n - 1$ (1) svorių sistemos nariai tenkina nelygybę

$\begin{eqnarray*} w_0 + w_1 + ... + w_{m - 1} < w_m, \end{eqnarray*}$

tai tokią svorių sistemą vadinsime sparčiai didėjančių svorių sistema. Taigi (3) yra sparčiai didėjančių svorių sistema. Panašiai, kaip šios sistemos atveju, kuprinės iškraustymo uždavinį galima greitai išspręsti ir turint bet kurią kitą sparčiai didėjančių svorių sistemą.

Taigi sparčiai didėjančių svorių sistemos atveju kuprinės iškraustymo uždavinį galima išspręsti lengvai, o kitais atvejais - sunkiai.

Merkle ir Hellmann pastebėjimai

R. Merkle ir M. Hellmanas 1975 metais atkreipė dėmesį, kad matematinės kuprinės sudėjimas ir iškraustymas primena šifravimą ir dešifravimą.

$\begin{array}{ll} \mbox{ Pranešimas } m = x_0 \\ \mbox{ Svoriai } w_0,w_1 \end{array} \longrightarrow \begin{array}{ll} \mbox{ $c = x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n-1} \cdot w_{n-1}$ } \\ \mbox{ $c$ - pranešimo $m$ sifras } \end{array}$

$\mbox{ Sudėti kuprinę - šifruoti pranešimą }$

$\begin{array}{ll} \mbox{ Šifras } c \\ \mbox{ Svoriai } w_0, w_1, ..., w_{n-1} \end{array} \longrightarrow \begin{array}{ll} c = x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n-1} \cdot w_{n-1} \\ m = x_0 x_1 ... x_{n-1} \end{array}$

$\mbox{ Iškrauti kuprinę - iššifruoti pranešimą }$

Kad būtų lengva šifruoti ir iššifruoti reikia naudotis, pavyzdžiui, sparčiai didėjančių svorių sistema. Ši svorių sistema būtų kriptosistemos raktas, kurį turėtų saugoti abu ryšio dalyviai. Gautume simetrinę kriptosistemą ir tiek. Tačiau R. Merkle ir M. Hellmanas norėjo sukurti viešojo rakto kriptosistemą. Panagrinėkime, kaip jie tai padarė.

Šifravimas

Sudarysime Merkle-Hellmano viešojo rakto kriptosistemą, kuria naudojantis bus galima siųsti šifruotus pranešimus Birutei. Pradėkime nuo privataus rakto sudarymo. Pasirinkime sparčiai didėjančių svorių sistemą

$\begin{eqnarray*} W = < w_0,w_1,...,w_{n-1} >, \end{eqnarray*}$

po to pasirinkime skaičių $ N $ , kad būtų

$\begin{eqnarray*} N > w_0 + w_1 + ... + w_{n-1}. \end{eqnarray*}$

Dabar pasirinkime kokį nors natūralųjį skaičių $ s > 1 $ , kad būtų $ DBD(s, N) = 1 $ . Skaičius $ s $ turi atvirkštinį moduliu N, raskime jį. Tegu tas atvirkštinis yra $ t $ , taigi

$\begin{eqnarray*} (s \cdot t)(modN) = 1 \end{eqnarray*}$

Privataus rakto parinkimas baigtas. Privatųjį Birutės raktą sudaro:

: Svorių sistema $W = < w_0,w_1,...,w_{n-1} >$ , skaičiai .

Dabar sudarykime viešąjį raktą. Naudodamiesi skaičiumi s, sudarykime naują svorių sistemą

$\begin{eqnarray*} V = < v_0, v_1, ..., v_{n-1}>, \mbox{ \hspace{40} } v_i = (w_i \cdot s)(modN). \end{eqnarray*}$

Ši naujoji svorių sistema ir yra viešasis raktas. Ją sudaro nebe sparčiai didėjantys svoriai. Vadinasi, viešasis raktas yra tiesiog sugadinta sparčiai didėjančių svorių sistema.

Taigi Algis, norėdamas nusiųsti Birutei pranešimą $m = x_0x_1...x_{n-1}$ , gali nusiųsti šifrą

$\begin{eqnarray*} c = x_0 \cdot v_0 + x_1 \cdot v_1 + ... + x_{n-1} \cdot v_{n-1}. \mbox{ \hspace{40} (4) } \end{eqnarray*}$

Jeigu svorių skaičius sistemoje $ V $ yra didelis, o svoriai nėra sparčiai didėjantys, galime nebijoti, kad kriptoanalitikas Zigmas iššifruos sugautą šifrą (suras skaičius, tenkinančius (4) lygybę, jei žinoma reikšmė $ c $ ir svoriai $ v_i $ ). Žinoma, sugaišęs daug laiko jis gali tai padaryti, tačiau tada pranešimas bus tikriausiai nebevertingas ir jo pastangos nueis vėjais.

Iššifravimas

O ką daryti su šifru $ c $

pačiai Birutei? Juk ieškoti skaičių $ x_i $

iš (4) lygybės jai taip pat sunku. Tačiau jai to daryti ir nereikia. Ji žino, kad blogi svoriai $ v_i $

gauti iš gerų svorių $ w_i $

ir gali dabar tuo pasinaudoti. Iš tikrųjų, kadangi $v_i = (w_i \cdot s)(modN)$ , tai $v_i = w_i \times_N s$ . Tačiau skaičius $ t $

yra skaičiaus $ s $

atvirkštinis moduliu N, t.y. $s \times_N t = 1$ . Padauginę lygybę $v_i = w_i \times_N s$ iš t moduliu N gautume

$\begin{eqnarray*} v_i \times_N t = w_i \times_N s \times_N t = w_i \times_N (s \times_N t) = w_i \times_N 1 = w_i. \end{eqnarray*}$

Jeigu iš $ t $ moduliu $ N $ padaugintume lygybę

$\begin{eqnarray*} c = x_0 \cdot v_0 + x_1 \cdot v_1 + ... x_{n-1} \cdot v_{n-1} \end{eqnarray*}$

gautume:

$\begin{eqnarray*} c \times_N t &=& x_0 \cdot (v_0 \times_N t) + x_1 \cdot (v_1 \times_N t) + ... + x_{n-1} \cdot (v_{n-1} \times_N t) \\ &=& x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n-1} \cdot w_{n-1}. \end{eqnarray*}$

Taigi

$\begin{eqnarray*} (c \cdot t)(modN) = (x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n-1} \cdot w_{n-1})(modN). \end{eqnarray*}$

Tačiau reiškinys

$\begin{eqnarray*} x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n-1} \cdot w_{n-1} \end{eqnarray*}$

yra mažesnis už $ N $ . Vadinasi, galima tiesiog rašyti

$\begin{eqnarray*} (c \cdot t)(modN) = x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n-1} \cdot w_{n-1}. \end{eqnarray*}$

Štai ši lygybė ir rodo, kaip turi elgtis Birutė. Apskaičiavusi sandaugos $c \cdot t$ dalybos iš $ N $ liekaną $c' \mbox{ \hspace{20} } (c' = (c \cdot t)(modN)$ , ji gali ieškoti skaičių $x_0,x_1,...,x_{n-1}$ iš lygybės

$\begin{eqnarray*} c' = x_0 \cdot w_0 + x_1 \cdot w_1 + ... + x_{n-1} \cdot w_{n-1}. \end{eqnarray*}$

Taigi dešifruojant Birutei tenka spręsti kuprinės iškraustymo uždavinį, kai svoriai sudaro sparčiai didėjančią seką.

Aptartoji kriptosistema taip ir vadinama - kuprinės kriptosistema (knapsack cryptosystem).

Generated on Fri Dec 30 20:04:12 2005 for knapsack by

1.4.5 [sepa]

Algoritmas

Sudėti ir iškrauti kuprinę.

Merkle ir Hellmann pastebėjimai

Šifravimas

Iššifravimas