Čo je šifrovanie RSA a ako vyriešiť svoje číselné čísla?

RSA (RIVEST-SHAMIR-ADLEMAN) je široko používaný kryptosystém verejného kľúču. Je založená na praktických ťažkostiach s faktorovaním produktu dvoch veľkých prvočísiel. Tu je porucha:

Ako RSA funguje:

1. Generovanie kľúčov:

*Vyberte dve odlišné prvočíselné čísla, *p *a *q *. Čím väčšie sú, tým bezpečnejšie šifrovanie.

* Vypočítajte * n =p * q *. * n* je modul.

* Vypočítajte φ (n) =(p-1) (q-1). Toto je Eulerovo totienková funkcia, ktorá predstavuje počet celých čísel menších ako *n *, ktoré sú relatívne hlavné k *n *.

* Vyberte celé číslo * E * (verejný exponent) tak, že 1 <* e * <φ (n) a gcd (e, φ (n)) =1 (najväčší spoločný deliteľ je 1; * e * a φ (n) coprime). Bežná voľba je 65537 (2 ^{16 + 1).}

* Vypočítajte * d * (súkromný exponent) tak, že * d * * e ≡ 1 (mod φ (n)). To znamená * d * * * e * opúšťa zvyšok 1, keď je vydelený φ (n). Toto sa zvyčajne robí pomocou rozšíreného euklidovského algoritmu.

2. verejný kľúč: Verejný kľúč je pár (*n*,*e*). Toto je zdieľané verejne.

3. Súkromný kľúč: Súkromný kľúč je pár (*n*,*d*). Toto musí byť udržiavané v tajnosti.

4. Šifrovanie: Na šifrovanie správy *m *(reprezentované ako číslo menej ako *n *):

* CipherText * C * =* M e *(mod *n *)

5. Dešifrovanie: Na dešifrovanie CipherText *C *:

In *(mod *n *)

Prečo to funguje: Eulerova veta uvádza, že ak *a *a *n *sú coprime, potom *a φ (n) ≡ 1 (mod n)*. Výber * D * a modulárnej aritmetiky zabezpečí, že dešifrovanie správne obnoví pôvodnú správu. Prerušenie RSA sa spolieha na faktoring *n *do *p *a *q *, čo je výpočtovo nemožné pre dostatočne veľké prvočísla.

Riešenie RSA Numericals:

Obtiažnosť riešenia číselných problémov RSA závisí od toho, aké informácie sú uvedené. Tu sú príklady typických problémov a ako ich vyriešiť:

Príklad 1:Šifrovanie

* Problém: Vzhľadom na * p * =11, * q * =13, * e * =7 a správa * m * =5, šifrujte správu.

* Riešenie:

1. Vypočítajte * n * =* p * * * q * =11 * 13 =143

2. Vypočítajte φ (n) =(11-1) (13-1) =120

3. Skontrolujte, či GCD (7, 120) =1 (sú coprime)

4. Encrypt:*c *=*m

e *(mod *n *) =5

7 (Mod 143)

* 5 7 =78125

* 78125 ÷ 143 ≈ 546 so zvyškom 67

* Preto, * c * =67

Príklad 2:dešifrovanie

* Problém: Vzhľadom na * p * =11, * q * =3, * e * =7 a CipherText * c * =10, dešifrujte CipherText.

* Riešenie:

1. Vypočítajte * n * =* p * * * q * =11 * 3 =33

2. Vypočítajte φ (n) =(11-1) (3-1) =20

3. Nájdite * d * tak, že * d * * * E * ≡ 1 (mod φ (n)) to znamená 7 * * d * ≡ 1 (mod 20). Môžete to vyriešiť pomocou rozšíreného euklidovského algoritmu alebo pokusom a omylom. * d * =3 funguje, pretože (7 * 3) =21 ≡ 1 (Mod 20).

4. Dešipovať:*m *=*c

d *(mod *n *) =10

3 (Mod 33)

* 10 3

=1000

* 1000 ÷ 33 ≈ 30 so zvyškom 10

* Preto, * m * =10

Príklad 3:Nájdenie D (súkromný exponent)

Nájdenie „D“ si často vyžaduje rozšírený euklidovský algoritmus, ktorý presahuje rámec jednoduchého vysvetlenia. Pre menšie čísla však môžu fungovať pokus a chyby. Hľadáte číslo 'd', ktoré spĺňa zhodu * d * * e ≡ 1 (mod φ (n)).

Dôležité úvahy:

* veľké čísla: RSA v reálnom svete používa extrémne veľké čísla primárne (stovky alebo tisíce bitov). Manuálne výpočty sú nemožné; Vyžaduje sa špecializovaný softvér.

* modulárna aritmetika: Pochopenie modulárnej aritmetiky je rozhodujúce pre prácu s RSA. Mnoho kalkulačiek a programovacích jazykov má vstavané funkcie pre modulárnu exponenciáciu.

* Zabezpečenie: Bezpečnosť RSA závisí výlučne od obtiažnosti veľkého počtu. S rastúcim výpočtovým výkonom sa musí zvýšiť aj veľkosť použitých prvočísiel.

Tieto príklady ilustrujú základné princípy. Pre pokročilejšie problémy budete pravdepodobne musieť používať výpočtové nástroje a hlbšie pochopenie teórie čísel.

• Predchádzajúca strana: Aký význam má šifrovanie bitky? 
• Ďalšia strana: Chcem resetovať heslá 100 používateľov, ako sa vám to páči?