RSA (Rivest-Shamir-Adleman) ist ein weit verbreiteter Kryptosystem für öffentliche Schlüssel. Es basiert auf der praktischen Schwierigkeit, das Produkt zweier großer Primzahlen zu berücksichtigen. Hier ist eine Aufschlüsselung:
Wie RSA funktioniert:
1. Schlüsselgenerierung:
*Wählen Sie zwei unterschiedliche Primzahlen aus, *p *und *q *. Je größer diese sind, desto sicherer die Verschlüsselung.
* Berechnen Sie * n =p * q *. * n* ist der Modul.
* Berechnen Sie φ (n) =(p-1) (q-1). Dies ist die Totient -Funktion von Euler, die die Anzahl der Ganzzahlen darstellt, die weniger als *n *zu *n *sind.
* Wählen Sie eine Ganzzahl * E * (öffentlicher Exponent), so dass 1 <* e * <φ (n) und gcd (e, φ (n)) =1 (der größte gemeinsame Divisor ist 1; * E * und φ (n) sind Coprime). Eine gemeinsame Wahl ist 65537 (2
16
+ 1).
* Berechnen Sie * d * (privater Exponent), so dass * d * * e ≡ 1 (mod φ (n)). Dies bedeutet, dass * d * * * e * einen Rest von 1 hinterlässt, wenn er durch φ (n) geteilt wird. Dies erfolgt typischerweise unter Verwendung des erweiterten euklidischen Algorithmus.
2. öffentlicher Schlüssel: Der öffentliche Schlüssel ist das Paar (*n*,*e*). Dies wird öffentlich geteilt.
3. Privatschlüssel: Der private Schlüssel ist das Paar (*n*,*d*). Dies muss geheim gehalten werden.
4. Verschlüsselung: Um eine Nachricht zu verschlüsseln *m *(dargestellt als Zahl weniger als *n *):
* CipherText * c * =* m
e
*(mod *n *)
5. Entschlüsselung: Um den Chiffrikett zu entschlüsseln *C *:
* PlainText * m * =* c
d
*(mod *n *)
Warum es funktioniert: Euler's Theorem stellt fest, dass *a *und *n *Coprime sind, dann *a
φ (n)
≡ 1 (mod n)*. Die Auswahl von * d * und der modularen Arithmetik sorgen dafür, dass die Entschlüsselung die ursprüngliche Nachricht korrekt erholt. Das Brechen von RSA beruht auf Factoring *n *in *p *und *q *, was rechnerisch für ausreichend große Primzahlen rechnerisch ist.
RSA -Numerikale lösen:
Die Schwierigkeit, RSA -numerische Probleme zu lösen, hängt davon ab, welche Informationen angegeben werden. Hier finden Sie Beispiele für typische Probleme und wie man sie lösen:
Beispiel 1:Verschlüsselung
* Problem: Gegeben * p * =11, * q * =13, * e * =7 und meldung * m * =5, verschlüsseln Sie die Nachricht.
* Lösung:
1. Berechnen Sie * n * =* p * * * q * =11 * 13 =143
2. Berechnen Sie φ (n) =(11-1) (13-1) =120
3. Überprüfen Sie, ob GCD (7, 120) =1 (sie sind Coprime)
4. Encrypt:*C *=*m
e
*(mod *n *) =5
7
(Mod 143)
* 5
7
=78125
* 78125 ÷ 143 ≈ 546 mit einem Rest von 67
* Daher * c * =67
Beispiel 2:Entschlüsselung
* Problem: Gegeben * p * =11, * q * =3, * e * =7 und ciphertext * c * =10, entschlüsseln Sie den Ciphertext.
* Lösung:
1. Berechnen Sie * n * =* p * * * q * =11 * 3 =33
2. Berechnen Sie φ (n) =(11-1) (3-1) =20
3. Finden Sie * d *, so dass * d * * * e * ≡ 1 (mod φ (n)) Dies bedeutet 7 * * d * ≡ 1 (mod 20). Sie können dies mit dem erweiterten euklidischen Algorithmus oder durch Versuch und Irrtum lösen. * d * =3 funktioniert, weil (7 * 3) =21 ≡ 1 (mod 20).
4. Entschlüsselt:*m *=*c
d
*(mod *n *) =10
3
(Mod 33)
* 10
3
=1000
* 1000 ÷ 33 ≈ 30 mit einem Rest von 10
* Daher * m * =10
Beispiel 3:Finden D (privater Exponent)
Das Finden von 'D' erfordert oft den erweiterten euklidischen Algorithmus, der hier außerhalb des Rahmens einer einfachen Erklärung liegt. Bei kleineren Zahlen können jedoch Versuch und Irrtum funktionieren. Sie suchen nach einer Zahl 'D', die die Kongruenz erfüllt * d * * e ≡ 1 (mod φ (n)).
Wichtige Überlegungen:
* große Zahlen: RSA in der realen Welt verwendet extrem große Primzahlen (Hunderte oder Tausende von Bits). Manuelle Berechnungen sind unmöglich; Spezielle Software ist erforderlich.
* modulare Arithmetik: Das Verständnis der modularen Arithmetik ist entscheidend für die Arbeit mit RSA. Viele Taschenrechner und Programmiersprachen haben integrierte Funktionen für die modulare Exponentiation.
* Sicherheit: Die Sicherheit von RSA hängt ausschließlich von der Schwierigkeit ab, große Zahlen zu berücksichtigen. Mit zunehmender Rechenleistung muss die Größe der verwendeten Primzahlen ebenfalls erhöhen, um die Sicherheit aufrechtzuerhalten.
Diese Beispiele veranschaulichen die Grundprinzipien. Für fortgeschrittenere Probleme müssen Sie wahrscheinlich Berechnungstools und ein tieferes Verständnis der Zahlentheorie verwenden.
