MÁRTON Gyöngyvér

Vissza

10. labor

Válasszunk véletlenszerűen két, legalább 512 bites prímszámot, majd határozzuk meg az RSA publikus és privát kulcsokat. Írjuk ki külön állományba a publikus kulcs base64-es alakját, egy másikba a privát kulcs base64-es alakját. Vegyünk egy tetszőleges ASCII nyomtatható karaktereket tartalmazó szöveget és titkosítsuk valamely állományból beolvasott publikus kulccsal. A titkosított szöveget hexadecimális formában írassuk ki a képernyőre, majd fejtsük vissza a rejtjelezett szöveget.

Írjunk egy Python programot, amelyben az RSA digitális aláírás algoritmusait implementáljuk:
- egy menüpontban, kulcsgenerálás néven lehessen kigenerálni a p, q, e, d, n értékeket, majd külön állományba lementeni a publikus kulcs base64-es alakját, és egy másik állományba a privát kulcs base64-es alakját,
- egy másik menüpontban lehetőség legyen a fileba lementett privát kulcsot beolvasni és segítségével egy tetszőleges K értékre meghatározni az aláírás értékét, majd az értéket és az aláírás base64-es alakját kiírni egy állományba,
- egy harmadik menüpontban lehetőség legyen a publikus kulcsot, beolvasni egy állományból, továbbá egy másik állományból az érték, és az aláírás base64-es alakját beolvasni majd ellenőrizni az aláírást.
Ugyanaz a szöveg, háromszor volt rejtjelezve textbook RSA-val, ahol adottak az (3, n₁), (3, n₂), (3, n₃) nyilvános kulcsok. Az n₁, n₂, n₃ értékek a modE3.txt állomány első három sorában találhatóak, ilyen sorrendben. A megfelelő rejtjelezett szövegek az cryptE3_1, cryptE3_2, cryptE3_3 állományokban találhatóak. Határozzuk meg az eredeti szöveget.

Útmutatás: Olvassuk be a rejtjelezett szövegek bájtjait, alakítsuk át a bájtokból álló 256-os számrendszerbeli számokat 10-es számrendszerbe. Ezután alkalmazható a kínai maradéktétel, ugyanis feltételezve, hogy az eredeti szövegnek megfelelő szám a nr, és a rejtjelezett szövegeknek megfelelő számok a c₁, c₂, c₃ megállapítható:
x = nr^e mod n₁ → x = c₁ mod n₁
x = nr^e mod n₂ → x = c₂ mod n₂
x = nr^e mod n₃ → x = c₃ mod n₃

Ha meghatározzuk a baloldali egyenletrendszerből az x-et, akkor köbgyököt vonva visszanyerhető a nr, mert x = nr³ mod (n₁·n₂·n₃).

Az x köbgyökének a meghatározásához használhatjuk a következő kódsort:
import decimal
decimal.getcontext().prec = 100
tmp = math.ceil(pow(x, 1/decimal.Decimal(3)))

Írjunk Python programot, amely meghatározza a következő r egyenletből álló kongruencia-rendszer legkisebb megoldását, feltételezve, hogy az m1, m2,…, mr pozitív egész számok páronként relatív prímek.
x = a1 mod m1
x = a2 mod m2
...
x = ar mod mr

Az RSA-textbook kriptorendszer visszafejtésének időigényét gyorsítani lehet, ha alkalmazzuk a kínai maradéktételt. Írjunk Python programot, amelyben összehasonlítjuk a két visszafejtési algoritmus időigényét.

Írjunk függvényt, amely meghatározza két "nagy" szám: X, Y összegét. Feltételezzük, hogy a gépszó hosszúsága nem nagyobb mint, H és X, Y egyike sem nagyobb, mint M, ahol természetesen H jóval kisebb, mint M. Pédául ha H = 100, akkor M = 10⁶, egy lehetséges választás
Először kiválasztjuk az m₁, m₂,..., m_k értékeket, úgy hogy m₁ · m₂· ...· m_k>= M, és m₁, m₂, ..., m_k mindegyike kisebb legyen, mint H, és páronként relatív prímek legyenek, ahol az m₁, m₂,..., m_k értékeket választhajuk prímeknek is. Meghatározzuk a következő kongruenciákat:
x1 = X mod m₁, y1 = Y mod m₁
x2 = X mod m₂, y2 = Y mod m₂
...
xk = X mod m_k, yk = Y mod m_k

majd a Kínai maradéktétellel megoldjuk a következő rendszert, ahol a kapott z érték, az X és Y összegét fogja jelenteni:
z = x1 + y1 mod m₁,
z = x2 + y2 mod m₂,
...
z = xk + yk mod m_k,

Határozzuk meg abban a sajátos esetben is, a két "nagy" szám: X, Y összegét, ha m₁ = 2ⁱ¹-1, m₂ = 2ⁱ²-1,..., m_k = 2^ik-1, ahol k egy pozitív egész szám.