Felsőfokú tanulmányaim során a matek volt az egyik legérthetetlenebb, legunalmasabb tantárgyam. Vizsgára felkészüléskor (amikor egyszerre félévnyi bizonyítást kellett volna elsajátítani) igencsak nehezemre esett elolvasnom a matematikai regényeket, mert sajnos a beleékelődő képletek zavarták a folyamatos olvasást.

Erre húsz évvel később hasonló levezetésekkel fárasztom a tisztelt nagyérdeműt. Mivel tudom, hogy viszonylag kevesen matekoznak munkahelyükön, egyszerű képlettel kezdjük, hogy a berozsdásodott fogaskerekek fokozatosan indulhassanak be. De kérem, ne add fel a harmadik oldalon! Ha kell, lapozz vissza, olvasd újra! Ha megemészted az RSA-t, soha többé nem fogod ugyanúgy látni a világot. Kitartás!

Gyermekkoromban minden nyári szünetben több hetet vidéken, nagyapáméknál töltöttem. Volt ott minden, mit városi gyerek csak rajzfilmen vagy kifestőkönyvben lát: háziállatok, kukoricagóré, lovaskocsi stb. Nagyapám minden évben elkápráztatott az alábbi "matematikai" bravúrral, s én minden évben újra és újra rácsodálkoztam, hogy mik vannak:

1. számmisztika

• Gondolj egy számot.
• Adj hozzá hatot. (No mi lesz?)
• Szorozd meg hárommal. (Megy ez!)
• Vond ki belőle a gondolt szám háromszorosát. (Ugye még ez is megy fejben?)
• Az eredmény: 18

Ha kicsit jobban belegondolunk, hamar rájövünk a "trükk" nyitjára.

(X+6)* 3 - 3X = 3X + 6 * 3 – 3X

azaz 3X kiesik, marad 3 * 6 = 18

Engem ezzel a feladvánnyal már húsz éve nem lehet megetetni.

Rivest, Shamir, Adleman

Ez a három úr azon néhány kiválasztott elméleti matematikus közé tartozik, akik eredményeiket a gyakorlatban is hasznosítani tudták. A többi matematikus "csak" bebizonyítja, hogy végtelen számú prímszám van, vagy kiszámolja Pí értékét négymillió jegyig - egyszóval semmi aprópénzre válthatót nem alkot.

A mi embereink azonban 1977-ben megalkották a nyílt kulcsú titkosítás máig el nem avult, fel nem tört algoritmusát, amellyel komplett iparágakat teremtettek. Sőt! Gondoljunk a digitális aláírásról szóló törvényre - a hármak bandája tehát országokat is mozgat!

Annyira egyszerű az RSA-algoritmus képlete, hogy valószínűleg a dolog nem is működik. Fogjuk a titkosítanó dokumentumot, felemeljük egy gigantikus hatványra, majd az eredményen maradékos osztást végzünk... és ezzel látszólag elveszítjük az eredeti dokumentumot. De mégsem, mert ha egy másik hatalmas számmal az eredményt ismét meghatványozzuk, majd megint modulóját vesszük, visszakapjuk az eredeti doksit. Hmmm. De miért? És meddig? Mi az esélye és veszélye annak, hogy az RSA-t megtörik?

E sok kérdésre egyelőre nem adom meg a választ, először ugyanis ismét számmisztikázunk. Hatványozni fogunk, így számológép használata javasolt!

2. számmisztika

• Gondolj egy számot (jelöljük T-vel). (2 és 10 között, különben kiakad a számológép.)
• Most keress egy tetszőleges prímszámot (jelöljük N-nel), mely nagyobb, mint az előző szám. (Ugye tudod, mi a bánat az a prímszám? Neeem? A prímszámok olyan csodaszámok, amelyeknek egyen és önmagukon kívül nincs egész osztójuk. Például: 2,3,5,7,11,13,17 stb. )
• Emeld a gondolt számot az (N-1). hatványra.
• Vedd az eredmény moduloját N-nel (modulus = maradékos osztás)
• A maradék: 1

Matekul ez így fest:

T(N-1) mod N = 1 (ha N nagyobb mint T, és N prímszám)

A fenti "trükk" megfejtéséhez már némileg több beleérzőképesseg kell. De nem túl sok. Ez Fermat kistétele (Pierre de Fermat, XVII. Szd.), Euler pedig bebizonyította, hogy a képlet minden prímszámmal működik, ha a prímszám nagyobb, mint a gondolt szám. Ezek a prímszámok tudnak valamit, amire a többi szám nem képes. Vegyük például ezt a másik, hasonló kiszámolót:

3. számmisztika

• Gondolj egy számot (T). (2 és 10 között, különben kiakad a számológép. Ne ugyanazt, mint az előbb!)
• Most keress egy tetszőleges prímszámot (N), mely nagyobb, mint az előző szám.
• Emeld a gondolt számot N. hatványra.
• Vedd az eredmény moduloját N-nel
• A maradék: a gondolt szám.

Ez már igen érdekes! Matekul kifejezve:

T ^ N mod N = T (ha N nagyobb mint T, és N prímszám)

Ez valójában nem más, mint a fentebbi, második számmisztikai egyenlet, melynek mindkét oldalát megszoroztuk T-vel. Íme előttünk az RSA-algoritmus alapja, egy hatványozós, modulós képlet, mely visszaadja az eredeti számot! Ez a játék azonban egyfelhasználós, az RSA-t viszont párban kell játszani (Titkosító, Megfejtő), másrészt ki engedte meg, hogy egy modulós képlet mindkét oldalát büntetlenül megszorozzuk T-vel? Ki mondta, hogy igaz marad az egyenlet? Egyelőre zsákutcába jutottunk. Tegyük félre egy pillanatra a játszadozást. Mi is a cél?

Ariadné, Indiana Jones és a függvények

Célunk egy olyan függvénypár találása, melyek egymást kiegészítve visszavisznek a kiindulóponthoz. Ha a két függvény egyikét a Titkosító, másikát a Megfejtő alkalmazza, ugyanazt az adatot kapjuk vissza. Ilyen függvénypárokat igen egyszerű találni, mivel gyakorlatilag mindegyik ilyen. Legyen a titkosítás például az, hogy a titkosítandó számhoz hozzáadunk egyet (hű, de bonyolult!):

Adat + 1 = titok

Ebben az esetben a kiegészítő függvény, mely az eredeti adatot visszaadja:

Titok – 1 = adat

Ugyanilyen formán a világ számtalan függvénye használható gagyi nyílt kulcsú titkosításra az y=2x+4-től a négyzetre emelésig, de egytől egyig mind gyatra, mert tulajdonképpen nincs is szükségem a fordított függvényre - bőven elég, ha az eredeti műveletsorozatot lépésről lépésre visszafelé hajtjuk végre. Ariadné függvények, mert húzzák maguk után a fonalat, amelynek segítségével bármilyen bonyolult labirintusból kitalálunk. De vegyük csak Indiana Jones példáját. Bemegy egy barlangba, ahol a háta mögött leomlik a fal, árvíz mossa el a hidakat, karók jönnek ki a földből, és ha még ez sem elég, hát meggyullad valami. Ott áll hősünk a barlang legmélyebb pontján bezárva, látszólag reménytelenül (orra előtt a dinkák ősi bálványszobra), de ebben a siralmas helyzetben hirtelen megtalálja a kivezető utat ábrázoló térképet. Ha nem Indiana Jones kavarodott volna be a barlangba, biztos nem talált volna ki, erről tanúskodnak a falak mentén némán üldögélő csontvázak. (Hollywood nem spórol a dramaturgiai kaptafákkal.)

Ez kell nekünk! Olyan függvény, melybe ha besétáltunk, visszaút nincs többé. Hiába próbálkozunk a lépések fordítottjával, a mennyezetről lezuhant szikla utunkat állja. Kijutni csak akkor tudunk, ha a bálvány talpa alól kihúzzuk a térképet. Na ez az RSA. Aki nem tudja, hogy a bálvány lába alatt van a térkép, az meghal.

Az ilyen függvényeket csapda (trapdoor) függvényeknek nevezzük. Az első működő példával Diffe és Hellmann rukkolt elő 1976-ban, pontosan a második számmisztikára alapozva. Most pedig lássuk, mi kell még:

• Moduloaritmetika és kongruencia
• Relatív prímek
• Euler fíje
• A szorzás, mint a helyzet megmentője

Sajnálom, hogy csalódást kell okoznom. Itt komolyra fordul a dolog. A gyengébb idegzetűek ne olvassák el a vonal alatti részt!

1. Moduloaritmetika, kongruencia

Ha az a cél, hogy beomoljon az alagút, keresve sem találhatnánk jobb matematikai műveletet a modulonál, vagyis a maradékos osztásnál. Oly kiválóan fejbecsapja az áldozat számot, hogy az eredményből soha nem leszünk képesek visszaállítani az eredetit. A modulo, vagy maradékos osztás életünk szerves részét képezi. Amikor azt mondjuk, ma kettőkor végzek a munkahelyemen, akkor valójában 14 óráról beszélünk, modulo 12. Modulo 12-vel fejbevágva a 14 tulajdonképpen egyenlő 2-vel. Ezt a furcsa egyenlőséget a matematikában kongruenciának hívják, és hármas egyenlőségjellel jelölik. Bármely szám bármely másikkal képzett moduloját igen könnyű vizualizálni. A

127 mod 21 = 1

nem más, mint egy 21 "órából" álló számkör, melyre a 127-et "felcsavarjuk". Többször körbefut, majd a vége valameddig elér a 21-es számkörön. Ez a maradék a modulo végeredménye. A fenti írásmód a „hétköznapi”. Ugyanez matekul:

127 º 1 (mod 21)

Ennek olvasata: a 127 valójában ugyanaz, mint az egy, ha modulo 21-ben gondolkozunk. A 2-kor végzek matekul így fest:

14 óra º 2 óra (mod 12-ben gondolkodva)

Hol találunk még modulót mindennapjainkban? Hát a számítógépeinkben. A mai elterjedt processzorok 32 bitesek, ami tulajdonképpen annyit jelent, hogy 2^32-nel modulálnak minden egész számon végzett matematikai műveletet. Ha túl nagy fába vágjuk a fejszénket, a túlcsordulás miatt könnyen azon kaphatjuk magunkat, hogy

1 + 1 º 256 + 1 + 1

Hármas egyenlőségjellel persze. De akkor már bánhatjuk. Modulo a hét napjai (mod 7), a beszélt nyelv (220V= kettő-húsz, azaz mod 100) stb. Modulo mindenütt.

Érdekes, és később hasznunkra válik majd, hogy a moduloaritmetikában (szinte) bármikor fejbecsaphatjuk a művelet tagjait a modulussal, a számítás előtt, vagy a végeredményen - egyre megy. Példa:

Most 11 óra van. Mennyit mutat majd a vekker 27 óra múlva?

1. számítás: a modulo a végeredményre sújt le:
11+27 = 38 º 2 (mod 12 esetén)

2. számítás: a moduloval már a kedzőértékeket fejbecsapjuk
27 º 3 (mod 12-vel lecsapva)
11 º 11 (mod 12-vel lecsapva. Nem változik)
11 + 3 = 14 º 2 (mod 12)

Ez a trükk ráadásul nemcsak összeadásra, hanem könnyen belátható módon gyorsított összeadásra, vagyis szorzásra is működik! Egy tyúk levágásának és feldolgozásának ideje 3 óra (forralás, belezés, belsőségek megtisztítása, darabolás, csomagolás, fagyasztás). Sajnos 50 élő tyúkot kaptunk vidékről bele a panellakás kellős közepébe. Ha délelőtt 11-kor kezdem, vajon fent lesz-e a napocska, amikor befejezem? Egyedül csinálom, a feleségem nem ért hozzá (nem sokat nyaralt vidéken gyermekkorában). Mivel a napocska hollétére vagyok kíváncsi, mod 24-gyel dolgozom:

1. számítás: mod 24 a végeredményre
3 * 50 = 150 º 6 (mod 24) A nap épp kelőben lesz.

2. számítás: mod 24 a kiindulási adatokra
50 mod 24 º 2 (mod 24)
2 * 3 = 6. A nap épp kelőben lesz.

Hogy én beledöglök-e a több mint hatnapi megszakítás nélküli tyúkpucolásba? Nem érdekes... Ennél sokkal fontosabb, hogy a moduloaritmetika bármikor bevethető. Például, ha egy moduloszámítás során kezdene elszaladni az eredmény a végtelen felé. Csak lesújtunk rá a moduloval, és rögtön nyugton marad, mi pedig számolhatunk tovább.

2. Relatív prímek

Megy még a prímtényezőkre bontás? Hatodik osztályos anyag. És hogy kapom meg két szám legnagyobb közös osztóját? Segítek.

Prímtényezőkre bontás:
18 = 2 * 3 * 3
30 = 2 * 3 * 5

A legnagyobb közös osztó (LKO)kiszámítása
Az LKO két szám közös prímtényezőinek szorzata. A fenti esetben a 2, és a 3 közös, így 18 és 30 legnagyobb közös osztója 6.

Ha két szám prímtényezői egyáltalán nem egyeznek, a legnagyobb közös osztójuk 1, a két szám relatív prím egymáshoz képest. Példa:

28 = 2 * 2 * 7
45 = 3 * 3 * 5

Prímtényezőikben nincs közös, legnagyobb közös osztójuk 1. A 28 és a 45 egymáshoz képest relatív prímek. Hogy mi a csudára jó ez nekünk? Hát kipróbálhatjuk, hogy a hatványozós-modulós játék (a 3. számmisztika) egészen biztosan csak akkor működik-e, ha N prím, vagy netalán a relatív prímek is eleget „tudnak”, és elég, ha N relatív prím T-hez képest?

HA a hatványkitevőt fel tudnánk bontani két részre, valahogy így:

N=P*Q (ami ugyebár addig nem megy, amíg ebben a számjátékban N kötelezően prím) akkor

T(P*Q) º T (mod N)

ugyanazt adná, a hatványozást pedig két különböző emberre bízhatnánk

Titkosító: T ^ P º R (mod N nyomása alatt)

Megfejtő: R ^ Q º T (mod N)

miénk is lenne az RSA.

1. próba:
T=5 (a titkosítandó szám)
N=6 (relatív prím T-hez, ha nem hiszi, számolja ki)
56 mod 6=...1

Jaj. Ez nem az eredeti szám, ez biza nem 5. Ez nem jött be. Euler! Segíts!

3. Euler fíje

Mitől működik... a 3. számmisztika? Jobban utánaolvasva kiderül, hogy a hatványkitevő csak prímszámok esetén ugyanaz, mint a modulus (N), és ott is csak azért, mert "véletlenül" így jön ki minden prímszámnál. A hatványkitevő ugyanis nem más, mint a modulus relatív prímjeinek száma + 1. Ez jó bonyolultan hangzik, úgyhogy vegyünk példákat:

9-hez képest relatív prímek (azaz a legnagyobb közös osztójuk 1): 1, 2, 4, 5, 7 és 8. Összesen 6 darab.
7-hez képest relatív prímek: 1,2,3,4,5 és 6. (Azaz minden nála kisebb szám, merthogy a 7 maga prím.) Összesen megint 6 darab.

Euler a görög f (fi) betűvel jelölte azt, hogy egy számnak hány relatív prímje van. Így f(9) = 6, és f(7) szintén 6 (bár merő véletlenségből annyi, nincs semmi köze a 7-nek a 9-hez). Prímszámoknál borzasztó egyszerű kiszámítani:

f (N) = N-1

minthogy mindegyik nála kisebb szám relatív prímje egy prímnek. A 3. számmisztika kijavítva:

T f (N)+1 º T (mod N)

Lássuk az előző példát, hátha így összejön!

2. próba
T=5 (a titkosítandó szám)
N=6 (relatív prím T-hez, 2*3 legnagyobb közös osztója 5-tel: 1)
f(6)=1 és 5, azaz összesen 2 darab

5 ^ (2+1) mod 6 = ...jaj de izgulok ... = 5!

Hurrá! visszakaptuk az eredetit! Pedig a matekozáshoz használt N nem is prím! Ki meri azt állítani, hogy a 6-os prímszám? Elégtelen!

Ez már majdnem RSA, csak egyfelhasználós.

RSA!

Itt buktunk el az előbb: ha a hatványkitevőt fel tudnánk bontani két részre, valahogy így:

f (N)+1=P*Q

ami most már megy, mert a 6 messze nem prím, akkor

T ^ (P*Q) º T (mod N után)

jól működne, a hatványozást pedig két különböző emberre bízhatnánk

Titkosító: T ^ P mod N = R
Megfejtő: R ^ Q mod N = T

és miénk lenne az RSA.

3. próba:
A fenti példában a hatványkitevő 3. Ezt sajna csak így lehet szorzótényezőkre bontani: 1*3. Az 1 nem valami "jó" hatványkitevő, ugyanis nem csinál semmit a hatványozás során. Már megint kicsúszott a markunk közül ez a nyomorult RSA, de nem adjuk fel!

4. A szorzás, mint a helyzet megmentője

A második számmisztika gyúrása (emlékeztetőül, ez volt az):

T ^ (N-1) º 1 (mod N)

Most már tudjuk (Euler segített), ez valójában

T ^ f (N) º 1 (mod N-nel kupánvágva)

Mindkét oldalt emeljük négyzetre:

T ^ f (N) * T ^ f (N) º 1 * 1 (mod N)

Most köbre:

T ^ f (N) * T ^ f (N) * T ^ f (N) º 1 * 1 * 1 (mod N)

Bízvást menne negyedik hatványra is... Írjuk fel a köböst a hatványkitevők összevonásával:

T ^ 3*f (N) º 1 (ne feledd: mod N!)

Ebben az a röhej, hogy a moduloaritmetika miatt a hármas helyén akármilyen szám állhat, és nem zavarja köreinket! Hoppá! Így ha a f(N)+1 felbontása olyan suta lenne, mint az előző bekezdésben (1 és 3 jött ki), semmi gond, mert ennek akárhányszorosa, azaz K*f(N)+1 éppoly jó felbontási alany, így:

2+1 helyett bátran megpróbálkozhatunk akár a

7*2+1 (=15) felbontásával: 3 és 5.

Sokadik nekifutás: 4. próba
T=5 (a titkosítandó szám)
N=6 (relatív prím T-hez, 2*3 legnagyobb közös osztója 5-tel: 1)
f(6)=1 és 5, azaz összesen 2
K*f(N)+1=7*2+1=15=P*Q. P=3, Q=5

Titkosító: T ^ P mod N=R, azaz 53 mod 6=5
Megfejtő: R ^ Q mod N=T, azaz 55 mod 6=5

RSA-zunk!!!!!

A publikus kulcs P és N
A privát kulcs Q és N

Egy hétköznapi példa

A hét napjaival fogunk titkosítani. Az egyszerűség miatt az év negyedik napja lesz a titkosítottan átküldött infó, a modulus pedig 7, azaz vasárnap. Azért választottam ezt a példát, mert ebben oly természetes a modulus!

T=4, csütörtök (a titkosítandó szám)
N=7, azaz egy naptárlap napjainak száma (relatív prím T-hez, legnagyobb közös osztója 4-gyel: 1)
f(7)=1, 2, 3, 4, 5 és 6, azaz összesen 6 nála kisebb relatív prímje van
K*f(N)+1=4*6+1=25=P*Q. P=5, Q=5 (ez bénaság, a két hatványkitevő sose legyen egyforma, de mi csak gyakorlunk)

A titkosítás valójában a naptár előrepörgetése rengeteg nappal, így rengeteg lappal. Ahol az előrepörgetés megáll, megnézzük milyen napot írunk (ez a Mod 7).

Titkosítás: T ^ P mod N=R, azaz 45 mod 7=2, azaz kedd. Ezt küldöm el a partneremnek.
Megfejtés: R ^ Q mod N=T, azaz 25 mod 7=4, azaz csütörtök.

A publikus kulcs P és N, azaz 5 és 7. Lássuk, pusztán ennek birtokában, hekkerként  vissza tudjuk-e fejteni az eredeti napot. A modulo miatt sok "vért" veszítettünk, gyakorlatilag fogalmunk sincs, hogy hány napot rohantunk előre, kizárólag a maradék maradt. Ennélfogva T akármi lehet, mert végtelen sok olyan szám van, amit ha P-edik hatványra emelünk, majd mod 7-tel lefejezünk, keddet ad eredményül. Visszaút nincs. Előre pedig csak azok hatolhatnak, akik ismerik Q-t, a privát kulcsot.

Kulcsgenerálás

Már tudjuk, hogy a modulusnak nem kell prímszámnak lennie, bőven elég, ha relatív prím a titkosítandó adathoz. Vajon hogy a csudába biztosítható, hogy a modulus:

• Oltári nagy szám legyen 
• Relatív prím gyakorlatilag bármihez (fontos.doc például) 
• Meg tudjuk állapítani a f-jét (relatív prímjeinek számát) 
• f-je felbontható legyen két egész szám szorzatára

Hmm. Ez igazán nehéz feladatnak tűnne, ha vakon bökdösnénk a számok között. E helyett okosan a következőt tesszük:

• Veszünk két hatalmas prímszámot, X és Y (www.mersenne.org és egyéb módszerek) 
• Ezek szorzata lesz N, a modulus, ami ugyan nem prím, de mivel két elvetemülten nagy prímszám szorzata, gyakorlatilag bármilyen nagy számhoz relatív prím lesz 
• Mindkét prímszámnak tudjuk a f-jét (prímszámokról lévén szó X-1 és Y-1), így N f-je is adott: f=(X-1)*(Y-1) 
• Ezután felbontjuk f-t két szám szorzatára (P és Q). Nem nehéz, hisz "K*f(N)+1 éppoly jó felbontási alany", lásd fenn. P és Q ideális esetben egymáshoz képest relatív prím, de ez nem szükséges feltétel 
• A nagy prímszámokat elhajítjuk. Többé nem kellenek.

A kulcspárok pedig P, N és Q, N

Gyenge pontok

Az RSA gyenge pontja nem az algoritmus, hanem a kulcsgenerálás. Mivel N része a publikus kulcsnak, az RSA addig „él”, amíg nincs jobb módszer N prímtényezőkre bontásához, mint a próbálgatás. 

Ellenőrzés

Ne mondd, hogy elsőre feldolgoztad. Nem igaz. Most légy szíves olvassa el ezt a fejezetet elölről. Ami nem megy elsőre, majd megy másodikra. Ami nem megy másodikra, majd sikerül harmadikra. Ami nem megy harmadikra...