RSA	[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]
Hohenstaufen-Gymnasium Kaiserslautern	Autor: mk Letzte Änderung dieser Seite: 17.03.2007 14:23:00  71 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 · (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' auf.

lokal