Az RSA m´ odszer Az RSA m´ odszer titkoss´ aga a pr´ımt´enyez˝ os felbont´ as neh´ezs´eg´en, a pr´ımt´enyez˝ok megtal´ al´ as´ anak hihetetlen neh´ez volt´ an alapszik. Az elj´ ar´ as matematikai alapja a kis” ” FERMAT-t´etel egy k¨ ovetkezm´enye: 2.1. T´ etel. Legyenek p ´es q k¨ ul¨ onb¨ oz˝ o pr´ımsz´ amok, e pozit´ıv eg´esz, ln.k.o.(e, (p − 1)(q − 1)) = 1, ´es d legyen e modulo (p − 1)(q − 1) inverze, azaz ed ≡ 1 (mod (p − 1)(q − 1)). Ekkor b´ armely s nemnegat´ıv eg´eszre sed ≡ s (mod pq). Bizony´ıt´ as. Mivel ed ≡ 1 (mod (p − 1)(q − 1)) ´ıgy
(1)
(p − 1)(q − 1) | (ed − 1).
Ha ln.k.o.(s, pq) = 1, akkor a kis FERMAT-t´etel szerint sp−1 ≡ 1 (mod p) ´es sq−1 ≡ 1 (mod q). ´Igy (1) miatt sed−1 ≡ 1 (mod p) ´es sed−1 ≡ 1 (mod q), ahonnan pq | (sed−1 − 1) | (sed − s), azaz val´ oban sed ≡ s (mod pq). Ha ln.k.o.(s, pq) = p, akkor p | s ´es ln.k.o.(s, q) = 1, ´ıgy sq−1 ≡ 1 (mod q), ahonnan
(1) miatt sed−1 ≡ 1 (mod q) k¨ ovetkezik. Ekkor teh´ at p | s ´es sed−1 ≡ 1 (mod q), ez´ert pq | s(sed−1 − 1) = sed − s, azaz val´oban sed ≡ s (mod pq). Az el˝ oz˝ o esethez teljesen hasonl´ o bizony´ıt´ as adhat´ o ln.k.o.(s, pq) = q eset´en, v´eg¨ ul az ln.k.o.(s, pq) = pq eset nyilv´ anval´ o. N´ezz¨ uk meg, hogyan is m˝ uk¨ odik az RSA m´ odszer! El˝ osz¨ or is v´ alasztunk k´et igen nagy pr´ımsz´ amot, p-t ´es q-t, majd kisz´ amoljuk ezek n = pq szorzat´ at. Ezut´ an az u ¨zenetet olyan k-bet˝ us blokkokra bontjuk, hogy az u ¨zenetelemek numerikus megfelel˝ oinek maximuma legfeljebb n − 1 legyen. (Azaz, ha p´eld´ aul N bet˝ us ´ ab´ec´et haszn´ alunk k bet˝ us blokkokkal, k akkor N ≤ n teljes¨ ulj¨ on.) Ez biztos´ıtja a k´ odol´ as egy´ertelm˝ us´eg´et. Majd kisz´ amoljuk
ϕ(n)-t, amit a p, q t´enyez˝ ok ismeret´eben k¨ onnyen megtehet¨ unk: ϕ(n) = (p − 1)(q − 1) = n + 1 − p − q. Ezut´ an kiv´alasztunk egy 1 ´es ϕ(n) k¨ oz¨ otti eg´esz sz´ amot, amely relat´ıv pr´ım ϕ(n) = (p − 1)(q − 1)-hez, majd meghat´ arozzuk d ≡ e−1 (mod ϕ(n))-t. Nyilv´ anoss´agra hozzuk az (n, e) k´ odol´ o kulcsot, a p, q, d sz´ amokat pedig titokban tartjuk. A k´ o dol´ o transzform´ aci´ o f (s) ≡ se (mod n), amit b´ arki el tud v´egezni a k´ o dkulcs
ismeret´eben. A dek´ o dol´o transzform´ aci´ o f −1 (t) ≡ td (mod n), amelyet azonban csak a titokban tartott d seg´ıts´eg´evel lehet kisz´ amolni. A 2.1. T´etel szerint a k´et transzform´a-
ci´ o egym´ asnak inverze, nevezetesen f ut´ an f −1 -et, vagy f −1 ut´ an f -et v´egrehajtva, az adott sz¨ ovegelem ed-edik hatv´ any´at kapjuk. Mivel ed ≡ 1 (mod ϕ(n)), ez a hatv´ any a
t´etel szerint ´eppen mag´ aval a sz¨ ovegelemmel, pontosabban annak numerikus megfelel˝ o j´evel kongruens modulo n.
A fentiek alapj´ an u ´gy t˝ unhet, mintha a sima s sz¨ ovegelemek S halmaza ´es a t titkos sz¨ ovegelemek T halmaza megegyezne. Mint fentebb m´ ar eml´ıtett¨ uk, a k´ o dol´ as egy´ertelm˝ us´eg´ehez sz¨ uks´eges, ha a sima sz¨ ovegelemek egy N bet˝ us ´ ab´ec´e k bet˝ us blokkjai, hogy az N k ≤ n egyenl˝ otlens´eg fenn´ alljon. Azaz n ´ert´eke legal´ abb annyi, mint ah´ any k´ o doland´o sima sz¨ ovegelem van. Mi a helyzet a titkos ´ ab´ec´evel? Ezt u ´gy kell megv´ alaszolnunk, hogy minden sima sz¨ ovegelem k´ odj´ anak legyen megfelel˝ o bet˝ uk´ odja. Mivel a k´ odol´ asn´ al modulo n sz´ amolunk, ezt u ´gy ´erhetj¨ uk el, ha valamilyen m´ odon kib˝ ov´ıtj¨ uk a sima ´ ab´ec´et. P´eld´ aul u ´gy, hogy 0 hosszabb l(> k) bet˝ us blokkokat, vagy nagyobb N (> N ) bet˝ usz´ am´ u´ ab´ec´et v´ alasztunk, l 0 k ¨ hogy az N ≥ n illetve az (N ) ≥ n egyenl˝ otlens´eg teljes¨ ulj¨ on. Osszefoglalva teh´ at fenn kell ´ allnia az N k ≤ n ≤ N l vagy az N k ≤ n ≤ (N 0 )k egyenl˝ otlens´egnek. ´ P´ elda. Alljon a sima sz¨ oveg a 26 bet˝ us ´ ab´ec´e digr´ afjaib´ ol, a titkos sz¨ oveg pedig ugyanezen
´b´ec´e trigr´afjaib´ a ol. A k´ o dol´ o kulcs legyen (n, e) = (2047, 179). (P´eld´ ankban ´es a feladatokban a k¨ onnyebb kisz´ amolhat´ os´ ag kedv´e´ert a gyakorlatban haszn´ alt ak´ ar t¨ obb sz´ az jegy˝ u sz´ amokn´ al j´ oval kisebbekkel dolgozunk.) A N E u ¨zenet elk¨ uld´es´ehez a felad´ onak el˝osz¨or meg kell hat´ aroznia az u ¨zenet numerikus megfelel˝ o j´et: N E = 13 · 26 + 4 = 342. Ezut´an ki kell sz´ amolnia se ≡ 342179 (mod 2047) ´ert´ek´et, (hogy ezt hogyan lehet megtenni, arra
k´es˝ obb visszat´er¨ unk) ami 1261 = 1 · 262 + 22 · 26 + 13. A titkos trigr´ af teh´ at BW N .
A c´ımzett ismeri n = 2047 = 23 · 89 pr´ımfelbont´ as´ at, ´ıgy ˝ o meghat´ arozhatja (p´eld´aul euklideszi algoritmus seg´ıts´eg´evel) e = 179 inverz´et modulo ϕ(n) = 22 · 88 = 1936, ami
441. Teh´ at a dek´ odol´ o kulcs (n, d) = (2047, 441). Ennek ismeret´eben kisz´ am´ıthatja td ≡ 1261411 (mod 2047) ´ert´ek´et, ´es ´ıgy megtudhatja az u ¨zenetet: 342 = 13 · 26 + 4 = N E. T´erj¨ unk most r´ a arra, hogyan lehet a k´ o dol´ as ´es dek´ o dol´ as sor´ an fell´ep˝ o nagy modul´ aris hatv´ anyokat kisz´amolni. Ha nekil´ atn´ ank, ´es mechanikusan elv´egezn´enk el˝ osz¨or a hatv´ anyoz´ ast, akkor p´eld´ aul se = 342179 eset´eben egy 537 jegy˝ u sz´ amot kapn´ ank, melynek m´eg meg kellene hat´ arozni a 2047-tel val´ o oszt´ asi marad´ek´at. Ez igen sok sz´ amol´ast ig´enyelne. Kevesebb sz´ amol´ assal is c´elt ´erhet¨ unk, ha alkalmazzuk az u ´gynevezett ism´etelt n´egyzetre emel´es m´ o dszer´et. K¨ ovess¨ uk v´egig ezt 342179 (mod 2047) p´eld´ a j´ an! Az els˝ o l´ep´esben fel´ırjuk a kitev˝ o kettes sz´ amrendszerbeli alakj´ at: 17910 = 101100112 , 7 5 4 azaz 179 = 2 + 2 + 2 + 2 + 1 = 128 + 32 + 16 + 2 + 1. Ez alapj´ an (∗)
342179 = 342128 · 34232 · 34216 · 3422 · 342. A m´ asodik l´ep´esben u ´jra ´es u ´jra n´egyzetre emelve meghat´ arozzuk 342 kett˝ ohatv´any
kitev˝ oj˝ u hatv´ anyait, term´eszetesen modulo 2047 sz´ amolva, ´es k¨ ozben a (∗) felbont´asban szerepl˝ oket mindig ¨ osszeszorozzuk.
3422 ≡ 285 3424 ≡ 2852 ≡ 1392
3428 ≡ 13922 ≡ 1202 34216 ≡ 12022 ≡ 1669 34232 ≡ 16692 ≡ 1641
34264 ≡ 16412 ≡ 1076 342128 ≡ 10762 ≡ 1221
342 · 3422 ≡ 342 · 285 ≡ 1261
1261 · 34216 ≡ 1261 · 1669 ≡ 293 293 · 34232 ≡ 293 · 1641 ≡ 1815 1815 · 342128 ≡ 1815 · 1221 ≡ 1261
(A kongruenci´ ak modulusa minden¨ utt 2047.) V´egeredm´eny¨ ul kapjuk teh´ at, hogy 342179 ≡ 1261 (mod 2047). Vajon csakugyan felt¨ orhetetlen ez a k´ od? Az u ¨zenet megfejt´es´ehez d-t kellene ismernie a felt¨ or´essel pr´ ob´ alkoz´ onak. Azonban csak e ´es n ´ert´ek´et ismeri, ´es tudja, hogy ed ≡ 1 (mod ϕ(n)) ´es n = pq alak´ u, de nem ismeri n t´enyleges felbont´ as´ at, e n´elk¨ ul pedig szinte rem´enytelen kisz´ amolnia ϕ(n) = (p − 1)(q − 1) = n + 1 − p − q ´ert´ek´et. A p ´es q pr´ımek ´ert´ek´et teh´ at olyan nagyra kell v´ alasztani, hogy az illet´ektelen megfejt˝o
sz´ am´ ara rem´enytelen legyen n pr´ımt´enyez˝ os felbont´ as´ anak meghat´ aroz´ asa. Term´eszetesen √ 2, 3, . . . , [ n] k¨ oz¨ ott biztosan meg lehet tal´ alni az n kisebbik pr´ımoszt´ o j´ at, de ez rendk´ıv¨ ul sok oszt´ as elv´egz´es´et ig´enyeln´e. A legkorszer˝ ubb pr´ımt´enyez˝ o meghat´ aroz´ asi m´ o dszerekkel a sz´ amol´ as mennyis´ege ugyan l´enyegesen cs¨ okkenthet˝o, de ha n t¨ obb sz´ az jegyb˝ ol ´all ´es m´eg egy´eb felt´etelek is fenn´ allnak (p ´es q nincs egym´ ashoz t´ ul k¨ ozel, stb.) a legmodernebb szupersz´ am´ıt´ og´eppel is rem´enytelen a t´enyez˝ ok meghat´ aroz´ asa.
Feladatok ¨ ´ 1. K´ odold a KULDJP ENZT u ¨zenetet RSA m´ odszerrel, ha a sima sz¨ ovegelemek a 30 bet˝ us, a titkos sz¨ovegelemek a 35 bet˝ us magyar ´ ab´ec´e digr´ afjai ´es p = 29, q = 37, e = 187! ¨ ¨ 2. A PWABSIVQ XRDQUGFPU u ¨zenetet kaptuk. Az u ¨zenetegys´egek trigr´ afok, a sima ab´ec´e 30, a titkos ´ ´ ab´ec´e 31 bet˝ us (30 bet˝ us + sz´ ok¨ oz = 31). A k´ odol´ o kulcs n = 27383, e = 14411. Dek´ odold az u ¨zenetet, ha 27383 pr´ımt´enyez˝ oi p = 139, q = 197! 3. Tegy¨ uk fel, hogy ellenfel¨ unk a 30 bet˝ us magyar ´ ab´ec´et haszn´ alja, a sima sz¨ ovegelemek trigr´ afok, a titkos sz¨ ovegelemek n´egyes blokkok (tetragr´ afok). A nyilv´ anos k´ odol´ o kulcs n = 36019, e = 25073. (a) Keresd meg n pr´ımt´enyez˝ oit ´es hat´ arozd meg a dek´ odol´ o kulcsot! ´ ¨ (b) Fejtsd meg az AUGLAOQJAGE OAXAEABPE u ¨zenetet!
A feladatok megold´ asai 1. Mivel n = pq = 29 · 37 = 1073, ´ıgy a k´ odol´ o transzform´ aci´ o t ≡ s187 (mod 1073) . A sima sz¨ovegelemek numerikus megfelel˝ oi 384 394 348 195 892. Az e kulcs kettes sz´ amrendszerbeli alakj´ anak (18710 = 101110112 ) seg´ıts´eg´evel, az ism´etelt n´egyzetre emel´es m´ odszer´evel a titkos sz¨ ovegelemek numerikus megfelel˝ oire a k¨ ovetkez˝oket kapjuk: 393 708 812 491 622. Mivel 393 = 11·35+8, 708 = 20·35+8, 812 = 23·35+7, 491 = 14·35+1, 622 = 17·35+27, ˝ ´ U. ´ a tikos sz¨ oveg ´ IGOGRFL AO 2. Mivel n = 27383 = 139 · 197, ´ıgy ϕ(n) = 138 · 196 = 27048. A d dek´ odol´ o kulcs meghat´ aroz´ as´ ahoz teh´ at e−1 ≡ 14411−1 (mod 27 048)-at kell kisz´ amolnunk. Az euklideszi algoritmust alkalmazva kapjuk, hogy d = 1235, ´ıgy a dek´ odol´ o transzform´ aci´ o s ≡ t1235 (mod 27383) . Ezzel ¨ ¨ = 18104 2583 24644 26571 19011 7309 7→ PWABSIVQ XRDQUGFP U ´ ´ 7→ 18201 26856 14345 10972 4890 4060 = RESZV ENYEKETELADNI. 3.(a) Az n = 36 019 pr´ımt´enyez˝ oi p = 181 ´es q = 199. Teh´ at ϕ(n) = 180 · 198 = 35640. Ismerve a nyilv´ anos e ´ert´eket, euklideszi algoritmus alkalmaz´ as´ aval d = 2 639. (b) Az (a) r´esz alapj´ an a dek´ odol´ o transzform´ aci´ o s ≡ t2639 (mod 36019) . A titkos u ¨zenetegys´egek numerikus megfelel˝ oi (n´egyes blokkok!) 20953 14981 34367 24305 2345. Az ism´etelt n´egyzetre emel´es m´ o dszer´evel sz´ amolva a sima sz¨ ovegelemek numerikus megfelel˝ oi 3762 14536 19963 12198 19842. ´ Az u ¨zenet teh´ at DEKODOTELLOPTAK. (Lehet, hogy feleslegesen sz´ amoltunk ennyit?)
