Vissza

6. labor: az RSA rendszer


 Publikus kulcsú rendszerek

1. Válasszunk két, legalább 256 bites prímszámot, majd RSA-kulcsként alkalmazva őket titkosítsunk és fejtsünk vissza egy tetszőleges ASCII karaktereket tartalmazó szöveget. A szöveget generáljuk véletlenszerűen, hossza pedig akkor legyen, hogy a szövegnek megfelelő szám kisebb legyen, mint az RSA-modulus. Ugyanazt a szöveget titkosítsuk ötször RSA-val, majd RSA-OAEP-vel. A titkosított bájtszekvenciákat hexa formában írjuk ki a képernyőre.
Segéganyagok:

2. Egy titkosított szöveg RSA módszerrel volt rejtjelezve, ahol a titkosítást bájtok felett végezték. Határozzuk meg az eredeti szöveget, ha ismert az RSA modulus, az e = 65537, a modulus egyik osztója a keys.txt állományban található prímszámok közül az egyik szám, és az eredeti állomány mérete 44 bájt volt.

3. Ugyanaz a szöveg,  három különböző félnek volt RSA-val rejtjelezve elküldve, ahol adottak felek nyilvános kulcsai, illetve a rejtjelezett szövegek.

key1.txt            key2.txt            key3.txt
encrypt1.txt      encrypt2.txt     encrypt3.txt
Fejtsük meg a rejtjelezett szöveget, tudva, hogy a rejtjelezést az angol ábécé  26 betűje + a space (melynek kódja 26) felett végezték.
Útmutatás: alkalmazzuk a kínai maradéktételt, majd a köbgyököt meghatározó algoritmust.
x = nre mod n1, azaz x = c1 mod n1
x = nre mod n2, azaz x = c2 mod n2
x = nre mod n3, azaz x = c3 mod n3
Ha meghatároztuk a megfelelő x-et, akkor visszanyerhető a nr, az alapján, hogy x = nr3 mod(n1·n2·n3).
Plusz adatok

4. Az itt található titkosított szöveg, RSA módszerrel volt rejtjelezve, ahol a titkosítást az angol ábécé 26 betűje és a "space" felett végezték, azaz 27 jelet használtak. Határozzuk meg az eredeti szöveget, ha a nyilvános kulcs: (n = 117909607, e = 65537).

Megjegyzés: A titkosított szöveg minden betűjének feleltessük meg a megfelelő számkódot, (számkódtábla), ahol a space számkódja 26, majd rendre 6-6 számkódból, feltételezve, hogy ezek 27-es számrendszerbeli számjegyeket jelölnek, képezzünk egy 276 számrendszerbeli számot, ahol a 6 értékét: ceil(log 27 117909607)-1 képletből nyertük. Az így kapott számra alkalmazzuk a visszafejtési képletet, majd ezt alakítsuk vissza 27-es számrendszerbeli számjegyekké, úgy hogy minden nagyszámból pontosan 5 számjegyet (számkódot) állítsunk elő.

5. A titkosított file AES-128-CBC módszerrel volt rejtjelezve, ahol a titkosítást bájtok felett végeztük. Határozzuk meg az eredeti GIF filet, ha az AES kulcs titkosított értékét hexában itt találjuk. Az AES kulcsot RSA-OAEP-vel titkosítottuk, ahol az RSA-modulus decimális alakja itt található, az RSA-exponens e = 65537, az AES-nél használt IV hexa értéke, pedig: IV = 1abcdef234567890123456789abcdef0.
Útmutatás:

  • faktorizáljuk az n értékét Fermat módszerével, határozzuk meg a titkos kulcsot és ez alapján határozzik meg az AES kulcsot;
  • az itt található példaprogram RSA kulcsokat generál a Crypto++ segítségével, majd véletlenszerűen generál egy bájt szekvenciát, ezt titkosítja RSA_OAEP-vel, majd visszafejti.

6. Az RSA kriptorendszer visszafejtésének időigényét gyorsítani lehet, ha alkalmazzuk a kínai maradéktételt. Alkalmazzuk ezt a gyorsítási folyamatot az 1-es, vagy 2-es feladatnál: feltételezzük, hogy a nyilvános kulcs: (n, e), a titkos kulcs: (n, d), és n = p·q
legyenek:

dp = d mod (p-1)
dq = d mod (q-1)
 Mq úgy hogy q · Mq = 1 mod p
Mp úgy hogy p · Mp = 1 mod q
Ha nr az érték, melyet vissza kell fejteni, akkor a nrd mod n értéket megadja az x értéke, ahol
x = (Mq· q · xp + Mp· p · xq )mod n
xp = nrdpmod p
xq = nrdqmod q
Írjunk programot, melyben összehasonlítjuk a két visszafejtési algoritmus időigényét.

7. A titkosított file AES-128-CTR módszerrel volt rejtjelezve, ahol a titkosítást bájtok felett végeztük. Határozzuk meg az eredeti JPG filet, ha az AES kulcs titkosított értékét hexában itt találjuk. Az AES kulcs értékét RSA-OAEP-vel titkosítottuk, ahol az RSA-modulus decimális alakja itt található, az RSA-exponens e = 65537, az AES-nél használt IV hexa értéke, pedig: IV = 1abcdef234567890123456789abcdef0.
Útmutatás:

8. Ugyanaz a szöveg RSA módszerrel, kétszer volt rejtjelezve, ahol a titkosítást bájtok felett végezték. Határozzuk meg az eredeti szöveget, ha tudjuk, hogy a titkosítást különböző exponensekkel (legyenek ezek e és f), de ugyanazzal a modulussal (legyen ez n) végezték, ahol (e, f) = 1. A két rejtjelezett szövegnek megfelelő bináris állomány itt és itt található, a két kulcs, ahol az első érték mindkét esetben a modulus, pedig itt és itt.

Útmutatás:
  • (e, f) = 1, azaz e·x + f·y = 1
  • text mod n = texte·x + f·y mod n  = (text e)x· (text f)y = ctext1 x· ctext2 y, ahol text-nek ctext1 az egyik, ctext2 egy másik titkosított értéke
  • az x és y a kiterjesztett Euklideszi algoritmussal határozható meg: (XGCD),
  • a titkosított állomány bájtjaiból egyetlen nagy számot hozzunk létre