Station - Das Verfahren und seine Korrektheit

Multiplikation statt Addition

Das Verfahren mit modularer Multiplikation funktioniert völlig analog zum Verfahren mit modularer Addition.

Zum Verschlüsseln wird hier im Beispiel der öffentliche Schlüssel (e, n) = (7, 30), zum Entschlüsseln der private Schlüssel (d, n) = (13, 30) benutzt.

Die Verschlüsselung einer Zahl x mit einem öffentlichen Schlüssel (e, n) erfolgt mit der Rechnung:

x -> [x * e]%n

Die Entschlüsselung einer Zahl y mit einem privaten Schlüssel (d, n) erfolgt analog mit der Rechnung:

y -> [y * d]%n

Aufgabe 1

Benutze die Standardcodierung und die Blocklänge 1 zur Codierung. Wähle als öffentlichen Schlüssel e = (11, 32) und verschlüssele hiermit die folgende Nachricht: GEHEIMNIS. Entschlüssele zur Kontrolle auch den Geheimcode. Benutze hierzu den privaten Schlüssel d = (3, 32).

Korrektheit des Verfahrens mit modularer Multiplikation

Korrektheitsüberlegungen liefern auch den entscheidenenden Hinweis, wie öffentlicher und privater Schlüssel bei dem Verfahren mit modularer Multiplikation zusammenhängen.

x
|                          # verschlüsseln
[x * e]%n
|                          # entschlüsseln
[[x * e]%n * d]%n 
=                          # Rechengesetze
[x * [e * d]%n]%n
=                          # Schlüsseleigenschaft
[x * 1]%n
=                          # Rechengesetz
[x]%n 
=                          # Schlüsseleigenschaft
x

Das Verfahren mit modularer Multiplikation ist korrekt, wenn der öffentliche Schlüssel (e, n) und der private Schlüssel (d, n) die folgende Schlüsseleigenschaft haben:

[e * d]%n = 1

Das heißt, e und d müssen modular invers zueinander bzgl. n sein bzw., d muss modulares Inverses von e bzgl. n sein (vgl. Station - Modulare Multiplikation).

Aufgabe 2

Überprüfe, ob e = 11 und d = 3 modular invers zueinander sind bzgl. n = 32.

Verfahren mit modularer Multiplikation

Schritt 1: Wahl der Blocklänge und Zerlegung des Textes

Schritt 2: Wahl der Codierung

Schritt 3: Wahl des öffentlichen Schlüssels (e, n)

Die Modulzahl n ist eine beliebige natürliche Zahl. Sie muss nur so gewählt werden, dass sie größer als die größtmögliche Codezahl einer Texteinheit ist.

Die Zahl e zum Verschlüsseln (e-ncrypt) ist eine beliebige natürliche Zahl, die kleiner als und teilerfremd zur Modulzahl n ist.

Schritt 4: Verschlüsselung codierter Texte

Zur Verschlüsselung eine Codezahl x benötigt man den öffentlichen Schlüssel (e, n). Die Verschlüsselung erfolgt hier durch modulare Multiplikation:

x -> [x * e]%n

Schritt 5: Bestimmung des privaten Schlüssels (d, n)

Die Zahl d zum Entschlüsseln (d-ecrypt) ist das modulare Inverse von e bgl. n.

Schritt 6: Entschlüsselung codierter Texte

Zur Entschlüsselung eine Codezahl y benötigt man den privaten Schlüssel (d, n). Die Entschlüsselung erfolgt analog zur Verschlüsselung:

y -> [y * d]%n