RSA-titkosítás: 4. lépés

Megtaláltuk Φ megoldásához a csapóajtót. Ha ismered N faktortényezőit, akkor Φ(N) kiszámítása könnyű. Például ha tudod, hogy 77 prím felbontása 7-szer 11, akkor tudod, hogy Φ(77)=6 · 10, azaz 60. Harmadik lépés: hogyan lehet összekötni a Φ függvényt a moduláris hatványozással? Ehhez Euler tétele kell, ami a Φ függvény és a moduláris hatványozás közötti kapcsolatot fogalmazza meg: m a Φ(N) hatványon kongruens 1 modulo n-nel. Vegyünk két tetszőleges számot, amiknek nincs közös osztójuk, hívjuk ezeket „m”-nek és „n”-nek. Mondjuk m=5 és n=8. Ha most m-et Φ(n) hatványra emeljük, azaz a negyedik hatványra, és elosztjuk n-nel, akkor a maradék mindig 1. Most ezt az egyenletet két egyszerű szabály alapján módosítjuk. Először is az 1 tetszőleges k hatványa mindig 1 lesz. Ugyanúgy, a Φ(n) kitevőt is megszorozhatjuk egy tetszőleges k számmal, az eredmény továbbra is 1 lesz. Másodszor, ha egy tetszőleges számot, m-et megszorzunk 1-gyel, akkor az eredmény mindig m lesz. Hasonlóképpen, ha a bal oldalt megszorozzuk m-mel, a jobb oldalon m-et kapunk. Ezt viszont így egyszerűsíthetjük: m a k · Φ(N) +1-dik hatványon. Ez a megoldás kulcsa. Van egy egyenletünk e · d megoldásához, ami Φ(n)-től függ. Itt d kiszámítása csak akkor könnyű, ha n prímtényezős felbontása ismert. Ez azt jelenti, hogy Aliz titkos kulcsa d. Ez az a csapóajtó, aminek segítségével vissza lehet alakítani az „e” hatását. Vegyünk egy egyszerű példát, hogy mindezt láthassuk működés közben! Tegyük fel, hogy Bob üzenetét számmá konvertálta egy konverziós séma alapján. Legyen ez „m”. Alíz egy titkos és egy nyilvános kulcsot generál az alábbiak szerint: Először generál két, hasonló méretű véletlen prím számot, és összeszorozza őket, így megkapja n-et, 3127-et. Ebből Φ(n)-t könnyen ki tudja számítani, hiszen ismeri n prím tényezőit. Eredményül 3016-ot kap. Ezután választ egy kis publikus „e” kitevőt, azzal a feltétellel, hogy páratlan legyen, és ne legyen közös osztója Φ(n)-nel. Ebben az esetben e=3-at választ. Végül kiszámítja a titkos d kitevőt, ami ebben az esetben (2 · Φ(n) + 1) / 3, ami 2011. Mindent elrejt, kivéve n-et és e-t, mert n és e a publikus kulcs. Tekintheted ezt egy nyitott lakatnak. Elküldi Bobnak, hogy zárja be vele az üzenetét. Az üzenet bezárásához Bob kiszámolja m az „e” hatványon modulo n értéket. Legyen ez „c”, a titkos üzenet, amit visszaküld Alíznak. Végül Alíz megfejti az üzenetet a d titkos kulcsa segítségével a csapóajtón keresztül: c a d. hatványon modulo n visszaadja Bob eredeti üzenetét, m-et. Figyeld meg, hogy Éva, vagy bárki más c, n és e ismeretével csak akkor képes megtalálni a d kitevőt, ha ki tudja számítani Φ(n)-t, amihez ismerni kell n prím tényezőit. Ha n elég nagy, Alíz bízhat abban, hogy ehhez több száz év kell, még a legerősebb számítógépes hálózat birtokában is. Ezt a trükköt a publikálást követően azonnal titkossá nyilvánították, de 1977-ben Ron Rivest, Adi Shamir és Len Adleman újra felfedezték, ezért RSA titkosítás ennek az eljárásnak a neve. Az RSA a legelterjedtebben használt nyilvános kulcsú algoritmus a világon, és a történelem leggyakrabban másolt szoftvere. A világ minden internet felhasználója RSA-t használ, vagy annak valamilyen változatát, akár tudnak róla, akár nem. Az erejét a prímtényezős felbontás nehézsége adja, ami mélyenszántó kérdéseket vet fel a prím számok elosztásával kapcsolatban. Ez a probléma több ezer év során megoldatlan maradt. (drámai zene)