RSA	Nachricht-zu-Zahl modulo-Rechnen modulares Potenzieren Algorithmus von Euklid Euler-Funktion Satz von Euler modulares Inverses Primfaktorzerlegung Primzahlen finden Schlüsselpaar Angriff Sicherheit Pfad: Startseite / Fächer / Informatik / Kryptologie / RSA / Schlüsselpaar
Autor: mk 02.05.2011 12:34 1352	Schlüsselpaar erzeugen

Schlüsselerzeugung

1. Wähle zwei verschiedene Primzahlen p und q. (Primzahl-Generator)
2. Berechne n = p·q .
3. Berechne φ(n). (Bemerkung: φ(n) = (p-1)·(q-1) bzw. Euler)
4. Wähle eine Zahl e, die teilerfremd zu φ(n) ist. (ggt)
5. Berechne d so, dass e·d mod φ(n) = 1 gilt. (Bachet: 1 = e·d - k·φ(n), e und k aus Modulares Inverses ablesen )

(d,n) ist der private Schlüssel, (e,n) der öffentliche Schlüssel. p,q und φ(n) müssen geheim gehalten werden.

Verschlüsselung

Eine Nachricht m ist eine Zahl < n . Der Geheimtext ist die Zahl c = m^e mod n. Der Empfänger entschlüsselt durch m = c^d mod n. ( Modpotenz )
e und d dürfen dabei auch vertauscht werden.

Warum funktioniert das?

Mit dem Satz von Euler gilt :(m^e mod n)^d mod n = m^e·d mod n = m^k·φ(n)+1 mod n = (m^φ(n)·k mod n) · (m¹ mod n) =(m^φ(n) mod n)^k mod n · (m¹ mod n)= 1 · m .

Aufgaben

Spiele den Zyklus Schlüsselerzeugung, Verschlüsselung und Entschlüsselung für kleine (2-3 Stellen) und große (ca. 8 Stellen ?) Primzahlen durch. Benutze dabei untenstehende Programme oder - besser - baue dir ein eigenes 'RSA-System' aus den 'Bausteinen' krypto.py bzw. krypto0.py (überarbeitet) auf.

'Beispielsitzung mit krypto.py'

Um die krypto-Befehle nutzen zu können, muss man kein Python können. Es ist auch nicht notwendig, Idle zu benutzen. Man kann eine Python-Shell auch so starten, dass nach der Ausführung eines Skripts der interaktive Modus bestehen bleibt.

mk@x2:~/Desktop$ python3 -i krypto.py

>>> p = primzahl(200,300)
>>> p
277
>>> q = primzahl(200,300)
>>> q
223
>>> n = p*q
>>> n
61771
>>> phin = (p-1)*(q-1)
>>> phin
61272
>>> phi(n)
61272
>>> e = 4321
>>> ggt(e,phin)
1
>>> d = modinv(e,phin)
>>> d
44497
>>> (d*e)%phin
1
>>> (d*e)//phin
3138
>>> d*e == 3138*phin + 1
True
>>> m = 42
>>> c = modpower(m,e,n)
>>> c
16547
>>> modpower(c,d,n)
42

Problem der Blockbildung

Das RSA-Verfahren verlangt, dass für die Nachricht m m < n gilt. Das ist in obigem Beispielsystem noch nicht einmal für 'ABC' erfüllt, denn es gilt nicht 4276803 < 61771. Es können also nur so viele Bytes zu einem Block zusammengefasst werden, dass die entstehende Zahl < n erfüllt. Die größte Zahl, die man mit k 256-er-Ziffern darstellen kann, ist 256^k-1. Es muss also die Ungleichung 256^k-1 < n erfüllt werden. Das ist äquivalent zu k < log(n+1)/log(256). Da k im Allgemeinen nicht ganzzahlig ist, wird man die Blockgröße zu floor(log(n+1)/log(256)) wählen. Leider gibt es aber noch ein zusätzliches Problem. Auch wenn man beim Verschlüsseln die Blockgröße einhält, so kann das Chiffrat so groß werden, dass es in nicht mehr in der Blockgröße darstellbar ist. In obigem Beispiel ist n = 61771, dh. ein Block darf nur die Länge 1 haben. Trotzdem wird 65 zu 58500 verschlüsselt.

>>> modpower(65,e,n)
58500

Eine mögliche Lösung ist, die Blockgröße beim Verschlüsseln zwar bei k zu halten, aber im Chiffrat auf k+1 zu erweitern, damit auch ein Überlauf gespeichert werden kann. Damit kann beim Entschlüsseln nicht die gleiche Funktion verwendet werden, wie es nach der Mathematik des Verfahrens möglich ist. Auch werden immer wieder Nullbytes im Chiffrat sein.

>>> s='Hallo Welt!'
>>> em=bytes(s,'utf8')
>>> em
b'Hallo Welt!'
>>> ec=verschluesseln(em,e,n)
>>> ec
b'\xe6KM\x05\x87\xbb\x87\xbb\x0b2\xa3\xe0\x12\xc1\xb4\x88\x87\xbb\x17-C\x97'
>>> entschluesseln(ec,d,n)
b'Hallo Welt!'
>>> 

Links

• rfc3447
• Gaußklammer