 |
|||
| HSG |
|
Schlüsselerzeugung
- Wähle zwei verschiedene Primzahlen p und q. (Primzahl-Generator)
- Berechne n = p·q .
- Berechne φ(n). (Bemerkung: φ(n) = (p-1)·(q-1) bzw. Euler)
- Wähle eine Zahl e, die teilerfremd zu φ(n) ist. (ggt)
- 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 = me mod n.
Der Empfänger entschlüsselt durch m = cd mod n.
( Modpotenz )
e und d dürfen dabei auch vertauscht werden.
Warum funktioniert das?
Mit dem Satz von Euler gilt :(me mod n)d mod n = me·d mod n = mk·φ(n)+1 mod n = (mφ(n)·k mod n) · (m1 mod n) =(mφ(n) mod n)k mod n · (m1 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 256k-1. Es muss also die Ungleichung 256k-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!' >>>