​

PROJEKT 8: KAPITEL EINS: DIE ILLUSION DER WIRKLICHKEIT.  

​

​

​

RSA ist ein Algorithmus , der von modernen Computern zum Ver- und Entschlüsseln von Nachrichten verwendet wird. Es ist ein asymmetrischer kryptographischer Algorithmus. Asymmetrisch bedeutet, dass es zwei unterschiedliche Schlüssel gibt. Dies wird auch als Public-Key-Kryptografie bezeichnet, da einer der Schlüssel jedem gegeben werden kann. Der andere Schlüssel muss geheim gehalten werden. Der Algorithmus basiert auf der Tatsache, dass es schwierig ist, die Faktoren einer großen zusammengesetzten Zahl zu finden: Wenn die Faktoren Primzahlen sind, wird das Problem als Primfaktorzerlegung bezeichnet. Es ist auch ein Generator für Schlüsselpaare (öffentlicher und privater Schlüssel).

​

​

​

• DIE NERD-BOX

• Kryptonisch sicherer

​

• Verschlüsselung Ihres Systems

• Entschlüsseln Ihres Systems

​

• Polsterung des NERD

• NERD unterschreiben

​

• Ich liebe den NERD

• xBORDER Cloud-X

​

​

Betrieb

RSA beinhaltet einen öffentlichen Schlüssel und einen privaten Schlüssel. Der öffentliche Schlüssel kann jedem bekannt sein – er wird verwendet, um Nachrichten zu verschlüsseln. Mit dem öffentlichen Schlüssel verschlüsselte Nachrichten können nur mit dem privaten Schlüssel entschlüsselt werden. Die Schlüssel für den RSA-Algorithmus werden folgendermaßen generiert:

​

1. Wähle zwei verschiedene große zufällige Primzahlen p {\displaystyle p\,} und q {\displaystyle q\,}

2. Berechne n = pq {\displaystyle n=pq\,}

3. n {\displaystyle n\,} ist der Modulus für den öffentlichen Schlüssel und die privaten Schlüssel

4. Berechnen Sie den Totienten : ϕ ( n ) = ( p − 1 ) ( q − 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,} .

5. Wähle eine ganze Zahl e {\displaystyle e\,} so dass 1 < e {\displaystyle e\,} < ϕ ( n ) {\displaystyle \phi (n)\,} und e {\displaystyle e\,} ist teilerfremd zu ϕ ( n ) {\displaystyle \phi (n)\,} dh: e {\displaystyle e\,} und ϕ ( n ) {\displaystyle \phi (n)\,} teilen sich keine anderen Faktoren als 1; ggT ( e {\displaystyle e\,} , ϕ ( n ) {\displaystyle \phi (n)\,} ) = 1.

   • e {\displaystyle e\,} wird als Exponent des öffentlichen Schlüssels freigegeben

6. Berechnen Sie d {\displaystyle d\,}, um die Kongruenzbeziehung zu erfüllen de ≡ 1 ( mod ϕ ( n ) ) {\displaystyle de\equiv 1{\pmod {\phi (n)}}\,} dh: de = 1 + x ϕ ( n ) {\displaystyle de=1+x\phi (n)\,} für eine ganze Zahl x {\displaystyle x\,} . (Einfach gesagt  : Berechnen Sie d = ( 1 + x ϕ ( n ) ) / e {\displaystyle d=(1+x\phi (n))/e\,} als ganze Zahl)

   • d {\displaystyle d\,} wird als Exponent des privaten Schlüssels beibehalten

Hinweise zu den obigen Schritten:

• Schritt 1: Zahlen können probabilistisch auf Primzahl getestet werden.

• ​

• Schritt 3: in PKCS#1 geändert  ( en ) v2.0 bis λ ( n ) = lcm ( p − 1 , q − 1 ) {\displaystyle \lambda (n)={\rm {lcm}}(p-1,q-1)\,} statt ϕ ( n ) = ( p − 1 ) ( q − 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,} .

• Schritt 4: Eine beliebte Wahl für die öffentlichen Exponenten ist e {\displaystyle e\,} = 216 + 1 = 65537. Einige Anwendungen wählen stattdessen kleinere Werte wie e {\displaystyle e\,} = 3, 5 oder 35. Dies geschieht, um die Verschlüsselung und Signaturüberprüfung auf kleinen Geräten wie Smartcards zu beschleunigen, aber kleine öffentliche Exponenten können zu größeren Sicherheitsrisiken führen.

• Die Schritte 4 und 5 können mit dem erweiterten euklidischen Algorithmus durchgeführt werden  ( de ); siehe modulare Arithmetik .

Der öffentliche Schlüssel besteht aus dem Modulus n {\displaystyle n\,} und dem öffentlichen (oder Verschlüsselungs-)Exponenten e {\displaystyle e\,} .
Der private Schlüssel besteht aus p, q und dem privaten (oder Entschlüsselungs-) Exponenten d {\displaystyle d\,}, der geheim gehalten werden muss.

• Aus Effizienzgründen kann eine andere Form des privaten Schlüssels gespeichert werden:

  • p {\displaystyle p\,} und q {\displaystyle q\,} : die Primzahlen aus der Schlüsselgenerierung,

  • d mod ( p − 1 ) {\displaystyle d\mod (p-1)\,} und d mod ( q − 1 ) {\displaystyle d\mod (q-1)\,} : oft dmp1 und dmq1 genannt.

  • q − 1 mod ( p ) {\displaystyle q^{-1}\mod (p)\,} : oft iqmp genannt

• Alle Teile des privaten Schlüssels müssen in dieser Form geheim gehalten werden. p {\displaystyle p\,} und q {\displaystyle q\,} sind empfindlich, da sie die Faktoren von n {\displaystyle n\,} sind und die Berechnung von d {\displaystyle d\,} bei gegebenem e {\ Anzeigestil e\,} . Wenn p {\displaystyle p\,} und q {\displaystyle q\,} nicht in dieser Form des privaten Schlüssels gespeichert werden, werden sie zusammen mit anderen Zwischenwerten aus der Schlüsselgenerierung sicher gelöscht.

• Obwohl diese Form eine schnellere Entschlüsselung und Signierung durch Verwendung des Chinese Remainder Theorem (CRT) ermöglicht, ist sie erheblich weniger sicher, da sie Seitenkanalangriffe ermöglicht  ( de ). Dies ist ein besonderes Problem, wenn es auf Chipkarten implementiert wird, die am meisten von der verbesserten Effizienz profitieren. (Beginne mit y = xe ( mod n ) {\displaystyle y=x^{e}{\pmod {n}}} und lass die Karte das entschlüsseln. Also berechnet sie yd ( mod p ) {\displaystyle y^{d }{\pmod {p}}} oder yd ( mod q ) {\displaystyle y^{d}{\pmod {q}}} deren Ergebnisse einen Wert z {\displaystyle z} ergeben. Induzieren Sie nun einen Fehler in einem der Berechnungen. Dann ergibt ggT ( z − x , n ) {\displaystyle \gcd(zx,n)} p {\displaystyle p} oder q {\displaystyle q} .)

Nachricht verschlüsseln

Alice gibt Bob ihren öffentlichen Schlüssel ( n {\displaystyle n\,} & e {\displaystyle e\,} ) und hält ihren privaten Schlüssel geheim. Bob möchte Nachricht M an Alice senden.

Zuerst wandelt er M in eine Zahl um, die kleiner ist als n {\displaystyle n}, indem er ein vereinbartes umkehrbares Protokoll verwendet, das als Padding-Schema bekannt ist. Er berechnet dann den Geheimtext c {\displaystyle c\,} entsprechend:

c = ich mod n {\displaystyle c=m^{e}\mod {n}}

Das geht schnell mit der Methode der Potenzierung durch Quadrierung . Bob sendet dann c {\displaystyle c\,} an Alice.

Nachricht entschlüsseln

Alice kann m {\displaystyle m\,} aus c {\displaystyle c\,} wiederherstellen, indem sie ihren privaten Schlüssel d {\displaystyle d\,} im folgenden Verfahren verwendet:

m = cd mod n {\displaystyle m=c^{d}{\bmod {n}}}

Bei gegebenem m {\displaystyle m\,} kann sie die ursprünglichen unterschiedlichen Primzahlen wiederherstellen, indem sie den chinesischen Restsatz auf diese beiden Kongruenzergebnisse anwendet

med ≡ m mod pq {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Daher,

cd ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Ein funktionierendes Beispiel

Hier ist ein Beispiel für die RSA-Verschlüsselung und -Entschlüsselung. Die hier verwendeten Parameter sind künstlich klein, aber Sie können OpenSSL auch verwenden, um ein echtes Schlüsselpaar zu generieren und zu untersuchen .

1. Wähle zwei zufällige Primzahlen.

2.   : p = 61 {\displaystyle p=61} und q = 53 ; {\displaystyle q=53;} Berechne n = pq {\displaystyle n=pq\,}

3.   : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}

4. Berechnen Sie den Totienten ϕ ( n ) = ( p − 1 ) ( q − 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,}

5.   : ϕ ( n ) = ( 61 − 1 ) ( 53 − 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}

6. Wähle e > 1 {\displaystyle e>1} teilerfremd zu 3120

7.   : e = 17 {\displaystyle e=17}

8. Wähle d {\displaystyle d\,}, um de mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,} zu erfüllen

9.   : d = 2753 {\displaystyle d=2753}

10.   : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

Der öffentliche Schlüssel ist ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Für eine aufgefüllte Nachricht m {\displaystyle m\,} wird die Verschlüsselungsfunktion c = me mod n {\displaystyle c=m^{e}{\bmod {n}}} zu:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,}

Der private Schlüssel ist ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Die Entschlüsselungsfunktion m = cd mod n {\displaystyle m=c^{d}{\bmod {n}}} wird zu:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,}

Um beispielsweise m = 123 {\displaystyle m=123} zu verschlüsseln, berechnen wir

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}

Um c = 855 {\displaystyle c=855} zu entschlüsseln, berechnen wir

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Diese beiden Berechnungen können effizient unter Verwendung des Square-and-Multiply-Algorithmus zur modularen Potenzierung berechnet werden  ( de ).

Ableitung der RSA-Gleichung aus dem Satz von Euler

RSA kann leicht unter Verwendung des Satzes von Euler und der Totient-Funktion von Euler abgeleitet werden.

Beginnend mit dem Satz von Euler,

m φ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\varphi (n)}\equiv 1{\pmod {n}}}

Unter Verwendung der modularen Arithmetik kann die Gleichung umgeschrieben werden als

Multiplizieren Sie beide Seiten mit m

m ≡ m φ ( n ) + 1 ( mod n ) {\displaystyle m\equiv m^{\varphi (n)+1}{\pmod {n}}}

Eulers Totient-Funktion hat die Eigenschaft für einige Werte p und q,

φ ( p × q ) = φ ( p ) × φ ( q ) {\displaystyle \varphi (p\times q)=\varphi (p)\times \varphi (q)}

Daher kann die Gleichung umgeschrieben werden als

m ≡ m φ ( p × q ) + 1 ( mod p × q ) {\displaystyle m\equiv m^{\varphi (p\times q)+1}{\pmod {p\times q}}}

Außerdem gilt für alle ganzen Zahlen k noch folgende Beziehung:

m ≡ mk × φ ( p × q ) + 1 ( mod p × q ) {\displaystyle m\equiv m^{k\times \varphi (p\times q)+1}{\pmod {p\times q} }}

Der Wert d wird aus der folgenden Gleichung abgeleitet, wobei e eine große Primzahl ist und für einige k so, dass d eine ganze Zahl ist:

d = k × φ ( p × q ) + 1 e {\displaystyle d={k\times {\varphi (p\times q)+1} \over {e}}}

Und nach Exponentenregeln gilt die folgende Aussage:

m = mek × φ ( p × q ) + 1 e {\displaystyle m=m^{e^{k\times {\varphi (p\times q)+1} \over {e}}}}

Da sich die e aufheben. Also beim Verschlüsseln des Geheimtextes m,

c ≡ ich ( mod p × q ) {\displaystyle c\equiv m^{e}{\pmod {p\times q}}}

Der ursprüngliche Wert von m kann von c abgeleitet werden, indem c auf d erhöht wird.

m ≡ cd ( mod p × q ) ≡ med ( mod p × q ) ≡ mek × φ ( p × q ) + 1 e ( mod p × q ) {\displaystyle m\equiv c^{d}{\pmod { p\times q}}\equiv m^{e^{d}}{\pmod {p\times q}}\equiv m^{e^{k\times {\varphi (p\times q)+1} \over {e}}}{\pmod {p\times q}}}

Die Gleichung zeigt die Äquivalenz gilt und den Fortschritt

Polsterschemata

In der Praxis muss RSA mit einem Padding-Schema kombiniert werden, damit keine Werte von M zu unsicheren Geheimtexten führen. Bei Verwendung von RSA ohne Polsterung können einige Probleme auftreten:

• Die Werte m = 0 oder m = 1 erzeugen aufgrund der Potenzierungseigenschaften immer Chiffretexte gleich 0 bzw. 1.

• Beim Verschlüsseln mit kleinen Verschlüsselungsexponenten (z. B. e = 3) und kleinen Werten von m kann das (nicht-modulare) Ergebnis von me {\displaystyle m^{e}} strikt kleiner als der Modulus n sein. In diesem Fall können Chiffretexte leicht entschlüsselt werden, indem die eth-Wurzel des Chiffretexts ohne Rücksicht auf den Modul genommen wird.

• Die RSA-Verschlüsselung ist ein deterministischer Verschlüsselungsalgorithmus . Es hat keine Zufallskomponente. Daher kann ein Angreifer erfolgreich einen ausgewählten Klartextangriff gegen das Kryptosystem starten. Sie können ein Wörterbuch erstellen , indem sie wahrscheinliche Klartexte unter dem öffentlichen Schlüssel verschlüsseln und die resultierenden Geheimtexte speichern. Der Angreifer kann dann den Kommunikationskanal beobachten. Sobald sie Chiffretexte sehen, die mit denen in ihrem Wörterbuch übereinstimmen, können die Angreifer dieses Wörterbuch verwenden, um den Inhalt der Nachricht zu erfahren.

In der Praxis können die ersten beiden Probleme auftreten, wenn kurze ASCII- Nachrichten gesendet werden. In solchen Nachrichten kann m die Verkettung eines oder mehrerer ASCII-codierter Zeichen sein. Eine Nachricht, die aus einem einzelnen ASCII-NUL-Zeichen besteht (dessen numerischer Wert 0 ist), würde als m = 0 codiert werden, was einen Chiffretext von 0 erzeugt, unabhängig davon, welche Werte von e und N verwendet werden. Ebenso würde ein einzelner ASCII-SOH (dessen numerischer Wert 1 ist) immer einen Chiffretext von 1 erzeugen. Für Systeme, die herkömmlicherweise kleine Werte von e verwenden, wie z Das größte m hätte einen Wert von 255, und 2553 ist kleiner als jeder vernünftige Modul. Solche Klartexte könnten wiederhergestellt werden, indem man einfach die Kubikwurzel des Geheimtextes zieht.

Um diese Probleme zu vermeiden, betten praktische RSA-Implementierungen typischerweise irgendeine Form von strukturiertem, randomisiertem Padding in den Wert m ein, bevor sie ihn verschlüsseln. Dieses Auffüllen stellt sicher, dass m nicht in den Bereich unsicherer Klartexte fällt und dass eine bestimmte Nachricht, sobald sie aufgefüllt ist, in einen von einer großen Anzahl verschiedener möglicher Chiffretexte verschlüsselt wird. Die letztgenannte Eigenschaft kann die Kosten eines Wörterbuchangriffs über die Möglichkeiten eines vernünftigen Angreifers hinaus erhöhen.

Standards wie PKCS wurden sorgfältig entwickelt, um Nachrichten vor der RSA-Verschlüsselung sicher aufzufüllen. Da diese Schemata den Klartext m mit einer gewissen Anzahl zusätzlicher Bits auffüllen, muss die Größe der nicht aufgefüllten Nachricht M etwas kleiner sein. RSA-Padding-Schemata müssen sorgfältig entworfen werden, um ausgeklügelte Angriffe zu verhindern. Dies kann durch eine vorhersagbare Nachrichtenstruktur erleichtert werden. Frühe Versionen des PKCS-Standards verwendeten Ad-hoc- Konstruktionen, die sich später als anfällig für einen praktischen adaptiven Ciphertext-Angriff erwiesen . Moderne Konstruktionen verwenden sichere Techniken wie Optimal Asymmetric Encryption Padding (OAEP), um Nachrichten zu schützen und gleichzeitig diese Angriffe zu verhindern. Der PKCS -Standard hat auch Verarbeitungsschemata, die dafür ausgelegt sind, zusätzliche Sicherheit für RSA-Signaturen bereitzustellen, z. B. das Probabilistic Signature Scheme for RSA ( RSA-PSS ).

Nachrichten signieren

Angenommen, Alice verwendet Bobs öffentlichen Schlüssel, um ihm eine verschlüsselte Nachricht zu senden. In der Nachricht kann sie behaupten, Alice zu sein, aber Bob hat keine Möglichkeit zu überprüfen, ob die Nachricht tatsächlich von Alice stammt, da jeder Bobs öffentlichen Schlüssel verwenden kann, um ihm verschlüsselte Nachrichten zu senden. Um also die Herkunft einer Nachricht zu verifizieren, kann RSA auch zum Signieren einer Nachricht verwendet werden.

Angenommen, Alice möchte eine signierte Nachricht an Bob senden. Sie erzeugt einen Hash-Wert der Nachricht, potenziert ihn mit d mod n (wie beim Entschlüsseln einer Nachricht) und hängt ihn als „Signatur“ an die Nachricht an. Wenn Bob die signierte Nachricht erhält, potenziert er die Signatur mit e mod n (genau wie beim Verschlüsseln einer Nachricht) und vergleicht den resultierenden Hash-Wert mit dem tatsächlichen Hash-Wert der Nachricht. Stimmen die beiden überein, weiß er, dass der Autor der Nachricht im Besitz von Alices geheimem Schlüssel war und die Nachricht seither nicht manipuliert wurde.

Beachten Sie, dass sichere Padding-Schemata wie RSA-PSS für die Sicherheit der Nachrichtensignierung genauso wichtig sind wie für die Nachrichtenverschlüsselung, und dass niemals derselbe Schlüssel sowohl für Verschlüsselungs- als auch für Signierungszwecke verwendet werden sollte.

Verweise

Andere Webseiten

• Das ursprüngliche RSA-Patent, wie es von Rivest beim US-Patentamt eingereicht wurde; Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. (Arlington, MA), 14. Dezember 1977, US-Patent 4,405,829  .

• PKCS #1: RSA-Kryptografiestandard (Website der RSA Laboratories )

  • Der PKCS #1- Standard „liefert Empfehlungen für die Implementierung von Public-Key-Kryptografie basierend auf dem RSA-Algorithmus, die die folgenden Aspekte abdeckt: kryptografische Primitive ; Verschlüsselungsschemata ; Signaturschemata mit Anhang; ASN.1 -Syntax zur Darstellung von Schlüsseln und zur Identifizierung der Schemata ".

• Erklärung von RSA mit farbigen Lampen bei YouTube

• Gründlicher Rundgang durch RSA

• Prime Number Hide-and-Seek: So funktioniert die RSA-Chiffre

• Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: Über die Macht der einfachen Branchenvorhersageanalyse

• Eine neue Schwachstelle in der RSA-Kryptographie, CAcert NEWS Blog

• Beispiel einer RSA-Implementierung mit PKCS#1-Padding (GPL-Quellcode)

• Kochers Artikel über Timing-Angriffe

• Eine animierte Erklärung von RSA mit seinem mathematischen Hintergrund von CrypTool

• Hacking Secret Ciphers with Python , Kapitel 24, Public Key Cryptography and the RSA Cipher

• Schmutz, James. „RSA-Verschlüsselung“ . Zahlenphil. Brady Haran .

• Wie RSA-Schlüssel für die Verschlüsselung in der realen Welt verwendet werden

• Primzahlen, Faktorisierung und ihre Beziehung zur Verschlüsselung

​

​

​

N