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
    PKB=( nb, eb ) 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" nb modulusánál.
  3. A titkosítást blokkonként az egyes már kódolt Mi számokon végrehajtja.
    Ci=( Mie , mod n )
  4. A titkosított üzenetet átküldi "B"-nek.

Visszafejtés:

  1. "B" kap egy C1 , C2 , …. üzenetet, ahol 0<= Ci<= nb.
  2. A visszafejtést a számsorozat Ci tagjain külön hajtja végre.
  3. "B" elvégzi a Db( C )= Db( Eb( M )  )=M visszafejtést, amely most a Mi=(Cid,mod n ) kifejezések kiszámítását jelenti. 
 
 
Copyright © 2004-2020 SafeSoft Kft. All Rights Reserved.