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

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 
    = [x * [e * d]%n]%n         # Rechengesetze
    = [x * 1]%n                 # Schlüsseleigenschaft
    = [x]%n                     # Rechengesetz
    = x                         # Schlüsseleigenschaft
    

Das Verfahren mit modularer Multiplikation ist also 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 sein bzgl. der Modulozahl n. Die Zahl d muss also das modulare Inverse von e sein bzgl. der Modulozahl n (vgl. Station - Modulare Multiplikation).

Aufgabe 2

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 ist als die größtmögliche Codezahl einer Texteinheit.

Die Zahl e zum Verschlüsseln (e-ncrypt) ist eine beliebige natürliche Zahl, die kleiner als und teilerfremd zur Modulzahl n ist. (Denn dann existiert eine modulare Inverse d, wie im späteren Abschnitt Station - Berechnung der modularen Inversen gezeigt wird.)

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