Matematikai háttér

1978-ban javasolt R. Rivest, A. Shamir és L. Adleman egy nyilvános kulcsú algoritmust, amelynek biztonsága a faktorizáció problémáján alapul. Az eljárás egyaránt használható titkos üzenetváltásra és digitális aláírás készítésére. Az algoritmust a szerzők neve alapján RSA-nak nevezték. Ha az RSA paramétereit jól választják meg, akkor a különféle feltörési kísérletek eredménytelenek maradnak. Az algoritmus működését a következő részekre lehet bontani:

Kulcsgenerálás:

1. a résztvevők választanak maguknak két kellően nagy ( legalább 100 decimális ) p és q prímszámot.
2. Kiszámítják az n=p*q modulust, és a j( n )=( p-1 )( q-1 ) számot.
3. Választ véletlenszerűen egy e számot, amely relatív prim a p-1-hez és q-1-hez is. Tehát az ( e, p-1 )=( e, q-1 )=1. Emiatt ( e, j( n ) )=1 is igaz.
4. Meghatározza az e szám inverzét modulo j( n ),  azaz keres egy olyan d számot, amelyre fennáll az e*dº1 ( mod j( n ) ) és 1<d<j( n ).
5. A p, q és j( n ) számokat megsemmisíti.

Titkosítás:

1. Ha "A" akar "B" számára üzenetet küldeni, akkor kiveszi "B" nyilvános
   PK_B=( n_b, e_b ) kulcsát a nyilvántartásból.
2. "A" blokkokra vágja átküldendő üzenetét, ügyelve arra, hogy a blokkok hossza ne legyen nagyobb "B" n_b modulusánál.
3. A titkosítást blokkonként az egyes már kódolt M_i számokon végrehajtja.
   C_i=( M_i^e , mod n )
4. A titkosított üzenetet átküldi "B"-nek.

Visszafejtés:

1. "B" kap egy C₁ , C₂ , …. üzenetet, ahol 0<= C_i<= n_b.
2. A visszafejtést a számsorozat C_i tagjain külön hajtja végre.
3. "B" elvégzi a D_b( C )= D_b( E_b( M )  )=M visszafejtést, amely most a M_i=(C_i^d,mod n ) kifejezések kiszámítását jelenti.