BSz1 Jegyzet

4. Tétel:

Polinomiális futásidejű algoritmus (vázlatos) fogalma. Számelmélet és algoritmusok: alapműveletek és hatványozás az egészek körében, moduláris hatványozás, ezek lépésszáma. Prímtesztelés, Carmichael számok. Nyilvános kulcsú titkosítás, RSA algoritmus (kódolás és dekódolás).

4.1. Algoritmusok elméleti alapjai (1.6.1. Definíció)

1.6.1. Definíció (Input mérete és polinomiális idő):

Az $A$ algoritmus egy lehetséges $I$ inputjának a mérete alatt az $I$-nek a memóriában való tárolásához szükséges bitek számát értjük. Az $A$ algoritmus akkor polinomiális futásidejű, ha léteznek olyan $c > 0$ és $k > 0$ rögzített konstansok, hogy minden $n \ge 1, n \in \mathbb{N}$ esetén az $A$ bármely $n$ méretű inputra futtatva legföljebb $c \cdot n^k$ lépés után megáll.

1.6.2. Alapműveletek műveletigénye

1
Összeadás és Kivonás

Bemenet: $a, b \in \mathbb{Z} > 0$

Kimenet: $a \pm b$

Lineáris futásidő

Lépésszám: $c \cdot (k + l)$

($k, l$ a jegyek száma, $c$ konstans)

2
Szorzás

Bemenet: $a, b \in \mathbb{Z} > 0$

Kimenet: $a \cdot b$

Polinomiális (nem lineáris)

Lépésszám: $c \cdot k \cdot l$

3
Maradékos osztás

Bemenet: $a, b \in \mathbb{Z}$

Kimenet: $\lfloor a/b \rfloor$ és $a \pmod b$

Polinomiális (nem lineáris)

Lépésszám: $c \cdot k \cdot l$

4.2. Moduláris hatványozás

Bár korábban kiderült, hogy $a^b$-t (polinomiális futásidőben) reménytelen kiszámítani, a nyilvános kulcsú titkosításhoz alapvető lesz, hogy $a^b$-nek egy adott $m$ szerinti osztási maradékát mégis meg tudjuk határozni. Ezt a feladatot hívják moduláris hatványozásnak:

Bemenet: $a, b$ és $m$ pozitív egészek;

Kimenet: $a^b \pmod m$ (vagyis $a^b$ osztási maradéka $m$ szerint).

Miért nem járható a közvetlen út?

Ennél a feladatnál már nem okoz problémát, hogy a kimenet túl nagy volna, hiszen az $m$-nél kisebb. Másrészt viszont nem járható út $a^b$ kiszámítása, majd annak $m$-mel való maradékos osztása, hiszen láttuk, hogy ez a terv már az első lépésnél meghiúsul. Az exponenciális tárigény problémáján segítene, ha az $a, a^2, \dots, a^b$ hatványok $m$ szerinti maradékát sorra kiszámítanánk (úgy, hogy mindig az előző maradék $a$-szorosának $m$ szerinti maradékát vesszük), de ez az eljárás is használhatatlanul lassú volna: $b-1$ darab ilyen lépést kellene tennünk, ami nem polinomiális algoritmust jelentene.

Szerencsére létezik hatékony, polinomiális futásidejű algoritmus is a moduláris hatványozás feladatára: az ismételt négyzetre emelések módszere.

Példa: $13^{53} \pmod{97}$ kiszámítása

Az alábbi számításban mindegyik sor az előző négyzetre emelésével keletkezik:

1. Lépés: 2-hatvány kitevőjű maradékok

$13^1 \equiv 13 \pmod{97}$

$13^2 = 169 \equiv \mathbf{72} \pmod{97}$

$13^4 = (13^2)^2 = 72^2 = 5184 \equiv \mathbf{43} \pmod{97}$

$13^8 = (13^4)^2 = 43^2 = 1849 \equiv \mathbf{6} \pmod{97}$

$13^{16} = (13^8)^2 = 6^2 = \mathbf{36} \pmod{97}$

$13^{32} = (13^{16})^2 = 36^2 = 1296 \equiv \mathbf{35} \pmod{97}$

Látszik, hogy ezzel a módszerrel a 13-nak az $1, 2, 4, 8, \dots$, vagyis a 2-hatvány kitevőjű hatványait tudjuk közvetlenül meghatározni. A sort $13^{32}$ után tovább folytatni értelmetlen volna, hiszen $13^{64}$ már nagyobb a kiszámítandó $13^{53}$-nál.

2. Lépés: Kitevő felbontása (Bináris alak)

A válasz egyszerű: $53 = 1 + 4 + 16 + 32$

Ez következik $b=53$ kettes számrendszerbeli alakjából: $110101_2 = 2^0 + 2^2 + 2^4 + 2^5$.

A négy tagnak a 97-es maradékait összeszorozva $13^{53}$-nal kongruens számot kapunk. Ezeket a szorzásokat is lépésenként végezzük:

$13^5 = 13^1 \cdot 13^4 \equiv 13 \cdot 43 = 559 \equiv \mathbf{74} \pmod{97}$

$13^{21} = 13^5 \cdot 13^{16} \equiv 74 \cdot 36 = 2664 \equiv \mathbf{45} \pmod{97}$

$13^{53} = 13^{21} \cdot 13^{32} \equiv 45 \cdot 35 = 1575 \equiv \mathbf{23} \pmod{97}$

A végeredmény tehát: $13^{53} \equiv 23 \pmod{97}$.

Az ismételt négyzetre emelések algoritmusa ($a^b \pmod m$)

Az algoritmus általános leírását elegendő a $0 < a < m$ esetre megadni (mert ha nem ez a helyzet, akkor $a$-t helyettesíthetjük az $m$ szerinti maradékával). Nem feltételezzük, hogy $b$ bináris alakja eleve adott, ezt is párhuzamosan határozzuk meg a négyzetre emelésekkel.

Bemenet: $a, b$ és $m$ (amelyekre $0 < a < m$ és $b \ge 1$ teljesül)

1    $c \leftarrow 1$

2    ciklus

3       ha $b$ páratlan, akkor:

4           $c \leftarrow c \cdot a \pmod m$

5       $b \leftarrow \lfloor \frac{b}{2} \rfloor$

6       ha $b = 0$, akkor

7           print „$a^b \pmod m =$”, $c$; stop.

8       $a \leftarrow a^2 \pmod m$

9    ciklus vége

Észrevétel: $b$ bináris alakjának utolsó jegye $b$ 2-es maradékával egyenlő, a többi jegy pedig megegyezik $\lfloor \frac{b}{2} \rfloor$ bináris alakjával. Ezen alapul a fenti algoritmus hatékonysága.

Moduláris hatványozás levezetése

4.3. Prímtesztelés (1.6.6.)

Többször említettük már, hogy a prímfaktorizálás feladatára nem ismert hatékony algoritmus; látni fogjuk, hogy ez nem feltétlen „rossz hír”, ezen alapszik ugyanis az RSA titkosítás. Ehhez képest meglepő, hogy egy adott számról hatékonyan el lehet dönteni, hogy prím-e vagy sem – ezt a feladatot hívják prímtesztelésnek:

Bemenet: $m$ pozitív egész;

Kimenet: „IGEN”, ha $m$ prím és „NEM”, ha $m$ nem prím.

A prímtesztelő algoritmusoknak az $m$ összetettségét úgy kell tudniuk kimutatni, hogy közben $m$ egyetlen valódi osztóját sem találják meg. Az egyik legegyszerűbb prímtesztelő módszer az 1.5.7. Euler-Fermat tételen alapszik: ha $m$ prím és $1 \le a \le m - 1$ tetszőleges, akkor $\phi(m) = m - 1$ és $(a, m) = 1$, így az $a^{m-1} \equiv 1 \pmod m$ kongruenciának teljesülnie kell.

Ha tehát sikerül találnunk egy olyan $1 \le a \le m - 1$ egészet, amelyre $a^{m-1} \not\equiv 1 \pmod m$, akkor $m$ biztosan nem prím.

A Fermat-teszt néven közismert eljárás egymás után generál véletlen $a$ számokat, és minden $a$-ra ellenőrzi a feltételt. Az algoritmust két ponton egészítjük ki: egyrészt először kiszámítjuk $(a, m)$ értékét (ha ez $> 1$, $m$ nem prím), másrészt beiktatunk egy számlálót, ami egy előre rögzített számú (pl. 100) kísérlet után megállítja az eljárást.

Fermat-teszt Algoritmus

Bemenet: $m$ egész

1    ciklus: $k$ fut 1-től 100-ig

2       Generáljunk egy $a$ véletlen számot 1 és $m - 1$ között.

3       Számítsuk ki $(a, m)$ értékét az EUKLIDESZI ALGORITMUSSAL.

4       ha $(a, m) \neq 1$, akkor:

5           print „$m$ NEM prím”; stop

6       különben:

7           Számítsuk ki $(a^{m-1} \pmod m)$ értékét az ISMÉTELT NÉGYZETRE EMELÉSEK MÓDSZERÉVEL.

8           ha $(a^{m-1} \pmod m) \neq 1$, akkor:

9              print „$m$ NEM prím”; stop

10   ciklus vége

11   print „IGEN, $m$ valószínűleg prím”

Kriminológiai analógia

Szokás a fenti eljárást a krimik nyelvezetét idéző módon is elmondani: az $a$ véletlen számokat sorban a tanúk padjára idézzük, az $a$ vallomása pedig (az $(a, m) = 1$ esetben) az $(a^{m-1} \pmod m)$ érték. Ha a vallomás nem 1, a tanú leleplezte $m$ összetettségét.

Megjegyzés a bizonyosságról: Ha az algoritmus azt mondja, „NEM prím”, az 100% biztos. Ha azt mondja, „IGEN”, az csak nagy valószínűség (léteznek ugyanis ún. Carmichael-számok, amelyek összetettségét a Fermat-teszt nehezen mutatja ki).

Fermat-teszt

A nagyobb tanúszám csökkenti a tévedés kockázatát.

4.3.1. A Fermat-teszt terminológiája és megbízhatósága

1.6.6. Definíció (Cinkos és Áruló):

Legyenek $m$ és $a$ olyan egészek, amikre $1 \le a < m$ és $(a, m)=1$.

  • Ekkor $a$-t az $m$ cinkosának nevezzük, ha $a^{m-1} \equiv 1 \pmod m$.
  • Ha viszont $a^{m-1} \not\equiv 1 \pmod m$, akkor $a$-t az $m$ árulójának mondjuk.

A terminológia magyarázata

Ezek az elnevezések onnan származnak, hogy ha $a$ cinkosa $m$-nek, akkor $a$ nem közöl információt $m$ prímségét illetően; ha viszont $a$ árulója $m$-nek, akkor leleplezi $m$ összetettségét.

Fontos megjegyzés: Az $(a, m) > 1$ esetben $a$-t nem nevezzük az $m$ árulójának annak ellenére sem, hogy természetesen ilyenkor is kiderül $m$ összetettsége; a cinkos és az áruló elnevezések egyaránt csak az $1$ és $m-1$ közötti, $m$-hez relatív prím $a$-kra vonatkoznak.

Algoritmuselméleti megfontolások

Az eljárás 2. sora véletlen szám generálását írja elő, de ennek a megvalósításával itt nem foglalkozunk annak ellenére sem, hogy ez a feladat messze nem magától értetődő.

  • ● A kriptográfiai alkalmazások megbízhatósága szempontjából alapvető, hogy jó minőségű – tehát a „valódi véletlent” nagyon jól imitáló – véletlen szám generátor álljon rendelkezésre.
  • ● A véletlen használata alapvető algoritmuselméleti kérdéseket is felvet, mert az algoritmus fogalmának elméleti megalapozása elsősorban a determinisztikus algoritmusokra vonatkozik.

Hatékonyság és Valószínűség

Eltekintve a véletlen szám generálása körüli elvi és gyakorlati problémáktól elmondható, hogy a Fermat-teszt nagyon hatékony eljárás: a rögzített számú (pl. 100 darab) legnagyobb közös osztó számítás és moduláris hatványozás együttesen is nyilván polinomiális futásidejű.

Mit értünk az alatt, hogy „m valószínűleg prím”?

Mire lehet következtetni 100 semmitmondó vallomásból, vagyis 100 sikertelen kísérletből $m$ összetettségének a bizonyítására? Ha például egy $m$ összetett számra előfordulhatna, hogy a hozzá relatív prím $a$-knak a $0,1\%$-a áruló, akkor $90\%$-nál is nagyobb volna a valószínűsége annak, hogy a 100 kísérlet során egy árulót sem találunk és $m$-et tévesen prímnek nyilvánítjuk.

Szerencsére az algebra eszközeivel belátható, hogy ez az eset (a Carmichael-számoktól eltekintve) nem lehetséges.

4.3.2. Az árulók aránya (1.6.7. Tétel)

1.6.7. Tétel:

Ha $m > 1$ összetett szám és $m$-nek van árulója, akkor az $1$ és $m$ közötti, $m$-hez relatív prím számoknak legalább a fele áruló.

Részletes Bizonyítás:

Legyen $a$ egy tetszőleges árulója $m$-nek, és legyen $c_1, c_2, \dots, c_k$ az $m$ összes cinkosa. Megmutatjuk, hogy az $a_i = (a \cdot c_i \pmod m)$ számok ($i = 1, 2, \dots, k$) mind páronként különböző árulói $m$-nek. Ebből következni fog, hogy az árulók száma legalább akkora, mint a cinkosok száma, ami ekvivalens a tétel állításával.

1. Relatív prímség: Vegyük észre, hogy $(a, m) = 1$ és $(c_i, m) = 1$. A számelmélet alaptétele miatt $(a \cdot c_i, m) = 1$ is teljesül, így az 1.5.1. Állítás szerint $(a_i, m) = 1$ is igaz, mert $a_i \equiv a \cdot c_i \pmod m$.

2. Az áruló jelleg igazolása: Emeljük az $a_i \equiv a \cdot c_i \pmod m$ kongruenciát az $(m-1)$-edik hatványra:

$a_i^{m-1} \equiv (a \cdot c_i)^{m-1} = a^{m-1} \cdot c_i^{m-1} \equiv a^{m-1} \cdot 1 = a^{m-1} \not\equiv 1 \pmod m$

(Itt felhasználtuk, hogy $c_i^{m-1} \equiv 1$ mert $c_i$ cinkos, és $a^{m-1} \not\equiv 1$ mert $a$ áruló.)

Tehát minden $a_i$ valóban áruló.

3. Páronkénti különbözőség: Tegyük fel indirekt, hogy $a_i = a_j$ valamely $i \neq j$ esetén.

Ekkor $a \cdot c_i \equiv a \cdot c_j \pmod m$ következik. Mivel $(a, m) = 1$, mindkét oldalt eloszthatjuk $a$-val a modulus megváltoztatása nélkül, így $c_i \equiv c_j \pmod m$.

Mivel azonban $1 \le c_i, c_j \le m - 1$ és $c_i \neq c_j$, ez ellentmondás.

Ezzel beláttuk, hogy legalább annyi áruló van, mint cinkos. A tétel bizonyítása kész. □

Miért fontos ez az algoritmusnak?

Ez a tétel adja meg a Fermat-teszt matematikai garanciáját: ha egy szám nem prím (és nem Carmichael-szám), akkor egy véletlen $a$ alap választásával legalább 50% eséllyel leleplezzük az összetettségét. 100 kísérlet esetén annak a valószínűsége, hogy egy összetett számra minden tanú "hazudik" (vagyis cinkos), kisebb mint $(1/2)^{100}$, ami elhanyagolhatóan kicsi.

4.3.3. Carmichael-számok (1.6.8. Definíció)

1.6.8. Definíció (Univerzális álprím):

Az $m > 1$ összetett számot univerzális álprímnek, vagy más néven Carmichael-számnak nevezzük, ha nincs árulója; vagyis ha minden $1 \le a < m, (a, m)=1$ esetén $a^{m-1} \equiv 1 \pmod m$.

A Fermat-teszt kudarca

Ha a Fermat-tesztet egy $m$ Carmichael-számra futtatjuk, akkor az nagy valószínűséggel tévesen prímnek fogja nyilvánítani azt. Az ilyen szám $m$ egyedül az $(a, m) = 1$ feltétel sérülésével „bukhatna le”, de ilyen $a$-ba botlani csak nagyon kis valószínűséggel fogunk.

A Carmichael-számok viszonylag ritkák: az 561 a legkisebb, az utána következő az $1105 = 5 \cdot 13 \cdot 17$. Egymillióig pedig összesen csak 43 darab van belőlük, de 1994-ben bebizonyították, hogy a számuk végtelen.

A Fermat-teszt három hiányossága

i.

Az algoritmus a Carmichael-számokat nagy valószínűséggel tévesen prímnek nyilvánítja.

ii.

Az eljárás az $m$ prímnek nyilvánításakor egy elhanyagolhatóan kicsi, de pozitív valószínűséggel akkor is tévedhet, ha $m$ tetszőleges összetett szám.

iii.

Az algoritmus nem determinisztikus, véletlent használ.

Modern megoldások

A gyakorlat szempontjából a fenti három hiányosság közül csak az (i) érdemel figyelmet. Szerencsére a Fermat-tesztnek ismertek olyan módosításai, amelyek éppen ezt a problémát oldják meg; ezek közül a Miller-Rabin-teszt a legtöbbet használt. Ez azon alapszik, hogy a tanúk „alaposabb kikérdezésével” már kiszűrhetők a Carmichael-számok is, miközben az algoritmus futásideje ettől alig romlik.

Létezik-e olyan polinomiális futásidejű algoritmus, amely minden $m$ szám prímségét determinisztikusan és teljes biztonsággal eldönti? A választ erre a kérdésre 2002 óta ismert: ekkor publikált Agrawal, Kayal és Saxena egy ilyen algoritmust (AKS-teszt). Bár ez az eredmény áttörés volt a prímszámok elméletében, a gyakorlati alkalmazásokban a nagyságrendekkel jobb lépésszáma miatt továbbra is a Miller-Rabin-tesztet használják.

4.4. RSA – Nyilvános kulcsú titkosítás

Az RSA elve:

I.

Generálunk 2 darab hatalmas prímet ($p, q$).

Ehhez random szám generálás és prímteszt (pl. Miller-Rabin) szükséges.

II.

$N = p \cdot q$

Az $N$ modulus olyan nagy, hogy nem fejthető vissza $p$ és $q$ tényezőkre (vagyis a faktorizáció megoldhatatlanul lassú).

III.

Keresünk $C$ és $D$ kölcsönösen egyértelmű függvényeket:

  • • A függvények egymás inverzei.
  • • A kód tulajdonsága: mindkét függvény értékét hatékonyan ki tudja számolni a tulajdonosa.
  • • A $C$-t létrehozó eljárás nyilvánosságra hozható, ezzel a $D$-t nem lehet hatékonyan kiszámolni.

A Kommunikáció Menete

Mivel $N \to \text{hatalmas}$, kódegyeztetés nélkül lehet titkos üzenetet fogadni.

"A" fél (Fogadó)

Elküldi a $C_A$-t kiszámító eljárást (nyilvános kulcs).

➜

"B" fél (Küldő)

Az $x$ üzenet helyett visszaküldi az $y = C_A(x)$ kódolt üzenetet.

"A" pedig a $D(y) = x$ művelettel visszafejti az eredeti üzenetet.

Mindkét fél rendelkezik $C, D$ párral: kétirányú titkos kommunikáció.

4.5. Az RSA algoritmus matematikai megvalósítása

I. Lépés

Generálunk 2 darab hatalmas prímet: $p, q$.

II. Lépés

Kiszámítjuk a modulust: $N = p \cdot q$.

III. Lépés

Választunk egy olyan $c \in \mathbb{Z}$ egész számot, amelyre $(c, \phi(N)) = 1$ teljesül.
Tehát $c$ és $\phi(N)$ relatív prímek.

IV. Nyilvános kódolás (C)

$C: x \mapsto x^c \pmod N$

Ez a művelet a 4.2. pontban tanult moduláris hatványozással hatékonyan kiszámolható.

V. Dekódolás (D)

$D: y \mapsto y^d \pmod N$

A titkosításhoz keressük azt a $d$ kitevőt, amely visszaállítja az eredeti üzenetet.

VI. Lépés: A titkos kulcs ($d$) meghatározása

A $d$ értéke a következő lineáris kongruencia megoldásával adódik:

$c \cdot x \equiv 1 \pmod{\phi(N)}$

➜ A megoldást ($x$) az Euklideszi algoritmussal kapjuk meg.

➜ A kapott értéket rendeljük hozzá $d$-hez: $d \leftarrow x$.

A $D$ függvényt (és benne $d$-t) titokban tartjuk!

Az adatok ($C$ és $D$) előállítása után a rendszer készen áll a titkos kommunikációra.

4.6. Miért működik a visszafejtés? (1.6.11. Állítás)

1.6.11. Állítás:

Legyenek $p$ és $q$ különböző prímek és $N = p \cdot q$. Ekkor tetszőleges $x$ és $k \ge 1$ egészekre: $$x^{k \cdot \phi(N) + 1} \equiv x \pmod N$$

Bizonyítás:

1. Eset: Ha $(x, N) = 1$, akkor az állítás az 1.5.7. Euler-Fermat tétel közvetlen következménye. Az $x^{\phi(N)} \equiv 1 \pmod N$ kongruenciát először a $k$-adik hatványra emelve, majd mindkét oldalt $x$-szel szorozva épp a bizonyítandó állítást kapjuk.

2. Eset: Ha $(x, N) \neq 1$, akkor $p \mid x$ vagy $q \mid x$. Ha mindkettő teljesül, akkor $N \mid x$, így a bizonyítandó állítás $0 \equiv 0 \pmod N$ miatt magától értetődő.

Tegyük fel ezért, hogy $p \nmid x$, de $q \mid x$ (a fordított eset bizonyítása ezzel analóg).

Mivel $p$ prím és $p \nmid x$, ezért $(x, p) = 1$ és $\phi(p) = p - 1$. Így az Euler-Fermat tétel miatt $x^{p-1} \equiv 1 \pmod p$.

Ezt a $k \cdot (q - 1)$-edik hatványra emelve, majd mindkét oldalt $x$-szel szorozva – mivel $\phi(N) = (p-1)(q-1)$ – a következőt kapjuk: $x^{k \cdot \phi(N) + 1} \equiv x \pmod p$

Ugyanakkor $q \mid x$ miatt ugyanez a kongruencia nyilván modulo $q$ is fennáll (hiszen mindkét oldal $0 \pmod q$).

Ebből azonban következik, hogy a kongruencia modulo $N$ is teljesül, hiszen $p$ és $q$ különböző prímek, és mindketten osztják az $(x^{k \cdot \phi(N) + 1} - x)$ különbséget.

A bizonyítás ezzel kész. □

Példafeladat: Teljes RSA folyamat

1. Kulcsgenerálás

  • - Prímek: $p = 3, q = 11$
  • - Modulus: $N = p \cdot q = 33$
  • - Euler-függvény: $\phi(33) = (3-1)(11-1) = 20$
  • - Nyilvános kitevő: $c = 3$ (mivel $(3, 20)=1$)
  • - Titkos kitevő ($d$): $3d \equiv 1 \pmod{20} \implies d = 7$

2. Titkosítás (C)

Üzenetünk legyen $x = 5$.

$y = x^c \pmod N = 5^3 \pmod{33}$
$y = 125 \pmod{33} = \mathbf{26}$

3. Visszafejtés (D)

A fogadó megkapja az $y = 26$ értéket.

$x' = y^d \pmod N = 26^7 \pmod{33}$

Ismételt négyzeteléssel számolva:

  • $26^1 \equiv -7 \pmod{33}$
  • $26^2 \equiv (-7)^2 = 49 \equiv 16 \pmod{33}$
  • $26^4 \equiv 16^2 = 256 \equiv 25 \equiv -8 \pmod{33}$
  • $26^7 = 26^4 \cdot 26^2 \cdot 26^1 \equiv (-8) \cdot 16 \cdot (-7)$
  • $26^7 \equiv 128 \cdot 7 \equiv (-4) \cdot 7 = -28 \equiv \mathbf{5}$

EREDMÉNY: $x' = 5 = x$

A dekódolás sikeres volt!

4.7. Az RSA kriptorendszer

Kulcsgenerálás

  1. 1. Válasszunk két nagy prímet: $p, q$.
  2. 2. $N = p \cdot q$. (Ez a modulus).
  3. 3. $\varphi(N) = (p-1)(q-1)$.
  4. 4. Válasszunk egy $e$ kitevőt: $(e, \varphi(N)) = 1$.
  5. 5. Számoljuk ki $d$-t: $e \cdot d \equiv 1 \pmod{\varphi(N)}$.

Nyilvános kulcs: $(N, e)$, Titkos kulcs: $d$.

Műveletek

Kódolás (Üzenet $M$):

$C = M^e \pmod N$

Dekódolás (Kódolt $C$):

$M = C^d \pmod N$

RSA Szimulátor (Gyakorló modul)