RSA algoritmus példaprogram kis számokkal, demonstrációs céllal?

A következő példa egy olyan Python program, amelyben kétjegyű számokat használ:

# RSA demonstration with small numbers

# Choose two prime numbers, p and q

p = 7

q = 11

# Compute n = pq

n = p * q

# Compute Euler's totient function of n

phi = (p-1) * (q-1)

# Choose an encryption key e, 1 < e < phi and gcd(e,phi) = 1

e = 3

# Compute the decryption key d, 1 < d < phi and ed = 1 mod phi

d = 7

# Public key (n,e)

public_key = (n, e)

# Private key (n,d)

private_key = (n, d)

# Message to encrypt

message = 8

# Encryption: ciphertext = message^e mod n

ciphertext = (message ** e) % n

# Decryption: message = ciphertext^d mod n

decrypted_message = (ciphertext ** d) % n

print("Original message: ", message)

print("Encrypted message: ", ciphertext)

print("Decrypted message: ", decrypted_message)

A fenti példában használt számok kicsik, ezért a valós alkalmazásokban sokkal nagyobb számokat kell használni a biztonságos titkosítás érdekében.

A fenti példa nem jó.

p=7 és q=11 prímek elvileg se lehetnek.

Ehhez nincs d érték melyre a d*e ≡ 1 (mod phi) kongurencia teljesüljön.

Így mivel hibás a d ami a titkos kulcs kitevője, sok értékre rosszul fog működni.

Csak egy példát írok:

Original message: 3

Encrypted message: 27

Decrypted message: 69

Jó példa:

p = 11

q = 17

d = 107

Ami matematikailag nem hibás, de szúrja a szememet:

ciphertext = (message ** e) % n helyett ciphertext = pow(message,e,n)

decrypted_message = (ciphertext ** d) % n helyett decrypted_message = pow(ciphertext,d,n)

Szúra a szememet mivel semmiből nem áll így átírni és túl pazarló. Egy optimalizáció a moduláris hatványozás, csak képzeld el hogy ha a kitevő egy száz jegyű szám (gyakorlatba ennél is nagyobb) nincs az a gép ami elvégzi azon hatványozást (nincs annyi atom se a belátható Univerzumban mint ahány jegyű szám a hatványozás erdeménye, nem is arról beszéltem amekkora értéket reprezentál az a szám, ekkora számnak kell venni a modulo n-jét, sokkal egyszerűbb eleve modulárisan hatványozni)

A python a pow(alap,kitevő,modulo) optimalizáltan végzi el a moduláris hatványozást.

A moduláris hatványozás optimalizálva gyakorlatilag a gyorshatványozás úgy módosítva, hogy mindig a modulo n-jét veszed, azaz n maradékosztályába számolod. Egy hatványozás modulo n eredménye ugynaz ha iteratívan végzed el szorzásonként minden szorzás után veszed modulo n-jét. A gyors hatványozást úgy kell elvégezni, hogy mindig négyzetremelést csinálsz (így exponenciálisan csökkentve a konkrét szorzótényezőket).A kitevőnek a bináris reprezentációja szerint ha 1 érték van az aktuális helyen akkor kerül bele a szorzatba. A gyors moduláris hatványozás pedig ugyanez csak mindig veszed a modulo n-jét, ez kerül a szorazba, de a python ezt megcsinálja, ha úgy használod a pow függvényt.

"Ahhoz, hogy üzenetként háromjegyű számokat is meg lehessen adni, hány jegyű prímszámokat kell választani?"

Nyersen használva az rsa-t, egy rsa-val n különböző adatot tudsz titkosítani. Vagyis az kell hogy n-be azaz p*q-ba beleférjen, triviálisan n legalább 1000 legyen, így a négyzetgyök 1000 ~ 31.62, legalább ennyi legyen a prímek értéke, de úgy hogy legyen hozzá d érték is. Azaz a fentebb írt lineáris kongurenciát elégítse is ki.

- Azért írtam, hogy egy rsa-val, mert gyakorlatba úgy szokott működni, hogyha nem fér bele az üzenet egyszerre akkor feldarabolják az üzenetet és minden darabot titkosítanak külön-külön.

- (Nyilván ha nem szám titkosítása a cél, az adott üzenetet előtte számmá vagy több számmá alakítják.) Azért írtam, hogy nyersen használva az rsa-t, mert nyersen nem ajánlott csak oktatási célból bemutatásra, azért hogy a megértést könnyítse, hogy ne vesszen el a részletekbe a tanuló. Gyakorlatban nem a nyers üzenetet titkosítják, hanem előtte kriptográfi kitöltést raknak rá (ez a padding, pl. PKCS 7 padding). Ez azért kell, mert a várható üzenet gyakran nem lehet sokféle. Például sok üzenet előre látható módon úgy végződik hogy Tisztelettel. Ha nem lenne paddig akkor a nyilvános kulcsával előre kiszámítva a gyakori üzeneteket könnnyen összeegyeztethető lenne az előre kiszámítottakkal, a privát kulcs sem kell hozzá.

A _ karakterek csak a szóközöket jelentik amit a gyk lenyelne:

def mod_inverse(a, m):

__for x in range(1, m):

____if (a * x) % m == 1:

______return x

__raise Exception("Nincs megoldas")

A d érték kiszámítására mutatom:

d = mod_inverse(e,phi)

Gyakorlatban nagy számokra használhatatlanul lassú optimalizálatlan lenne a mod_inverse függvény. Ezt csak oktatási célra mutatom, mivel faék egyszerű ez a kód.

Egyébként gyakorlatilag az sem triviális hogy hogyan válasszák meg a prímeket, nem csak random nagy prímeket választanak, ennél komplikáltabb, úgynevezett erős prímeket válaszanak, hogy a lehető legnehezebb legyen törni, de ezek már a finom részletek. Az alap részének megértéséhez ez nem tartozik.

"hanem előtte kriptográfi kitöltést raknak rá"

jav.:

hanem előtte kriptográfiai kitöltést raknak rá