Intro('Tzv. batohov² algoritmus (zalo₧en na batohovΘm problΘmu) je jeden z prvnφch pokus∙ jak se vyrovnat s hlavnφ nev²hodou symetrickΘ kryptografie û s nutnostφ bezpeΦnΘho p°enosu Üifrovacφho klφΦe p°edtφm, ne₧ se vlastnφ Üifra pou₧ije. MatematickΘ schΘma, na kterΘm systΘm stojφ, pat°φ do kategorie tzv. NP-complete (non-polynomial, tedy kompletn∞ nepolynomißlnφch) problΘm∙. ╪eÜenφ takov²chto ·loh nenφ zatφm znßmΘ v polynomißlnφm, n²br₧ pouze v exponencißlnφm Φase. VÜechny takovΘto problΘmy jsou na sebe navzßjem p°evoditelnΘ. Pokrok v °eÜenφ jednoho z nich se tedy promφtne na vÜech ostatnφch.');
V∞tÜina Üifrovacφch algoritm∙, kterΘ jsou na batohu zalo₧eny, byly ovÜem ji₧ dßvno ·pln∞ rozbity, nicmΘn∞ dodnes, nehled∞ na jejich zajφmavost, velmi dob°e demonstrujφ principy a zßkladnφ algebru asymetrickΘ kryptografie.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Samotn² problΘm ale vy°eÜen nebyl. Zßdrhel je toti₧ v tom, ₧e navr₧enΘ kryptografickΘ schΘma neodpovφdalo matematickΘmu problΘmu ·pln∞. Privßtnφ klφΦ, jak se po zkoumßnφ zjistilo, je mo₧nΘ mo₧nΘ vypoΦφtat z klφΦe ve°ejnΘho i bez °eÜenφ p°φsluÜnΘ obtφ₧nΘ ·lohy, tj. batohu v danΘ konfiguraci (viz dßle). ProblΘm °eÜenφ batohu nebyl prost∞ s problΘmem v²poΦtu tajnΘho klφΦe ekvivalentnφ. Kdyby Üifrovacφ algoritmus byl p°esnou logickou kopiφ batohu, byl by dodnes bezpeΦn² minimßln∞ tak bezpeΦn², jak t∞₧kΘ je °eÜenφ jakΘhokoliv NP-complete problΘmu.
Batohov² problΘm mß nßsledujφcφ jednoduchΘ zadßnφ. Mßme k dispozici mno₧inu v∞cφ, ka₧dou o urΦitΘ kladnΘ hmotnosti. NaÜφm ·kolem je vybrat takovou podmno₧inu, aby jejφ celkovß "hmotnost" byla rovna n∞jakΘ hodnot∞ <SPAN Class=CODE>w</SPAN>.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Jak se ·loha m∙₧e jevit na prvnφ pohled jednoduchß, ve skuteΦnosti Φas pot°ebn² k °eÜenφ nar∙stß exponencißln∞ s celkov²m poΦtem p°edm∞t∙. Nenφ znßm postup, jak dojφt k ·sp∞ÜnΘmu °eÜenφ v polynomißlnφm Φase a mnoho lidφ v∞°φ, ₧e v n∞m na deterministickΘm Turningov∞ stroji nenφ °eÜitelnß. To je velmi dobr² model dneÜnφch poΦφtaΦ∙ (na nedeterministickΘm stroji ·loha °eÜitelnß je, nicmΘn∞ v tomto p°φpad∞ se p°ipouÜtφ mo₧nost paralelnφho v²poΦtu "v∞tvφ" backtrackingu).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
NicmΘn∞ existujφ batohy, jejich₧ °eÜenφ je trivißlnφ. Je to v p°φpad∞, ₧e hmotnost ka₧dΘ polo₧ky nenφ ni₧Üφ, ne₧ hmotnost polo₧ek p°edchßzejφcφch dohromady. Takov²to batoh naz²vßme superrostoucφ (superincreasing).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
P°i v²poΦtu °eÜenφ budeme postupovat nßsledovn∞. Nejprve vezmeme nejt∞₧Üφ objekt. Pokud je jeho hmotnost menÜφ ne₧ celkovß po₧adovanß hmotnost <SPAN Class=CODE>w</SPAN>, za°adφme jej do ôpou₧it²chö v∞cφ a od <SPAN Class=CODE>w</SPAN> odeΦteme jeho hmotnost. Pokud ne, nechßme jej b²t a pokraΦujeme dßle. Pokud jsme po prozkouÜenφ vÜech v∞cφ nedosßhli cht∞nΘ hmotnosti (tj. kdy₧ <SPAN Class=CODE>w != 0</SPAN>), nemß ·loha s tφmto zadßnφm °eÜenφ.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Mßme tedy k dispozici lehkou a t∞₧kou variantu problΘmu. K jeho p°etvo°enφ na Üifrovacφ algoritmus s ve°ejn²m (a soukrom²m) klφΦem pot°ebujeme jeÜt∞ dv∞ v∞ci. Jednak musφme vymyslet, jak budeme vlastnφ data Üifrovat (tj. jak bude vypadat matematickß funkce, kterß p°evßdφ s ·Φastφ klφΦe otev°en² text na text zaÜifrovan²) a jak budeme konvertovat batoh "lehk²" na batoh "t∞₧k²". Merkle a Hellman navrhli nßsledujφcφ metodu.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Konverze z tajnΘho klφΦe, tj. ze superrostoucφho batohu, na klφΦ ve°ejn², tj. na normßlnφ obtφ₧n∞ °eÜiteln² batoh) bude probφhat nßsledujφcφm zp∙sobem. Zvolφme modulo <SPAN Class=CODE>m</SPAN>, co₧ bude Φφslo v∞tÜφ ne₧ celkov² souΦet hodnot ("hmotnost") <SPAN Class=CODE>w</SPAN>.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Dßle zvolφme druhΘ Φφslo <SPAN Class=CODE>n</SPAN> tak, ₧e <SPAN Class=CODE>(n,m)=1</SPAN>, jin²mi slovy v a m nemajφ ₧ßdnΘho spoleΦnΘho d∞litele, jsou nesoud∞lnß (v anglickΘ literatu°e takΘ Φasto oznaΦovßno jako relative prime).
Vynßsobφme ka₧dou hodnotu prvku mno₧iny Φφslem <SPAN Class=CODE>n (mod m)</SPAN>. N∞kterΘ zdroje na tomto mφst∞ jeÜt∞ udßvajφ vhodnost (pseudo-) nßhodnΘ permutace v²sledku, kterß hraje d∙le₧itou roli p°i luÜt∞nφ tΘto Üifry. Zde jsem ji pro zjednoduÜenφ vypustil.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
K zaÜifrovßnφ jednoho bitu pou₧ijeme 1, pokud jsme p°φsluÜn² objekt do batohu zahrnuli a 0 pokud ne.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
P°φjemce vynßsobφ hodnoty zaÜifrovanΘho textu <SPAN Class=CODE>z<SUP>-1</SUP> mod m</SPAN>, co₧ p°edstavuje inverzi n mod m a pou₧ije vznikl² superrostoucφ batoh k deÜifrovßnφ zprßvy. Pokud tedy platφ, ₧e <SPAN Class=CODE>a*z</SPAN> je kongruentnφ s <SPAN Class=CODE>1 (mod m)</SPAN>, snadno ukß₧eme, ₧e <SPAN Class=CODE>(a*n mod m)*z mod m = a</SPAN>. Tohoto vztahu budeme vyu₧φvat p°i vzßjemnΘm p°epoΦφtßvßnφ (tj. vlastn∞ Üifrovßnφ a deÜifrovßnφ) z normßlnφho batohu do superrostoucφho a naopak.
</DIV></FONT></b></i>
<A Name="Title2"><FONT Size=3><DIV Class=Headline>Nenφ nad praktickou ukßzku</DIV></font>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Nßzorn² p°φklad je v₧dy nad vÜφ teorii, uva₧me tedy batoh <SPAN Class=CODE>[3,4,9,19,38,77]</SPAN>. Zvolφme modul <SPAN Class=CODE>m</SPAN>, v∞tÜφ ne₧ souΦet vÜech polo₧ek batohu, nap°φklad 155. Jako s <SPAN Class=CODE>m</SPAN> nesoud∞lnΘ <SPAN Class=CODE>n</SPAN> zvolφme t°eba 27. Nynφ vypoΦφtßme hodnoty obtφ₧n∞ °eÜitelnΘho batohu.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
<SPAN Class=CODE>
3*27 mod 155 = 81<br>
4*27 mod 155 = 108<br>
9*27 mod 155 = 88<br>
19*27 mod 155 = 48<br>
38*27 mod 155 = 96<br>
77*27 mod 155 = 64<br>
</SPAN>
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Budeme tedy Üifrovat s ve°ejn²m klφΦem <SPAN Class=CODE>[81,108,88,48,96,64]</SPAN>. Zprßvu <SPAN Class=CODE>100110001101010001</SPAN> si nejprve rozd∞lφme do jednotliv²ch blok∙, v tomto p°φpad∞ po Üesti bitech (naÜe sada "v∞cφ" mß Üest hodnot).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
<SPAN Class=CODE>100110 001101 010001</SPAN>
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Podφvßme-li se na prvnφ blok, nalezneme hodnoty 1 na prvnφm, ΦtvrtΘm a pßtΘm mφst∞. To odpovφdß Φφsl∙m 81, 48 a 96 ve ve°ejnΘm batohu, zaÜifrovan² text tedy bude 81+48+96=225. Obdobn∞
V²sledn² zaÜifrovan² text je tedy <SPAN Class=CODE>[255,200,172]</SPAN>. Pro deÜifrovßnφ musφme znßt inverzi <SPAN Class=CODE>n mod m</SPAN>. Jak u₧ bylo °eΦeno, je to takovß hodnota <SPAN Class=CODE>n*z</SPAN>, pro kterou platφ <SPAN Class=CODE>n*z = = 1 (mod m)</SPAN> (= = zde p°edstavuje kongruenci). S pomocφ tohoto Φφsla jednoduÜe pro ka₧d² blok spoΦφtßme <SPAN Class=CODE>b*z (mod m)</SPAN>. V naÜem p°φpad∞ <SPAN Class=CODE>z=23</SPAN>.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
<SPAN Class=CODE>
225*23 mod 155 = 60 = 3+19+38 = 100110<br>
200*23 mod 155 = 105 = 9+19+77 = 001101<br>
172*23 mod 155 = 81 = 4+77 = 010001<br>
</SPAN>
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Dostali jsme v²slednou hodnotu <SPAN Class=CODE>100110001101010001</SPAN>, kterß odpovφdß p∙vodnφ zprßv∞.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Pozd∞ji bylo batohovΘ schΘma äobohacenoô o mo₧nost digißlnφho podpisu dokument∙, obdobn∞ jak je tomu mo₧nΘ jako nap°φklad u algoritmu RSA. O prolomenφ tohoto schΘmatu si m∙₧ete p°eΦφst nap°φklad na strßnce <a href=../www.cs.wm.edu/~hallyn/public_key/break.html> http://www.cs.wm.edu/~hallyn/public_key/break.html</a> (z tohoto webu byl p°evzat p°φklad). Pozd∞ji byl tento algoritmus zkouÜen jako iteraΦnφ. ╪φkß se, ₧e se Ralph Merkle vsadil o tisφc dolar∙, ₧e nikdo nerozluÜtφ zprßvu 40ti-nßsobn∞ zaÜifrovanou. Prohrßl.
