MASARYKOVA UNIVERZITA V B R N Ě Přírodovědecká fakulta 1^ i ľ ^ \ S^ W jpg % S A R Y ^ Jiřina Forbelská L L L ALGORITMUS A JEHO APLIKACE Bakalářská práce Vedoucí práce: Mgr. Michal Bulant, Ph.D. Brno, 2006 Jméno a příjmení autora: Název bakalářské práce: Název v angličtině: Studijní program: Studijní obor: Vedoucí bakalářské práce: Rok obhajoby: Klíčová slova v češtině: Klíčová slova v angličtině: Jiřina Forbelská LLL algoritmus a jeho aplikace LLL algorithm and its applications Matematika Matematika se zaměřením na vzdělávání, Informatika a druhý obor Mgr. Michal Bulant, Ph.D. 2006 Gram-Schmidtův ortogonalizační proces, mřížka, LLL algoritmus, Merkle-Hellman šifrovací systém Gram-Schmidt Orthogonalization, lattice, LLL algorithm, Merkle-Hellman Knapsack Cryptosystem LLL algoritmus publikovali v roce 1982 A. K. Lenstra, H. W. Lenstra a L. Lovász jako algoritmus pro faktorizaci polynomů s racionálními koeficienty. LLL algoritmus hledá redukovanou bázi nebo nejkratší vektor mřížky, avšak mnoho zajímavých matematických i informatických problémů lze převést na některý z těchto problémů volbou vhodné mřížky. Cílem práce je představit LLL algoritmus, jeho teoretické aspekty a matematické pozadí, ale i četné aplikace. Na příkladu kryptoanalýzy Merkle-Hellman šifrovacího systému je pak ukázáno použití LLL algoritmu včetně konkrétních příkladů. LLL algortihm was invented in 1982 by A. K. Lenstra, H. W. Lenstra and L. Lovász for factoring polynomials with rational coefficients. LLL algorithm is using for searching for reduced basis or the shortest vector of a lattice, but many interesting problems from mathematics and informatics can be transformed to these problems with a fitted lattice. The intention of this thesis is to introduce the LLL algorithm, its theoretical aspects, mathematical background and its multiple applications. There is shown an application of LLL algorithm including the illustrations in the thesis: the cryptoanalysis of Merkle-Hellman Knapsack Cryptosystem. Prohlášení Prohlašuji, že tuto práci jsem vypracovala samostatně. Veškerou literaturu a ostatní prameny, z nichž jsem při přípravě práce čerpala, řádně cituji a uvádím v seznamu použité literatury. V Brně 9. 5. 2006 Jiřina Forbelská Poděkování Chtěla bych poděkovat Mgr. Michalu Bulantovi, Ph.D., vedoucímu práce, za cenné připomínky, podněty a motivaci v průběhu psaní práce. Jsem vděčná také všem učitelům a spolužákům, kteří mi pomohli získat potřebné znalosti a dovednosti, především Mgr. Martinu Dvořákovi, Ph.D. a RNDr. Romanu Plchovi, Ph.D., díky kterým jsem získala dovednosti klíčové pro napsaní této práce. Zvláštní dík patří i mému manželovi a rodičům za jejich podporu při studiu. Obsah Úvod 6 Často používané označení 8 1 Matematický základ algoritmu 9 1.1 Kvadratické a bilineární formy, prostory se skalárním součinem 9 1.2 Mřížky 13 2 LLL algoritmus 19 2.1 LLL-redukovaná báze 19 2.2 Popis LLL algoritmu 22 3 Aplikace 29 3.1 Problém batohu 31 3.2 Šifrovací systémy založené na problému batohu - prohraná sázka kryptografie? 32 3.2.1 Šifrovací systémy Merkle-Hellman založené na problému batohu 32 3.2.2 Kryptoanalýza Merkle-Hellman šifrovacího systému založeného na aditivním problému batohu 34 3.2.3 Řešení batohů s nízkou hustotou 35 3.2.4 Využití diofantických aproximací 37 3.2.5 Bezpečnost a budoucnost těchto šifrovacích systémů . . 42 Seznam použité literatury 42 Přílohy 47 A pseudokód LLL algoritmu 48 B Šifrovací systém Merkle-Hellman 50 Úvod LLL algoritmus publikovali v roce 1982 A. K. Lenstra, H. W. Lenstra a L. Lovász jako algoritmus pro faktorizaci polynomů s racionálními koeficienty v článku [31], který spolu s [7, Chapter 2] tvoří hlavní zdroje, z kterých tato práce čerpá. Jedná se o poměrně jednoduchý algoritmus, který lze snadno naprogramovat a jehož pochopení nevyžaduje žádné speciální znalosti. Ihned po svém zveřejnění se však stal katalyzátorem dalšího vývoje a to v matematice, v informatice, ale také v kryptoanalýze a kryptografii. Velice rychle byla nacházena jeho další a další použití, algoritmus byl postupně specializován pro jednotlivé aplikace, ale také různě zefektivňován. Proto bude naším cílem představit tento algoritmus českému čtenáři. Rozsah práce bohužel nedovoluje věnovat se této problematice v celé její šíři, proto často odkazujeme na další zdroje, které mohou dotvořit představu o algoritmu a jeho aplikacích i o dalších souvislostech. Na straně čtenáře předpokládáme základní znalosti z lineární algebry a geometrie (alespoň na úrovni bakalářského studia učitelství matematiky či elektronického učebního textu [50]). Algoritmus je postaven na zobecnění Gram-Schmidtova ortogonalizačního procesu, který můžeme provádět v prostorech se skalárním součinem. Teorii těchto prostorů stručně připomínáme v 1. části 1. kapitoly, přičemž vybíráme pouze základní věty a definice, které jsou klíčové pro porozumění LLL algoritmu. Pomíjíme zde důkazy a často i některé souvislosti mezi definovanými pojmy - tohoto zjednodušení se dopouštíme především proto, že k tématu existuje dostatek kvalitní literatury i v češtině a slovenštině, především [50, 21, 2]. Podrobně dokazujeme pouze samotný Gram-Schmidtův ortogonalizační proces, kde zavádíme i označení používané v celé další práci. Ve druhé části 1. kapitoly už se zaměřujeme podrobněji na mřížky, tedy strukturu, nad kterou pracuje LLL algoritmus. Oproti [7, Definition 2.5.2] se omezujeme pouze na mřížky nad vektorovým prostorem W1 , a to především proto, že z hlediska aplikací téměř o nic nepřicházíme a tato definice je jednodušší a nevyžaduje definování dalších pojmů. Ve 2. kapitole se soustředíme na samotný LLL algoritmus - pro dobré pochopení této kapitoly předpokládáme u čtenáře základní znalosti z teorie 6 ÚVOD 7 algoritmů (definice algoritmu, časová složitost, korektnost algoritmu), které jsou shrnuty např. v elektornickém učebním textu [47]. Samotný algoritmus tu uvádíme formálním zápisem používaným např. v [7], tvar vhodný pro zápis v některém z vyšších programovacích jazyků je uveden v příloze. Ve 3. kapitole alespoň stručně zmiňujeme hlavní oblasti použití LLL algoritmu. Poté podrobněji rozebíráme jednu z nejstarších aplikací algoritmu: útok na jedno-iterativní verzi šifrovacího systému Merkle-Hellman. Důvodem, proč jsme zvolili takto ,,starou" aplikaci, je to, že novější aplikace tohoto algoritmu jsou zpravidla mnohem komplikovanější a vyžadovaly by zavedení mnoha dalších pojmů. Navíc zde můžeme alespoň částečně ukázat to, jak mocnou zbraní v souboji kryptoanalýzy a kryptografie se stal LLL algoritmus, který vznikl jen několik let po zveřejnění myšlenky šifrovacích systémů s veřejným klíčem (přestože jeho autoři původně zřejmě vůbec nepomýšleli na využití v kryptoanalýze či kryptografii). Část 3.2.4 předpokládá alespoň základní znalosti teorie diofantických aproximací. K podrobnějšímu studiu tohoto tématu můžeme doporučit např. [5, 30, 22]. Pro hrubší představu by však měla být tato část srozumitelná i bez předchozích znalostí této problematiky. Uvádíme ji především proto, že použití diofantických aproximací výrazně rozšiřuje použití LLL algoritmu při kryptoanalýze zvoleného systému a učinilo tento systém prokazatelně napadnutelným v polynomiálním čase. Hlavní zdroje, z kterých celá 3. kapitola čerpá, jsou [26, 15, 39, 33], které můžeme doporučit k rozšiřujícímu studiu tématu šifrovacích systémů založených na problému batohu a jejich kryptoanalýzy. Často používané označení ^ ^ právě tehdy když A a zároveň V obecný kvantifikátor 3 existenční kvantifikátor En jednotková matice řádu n det(A) determinant matice A AT matice transponovaná k matici A A-1 inverzní matice k matici A GLn(Z) grupa regulárních čtvercových matic řádu n s číselnými prvky N množina přirozených čísel No NU{0} Z množina celých čísel Q množina racionálních čísel E množina reálných čísel E+ množina kladných reálných čísel Wn množina uspořádaných n-tic reálných čísel gcd (a, b) největší společný dělitel čísel a a b u vektor o nulový vektor [Ui,...,Uk ] vektorový podprostor generovaný vektory Ui,. 1. Matematický základ algoritmu 1.1 Kvadratické a bilineární formy, prostory se skalárním součinem Nechť dále T je těleso, jehož charakteristika je různá od 2 a V vektorový prostor konečné dimenze nad tělesem T. Definice 1.1.1. Zobrazení b : V x V --ˇ T se nazývá bilineární forma na vektorovém prostoru V, jestliže pro každé tři vektory u , v , w G V a každé r E T platí: (i) 6(u + v, w) = 6(u, w) + 6(v, w) (ii) 6(u, v + w) = 6(u, v) + 6(u, w) (iii) 6(ru,v) = 6(u,rv) = r6(u,v) P o z n á m k a 1.1.2. Bilineární zobrazení b je tedy takové zobrazení, které je lineární v obou složkách. Definice 1.1.3. Řekneme, že bilineární forma b na V je symetrická, resp. antisymetrická, jestliže pro každé dva vektory u, v G V platí 6(u, v) = 6(v, u), respektive 6(u,v) = --6(v,u). Věta 1.1.4. Ke každé bilineární formě b na V existuje právě jedna symetrická bilineární forma bs a právě jedna antisymetrická bilineární forma ba na V tak, že: 6(u, v) = bs(u, v) + 60(u, v). P o z n á m k a 1.1.5. Hledané formy bs a ba jsou tvaru: Mu 'v ) = 2(6 (u >v ) + 6 (v >u ))> Mu >v ) = 2(6 (u >v ) -Hv >u ))> P o z n á m k a 1.1.6. Nechť M = {uly... un } je libovolná báze ve V. Potom u = xiUx + ˇ ˇ ˇ + xnun, v = yiUi + ˇ ˇ ˇ + y,,un, kde XÍ, I/Í G T. Dosazením do bilineární formy dostaneme: ( n TI \ TI TI ^XiUi^yjuA = ^ x t ^ ^ ( U Í , Uj). í=l j=l J í=l 3= 1 Označme a^ = 6(u;, Uj) a uvažujme matici Ab = (a^). Potom můžeme psát: n b(u,v) = J2aijxiyj. (1.1) i,3 = l 9 1. MATEMATICKÝ ZÁKLAD ALGORITMU 10 Definice 1.1.7. (1.1) nazýváme analytickým vyjádřením formy b v bázi M a matice Ab = (b(ui, Uj)) se nazývá matice bilineární formy b v bázi M. Poznámka 1.1.8. (1) Pro libovolnou bázi M = {ui,...un } vektorového prostoru Vn a libovolnou čtvercovou matici A = (a^) řádu n nad tělesem T existuje právě jedna bilineární forma b na prostoru Vn, jejíž matice vzhledem k bázi M je právě matice A. (2) Bilineární forma b je symetrická (antisymetrická) právě tehdy, když Ab je symetrická (antisymetrická) matice. Věta 1.1.9. Necht M a M' jsou dvě báze vektorového prostoru Vn a b je bilineární forma na Vn. Je-li A matice formy b vzhledem k bázi M a C matice přechodu od báze M k bázi M', pak CT AC je matice formy b vzhledem k bázi M1 . Definice 1.1.10. Hodností bilineární formy b rozumíme hodnost matice formy Ab v libovolné bázi. Je-li Ab regulárni matice, nazýváme bilineární formu b regulárni, je-li Ab singulární, nazýváme bilineární formu b singulární. Definice 1.1.11. Zobrazení q: V --ˇ T se nazývá kvadratická forma na vektorovém prostoru V, jestliže existuje bilineární forma b taková, že pro každý vektor u G V je q(u) = b(u, u). Říkáme, že bilineární forma b určuje kvadratickou formu q. Věta 1.1.12. Ke každé kvadratické formě existuje právě jedna symetrická bilineární forma, která ji určuje. Poznámka 1.1.13. Příslušná bilinární forma má tvar: Hu >v ) = 2 ^ ( u + v ) -i(u ) -9(v ))> Definice 1.1.14. Hodností kvadratické formy q rozumíme hodnost příslušné symetrické bilineární formy ke q. Říkáme, že kvadratická forma je regulárni (singulární), je-li regulární (singulární) příslušná symetrická bilineární forma. Definice 1.1.15. Bázi M = {u1}... un } vektorového prostoru V nazýváme polární bází kvadratické formy q, jestliže pro každé i,j = l,...,n,i^j, platí 6(UÍ, Uj) = 0, kde b je bilineární forma, která určuje kvadratickou formu q. Věta 1.1.16. Ke každé kvadratické formě existuje polárni báze. Věta 1.1.17. Ke každé kvadratické formě n q(u) = ^2 ciíjXiXj 1. MATEMATICKÝ ZÁKLAD ALGORITMU 11 existuje taková lineární transformace souřadnic n Xi = y ^QijVj) i = i,... ,n, j=i že souřadnicové vyjádření q v souřadnicích yi,... ,yn je tvaru: n í=i tj. matice Bq kvadratické formy q je diagonální. Definice 1.1.18. Nechť q je kvadratická forma na vektorovém prostoru V nad T. Říkáme, že q je pozitivně (resp. negativně) definitní, jestliže pro každý vektor u ^ o platí q(u) > 0 (resp. q(u) < 0). Poznámka 1.1.19. Je-li kvadratická forma q vyjádřena vzhledem k polární bázi (tj. její matice vzhledem k této bázi je diagonální), pak je forma pozitivně definitní, právě když au > 0 \/i a negativně definitní, je-li au < 0 Vi Definice 1.1.20. Prostorem se skalárním součinem nazýváme dvojici (V, b), kde V je vektorový prostor a b je pozitivně definitní symetrická bilineární forma na V. Forma b se nazývá skalární součin a číslo 6(u, v) se nazývá skalární součin vektorů u, v G V. Jestliže 6(u, v) = 0, pak říkáme, že vektory u,v jsou navzájem kolmé (ortogonální) a zapisujeme u_Lv. Pokud je skalární součin b předem jednoznačně dán, budeme jej zjednodušeně označovat (u,v) = 6(u,v). Příklad 1.1.21. Ve vektorovém prostoru W1 je skalárním součinem např. bilineární forma zadaná vztahem: n (u,v) = ^2uiVi, í=l prou = (ui,...,un) e f , v = (vi,...,vn) eRn . Takovýto skalární součin nazýváme standartním skalárním součinem na Era . Štandartní skalární součin vektorů u a v označíme u ˇ v. Definice 1.1.22. Buď (Vn, b) prostor se skalárním součinem. Pro každý vektor u G V označíme ||u||6 = y/q(u). Číslo ||u||6 nazýváme normou vektoru u (vzhledem ke skalárnímu součinu b). Pokud je skalární součin b předem jednoznačně dán, budeme normu zjednodušeně označovat ||u|| = ||u||fe. 1. MATEMATICKÝ ZÁKLAD ALGORITMU 12 Definice 1.1.23. Báze M = { u i , . . . u n } prostoru se skalárním součinem (Vn,b) se nazývá ortogonální báze, jestliže je polární bází bilineární formy b (tj. je-li 6(u;, Uj) = 0 pro všechna i,j = l,...,n,i^ j). Nechť q je kvadratická forma určená bilineární formou b. Ortogonální báze, pro kterou navíc platí q(ui) = 1, i = 1,..., n, se nazývá ortonormální báze prostoru Vn. Poznámka 1.1.24. (1) Předchozí věta jinými slovy slovy říká, že matice skalárního součinu b vzhledem k ortogonální bázi je diagonální a vzhledem k ortonormální bázi dokonce jednotková. (2) Nechť M je ortonormální báze prostoru se skalárním součinem (V, b), u, v G V vektory, jejichž souřadnice vzhledem k M jsou u = (u\,..., vn), v = {v\,..., vn), pak skalární součin vektorů u , v je tvaru: (u,v) = Era i = l UiVi. (3) Je-li v G Vn,v 7^ o libovolný, pak položíme-li u = TTZT- = Z--; dosta- llv llq Vg(v) neme: q(u) = b . , . = ---- ˇ q(v) = 1. Tímto ,,znormováním" každého vektoru ortogonální báze { v i , . . . , v n } prostoru se skalárním součinem Vn získáme vektory u; = TT^-^Í = q 1,... , n, které tvoří ortonormální bázi prostoru Vn. Věta 1.1.25. V každém prostoru se skalárním součinem (Vn,b) existuje ortonormální báze. Důkaz. Podle věty 1.1.16 existuje ortogonální báze prostoru (Vn, b) a z ní už ortonormální bázi získáme postupem popsaným v poznámce. D Věta 1.1.26. Nechť { u i , . . . , uk } je libovolná báze podprostoru W prostoru se skalárním součinem (Vn,b). Pak existuje ortogonální báze {u{,... ,u^} prostoru W taková, že uj G [ui,..., Uj] pro každé j = 1,..., k. Důkaz. (Gram-Schmidtův ortogonalizační proces.) Budeme postupovat indukcí podle k: (1) Položme u{ = Ui, pak zřejmě {u{} je ortogonální bází prostoru W. (2) Nechť k > 1 a předpokládejme, že existuje {u,..., ujj^} ortogonální báze podprostoru [ u i , . . . , Uk_i] taková, že uj G [ u i ,. . . , Uj] Vj : 1 < j < k. Pak položíme: fc-i u = - ^ j U j f e j U j + u k , /ikJ eR,j = l,...,k-l (1.2) i = i 1. MATEMATICKÝ ZÁKLAD ALGORITMU 13 Zřejmě pro libovolnou volbu koeficientů ßkj platí uj G [ u i ,. . . , Uj] Vj = 1,... , k. Koeficienty ßk,j zvolíme tak, aby vektory u{,... , uk byly navzájem ortogonální. Vzhledem k indukčnímu předpokladu stačí &(uk, uj) = 0 pro j = 1,..., k -- 1. Z (1.2) pak dostáváme: &(uk, uj) = 0 = --/ifcjg(uj) + 6(uk, uj). Platí: uj 7^ o (protože { u i , . . . , uk } je báze podprostoru W ve (Vn, b)), a tedy ßkj = --( 'J ˇ Tím jsme získali všechny hledané koeficienty ßk,j : 6(uk,uí) W = - ^ ) Vj,k:l. Množinu M = { b i , . . . b m } nazýváme bází mřížky L, m nazýváme dimenzí mřížky L. 1. MATEMATICKÝ ZÁKLAD ALGORITMU 14 P o z n á m k a 1.2.2. (1) Tato definice mřížky už je poněkud zjednodušená abychom mohli definovat LLL-redukovanou bázi mřížky, budeme potřebovat ještě pozitivně definitní kvadratickou formu q a příslušnou symetrickou bilineární formu b na W1 a správně bychom tedy měli jako mřížku označovat uspořádanou dvojici (L,q). Vzhledem k tomu, že kvadratická forma (a tím i příslušná symetrická bilineární forma) je většinou předem dána, budeme dále mřížku označovat pouze L. (2) Pokud není v textu výslovně uvedeno jinak, mřížkou dimenze n máme na mysli mřížku dimenze n v W1 . (3) V [7, Definition 2.5.2] lze najít obecnější definici mřížky, která používá pojmy volný Z-modul (anglicky free Z-module) a tenzorový součin. Vysvětlení těchto pojmů však přesahuje rozsah této práce, proto jsme se v definici omezili pouze na prostory se skalárním součinem nad W1 . Pro bližší studium výše zmíněných pojmů a pochopení obecnější definice však lze doporučit např. [12, Chapter 10] a [29, Chapter III, Chapter XVI] nebo pro příznivce slovensky psané literatury např. [28, kapitoly VI a IX]. P o z n á m k a 1.2.3. Vzhledem k tomu, že v mřížce uvažujeme pouze celočíselné souřadnice vzhledem k bázovým vektorům, nemusí (ale mohou) být dvě mřížky určené dvěma různými bázemi v W1 stejné. Mřížky nad dvěma bázemi budeme považovat za stejné, pokud jsou tvořeny stejnými množinami vektorů. Zřejmě například platí: pokud báze M = {ux,..., un } generuje mřížku L, pak báze M' = { v í , . . . , v n } , kde v; = --u; pro i = 1,..., n generuje mřížku Ľ, která je ekvivalentní s mřížkou L. Dále podáme přesnou definici ekvivalence mřížek a budeme zjišťovat, které mřížky v W1 jsou navzájem ekvivalentní. Definice 1.2.4. Bijektivní zobrazení / : (L,q) --ˇ (Ľ,q') nazveme izomorfismus mřížek L a Ľ, pokud pro každý vektor u E L platí f(q(u)) = q'(f (u)). Definice 1.2.5. Řekneme, že mřížky (L, q) a (Ľ, q') jsou ekvivalentní, pokud existuje izomorfismus / : (L,q) --ˇ (Ľ,q'). P o z n á m k a 1.2.6. Nechť M = {u1}... ,un } a M' = {vx,..., vn } jsou dvě báze W1 , P = {pij) matice přechodu od M' k M, L mřížka generovaná bází M, Ľ mřížka generovaná bází M', u E L libovolný vektor, X = (x\,..., xn),iesp. Y = (j/i,... , yn) sloupcové vektory souřadnic u vzhledem k bázi M, resp. M'. Pak vhodným zobrazením zřejmě bude / určené předpisem: /(u) = u, tedy souřadnicově: f(X) = PX. Aby se jednalo o zobrazení L do Ľ, musí platit Pu E Z, aby /(u) E Ľ. Tedy det(P) G Z a zároveň P E GLn(Z) (vzhledem k tomu, že P je matice přechodu). Vzorem Y je prvek X = P~l Y 1. MATEMATICKÝ ZÁKLAD ALGORITMU 15 a aby bylo / surjektivní, musí platit X G Zn , tedy det(P_ 1 ) G Z. Zároveň ale platí: det(P)det(P_ 1 ) = det('ra) = 1. Pro matice P a P - 1 , které splňují tuto rovnost a zároveň det(P) G Z A det(P_ 1 ) G Z, musí platit: det(P) = det(P_ 1 ) = 1 . V tomto případě je / surjektivní zobrazení L do Ľ a vzhledem k tomu, že P je regulárni, je / i prosté. Dvě mřížky L a Ľ prostoru Era jsou tedy ekvivalentní, právě tehdy když pro matici P přechodu od báze mřížky L k bázi mřížky V platí: P G GLn(Z) Adet(P) = 1 . P o z n á m k a 1.2.7. Mřížku můžeme jednoznačně zadat různými způsoby podívejme se alespoň na dva, které jsou dobře použitelné v praxi: (1) Můžeme vybrat libovolnou bázi M = {b>i,..., b m } mřížky L. Potom vektor x G P můžeme vyjádřit jeho (celočíselnými) souřadnicemi vzhledem k bázi M. Skalární součin je pak vzhledem k bázi M vyjádřen pozitivně definitní symetrickou maticí Q = (qij),qij = 6(bi,bj). Matice Q je čtercová matice řádu m a nazývá se Gramová matice. Poznamenejme, že Gramová matice je zároveň maticí symetrické pozitivně definitní bilineární formy b vzhledem k bázi M. Pak 6(x, y) = YT QX a speciálně, pokud q je kvadratická forma určená bilineární formou b, q(x) = XT QX, kde X, resp. Y jsou sloupcové vektory určující souřadnice x, resp. y v bázi M. Pokud bychom místo báze M vybrali bázi M' a P by byla matice přechodu od M k M', pak podle 1.1.9 dostáváme g(x) = (PX)T Q(PX) = XT Q'X, kde Q' = PT QP. Tedy třídy ekvivalence mřížek odpovídají třídám ekvivalence pozitivně definitních symetrických matic, kde dvě matice jsou v ekvivalenci Q ~ Q' právě tehdy když existuje matice P G GLm(Z) tak, že Q' = PT QP. Determinant P je podle předchozí poznámky roven 1 , takže determinant Q je nezávislý na volbě báze mřížky. Q je navíc pozitivně definitní, takže det(Q) > 0 a můžeme položit d(L) = +y/det(Q). Číslo d(L) nazýváme determinant mřížky L. (2) Nechť M = { b i , . . . , b m } je libovolná báze L ve vektorovém prostoru W1 . Můžeme vybrat ortonormální bázi E = { e i , . . . , e m } vektorového prostoru [b1,..., b m ] . Nechť B je matice přechodu od E k M typu nxm. Pak podle 1.1.9 Q = BT EnB = BT B a tedy pro mřížky dimenze n v lRra platí d(L) = |det(P)|. Pokud bychom vybrali jinou ortonormální bázi E', pak matice přechodu B' od E' k M by měla tvar B' = KB, kde K je matice přechodu od E1 k E. K je matice přechodu od ortonormální báze k ortonormální bázi, proto K je ortogonální matice - tedy matice, pro kterou platí KT K = KKT = En. 1. MATEMATICKÝ ZÁKLAD ALGORITMU 16 Těmito úvahami jsme dokázali následující tvrzení: Věta 1.2.8. (i) Nechť Q je maticí pozitivně definitní kvadratické formy. Pak Q je Gramovou maticí některé báze mřížky, tzn. existuje matice B e GLn(R) tak, že Q = BT B. (ii) Gramová matice vzhledem k bázi mřížky M = {b>i,..., bn } určuje tuto bázi jednoznačně až na ortogonální transformaci, přesněji: Pokud M a M' mají stejnou Gramovú matici, pak M' vznikla z M ortogonální transformací. Maticově: M' = KM, kde K je ortogonální matice. Věta 1.2.9. Podle předchozího tedy jsou izomorfní následující množiny: { Třídy ekvivalence mřížek dimenze n} {Pozitivně definitní symetrické matice } / ^ , kde Q ~ Q' -<=/- Q' = PT QP pro nějakou matici P E GLn(Z) {GLn(m/~, kde B ~ B' <í=^> B' = KBP pro nějakou matici P E GLn(Z) a nějakou ortogonální matici K Poznámka 1.2.10. Dále budeme používat označení zavedené ve větě 1.1.26 a v jejím důkazu (Gram-Schmidtův ortogonalizační proces) a odvodíme některé její důsledky. Především z této věty plyne následující vztah pro determinant mřížky L, jejíž báze je M = {b>i,... , bn }: n d(L)2 = H\\btf. í=i 11 2 Označení. Dále budeme symbolem Bi označovat ||bí|| . Důsledek 1.2.11 (Hadamardova nerovnost). Nechť (L,q) je mřížka, d(L) její determinant, M = {bi,..., bn } báze L. Pak platí: (i) n d() B *3 = 1 n n Pak: d{Lf = \\Bl< ]^[ ||bi||2 í=i í=i (ii) Jedná se o vyjádření (i) pro případ, že q je určena standartním skalárním součinem. D Důsledek 1.2.12. Nechť B e GLn(R). Pak existují jednoznačně určené matice K, A a N tak, že: (i) B = K AN. (ii) K je ortogonální matice (tzn. KT = K-1 ). (iii) A je diagonálni matice s kladnými prvky, (iv) N je horní trojúhelníková matice a platí: na = 1 \/i = 1 , . . . , n Důkaz. Existence: Nechť b i , . . . , b n jsou sloupcové vektory matice B. Na tyto vektory uplatníme Gram-Schmidtův ortogonalizační proces, při kterém získáme vektory h\,..., b*, které budou tvořit sloupce matice B*. Pak B* = BN, kde N = (riij) je horní trojúhelníková matice, která má na diagonále 1 (a nad diagonálou na pozici n^ je prvek --ßij). Protože b , . . . , b* je ortogonální bází Rra , Gramová matice těchto vektorů je diagonální s kladnými koeficienty, označme ji D. Nechť A je matice, která z matice D vznikne takto: a,ij = +\fd~íj. Pak Gramovou maticí sloupcových vektorů A bude opět matice D, z čehož podle 1.2.7 a 1.2.8 plyne: B*T B* = D ^=> B* = K A pro nějakou ortogonální matici K. Celkem tedy: BN = K A -t==> B = KAN-1 , přičemž iV_1 je horní trojúhelníková matice (neboť N byla horní trojúhelníková) . Jednoznačnost: B* = BN = K A, což znamená, že b{,..., b* tvoří ortogonální bázi, kterou lze získat z b 1 ; . . . , b n Gram-Schmidtovým ortogonalizačním procesem, který je jednoznačný. D Poznámka 1.2.13. (1) Předpoklad, že prvky na diagonále matice A jsou kladné, není podstatný a je ve větě pouze kvůli jednoznačnosti vyjádření. (2) Stejného výsledku lze dosáhnout, pokud matice N bude dolní trojúhelníková matice. Pak bude platit B = N AK. 1. MATEMATICKÝ ZÁKLAD ALGORITMU 18 (3) S = AN je horní trojúhelníková matice s kladnými prvky na diagonále. Každá taková matice může být jednoznačně zapsána jako součin právě těch matic A a N, uvedených v 1.2.12. Věta 1.2.14. Nechť Q je matice pozitivně definitní kvadratické formy. Pak existuje právě jedna horní trojúhelníková matice S, která má na diagonále kladné prvky tak, že Q = ST S (nebo ekvivalentně: Q = NT DN, kde N je horní trojúhelníková matice s prvky na diagonále rovnými 1 a D je diagonální matice s kladnými prvky na diagonále). Důkaz. Existence. Podle 1.2.8 i existuje B E GLn(R) tak, že Q = BT B. Z 1.2.12 a 1.2.13 víme, že existují matice K a S tak, že B = KS, kde K je ortogonální a S je horní trojúhelníková matice s kladnými prvky na diagonále. Celkem tedy Q = (KSfKS = ST KT KS = ST S. Jednoznačnost. Sporem: Nechť existuje S\ různá od S tak, že Q = ST S = S^S1 (1.5) a S i Si jsou horní trojúhelníkové matice s kladnými prvky na diagonále. Pak platí: (SiT )_ 1 ST = S^-1 , (1.6) přičemž S_1 a (S\T ) existují, protože matice Q je pozitivně definitní. Na levé straně rovnosti (1.6) je dolní trojúhelníková matice, na pravé straně horní trojúhelníková matice. Tedy obě strany této rovnosti musí být rovny diagonální matici D. Z rovnosti (1.5) (dalším přenásobením inverzními prvky) dostáváme D2 = En. Protože prvky na diagonále matice D = SiS-1 jsou kladné, musí platit D = En, z čehož plyne S = S\, což je spor. D 2. LLL algoritmus 2.1 LLL-redukovaná báze Báze mřížky není určena jednoznačně, dokonce každá mřížka v prostoru W1 , n > 2 má nekonečně mnoho bází - některé z nich jsou však významější než jiné. Ty, které obsahují ,,nejkratší" vektory (tedy vektory s co nejmenší normou vzhledem ke skalárnímu součinu b), se nazývají redukované. Gramový matice všech bází jedné mřížky mají stejný determinant, a proto ,,redukovanost" znamená, že příslušná báze se blíží k tomu být ortogonální. Definice 2.1.1. Nechť L je mřížka dimenze n. Pro i G N, 1 < i < n, i-té postupné minimum L značíme Xi(L) a definujeme ho takto: Xi(L)= min {maxJvjH}. vi,...vneL i 2 (pro dimenzi 2 popsal algoritmus s kvadratickou časovou složitostí na počátku 19. století Gauss, mnohem později ještě objevil kubický algoritmus pro dimenzi 3 Vallée). Se skutečným převratem přišli v roce 1982 A. K. Lenstra, H. W. Lenstra a L. Lovász, kteří zavedli novou definici redukované báze a zároveň předložili algoritmus, který pro libovolnou dimenzi najde takto definovanou redukovanou bázi v polynomiálním čase. Definice 2.1.3. Nechť M = { b i , . . . , b n } je báze mřížky L a {b*,..., b^} = M* je ortogonální báze získaná z M Gram-Schmidtovým ortogonalizačním procesem 1.1.26, ßij = , ľ i, pro \/i,j:l T | | b i - i | | pro 1 < í < n Poznámka 2.1.4. (1) Podmínka (n) Z předchozí definice je zřejmě ekvivalentní následující podmínce: N I *i|2 -^ / 3 2 \ l l i * ||2 ||bi || > ( - - / i M _ ! 1 Hbi.ill (2) Místo konstanty | lze v (ii) zvolit libovolné pevné c G l : | < c < l . Pak se ale také změní odhady a důkaz následující věty - 2 bychom museli nahradit a = -^r a použít slabší nerovnost ß\ l < ^-^. Věta 2.1.5. Nechť M = { b i , . . . , b n } je LLL-redukovaná báze mřížky L. Pak platí: (i) (H) (iii) |bj|| < 2 2 IJbj*!! , pokud 1 < j < i < n, d(L) < n Ubili <2!íí V1 d(L), |bi|| <2^^/ď(Ľ), (iv) Pro každý vektor x e L , x / o platí: n - l ,, ,, ||bi|| < T^ ||x|| , f-yj Obecněji, pro Xi,... xt G L lineárne nezávislé platí: n -- 1 ||bj|| < 2^~ max{||xi|| , . . . , ||xt||} pro 1 < j < í. 2. L L L ALGORITMUS 21 Důkaz. (i) Je-li báze M = {b>i,...bn } LLL-redukovaná, pak z definice platí: 5 Í > ( - - / Í M _ I j Sí-i > ----, neboť |/iM_i| < - . Z toho matematickou indukcí dostáváme Bj < 2í _ J i?í pro 1 < j < i < n. Dále z 1.1.26 a 2.1.3 (i) plyne: í-i í-i 3= 1 3 = 1 = Bt(l + l(T-2)) s\Bi > Bi. Podle (i) platí: ||bi||2 < 2i ~1 Bi < 2n ~l Bi a odtud už ||bi||2 < 2n ~l Bi < 2n ~l ||x||2 . (v) Nechť Xj = ~Y^i=ir ijbii kde r\j E Z. Pro pevné j nechť i(j) je největší index i tak, že r^ 7^ 0. Pak podle důkazu (iv) platí: ||xj||2 > Bi{j)pio j = l,...,t (2.1) Přečíslujeme vektory Xj tak, aby i(l) < i(2) < ˇ ˇ ˇ < i(t) a ukážeme, že i(j) > j P r o j = 1, ˇ ˇ ˇ ,t. Sporem: Pokud by platilo i(j) < j , pak platí 2. L L L ALGORITMUS 22 xs E [b>i,... bj_i] pro s = 1,..., j , což je spor s lineární nezávislostí Xi,... xt . Pak z (2.1) dostáváme: lib-II2 < 2i{ -^~l B<\ < T~l llx-ll2 nro i = 1 t II u j II -- ^ ^AJ) -- II^-JII P i u J -"-> ˇ ˇ ˇ J b i z čehož plyne dokazované tvrzení. D Poznámka 2.1.6. (1) Nechť M' = \\{L),..., Xn(L) jsou i-tá postupná minima mřížky L a M = { b i , . . . , b n } je LLL-redukovaná báze L. Pak podle 2.1.5 (i) a (iv) a platí: 2 1 _ Í A Í ( L ) < ||bi||2 < T-l \i(L) proi = l,...,ra, tedy ||bi|| je poměrně dobrým přiblížením Xi(L). (2) Z 2.1.5 (iii) zase vidíme, že vektor bi LLL-redukované báze je jedním z nejkratších nenulových vektorů mřížky L. Ve skutečnosti je to často opravdu ten nejkratší nebo s ním lze pracovat místo nejkratšího vektoru mřížky. 2.2 Popis LLL algoritmu Základní myšlenka algoritmu Představme si, že vektory b i , . . . , bk_i už jsou LLL-redukované (přesněji jsou LLL-redukovanou bází mřížky, kterou generují) - to je triviálně splněno pro k = 2.Vektor b^ chceme změnit tak, aby vektory b 1 ; . . . , b^ byly LLL- redukované. Nejdříve tedy změníme vektor bk tak, aby byla splněna podmínka (i) definice LLL-redukované báze 2.1.3, tedy: \ßk,j\ < \ pro všechna j < k. Splnění této podmínky dosáhneme přiřazením b k := b k -- J2j=1 cijbj pro vhodné aj E Z takto: aj budeme hledat postupně pro l = k,... ,1. Pro každé takové / budeme předpokládat platnost podmínky pro / < j < k a budeme chtít dosáhnout platnosti podmínky pro l -- 1 < j < k. Předpokládejme, že \ßk,j\ < \ pro l < j < k. Pak pokud q = [ßk,i] je nejbližší celé číslo k ßk>h provedeme přiřazení b^ := b k -- qh\. Tímto přiřazením se koeficienty ßk,j změní takto: _ ( b k , b ? ) g(b1;b?) ßk '3 (bj,bj) (bj,bj) Tedy pro j > l se koeficienty ßkj nezmění, neboť bj_Lbi, tzn. že druhý člen výrazu je roven 0. ßk,i se změní na ßk,i -- Q, protože podle 1.1.27 je druhý 2. L L L ALGORITMUS 23 člen výrazu roven q. Touto změnou bk jsme však především dosáhli toho, že \ßk,i -- q\ < §> a proto nové koeficienty ßkj splňují podmínku (i) definice 2.1.3: \ßk,j\ < \ pro l -- 1 < j < k. Teď, když vektor b k splňuje podmínku (i) definice 2.1.3, potřebujeme, aby splnil ještě podmínku (ii): Bk > (f -- ß\ k-i)Bk-i- Otestujeme tedy, jestli vektor bk tuto podmínku splňuje. Pokud ano, zvýšíme k o l a pokračujeme s dalším vektorem, pokud ještě nějaký zbývá. Pokud ne, vyměníme vektory b k a bk _i - pak musíme snížit k o l a víme, že vektory b x , . . . , bk_2 jsou LLL-redukované a pokračujeme znovu od začátku. Z výše popsaného postupu není hned vidět, jestli postupné zvyšování a snižování k vždycky skončí, ale později ukážeme, že tomu tak opravdu je. Příklad 2.2.1. Mějme v E3 mřížku (L,q) určenou bází M = {bx,b2 ,b3 }, kde bi = (--1,0,1), b2 = (1,2,3), b3 = (0,1,1), q je kvadratická forma určená standartním skalárním součinem. Snadno se přesvědčíme, že báze M není LLL-redukovaná, protože např. ß2,i = 1, tedy není splněna podmínka (i) definice LLL-redukované báze 2.1.3. (Bázi M zde zapisujeme jako množinu, v LLL algoritmu s ní však zacházíme jako s uspořádanou trojicí. Pokud bychom zadali vektory báze M v jiném pořadí, získali bychom jinou LLLredukovanou bázi.) Z této báze získáme LLL-redukovanou bázi postupem uvedeným v základní myšlence takto: k <-- 2,1 <-- 1, Gram-Schmidtovým ortogonalizačním procesem spočítáme všechny ßitj, bí pro i = 1, 2, 3, j = 1,... , i -- 1; [k = 2] [l = 1] ß2,i = 1, q = 1, b 2 <- b 2 - bi = (2, 2, 2). Tím se změní //2,i, ale nezmění se bí pro i = 1,2,3. ß2,i <-- ^2,1 -- QOvěříme B2 > (f -- ß2i) >i, což platí, k <-- k + 1 = 3,Z < - f c - l = 2 [k = 3] [/ = 2] q <-- [^3,2 + \\ = 0 , tedy vektory b; se nezmění a / <-- 1-1 = 1 [/ = 1] q <- LjU3)i + |J = 1, tedy b 3 <- b 3 - bx = (1,1,0), ^3,1 <-- ^3,1 - q- B3 < (f - //|)2) ß 2 (Lovászova podmínka není splněna) b 3 ^ b2 ; Gram-Schmidtovým ortogonalizačním procesem přepočítáme všechny /j,itj, bí pro i = l,...,k,j = l,...,i -- l;k<^k--l = 2,l<^k--l = l [k = 2] [/ = 1] q <-- L/^2,1 + 2J = 0) tedy b 2 se nezmění, B2 > (i - j"Í1) B u tedy fc ^ fc + 1 = 3, / <- fc - 1 = 2 [fc = 3] [/ = 2] g ^ L"3,2 + §J = 3, b 3 ^ b 3 - 3 b 2 = ( - 1 , - 1 , 2 ) , ^3,2 <-- ^3,2 - ? , / < -- / - 1 = 1. [/ = 1] g ^- L^3,i + ^J = 2, b 3 ^ b 3 - 2bx = (1, -1,0), A/3,1 ^ ^3,1 -- q- B3 > ( | -- //| 2) >2, takže jsme hotovi. 2. L L L ALGORITMUS 24 Výsledná LLL-redukovaná báze tedy je: {(--1, 0,1), (1,1, 0), (1, --1, 0)}. Jako výstup LLL algoritmu, který uvedeme na str. 25, bychom dostali jinou bázi {(--1, 0,1), (0,1,1), (0, --1,1)}. Je to způsobeno tím, že tento algoritmus používá některá zefektivnění, která nemají vliv LLL-redukovanost báze, konkrétní výsledná báze je však odlišná. Jak vylepšit základní myšlenku? Gram-Schmidtovy koeficienty ßij můžeme aktualizovat pouze, až s nimi budeme potřebovat dále počítat. Ve výše popsaném algoritmu totiž vždy musí být změněny koeficienty ßi>k a ß^k-i pro i > k, které se pravděpodobně ještě několikrát změní před tím, než budou použity. Proto budeme koeficienty ßij dopočítávat, až když je budeme potřebovat, a v proměnné kmax si budeme udržovat maximální aktuální hodnotu. Dalším zlepšením základní myšlenky může být zkontrolovat v prvním kroku pouze koeficient ßk>k-\ a ne všechny ßk>m pro m < k, protože koeficient ßk,k-i je jediný, který musí být v absolutní hodnotě menší než \ před ověřením Lovászovy podmínky (a pokud tato podmínka nebude splněna, pak jsme všechny ßk,m pro m < k -- 1 měnili zbytečně). Ověřování Lovászovy podmínky Všechna tato zlepšení použijeme a v této situaci si ještě podrobněji rozeberme ověřování Lovászovy podmínky. Předpokládejme tedy, že: \ßk,k-i\ < g pokud k > 1. (2.2) (Toho dosáhneme zjednodušením postupu popsaného v základní myšlence algoritmu.) Při ověřování Lovászovy podmínky pak mohou nastat dva případy: (1) fc>2a zároveň podmínka není splněna, tedy Bk < Q - ßl,k.^j Bk.x (2.3) Vyměníme vektory b]í_1 a b^, ostatní vektory b>i ponecháme beze změny. Musíme tedy změnit i vektory b^_x a b a čísla ßk,k-i, ßk-i,j, ßkj, ßitk-i, ßi,k pro j < k -- 1 a pro i > k. Nejdůležitější z těchto změn je: b^._x <-- b + /ifc,fc-ibk_!, tedy nová hodnota Bk-i je rovna nejvýš | staré hodnoty tohoto výrazu. Po provedení těchto změn snížíme k o l a pokračujeme dalším průchodem algoritmem. (2) k = 1 nebo [k>2ABk>[^- ii\k_x ) Bk_x ) (2.4) 2. L L L ALGORITMUS 25 V tomto případě už má smysl, abychom zajistili splnění následující pod­ mínky: \ßk,j\ < - pro 1 < j < k - 1. (2.5) (Pro j = k -- 1 už tato podmínka platí podle (2.2).) Pro ostatní indexy opakujeme postup popsaný výše pro splnění podmínky (i) definice LLLredukované báze tak dlouho, dokud neplatí (2.5). Pak k zvýšíme o 1 a pokračujeme dalším průchodem algoritmem. Poznamenejme, že v případě, kdy k = 1 neudělá celý algoritmus nic jiného, než že k zvýší o 1. Na základě těchto úvah můžeme uvést kompletní algoritmus. V následujícím algoritmu c <-^ d označuje ,,prohození" hodnot v proměnných c a d. Algoritmus (LLL algoritmus). Mějme danou mřížku (L,q) a její libovolnou bázi M = {b>i,...,bm } (zadanou souřadnicemi vzhledem ke kanonické bázi Rra pro n > m). Výstupem algoritmu budou nové vektory bi, ˇ ˇ ˇ , b m , které budou tvořit LLL-redukovanou bázi L a matice H, která bude udávat souřadnice této LLL-redukované báze vzhledem k původně zadané bázi, sloupcové vektory matice H označíme hi. 1. [Inicializace] Polož k <-- 2, fcmax <-- l , b í <-- b1}Bi <-- (bi,b>i),ií <-- E 2. [Gram-Schmidt] Je-li k < kmax, jdi na 3. Jinak polož fcmax <-- k, b k <-- bk . Pro j = 1,..., k - 1 polož ßktj <-- ^ ^. , b k <-- b k - ßkjby Poté polož Bk <-- (bk ,bk ). Je-li Bk = 0, vypiš chybové hlášení, že vektory bi netvoří bázi mřížky a ukonči algoritmus. 3. [Test Lovászovy podmínky] Proveď RED(fc,fc -- 1). Je-li splněno Bk < (I ~~ ß\k-\) -Sfc-i) proveď SWAP(fc), polož k <-- max{2,fc -- 1} a jdi na 3. Jinak pro / = k -- 2, k -- 3 , . . . , 1 proveď RED(fc, /), poté polož fc<-fc + l. 4. [Hotovo?] Je-li k < m, jdi na 2. Jinak vypiš LLL-redukovanou bázi b; a transformační matici i í G GLm(Z) a skonči. Funkce RED(fc,/). Je-li l/^l < | skonči. Jinak polož q <-- |jUfc,zl = L| + Aífc,iJ, b k <- b k - gbi,ířfc <- ířfc - qHi,ßk,i <- ^M - 9, pro všechna i = 1 , . . . , / -- 1 přiřaď /ifc;í <-- /ifc;í -- g^; í a skonči. Funkce SWAP(fc). Proveď b k <-ˇ bk_x, Hk <-ˇ Hk-i- Je-li k > 2, pro každé j = l,...,fc -- 2 proveď //.,ˇ <-ˇ ßk-i,j- Potom přiřaď // <-- ßktk-i,B <-- 2. L L L ALGORITMUS 26 Bk + fŕBk-!,^-! <- ^ ^ , b ^ b ^ b * ^ <- b* + /xb,b* <- -jUfc)fc_1bj; + f^b, Sfc <- ^ ^ , Sfc_! <- R Pro i = k + 1, fc + 2 , . . . , fcmax přiřaď t 0 ŕaft, že p/aíí: v každé mřížce (L, q) 2 nad W1 3x, x ^ o ía&; že q(x) < j%d(L)ň. P o z n á m k a 2.2.3. (1) Důkaz tohoto tvrzení překračuje rámec této práce, lze ho najít v [23]. (2) Nejlepší možné konstanty j n se nazývají Hermitovy konstanty a jejich hodnoty jsou známé pouze pro n < 8: 4 64 7i = 1,72 = 3,73 = 2,74 = 4,75 = 8,7e = y , 7 7 7 = 64,78 8 = 256 n(n --1) Pro n > 8 máme rekurzivní odhad horní hranice 7TM: 7TM < 7raľi2 ˇ Důkaz. (Důkaz toho, že algoritmus skončí a je korektní.) Je jednoduché ukázat, že na začátku kroku 4 jsou LLL podmínky z definice 2.1.3 splněny pro i < k -- 1 (stačí použít úvahy, které jsme už uvedli v základní myšlence algoritmu a jejím vylepšení). Proto pro k > m jsme skutečně obdrželi LLLredukované vektory. Vzhledem k tomu, že na vstupní matici M = {bi} jsme průběhu algoritmu prováděli pouze takové operace, které jsou ekvivalentní s přenásobením maticí s determinantem 1 , tvoří tyto LLL-redukované vektory LLL-redukovanou bázi L. Zbývá dokázat, že algoritmus vždy skončí. Zřejmě algoritmus skončí, pokud k = m+1. Na začátku má k hodnotu 2, ta se v průběhu algoritmu buď zvýší o 1 (pokud je splněna Lovászova podmínka pro aktuální Bk), nebo se sníží o 1 (pokud Lovászova podmínka pro Bk není splněna). To, jestli podmínka bude nebo nebude splněna, závisí pouze na hodnotách Bk a Bk_x. Přitom hodnoty B i se mění pouze ve funkci SWAP(fc), kterou voláme pouze v případě, že Lovászova podmínka pro příslušné k není splněna. Uvnitř této funkce se vždy zmenší Bk-\ na maximálně | své původní hodnoty. Pokud by se nám podařilo odhadnout nľ=i -Biz dola vhodnou konstantou (závislou na mřížce L), znamenalo by to, že po určité době už určitě Lovászova podmínka bude vždy splněna, a tedy k už se bude pouze zvyšovat, až dosáhne hodnoty m + 1 a a lgoritmus skončí. Označme tedy pro 0 < i < m: d = n B3 2. L L L ALGORITMUS 27 Zavedené označení bude jasnější, uvědomíme-li si, že podle poznámky 1.2.10 di = det ŕ (br , b s ) 1 < r s < í ) . Zřejmě di > 0,do = l,dn = d(L)2 . Označme Li mřížku dimenze i generovanou vektory bj pro j < i. Pak zřejmě také di = d(Li)2 . Dále položíme D = YYÍ=I di- K dokončení důkazu nám nyní stačí odhadnout di zdola vhodnou konstantou závislou pouze na L a i tím získáme dolní odhad pro D i pro Yľi=i &i závislý pouze na L, a tedy algoritmus skončí. Nechť Si je nejmenší nenulová hodnota q v Li. Z tvrzení 2.2.2 získáváme: di = d(Li)2 >d(Liý>8hri >siljri Protože sn je nejmenší nenulová hodnota q(x) na L, poslední výraz závisí pouze n a i a nezávisí na bj, tedy di je zdola ohraničeno kladnou konstantou závislou pouze na i a L. D P o z n á m k a 2.2.4. (1) Časová složitost LLL algoritmu je 0(n6 In3 B), pokud ||bi|| < B pro všechna i a použijeme klasické aritmetické operace. Pokud použijeme efektivnější algoritmy pro aritmetické operace, můžeme časovou složitost snížit na 0(n4 lriB). Důkaz této časové složitosti lze najít v [31, s. 522-524]. (2) Pokud bychom měli bázi M zadanou Gramovou maticí, vektory bi a bí existují pouze abstraktně. Algoritmus tedy musíme pro tuto situaci upravit a jediným výstupem algoritmu bude matice H. Příslušnou úpravu algoritmu uvádí [7, s. 89]. Takto upravený algoritmus je efektivnější než původní, ale ne zas o tolik, aby se nám vyplatilo Gramovú matici počítat, pokud máme bázi mřížky zadanou souřadnicemi vzhledem ke kanonické bázi. (3) Jak už jsme uvedli v 2.1.4 (2), konstantu | v kroku 3 můžeme nahradit libovolnou konstantou c, c e R , ] < c < 1. Použití jiné konstanty samozřejmě ovlivní ,,kvalitu" výsledné LLL-redukované báze i čas, který bude algoritmus potřebovat k jejímu spočítání. Ideální by bylo zvolit c = 1, ale v tomto případě už není zaručeno, že algoritmus bude mít polynomiální časovou složitost. Můžeme tedy například zvolit c = 0,99. Další možností je variace konstanty c v průběhu výpočtu: začneme s konstantou c= \, pro kterou je redukce nejrychlejší a postupně zvyšujeme c až na hodnotu c = 0,99 - pro tuto hodnotu zase dostaneme nejlepší redukovanou bázi. Více podrobností o této metodě je popsáno v [27]. (4) Také bychom mohli Lovászovu podmínku Bk > (f - \i\ hradit tzv. Siegelovou podmínkou Bk > --y^. Protože \ßk,k-i\ < \, Lovászova podmínka s konstantou c = | implikuje splnění Siegelovy podmínky a naopak pokud nějaká báze splňuje Siegelovu podmínku, pak 2. L L L ALGORITMUS 28 splňuje také Lovászovu podmínku s konstantou c = \. V případě použití Siegelovy podmínky místo Lovászovy podmínky bychom mohli volání RED(fc, k -- 1) provádět spolu s voláním ostatních RED(fc, /). (5) V algoritmu předpokládáme, že zadané vektory bi jsou lineárně nezávislé - pokud nejsou, vypíše algoritmus chybové hlášení. Jistě by nebylo těžké upravit algoritmus tak, aby pro zadané lineárně závislé vektory byla výstupem LLL-redukovaná báze mřížky, kterou tyto vektory generují. Takto upravený algoritmus lze najít v [7, Algorithm 2.6.8]. (6) Pokud bychom uvažovali, že Gramová matice může mít reálné koeficienty (ne jen racionální), museli bychom čísla ßij a B^ počítat přibližně v pohyblivé řádové čárce. Nepřesnosti způsobené takovouto reprezentací čísel pak mohou způsobit chybné výstupy LLL algoritmu (přičemž můžeme získat bázi, která je ,,téměř" LLL-redukovaná, ale také bázi, která má k LLL-redukovanosti ,,velice daleko"). Podrobnosti týkající se této situace tu více rozebírat nebudeme, zvídavého čtenáře však můžeme odkázat na [7, s. 90] a pro podrobnější informace na [43, 45]. (7) Neustále se objevují nové verze LLL algoritmu, či jsou na jeho základě vytvářeny nové algoritmy specializované pro určitou oblast použití. Nebudeme se zde snažit všechny možné varianty ani vyjmenovat, jen namátkou však můžeme dychtivým čtenářům doporučit [7, s. 90-97] a [41, 43, 44, 45, 46]. 3. Aplikace A. K. Lenstra, H. W. Lenstra a L. Lovász publikovali LLL algoritmus jako algoritmus pro faktorizaci polynomů s racionálními koeficienty (viz článek [31]). Od té doby byla nalezena řada oblastí uplatnění tohoto algoritmu v matematice, informatice i kryptologii1 . Zároveň samotný algoritmus procházel řadou změn, vylepšení i modifikací vhodných pro různé oblasti použití a stal se základem či součástí mnoha komplikovanějších a efektivnějších algoritmů. Pokusíme se zde alespoň stručně popsat hlavní oblasti použití algoritmu vzhledem k tomu, že rozsah práce nedovoluje věnovat se jednotlivým oblastem podrobněji, uvádíme alespoň odkazy na další literaturu k jednotlivým tématům. LLL algoritmus se používá především v těchto oblastech: 1. Faktorizace polynomů nad celými nebo racionálními čísly, případně nad dalšími tělesy. Přestože LLL algoritmus je polynomiální, exponenciální algoritmus Berlekamp-Zassenhaus byl pro mnoho polynomů prakticky rychlejší, protože LLL algoritmus vedl na mřížky velké dimenze s velkými koeficienty. V současnosti se používá2 algoritmus Marka von Hoeije (viz [16]) z roku 2000, ve kterém se podařilo zkombinovat dobré vlastnosti obou al­ goritmů. 2. Problémy teorie mřížek: Problém nejmenší báze mřížky, problém nejkratšího vektoru mřížky a problém nejuzavřenějšího vektoru mřížky. Problém nejkratšího vektoru mřížky L dimenze n (SVP) je najít vektor v G L tak, že ||v|| = Ai(L) (viz definice 2.1.1). Vzhledem k tomu, že nejkratší vektor mřížky zatím obecně nedokážeme v polynomiálním čase najít, postačí nám často najít vhodnou aproximaci nejkratšího vektoru mřížky, tedy vektor v G L tak, že ||v|| = f(n)Xi(L) pro nějaký aproximační faktor f(n). Z 2.1.5 (iv) vidíme, že LLL algoritmus dokáže aproximovat SVP s faktorem 2 ^ ~ . Problém nejuzavřenějšího vektoru mřížky (CVP) je následující: pro danou mřížku L C Qn a daný vektor u G W1 najít vektor v G L tak, aby ||u -- v|| byla minimální. Jedná se tedy o nehomogenní verzi SVP. Problém nejmenší báze mřížky: pro danou mřížku L najít bázi M = { b i , . . . , b n } , která minimalizuje buďmaxi f(x) má vlastnost ir2. NP-úplné nazveme takové problémy třídy NP, na které lze polynomiálně redukovat všechny ostatní problémy z NP. Řekneme, že problém n je NP-těžký, pokud existuje nějaká NP-úplná vlastnost no tak, že pokud existuje polynomiální algoritmus pro n, existuje i polynomiální algoritmus pro 7To. Jednou z největších nevyřešených otázek je, zda P ^ N P (za rozhodnutí této otázky dokonce vypsal Clay Mathematics Institute of Cambridge v r. 2000 odměnu $ 1 000 000.) 7 Posloupnost {aiYi=\Ta i ^ nazveme superrostoucí, pokud platí: a,j > YJI=I a i Pr °Vj = 2,..., n, tedy každý prvek posloupnosti je ostře větší než součet všech prvků, které mu předchází. 3. APLIKACE 32 můžeme v tomto případě počítat XÍ od xn po x\ pomocí vztahu: n ˇAJ% -i- * \ r Cr / thjyjjj ^ ^%' j= i+l Jednoduchý algoritmus na počítání XÍ můžeme pak sestrojit velice podobně jako algoritmus na převod čísla z desítkové do dvojkové soustavy. Aditivní problém batohu 0-1 můžeme zobecnit tak, že složky vektoru x budou z množiny {O,1, 2 , . . . , 2b -- l j , kde b G No, místo z množiny {0,1}. Tento problém batohu pak nazveme zobecněný problém batohu. Dalším problémem batohu může být tzv. multiplikativní problém batohu, kdy pro daný vektor vah položek a a danou nosnost s G N hledáme vektor x, tak aby: nľ=i a ľi = s - Rozhodnout, zda má zadaný multiplikativní problém batohu řešení, je také NP-úplný problém. Vyřešit ho je jednoduché, pokud jsou jednotlivé váhy položek navzájem nesoudělná čísla. Multiplikativní problém batohu lze převést na aditivní zlogaritmováním. Problém batohu se stal předmětem zájmu zkoumání mnoha kryptografů a matematiků poté, co Dime a Hellman zveřejnili v roce 1976 svůj nápad šifrovacího systému s veřejným klíčem [li]8 . Zdálo se, že NP-úplnost problému rozhodnutí, zda má problém batohu řešení, by mohla zajistit dostatečnou bezpečnost a přispět k nalezení tzv. jednosměrné funkce (funkce invertovatelné jen za pomoci nějaké ,,soukromé" informace)9 , která byla nezbytná pro uvedení systémů s veřejným klíčem do praxe. Proto byly také postupně formulovány různé varianty problému batohu - výše zmíněné, ale i další, o kterých se může zvídavý čtenář více dozvědět např. v [26]. 3.2 Šifrovací systémy založené na problému batohu -- prohraná sázka kryptografie? 3.2.1 Šifrovací systémy Merkle-Hellman založené na problému batohu V roce 1978 navrhli Merkle a Hellman jeden z prvních šifrovacích systémů s veřejným klíčem [34]10 . Merkle a Hellman navrhli 2 metody, jak vytvořit šifrovací systém založený na problému batohu. První, známější metoda, využívala převodu aditivního 0-1 batohu se superrostoucí posloupností vah položek 8 Jejich práce byla ovlivněna myšlenkami R. C. Merkla. 9 Formálnější definice jednosměrné funkce viz např. [6, s. 138-140], [37, str. 78-80]. 10 Svůj návrh zveřejnili několik měsíců po tom, co Rivest, Shamir a Adelman publikovali první systém s veřejným klíčem: RSA. 3. APLIKACE 33 na, jak doufali, těžký aditivní 0-1 problém batohu, kde inverzní převod by byl nemožný bez znalosti soukromého klíče. Druhá metoda je založena na multiplikativním problému batohu: jednoduchý multiplikativní problém batohu, kde váhy položek a = (cii,..., an) jsou navzájem nesoudělná čísla, je pomocí umocňování čísla b modulo m, kde b < m, m je prvočíslo a m > Yľí=ia í> převeden na těžký multiplikativní problém batohu. Merkle s Hellmanem také navrhovali různá vylepšení obou metod, která by ztížila kryptoanalýzu tohotu systému: permutovat váhy položek či přenásobit vektor vah položek libovolnou konstantou. Navrhli také iterativní metodu šifrování a dešifrování: v každé iteraci jsou zvoleny nové M a W, pomocí kterých se původní jednoduchý problém batohu převede několikrát až na výsledný těžký problém batohu. Tato verze je známá jako multi-iterativní, základní verze s jedním převodem jako jedno-iterativní. Dále se budeme pro jednoduchost zabývat podrobněji pouze aditivní jedno-iterativní variantou šifrovacího systému Merkle-Hellman. Pseudokód tohoto šifrovacího systému je uveden v příloze. Nechť s = (si,... ,sn) je superrostoucí posloupnost vah položek, M,W E Z tak, že: M > Y17=is ^ gcd (M, W) = 1. Merkle a Hellman převedli váhy položek batohu s na jinou posloupnost vah položek a transformací: di = WSÍ mod M 1 < i < n. Veřejným klíčem je nová posloupnost vah položek a. Soukromým klíčem je (M,W,s). Zprávu x G {0,l}r a zašifrujeme: c = (x, a). K rozšifrování, tedy k získání x z c, bychom při znalosti veřejného klíče a potřebovali vyřešit problém batohu s vahami položek a a nosností c, což je obecně NP-těžký problém, pro který nemáme zatím k dispozici žádný deterministický polynomiální algoritmus. Exponenciální algoritmus pro řešení tohoto problému můžeme snadno zkonstruovat tak, že budeme rekurzivně procházet všechny možnosti součtů vah položek, přičemž zkoumání každé možnosti ukončíme v případě, že součet vah položek je větší nebo roven c. Vzhledem k exponenciální časové náročnosti takového algoritmu však pro dostatečný počet položek batohu však řešení budeme hledat opravdu dlouho. Jak však brzy ukážeme, při kryptoanalýze nám může výrazně pomoct například to, jak byl problém batohu určený veřejným klíčem získán z problému batohu se superrostoucí posloupností vah položek. Pokud známe soukromý klíč, získáme zprávu x tak, že vyřešíme problém batohu s vahami položek s a nosností d = cW~l mod M, což je jednoduchý problém, protože s je superrostoucí posloupnost. Označme U = W~l mod M, pak: d = cli = (x ˇ a) U = x ˇ (all) = x ˇ s (mod M). 3. APLIKACE 34 Protože Y17=i x is i < M, platí: d = x ˇ s. Merkle si byl jistý, že tato verze je dostatečně bezpečná a vypsal odměnu $ 100 za její prolomení. Příklad 3.2.1. Alice a Bob si chtějí posílat důvěrné zprávy. Protože vědí, že linku, po které si zprávy posílají, odposlouchává pan X, rozhodli se své zprávy šifrovat - po lince tedy budou putovat pouze kryptogramy (zašifrované zprávy), o kterých doufají, že je pan X nedokáže rozluštit. Domluvili se, že pro šifrování použijí Merkle-Hellman jedno-iterativní aditivní systém. Nechť n = 5. Alice zvolí W = 37, M = 43 a superrostoucí posloupnost s = (1, 3, 5,11, 21) a spočítá svůj veřejný klíč a : cii = W ˇ Si (mod M), tedy a = (37, 25,13, 20, 3). Alice má tedy veřejný klíč (37, 25,13, 20, 3) a soukromý klíč (43,37,(1,3,5,11,21)). Zašifrování zprávy: Bob, který chce Alici poslat zprávu x = (1, 0,1,1, 0), spočítá c = 37 + 13 + 20 = 70 a pošle toto číslo Alici. Dešifrování zprávy: Aby Alice dešifrovala zprávu, kterou obdržela od Boba, spočítá d = W~1 c (mod M) = 7-70 = 17 (mod M) a vyřeší problém batohu se superrostoucí posloupností a a nosností d: 17 -- 0-21(0) = 17-1-11(1) = 6 - 1 - 5 ( 1 ) = 1 - 0 - 3 ( 0 ) = 1 - 1 - 1 ( 1 ) = 0. Tak získá zprávu x = ( l , 0 , l , l , 0 ) . Útok na systém: Pan X zachytí kryptogram, který poslal Bob Alici a zná pouze Alicin veřejný klíč. Pokud chce rozluštit zprávu, mohl by vyřešit problém batohu s vektorem vah položek (37, 25,13, 20,3) a nosností 70. V tomto případě pan X snadno uhodne, že řešením je 37+13 + 20 = 70, tedy původní zpráva je x = (1, 0,1,1, 0). Pro větší n a větší čísla a^ by měl pan X s hledáním řešení obecného batohu mnohem více práce. Jak však brzy ukážeme (v částech 3.2.3 a 3.2.4), pokud pan X dokáže dobře použít LLL algoritmus, s velice vysokou pravděpodobností se mu podaří kryptogram rozšifrovat v polynomiálním čase. Alice a Bob dnes tedy tento systém použijí pouze, pokud jim záleží spíše na rychlosti a jednoduchosti šifrování a dešifrování zpráv než na bezpečnosti celého systému. 3.2.2 Kryptoanalýza Merkle-Hellman šifrovacího systému založeného na aditivním problému batohu V roce 1982 Shamir předvedl útok na tento systém [42] a získal slíbenou odměnu $ 100. Jeho útok byl založen na vyřešení problému lineárního programování. Po úspěšném útoku Shamira byl Merkle přesvědčen, že multi-iterativní verze šifrovací systému Merkle-Hellman je absolutně bezpečná a vypsal za její prolomení odměnu $ 1 000. K jeho velké smůle však v roce 1982 také A. 3. APLIKACE 35 K. Lenstra, H. W. Lenstra a L. Lovász publikovali LLL algoritmus, který se záhy začal používat v kryptoanalýze - už v tomtéž roce předvedl Adelman útok na šifrovací systém Graham-Shamir [1], byl výrazně zefektivněn útok na jedno-iterativní šifrovací systém Merkle-Hellman, a konečně roku 1984 Brickell předvedl úspěšný útok na multi-iterativní verzi šifrovacího systému Merkle-Hellman založený na redukci mřížek [4]. Nezbývá než doufat, že to byla poslední Merkleova sázka na tenkém ledě kryptografie11 . 3.2.3 Řešení batohů s nízkou hustotou Jde o skupinu problémů batohu, které lze řešit pomocí redukce mřížky. Nechť a = (cii,... ,an) je vektor vah položek s maximální váhou A, tedy A = max^j^ßj. Hustotu vah položek cii,... ,an označíme d a definujeme: d = J^J- Brickell v [3] a Lagarias a Odlyzko v [24] nezávisle na sobě dokázali, že většinu batohů s nízkou hustotou pro velké n lze vyřešit, pokud máme tip na nejkratší vektor příslušné mřížky. Útok Lagariase a Odlyzka funguje pro většinu batohů, ve kterých je hustota vah položek d < 0,6463...: spočívá v nalezení nejkratšího vektoru mřížky L0 generované řádky matice Bn / l 0 .. 0 Ncn\ 0 1 "ˇ ': Na2 0 ': 1 Nan [o .... 0 N s J kde N > ^Y je libovolné celé číslo. Nechť x = (x\,... ,xn) G {0,1}"" je řešení batohu s vahami položek a a nosností s. Vektor souřadnic c0 = (xi,... ,xn, --1) G Zn+1 generuje vektor mřížky b0 = c0B0 = (xi,... ,xn,N(xidi H Yxnan - s)\ = (xu ... ,xn,0). Nalezením nejkratšího vektoru b0 v mřížce L0 tedy získáme x = (x\,..., xn). Za předpokladu, že nejvýš \ hodnot Xi je různá od 0, je tento vektor velice malý (||b0|| < \n). Pro velká n autoři ukázali, že pravděpodobnost P, že b0 je opravdu nejmenším vektorem v mřížce LQ je dána vzorcem: P < n[ 2n\i --n )c0n A ' n Ralph C. Merkle je profesorem na College of Computing v Georgii a kromě kryptografie se zabývá také nanotechnologiemi. Za spoluobjevení kryptografie s veřejným klíčem získal ceny společností ACM a IEEE. 3. APLIKACE 36 kde co = 1,54724... Tento odhad pravděpodobnosti byl získán počítáním bodů mřížky ve vysokých dimenzích. Při volbě A = 2cn konverguje tato pravděpodobnost k nule a n se zvětšuje, kdykoliv c > c0. Tedy většinu problémů batohu s velkým n a hustotou d = j^j = \ < 0,6463... můžeme vyřešit, pokud máme tip na nejkratší vektor mřížky. Kompletní důkaz těchto tvrzení lze najít v [24]. Tato hranice hustoty byla nezávisle zvýšena Costerem, LaMacchiou a Schnorrern a také Jouxem a Sternem. Jejich výsledky jsou shrnuty v [9]. Coster, LaMacchia, Odlyzko a Schnorr uvažují mřížku Li generovanou řádky matice / l 0 0 Nai \ Bx 0 1 0 0 0 1 2 1 0 1 2 0 1 1 2 Na2 N On-] Nan Ns 1 X\ i %n 1 2> Zn+Í - | , 0 generuje . Zřejmě V tomto případě vektor souřadnic Ci = nejkratší vektor mřížky Li: bi = Q.\B\ každá složka vektoru bx je rovna -- | , 0 nebo | , protože XÍ E {0,1} pro každé i = 1,... ,n. Bez ohledu na skutečné hodnoty XÍ vektor bx musí splňovat: 11 2 1 ||bi|| = -^n. Tedy vektor bi je malým vektorem v mřížce Li. Autoři ukazují, že pravděpodobnost P, že bi není opravdu tím nejmenším vektorem v mřížce, je ohraničena: P < n ( An\/n + 1 OCl, A kde c\ = 1,0628.... Pokud A = 2cra , pravděpodobnost konverguje k 0 a n se zvětšuje kdykoli c > c\. Tedy téměř všechny problémy batohu s velkým n a hustotou d < \ = 0,9408... lze vyřešit, pokud dokážeme najít nejkratší vektor mřížky. Zatím nedokážeme najít nejkratší vektor mřížek dimenze n > 4, ale v praxi nám většinou stačí vektor, který najde LLL algoritmus. Příklad 3.2.2. Předpokládejme, že pan X zachytil kryptogram c = 1605, který poslal Bob Alici, ví, že zpráva je zašifrována Merkle-Hellman šifrovacím systémem a našel si Alicin veřejný klíč a = (319,196, 250, 477, 200, 559). Pouze se znalostí těchto údajů chce pan X zjistit původní zprávu x. Zkusí tedy spočítat hustotu problému batohu zadaného Alicinými veřejným klíčem: d = lo 6 559 = 0,66 < 0,9408. Po tomto zjištění už má pan X poměrně vysokou pravděpodobnost, že se mu podaří zprávu x zjistit v polynomiálním čase takto: 3. A P L I K A C E 37 Pan X zvolí N > ^ , např. A" = řádkové vektory pak uplatní LLL algoritmus: / l 0 0 0 0 0 2 0 1 0 0 0 0 2 0 0 1 0 0 0 2 A = 0 0 0 1 0 0 2 0 0 0 0 1 0 2 0 0 0 0 0 1 2 í i i i i i 2 2 2 2 2 2 2 a vytvoří matici A, na jejíž 319 \ 196 250 477 200 559 2ˇ1605/ Výsledkem aplikace LLL algoritmu na řádkové vektory matice A, jsou řádkové vektory matice A' : A' 1 1 1 1 1 1 2 2 2 2 2 2 0 0 1 0 2 1 0 1 - 2 2 0 1 1 2 1 2 i 2 3 2 3 2 1 2 - 3 - 1 0 2 1 0 3 5 3 i 3 1 2 2 2 2 2 2 1 2 3 2 3 2 3 2 1 2 3 2 °\ o o 2 2 0 2/ Pana X z těchto vektorů zajímá pouze první vektor bx = (y1,... ,yn), yí E { --2> 0, | } Vz = 1, 2 , . . . , n + 1. Zkusí spočítat Xj = --J/Í + | Vz = 1, 2 , . . . , n, čímž získá tip na vektor x = (1, 0,1,1, 0,1) a ověří, jestli opravdu našel řešení: 319 + 250 + 477 + 559 = 1605. Tedy zpráva, kterou poslal Bob Alici, byla 101101. Na závěr poznamenejme, že problém batohu uvedený v příkladu 3.2.1, by se panu X touto metodou vyřešit nepodařilo, protože hustota problému batohu určeného veřejným klíčem je větší než 0,9408. 3.2.4 Využití diofantických aproximací Definice 3.2.3. Nechť a E R,p E Z, q E N & gcd(p,q) = 1. Racionálni číslo - se nazývá dobrá diofantická aproximace čísla a, jestliže pro všechna q' E N,q' < q platí \q'a -- p\ > \qa -- p\. Nyní ukážeme útok na jedno-iterativní Merkle-Hellman šifrovací systém, založený na redukci báze mřížky a zároveň na diofantických aproximacích. Začneme s kongruencí aj = SiW (mod M). Definujeme ki E Z pro i = 1,..., n tak, že: aAJ - h M (3.1) 3. APLIKACE 38 a budeme se snažit uhodnout čísla ki. Prvním důležitým faktem je, že daný problém batohu s vahami položek a a nosností c lze převést na nekonečně mnoho problémů batohu se superrostoucí posloupností vah a' a nosností d. To bylo nezávisle dokázáno Eierem a Laggerem [13] a Desmedtem, Vanderwallem a Govaertsem [10]. Jejich výsledky (jejichž důkaz zde neuvedeme), lze shrnout do následujícího lemmatu: Lemma 3.2.4. Nechť M,U,a,kiproi výše. Pak existuje e > 0 tak, že: 1,..., n jsou definována stejně jako Iľ_ W II' II e(y>A ~M'~" M < e = > s ' = (si, ...,s'n), kdes'i = cnU' - hM' pro i = 1,..., n, je superrostoucí. Stačí nám tedy najít takovou vhodnou dvojici čísel (U',M'), která nám převede původní problém batohu na problém batohu se superrostoucí posloupností vah položek. Ten už umíme jednoznačně vyřešit, takže znalost této dvojice je ekvivalentní znalosti tajných U a M. Z rovnosti 3.1 zřejmě pro každé i = 1,... n platí: f -- -- = -^jb, tedy každé -- je dobrou aproximací 44. Tedy, pokud budeme znát kil pomocí -1 můžeme dopočítat U' aM M', které splňují podmínky lemmatu 3.2.4. Pro hodnoty ki odvodil Shamir v [42] následující vztah: a\ kl < M \a\k\ pro i = 1, ..., n, (3.2) tedy každé ^ je dobrou aproximací ^-. To vede k problému nalezení simultánní diofantické aproximace - tedy aproximace vektoru (--,--,..., --) G wi-i vektorem ( fc2 ks fcl ' fcl ; M J - 1 k\ < a\. Definice 3.2.5. Nechť ó G E pevné. Řekneme, že vektor (2i;^ Qn je simultánní diofantickou aproximací 5-kvality vektoru (--, -- Qn , když p < q a zároveň: p- IM < q pro i = 1,2,... ,n. (Čím větší je 8, tím lepší je aproximace.) Dále řekneme, že se jedná o neobyčejně dobrou simultánní diofantickou aproximaci (UGSDA), pokud 8 > -. Takovou aproximaci nazýváme neobvykle dobrou, neboť pravděpodobnost toho, že taková aproximace existuje, je poměrně malá vzhledem ke všem 3. APLIKACE 39 možným volbám QÍ. Nalezení simultánní diofantické aproximace ö-kvality i nalezení UGSDA lze řešit LLL algoritmem např. následujícím algoritmem popsaným v [25, 33]. Algoritmus (Nalezení diofantické simultánní aproximace í-kvality). K zadanému vektoru (--,--,...,--) e Qn najdeme simultánní diofantickou aproximaci (^, ^ , . . . , ^ ) č-kvality, á e ť takto: [Krok 1 ] A <- L^J [Krok 2 ] Najdeme LLL redukovanou bázi B = {b>i,... b n } mřížky dimenze (n + 1), která je generována řádkovými vektory matice A : A ( Xq 0 0 0 Xq 0 0 0 Xq \-Xqi -Xq2 -Xq3 0 0 0 0\ 0 0 -Xqn 1/ [Krok 3 ] Pro každý vektor v = (v\, v2, ˇ ˇ ˇ , vn, vn+i) E B, pro který vn+\ ^ q, polož: p <-- vn+i, pro i , n polož pi pqA. Jestliže q s pro každé i, 1 < i < n, vrať ( VI V2 - ) ˇ p (a Vi < [Krok 4 ] Vrať chybové hlášení - Buď simultánní diofantická aproximace ökvality neexistuje, nebo se ji nepodařilo tímto algoritmem najít. Volbou ó > - můžeme právě uvedeným algoritmem najít UGSDA. Algoritmus (Kryptoanalýza jedno-iterativního šifrovacího systému Merkle-Hellman založeného na aditivním problému batohu). Pro vektor vah položek a a kryptogram c se pokusí najít původní zprávu x: [Krok 1 ] Nalezení neobvykle dobré simultánní diofantické aproximace vektoru (^-, ^-,..., ^ ) . Pokud se nepodaří UGSDA najít, algoritmus skončí ne­ úspěchem. [Krok 2 ] Nalezení čísla jjj, které bude dobrou aproximací ^ tak, aby platilo gcd(U',M') = 1. [Krok 3 ] Problém batohu s vahami položek a a nosností c převedeme na jednoduchý problém batohu se superrostouci posloupností vah položek a' a nosností c', kde a!i = ciiU' mod M' pro i = 1, ... ,n a, c. = cli' mod M'. Poznámka 3.2.6. Uvedený postup funguje tím lépe, čím větší je n a jemu odpovídající M, W, s a a. Neobvykle dobré simultánni diofantické aproximace jsou čím dál vzácnější pro vzrůstající n. Malé hodnoty n se v systému Merkle-Hellman z bezpečnostních důvodů nepoužívají, protože pak by 3. APLIKACE 40 bylo možné řešit obecný prolém batohu zadaný veřejným klíčem a kryptogramem exponenciálním algoritmem. Merkle a Hellman v [34] doporučují používat 100 < n < 200 a pro n = 100: 2201 + 1 < M2202 - 1, (2Í "1 - 1) ˇ 2100 < Si < 2i -1 21 00, 2 < U < M - 2. Ukážeme teď jeden ,,malý" příklad na tento způsob kryptoanalýzy s tím, že zdaleka ne pro všechny takto ,,malé" příklady lze najít řešení LLL algoritmem a ani tento příklad nelze řešit úplně bez potíží. Příklad 3.2.7. Tentokrát předpokládejme, že pan X zachytil kryptogram c = 6665 a chce ho dešifrovat metodou diofantických aproximací. Najde Alicin veřejný klíč a = (575,436,1586,1030,1921,569,721,1183,1570, 726). Pan X spočítá 6 <-- ^-j-, A <-- |_ n_ v// 575j = 2 a použije LLL algoritmus na řádkové vektory matice B: B í 2-575 0 0 0 2-575 0 0 0 2-575 V -2 ˇ 436 - 2 ˇ 1586 - 2 ˇ 1030 0 0 0 -2 ˇ 726 0\ 0 o Výsledkem LLL algoritmu budou řádkové vektory {b^,... ,b'n}. Pokud bude pan X postupovat podle algoritmu pro nalezení simultánní diofantické aproximace ^-kvality, získá pro b'6 koeficienty k = (fci,...,fcra) = (91,69,251,163,304,90,114,187,249,115). (Přestože nalezené hodnoty kí přesně odpovídají hodnotám kí z rovnosti 3.1, kg nesplňuje podmínku na UGSDA.) Vzhledem k tomu, že gcd(fci,ai) = gcd(91,575) = 1, položí pan X: U' <-- 91 a M' <-- 575. Pak spočítá nový vektor vah položek a' = (a[,..., a'n) = (0,1,1,5,11,29,61,128,270,516), kde a't = cii ˇ 91 mod 575 a nové d = 6665 ˇ 91 = 465 mod 575. Přestože nový vektor vah položek a' neobsahuje úplně superrostoucí posloupnost, pan X už snadno uhodne řešení (váhat bude pouze u prvních 3 jeho složek): x = (1,0,1,1,0,0,1,1,1,0). A skutečně 575 + 1586 + 1030 + 721 + 1183 + 1570 = 6665, tedy původní zpráva byla 1011001110. 3. APLIKACE 41 Další možnost hledání U G S D A Pro velká n můžeme použít jiný postup pro hledání UGSDA uvedený v [15], kde stačí použít vhodnou mřížku dimenze t < n. Uvažujme í-dimenzionální mřížku L, jejíž bází jsou řádky matice B: í B a2 a3 .. at [at d\ 0 .. 0 0 --a\ V o o -d\ o / Každý vektor u G L je tvaru: u = íttiG^ -- 2^1, ˇ ˇ ˇ ,u\at -- Utai,ui[a{\ kde U\,...,Ut G Z. Pokud v je nejmenší vektor mřížky L nalezený LLL algoritmem, pak podle 2.1.5 (iii) platí: |v|| < 2^d(L) Nyní potřebujeme spočítat determinant mřížky L - podle 1.2.7 (2) (Pohybujeme se v R" a uvažujeme štandartní skalární součin - ortonormální bází je kanonická báze E = { e i , . . . , e n } , kde eü = l,eý- = 0 pro i 7^ j.) je bází mřížky L absolutní hodnota z determinantu matice přechodu od K k bázi mřížky, tedy |det(>T )| = |det(>)|. Laplaceovým rozvojem tohoto determinantu podle prvního řádku získáváme (äij označuje algebraický doplněk prvku a,ij): d(L) = J2j=1ciijä\j, kde zřejmě všechny äy pro 0 < i < t -- 1 jsou rovny nule, au = (--1) a>\ ˇ Tedy d(L) = [a[\aľ a platí: |v|| < 2--d(L)t < 2--aS [aj\^ < 2^aľ Pak pro i = 1,... , t -- 1 platí: a\ -ví - vt < ||v|| < 2~aľ t+i . í + i 4 1 ° S 2 a l t1 < a. kde poslední nerovnost platí, pokud t > 2-^/log2 i- Tedy, pokud použijeme dostatečně velké t, pomocí LLL algoritmu najdeme vektor, který odhalí UGSDA (--,..., -- ). Protože UGSDA jsou poměrně vzácné, můžeme před- i i pokládat, že VÍ = ki pro i = 1,..., n. 3. APLIKACE 42 3.2.5 Bezpečnost a budoucnost těchto šifrovacích sys­ témů V roce 2000 přijala IEEE standard P1363 (a v roce 2004 ho aktualizovala jako P 1363a): Standard Specifications For Public Key cryptography [20], ve kterém specifikuje 3 hlavní oblasti kryptografických funkcí: faktorizaci celých čísel, diskrétní logaritmus v konečném tělese a diskrétní logaritmus v grupě bodů eliptické křivky nad konečným tělesem. V roce 2005 přijala další standard P1363.1 týkající se kryptografických systémů založených na teorii mřížek. Tento fakt vyjadřuje názor kryptografické komunity na systémy založené na problému batohu: Přestože ani o jednom ze 3 problémů v P1363 není dokázáno, že by byl NP-těžký nebo NP-úplný, je jim v aplikacích v kryptografii důvěřováno mnohem víc než problému batohu, který je prokazatelně NP-těžký. Počet šifrovacích systémů založených na problému batohu, které už byly prolomeny12 je dostatečně odstrašující na to, aby pro tyto systémy byly vytvářeny nějaké standardy, přestože některé šifrovací systémy na principu batohu dosud prolomeny nebyly. Problém je v tom, že problém batohu je NPtěžký jako celek, ale konkrétní zadání nemusí být NP-těžké - i kdyby pouhé 1 % konkrétních zadání problému batohu bylo polynomiálně řešitelných, oslabuje to bezpečnost šifrovacího systému. Mnoho dosavadních šifrovacích systémů bylo prolomeno díky své konstrukci - snažili se jen zakrýt původní snadno řešitelný batoh, ale už tato informace poskytla dostatek informací k jejich prolomení. Dalším problémem je, že batohy s hustotou menší než 0,9408 dokážeme s poměrně velkou pravděpodobností řešit a batohy s hustotou větší než 1 už pro šifrovací systémy nelze použít, protože by se mohlo stát, že z jednoho kryptogramu bychom mohli obdržet více platných zpráv. Na druhou stranu systémy založené na principu batohu umožňují poměrně rychlé šifrování a dešifrování. Jak je uvedeno v [36]: ,,Jedno-iterativní šifrovací systém Merkle-Hellman se 100 položkami může být až 100x rychlejší než RSA s modulem zhruba 500 bitů." Pokud by se tedy podařilo dobře využít NP-těžkosti obecného problému batohu, mohl by vzniknout velice zajímavý šifrovací systém. V současné době lze jen těžko odhadnout, jestli budou vznikat nějaké další šifrovací systémy založené na principu batohu, pokud už jsou známé tak populární systémy jako FíSA či tak nadějné systémy jako NTFíU. Jisté je jen to, že systémů založených na principu batohu vzniklo od 80. let minulého století mnoho. Přestože většina z nich už byla prolomena, jejich vývoj se zatím úplně nezastavil. 2 Podrobnosti o různých systémech a útocích na ně viz [26] Seznam použité literatury [1] Adelman, L. M. (1983). On Breaking Generalized Knapsack Public Key Cryptosystems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (s. 402-412). ACM, New York. Dostupný na http://delivery.acm.org/10.1145/810000/808771/ p402-adleman.pdf?keyl=808771&key2=8238442411&coll=GUIDE&dl= GUIDE&CFID=71438707&CFT0KEN=58602468 [2] Bican, L. Lineární algebra a geometrie. Praha: Academia, 2000. ISBN 80-200-0843-8. [3] Brickeil, E. F. Solving low density knapsacks. In D. Chaum, editor, Advances in Cryptography - Proceedings of CRYPTO '96, svazek 1666 Lecture NOtes in Computer Science, s. 129-142. Springer-Verlag, 1996. [4] Brickell, E. F. (1985). Breaking Iterated Knapsacks. In G. R. Blakley, David C. Chaum (Ed.) Advances in Cryptology - CRYPTO '84, Lecture Notes in Computer Science: vol. 196 (s. 342-358). Springer-Verlag, Berlin. Dostupný na h t t p : / / d s n s . c s i e . n c t u . e d u . t w / r e s e a r c h / c r y p t o / HTML/PDF/C84/342.PDF [5] Cassels, J. W. S. An Introduction to Diophantine Approximation. University Press, Cambridge: 1965. [6] Černá, I. Úvod do teorie zložitosti. Učební text Fakulty informatiky Masarykovy univerzity, Brno 1998. Dostupný na h t t p : //www. f i . muni . cz/ usr/cerna/Slozitost/ia012.html.windows-1250 [7] Cohen, H. A course in computational algebraic number theory. 4th print. New York: Springer-Verlag, 2000. ISBN 0-387-55640-0. [8] Coppersmith, D. a Shamir, A. Lattice Attacks on NTRU. In Advances in Cryptology - Euro crypť97. Springer-Verlag, 1997. Dostupný na h t t p : //dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/E97/52.PDF 43 SEZNAM P O U Ž I T É L I T E R A T U R Y 44 [9] Coster, M. J., Joux, A., LaMacchia, B. A., Odlyzko, A. M., Schnorr, C. P. a Stern, J. Improved low-density subset sum algrithms. Computational Complexity, 1992. [10] Desmedt, Y. G., Vandewalle, J. P. a Govaerts, R. J. M. A critical analysis of the security of knapsack public-key algorithms. IEEE Transactions on Information Theory, IT-30: s. 601-611, 1984. [11] Diffie, M. a Hellman, M. E. New Directions in Cryptography IEEE Transactions on Information Theory, IT-22(6): s. 644-654, 1976. Dostupný na http://www.cs.rutgers.edu/~tdnguyen/classes/cs671/ presentations/Arvind-NEWDIRS.pdf [12] Dummit, D. S. a Foote, R. M. Abstract Algebra. 3rd edition. New York: John Wiley & Sons, 2004. ISBN 0-471-43334-9. [13] Eier, R. a Lagger, H. (1983). Trapdoors in knapsack cryptosystems. In T. Beth (Ed.) Advances in Cryptology - Proceedings of CRYPTO '82, Vol. 149 Lecture Notes in Computer Science (s. 316322). Springer-Verlag. Dostupný na h t t p : / / d s n s . c s i e . n c t u . e d u . t w / research/crypto/HTML/PDF/E82/316.PDF [14] Goldreich, O., Goldwasser, S. a Halevi, S. Public-Key Cryptosystems from Lattice Reduction Problems. Lecture Notes in Computer Science, 1294: s. 112-131, 1997. Dostupný na h t t p : / / t h e o r y . l c s . m i t . e d u / ~ oded/crypt ography.html [15] Hinek, M. J. Lattice Attacks in Cryptography: A Partial Overview. 2004. Dostupný na http://www.cacr.math.uwaterloo.ca/techreports/ 2004/cacr2004-08.pdf [16] Hoeij, M. van. Factoring polynomials and the knapsack problem. Journal of Number Theory, 95: s. 167-189, 2002. Dostupný na: http://www. math.f su.edu/~hoeij/knapsack/paper/knapsack.pdf [17] Hoffstein, J., Pipher, J. a Silverman, J. H. NTRU: A Ring-Based Public Key Cryptosystem Lecture Notes in Computer Science, 1423: s. 267-288, 1998. Dostupný na http://ntru.com/cryptolab/pdf/ANTS97.pdf [18] Horák, P. a Janyška, J. Analytická geometrie. Brno: Masarykova univerzita, 2002. ISBN 80-210-1623-X. [19] Horák, P. Úvod do lineárni algebry. Učební text UJEP Brno, 1978. SEZNAM POUŽITÉ LITERATURY 45 [20] IEEE. P1363: Standard Specifications For Public Key Cryptography. Dostupný na http: //grouper. ieee. org/groups/1363/ [21] Janyška, J. a Sekaninová, A. Analytická teorie kuželoseček a kvadrik. Brno: Masarykova univerzita, 1996. ISBN 80-210-1435-0. [22] Klazar, M. Kaleidoskop teorie čísel, kapitola 2: diofantické aproximace. Učební text MMF UK Praha, 2000. Dostupný na http://kam.mff. cuni.cz/~klazar/lectnotes.html [23] Knuth, D. E. The art of computer programming. Vol. 2, Seminumerical algorithms. Addison-Wesley Publishing Company, 1981. ISBN 02-010- 3822-6. [24] Lagarias, J. C. a Odlyzko, A. M. Solving low-density subset sums problems. J. Assoc. Comput. Mach., 31, s. 229-246, 1985. [25] Lagarias, J. C. Knapsack public key cryptosystems and Diophantine approximation. In D. Chaum (Ed.), Advances in Cryptology: Proceedings of Crypto 83 (s.3-23). New York and London: Plenum Press, 1984. Rozšířený abstrakt dostupný na http://www.math.lsa.umich. edu/~lagarias/doc/1218knap.pdf [26] Lai, M. K. Knapsack Cryptosystems: The Past and the Future, 2001. Dostupný na http://www.cecs.uci.edu/~mingl/knapsack.html [27] LaMacchia, B. Basis Reduction Algorithms and Subset Sum Problems. Thesis, MIT Artificial Intelligence Lab, 1991. Dostupný na http: //www. farcaster.com/papers/sm-thesis/index.htm [28] Mac Lane, S. a Birkhoff, G. Algebra, 2. vydání, přeložili Legéň, A. a Smítal, J., Bratislava: Vydavatelstvo technickej a ekonomickej literatúry, 1974. [29] Lang, S. Algebra. 3rd edition. New York: Springer Verlag, 2002. ISBN 0-387-95385-X. [30] Lang, S. Introduction to Diophantine approximations. Springer-Verlag, New York, 1995. ISBN 0-387-94456-7. [31] Lenstra, A. K., Lenstra, H. W. a Lovász, L. Factoring Polynomials with Rational Coefficients. Mathematische Annalen, 261(4): s. 515-534, 1982. ISSN: 0025-5831. SEZNAM P O U Ž I T É L I T E R A T U R Y 46 [32] Lenstra, H. W. Jr. Integer Programming with a fixed number of variables Math. Op. Res., 8: s. 538-548, 1983. [33] Menezes, A. J., Oorschot, P. C. a Vanstone, S. C. Handbook of Applied Cryptography, 5th printing. CRC Press, 1996. ISBN 0-8493-8523-7. Dostupný na http://www.cacr.math.uwaterloo.ca/hac/ [34] Merkle, R. C. a Hellman, M. E. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, IT-24: s. 525-530, 1978. Dostupný na h t t p : //www-ee . Stanford. e du/"hellman/ publications/30.pdf [35] Ngyen, P. O. a Stern, J. The Two Faces of Lattices in Cryptology. Lecture Notes in Computer Science, 2146: s. 146-180, 2001. Dostupný na h t t p : //www.di.ens.fr/~pnguyen/pub.html#NgSt01 [36] Odlyzko, A. M. The Rise and Fall of Knapsack Cryptosystems. In C. Pomeranče (Ed.), Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, vol. 42 (s. 75-88), American Mathematics Society, 1990. Dostupný na http://www.dtc.umn. edu/~odlyzko/doc/arch/knapsack.survey.pdf [37] Paseka, J. Kryptografie. Učební text Přírodovědecké fakulty Masarykovy univerzity, 1998. Dostupný na ftp://www.math.muni.cz/pub/math/ people/Paseka/lectures/CRYPTO/ [38] Regev, O. Integer Programming (Lattices in Computer Science: Lecture 5). Učební text Tel Aviv University, 2004. Dostupný na h t t p : / / w w w . e s . t a u . a c . i l / ~ o d e d r / t e a c h i n g / l a t t i c e s _ f a l l _ 2 0 0 4 / ln/integer_programming.pdf [39] Regev, O. LLL Algorithm (Lattices in Computer Science: Lecture 5). Učební text Tel Aviv University, 2004. Dostupný na http://www.es. t a u . a c . i l / ~ o d e d r / t e a c h i n g / l a t t i c e s _ f a l l _ 2 0 0 4 / l n / l l l . p d f [40] Ryjáček, Z. Teorie grafů a diskrétní optimalizace 2. Učební text Západočeské univerzity, 2001. Dostupný na http://cam.zcu.cz/~ryjacek/ students/ps/TGD2.pdf [41] Seysen, M. Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica, 13(3): s. 363-376, 1993. [42] Shamir, A. (1982) A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem. In Proceedings of the IEEE SEZNAM P O U Ž I T É L I T E R A T U R Y 47 Symposium on Foundations of Computer Science (s. 145-152). New York: IEEE. Dostupný na h t t p : / / w w w . b i t s - p i l a n i . a c . i n : 12356/faculty/sundarb/courses/netsec/readings/crypto/ complexity/breaking-mh.pdf [43] Schnorr, C. P. A more efficient algorithm for lattice basis reduction. J. Algorithms, 9: s. 47-62, 1988. [44] Schnorr, C. P. Fast LLL-Type Lattice Reduction. Inf. Comput., 204(1): s. 1-25, 2006. Dostupný na http://www.mi. informatik, uni-frankfurt.de/research/papers.html [45] Schnorr, C. P. a Euchner, M. (1991). Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems. In L. Búdach (Ed.), Proc. Fundamentals of Computational Theory '91, LNCS 529 (s. 68-85), Springer-Verlag, http://www.mi . informatik, uni-f rankf u r t . de/research/papers.html#1994 [46] Schnorr, C. P. a Hörner, H. H. Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction. Lecture Notes in Computer Science, 921: s. 1-12, 1995. Dostupný na http://www.mi . informatik, uni-frankfurt.de/research/papers.html [47] Škarvada, L. a Pitner, T. Návrh algoritmu I. Učební text FI MU. Dostupný na http://www.fi.muni.cz/~libor/vyuka/IB002/ [48] Schrivjer, A. Theory of Linear and Integer Programming. Chichester: John Wiley & Sons, 1986. ISBN 0-471-90854. [49] Stern, J. a Toffin, P. (1990). Cryptoanalysis of a Public-key Cryptosystem Based on Approximations by Rational Numbers Advances in Cryptology - Euro crypť90. Springer-Verlag. [50] Zlatoš, P. Lineárna algebra a geometria. Elektronický učební text FMFI UK, Bratislava 2003. h t t p : / / t h a l e s . d o a . f m p h . u n i b a . s k / katc/pages/member.php?jazyk=sk&clen=zlatos A P S E U D O K Ó D LLL A L G O R I T M U 48 A pseudokód LLL algoritmu Mějme danou mřížku (L,q) a její libovolnou bázi M = {b>i,...,bn } (buď souřadnicemi vzhledem ke kanonické bázi MF prop > n nebo její Gramovou maticí). Výstupem algoritmu budou nové vektory b>i,...,bn , které budou tvořit LLL-redukovanou bázi L a matice H, která bude udávat souřadnice této LLL-redukované báze vzhledem k původně zadané bázi, sloupcové vektory matice H označíme hi. Poznamenejme, že v následujícím algoritmu c <-^ d označuje ,,prohození" hodnot v proměnných c a d. Předpokládáme, že proměnné i,j,m,r jsou lokální (tedy unikátní v každém podprogramu algoritmu), zatímco ostatní proměnné jsou globální (tedy všechny funkce i hlavní program k nim mohou přistupovat a měnit jejich hodnotu). Algorithm 1: LLL algoritmus k := 2; kmax := 1; H := En /* i n i c i a l i z a c e */ M := b, >i := (bi, bi) /* konec i n i c i a l i z a c e */ repeat if k > kmax then /* Aktualizace G-S procesu */ fcmax : = "-j t ) ^ '.= Dk for j = 1,..., k -- 1 do ßkj ˇˇ= ^ ; b := b* - ßkahl;Bk := (b*,b*) end if >k = 0 then error: Vektory bi netvoří bázi; exit end /* Konec aktualizace G-S procesu */ RED (k, k -- 1) /* Ověřováni LLL podminek */ while Bk < (| - ii\k_^Bk_x do SWAP (fc); k := max{2, k - 1}; RED (k, k - 1) end for m = k - 2, k - 3 , . . . , 1 do RED (k, m) k:=k + l until k = n + 1 Vypiš LLL-redukovanou bázi bi a matici H. A PSEUDOKÓD LLL ALGORITMU 49 Function RED(k,m) if \\ßk,m\\ > \ then r : = [ßk,m\ = L2 + ßk,m\ bk := bk - r b m ; hk := hk - rhr for j = 1,... m -- 1 do end ßk,m ˇ ßk,m ' end Function SWAP (A;) b k - i <-ˇ b k ; h k - i 2 then for j = 1,2,...,k- 2 do ßk-l,j ^ ßk,j end p.Bk-\ ß 'ˇ-- ßk,k-i'i B :-- Bk + ß -Sfc-i; ßk,k-i 'ˇ-- B b := bk_x; bk_! := b* + ^b; b* := -ßk,k-XK + f b D Bk-iBk . r> r> -Dfc ˇ-- , -Dfc-1 ˇ-- -D for z = fc + 1,fc+ 2,..., kmax do t 'ˇ= ßi,k] ßi,k 'ˇ= ßi,k-l -- ßt ßi,k-l 'ˇ= t + ßk,k-lßi,k end end B ŠIFROVACÍ SYSTÉM MERKLE-HELLMAN 50 B Šifrovací systém Merkle-Hellman Aditivní jedno-iterativní šifrovací systém Merkle-Hellman Function Merkle-Hellman: Generování-klíče(n) Input: parametr n Output: soukromý klíč (M, W,(bi,..., bn)) a veřejný klíč (cii,..., an) (bi,... ,bn) := libovolná superrostoucí posloupnost M := libovolné M E N tak, že M > YTM=1 bt W := náhodné W E N tak, že W < M - 1 A gcd (M, W) = 1 for i = 1, 2 , . . . , n do a,i:=W ˇ h mod M end Vypiš soukromý klíč (M, W,(bi,..., bn)) a veřejný klíč (ai,..., an). Function Merkle-Hellman: Šifrování Input: veřejný klíč (ai,..., an) a otevřený text m E {0, l}n , m = mi... win Output: šifrový text c E {0, l}"E n i=1 niiCii Vypiš c. Function Merkle-Hellman: Dešifrovaní Input: Soukromý klíč (M, W,(bi,..., bn)) a šifrový text c Output: zpráva m odpovídající c U := W~l c mod M (mi, ˇ ˇ ˇ ,mn) := m, G 0,1 tak, že U = YH=I m ih Vypiš m.