Az RSA titkosítási eljárás
[ Bevezető | Az eljárás leírása | RSA demo | Prímek előállítása ]

Az eljárás leírása

Az alábbiakban ismertetésre kerül az RSA eljárás. Az eljáráshoz szükséges algoritmusokat külön nem részletezzük, ám a megjelölt algoritmusra kattintva új ablak nyílik, és ki lehet próbálni annak működését.


  1. Generálni kell két nagy prímet:

    p1 és p2 (titkos)

    Fontos, hogy a prímek tényleg nagy számok legyenek, általában kb. 100 decimális számjegyből állnak. Annak eldöntése, hogy a generált számok valóban prímek-e, pontosan ugyanolyan nehéz feladat, mint az RSA titkosítás brute force-szal való feltörése, mert több, mint száz jegyű szám faktorizálása nagyon sokáig tart.
    Ezután elő kell állítani az

    n := p1 . p2 (nyilvános)

    illetve az

    m := (p1 - 1) . (p2 - 1)

    számokat.

  2. Generálni kell egy véletlen

    e (nyilvános)

    számot úgy, hogy m és e relatív prímek legyenek.
    Véletlen szám előállítására többféle módszer létezik, abban mind közös, hogy valamiféle zajt (a számítógép valamely hardverének zaját vagy az éterből, világűrből vett zajt), vagy a felhasználói interakció kiszámíthatatlanságát (véletlenszerűségét) veszi alapul.
    Annak eldöntése, hogy az m és az imént generált e szám relatív prímek-e, egyszerű feladat: a legnagyobb közös osztó az euklideszi algoritmus segítségével O(log(n)) lépésben meghatározható, s ha az 1, akkor relatív prímek.

  3. Meg kell határozni az e szám multiplikatív inverzét modulo m:

    d := e-1 (mod m) (titkos)

    azaz

    e . d = 1 (mod m)

    Az e szám inverzét, azaz a d számot az inverz euklideszi algoritmus segítségével határozzuk meg.

  4. Az információ, egy x szám (x < n) titkosítása ezután a következőképpen történik:

    y := xe (mod n)

    azaz a nagy számok hatványozása algoritmus segítségével.

  5. A titkosított információ megfejtéséhez ugyanezt a hatványozó algoritmust használhatjuk:

    x' := yd (mod n)

    és ideális esetben, tehát ha p1 és p2 valóban prímek voltak, e és m valóban relatív prímek, és x < n, akkor x' = x, vagyis visszakapjuk az eredeti információt.

Néhány megjegyzés:

<< Előző | Tartalom | Tovább >>
Az oldalt összeállította, a demo programot és a script-eket készítette: Barta Áron, 2004