In der Multiplikativen Verschlüsselung weisen wir jedem Buchstaben unseres Alphabets eine Zahl zu. Als Beispiel am Alphabet {A,B,C,D,E}:

Die Zahlen sind durch Z_m (Modulorestklasse) mit m=5 darstellbar. Die Modulorestklassen werden durch die Modulo-Operation bestimmt. Die Modulo-Operation dividiert zwei Zahlen miteinander und findet den ganzzahligen Rest heraus. Teilen, wir also zum Beispiel 21 mod 4 , so erhalten wir als Ergebnis 1, da sich 20 / 4 ohne Rest teilen lässt, es entsteht also ein Rest von 1.

Der Schlüssel ist bei der Verschlüsselung sehr wichtig. Er muss so gewählt sein, dass es nicht zu einfach wird, die Verschlüsselung zu knacken (dh. 1 fällt als Schlüssel weg) und die Verschlüsselung muss umkehrbar sein. Der Schlüssel hat dann ein inverses Element (mit dem wir die Entschlüsselung vornehmen) wenn der Schlüssel und m teilerfremd sind, dh. der größte gemeinsame Teiler der beiden Zahlen 1 ist. Diese Überprüfung ist für die Zahlen 0 und 1 sinnlos.

Für das oben gewählte Beispiel gilt also für alle Zahlen, die größer als 1 sind, dass sie und m teilerfremd sind, wir können also mit folgenden Zahlen verschlüsseln: {2, 3, 4}.

Die Verschlüsselung ist nun relativ einfach. Wir wählen uns aus den Zahlen oben einen Schlüssel mit dem wir ein Wort (bzw. Zeichenkette) verschlüsseln wollen. Hier wähle ich mir Beispielshaft als Schlüssel 3 und als Wort „DAE“.

Um die verschlüsselte Zeichenkette zu erhalten rechnen wir (für jedes Zeichen einzeln, a ist das Zeichen, s der Schlüssel):

y = (a*s) mod m

Also:

y_1=(3*3) mod 5 = 9 mod 5 = 4
y_2=(0*3) mod 5 = 0
y_3=(4*3) mod 5 = 12 mod 5 = 2

Als verschlüsseltes Wort erhalten wir also „EAC“.

Zum Entschlüsseln der Zeichenkette benötigen wir das inverse Element des Schlüssels. Für das Inverse Element (h) des Schlüssels gilt:

s*h = 1 mod m

Wir können den Schlüssel auch iterativ über folgende Formel berechnen:

((1+(i*m))/s)=h

Dabei muss i von 0 beginnend hochgezählt werden. h ist genau dann das inverse Element für den Schlüssel s, wenn es ganzzahlig wird, dh. es darf bei der Division des Zählers durch den Schlüssel s kein Rest übrig bleiben.

1/3 ⇒ Rest 1
1+5/3 = 6/3 = 2 Rest 0

Das inverse Element von 3 ist hier also 2.

Um nun eine verschlüsselte Zeichenkette zu entschlüsseln, gehen wir genauso vor wie bei der Verschlüsselung, nur dass wir nun anstelle des Schlüssels das inverse Element des Schlüssels benutzen.

a = (x*h) mod m

Also hier:

4*2 mod 5 = 3 D
0*2 mod 5 = 0 A
2*2 mod 5 = 4 E

Beispielimplementierung in C