RSA (Rivest-Shamir-Adleman) är ett allmänt använda offentligt nyckelkryptosystem. Det är baserat på den praktiska svårigheten att ta upp produkten från två stora primtal. Här är en uppdelning:
Hur RSA fungerar:
1. Nyckelgenerering:
*Välj två distinkta primtal, *P *och *Q *. Ju större dessa är, desto säkrare krypteringen.
* Beräkna * n =p * q *. * n* är modulen.
* Beräkna φ (n) =(p-1) (Q-1). Detta är Eulers totientfunktion, som representerar antalet heltal mindre än *n *som är relativt prima för *n *.
* Välj ett heltal * e * (offentlig exponent) så att 1 <* e * <φ (n) och gcd (e, φ (n)) =1 (största gemensamma divisor är 1; * e * och φ (n) är coprime). Ett vanligt val är 65537 (2
16
+ 1).
* Beräkna * d * (privat exponent) så att * d * * e ≡ 1 (mod φ (n)). Detta betyder * d * * * e * lämnar en resten av 1 när den är dividerad med φ (n). Detta görs vanligtvis med den utökade euklidiska algoritmen.
2. offentlig nyckel: Den offentliga nyckeln är paret (*n*,*e*). Detta delas offentligt.
3. Privat nyckel: Den privata nyckeln är paret (*n*,*d*). Detta måste hållas hemligt.
4. Kryptering: För att kryptera ett meddelande *M *(representerat som ett nummer mindre än *n *):
* Chiffertext * c * =* m
e
*(mod *n *)
5. dekryptering: För att dekryptera chiffertexten *C *:
* PlainText * m * =* c
d
*(mod *n *)
Varför det fungerar: Eulers sats säger att om *a *och *n *är coprime, så *a
φ (n)
≡ 1 (mod n)*. Valet av * d * och den modulära aritmetiken säkerställer att dekryptering korrekt återvinner det ursprungliga meddelandet. Att bryta RSA förlitar sig på factoring *n *i *p *och *q *, vilket är beräkningsmässigt omöjligt för tillräckligt stora primes.
Lösning av RSA -numeriska:
Svårigheten att lösa RSA -numeriska problem beror på vilken information som ges. Här är exempel på typiska problem och hur man löser dem:
Exempel 1:Kryptering
* Problem: Givet * p * =11, * q * =13, * e * =7, och meddelande * m * =5, kryptera meddelandet.
* Lösning:
1. Beräkna * n * =* p * * * q * =11 * 13 =143
2. Beräkna φ (n) =(11-1) (13-1) =120
3. Kontrollera att GCD (7, 120) =1 (de är coprime)
4. Kryptering:*C *=*M
e
*(mod *n *) =5
7
(mod 143)
* 5
7
=78125
* 78125 ÷ 143 ≈ 546 med en återstående av 67
* Därför * C * =67
Exempel 2:dekryptering
* Problem: Givet * p * =11, * q * =3, * e * =7, och chiffertext * c * =10, dekryptera chiffertexten.
* Lösning:
1. Beräkna * n * =* p * * * q * =11 * 3 =33
2. Beräkna φ (n) =(11-1) (3-1) =20
3. Hitta * d * så att * d * * * e * ≡ 1 (mod φ (n)) Detta betyder 7 * * d * ≡ 1 (mod 20). Du kan lösa detta med den utökade euklidiska algoritmen eller genom test och fel. * d * =3 fungerar eftersom (7 * 3) =21 ≡ 1 (mod 20).
4. Dekryptera:*m *=*c
d
*(mod *n *) =10
3
(mod 33)
* 10
3
=1000
* 1000 ÷ 33 ≈ 30 med en resten av 10
* Därför * m * =10
Exempel 3:Hitta D (privat exponent)
Att hitta 'D' kräver ofta den utökade euklidiska algoritmen, som ligger utanför räckvidden för en enkel förklaring här. För mindre antal kan emellertid prövning och fel fungera. Du letar efter ett nummer 'd' som uppfyller kongruensen * d * * e ≡ 1 (mod φ (n)).
Viktiga överväganden:
* Stora antal: Verklig RSA använder extremt stora primtal (hundratals eller tusentals bitar). Manuella beräkningar är omöjliga; Specialiserad programvara krävs.
* Modular Aritmetic: Att förstå modulär aritmetik är avgörande för att arbeta med RSA. Många kalkylatorer och programmeringsspråk har inbyggda funktioner för modulär exponentiering.
* Säkerhet: Säkerheten för RSA beror helt på svårigheten att ta upp stora antal. När datorkraften ökar måste storleken på de använda primarna också öka för att upprätthålla säkerheten.
Dessa exempel illustrerar de grundläggande principerna. För mer avancerade problem kommer du sannolikt att behöva använda beräkningsverktyg och en djupare förståelse av antaleteorin.
