Kliger

Im Jahr 1980 veröffentlichte der Kryptologe Frank Rubin ein mathematisches Verschlüsselungsverfahren, das von Albert Kliger stammt und ihm zugesandt worden war. Die exakte mathematische Zahlentheorie soll nicht im Detail formuliert, sondern nur der zentrale Begriff Primitivwurzel verständlich erklärt werden, soweit es für das Verständnis des Verfahrens erforderlich ist. Zusätzlich wird eine weitere Einschränkung vorgenommen, da für das Verfahren nur Primzahlen betrachtet werden.

Sei p eine Primzahl. Dann heißt mPrimitivwurzel modulo p genau dann, wenn

{ m^x | x = 1,2, … p-1 }  =  { 1,2, … p-1 }

Die zentrale Eigenschaft einer Primitivwurzel m modulo p ist also, dass jedes Element der Menge { 1,2,...,p-1 } als Potenz der Primitivwurzel dargestellt werden kann. Ist m eine Primitivwurzel modulo p, so bezeichnet man für die Zahlen x ∈ { 1,2,..., p-1 } die eindeutige Lösung der Gleichung c=m^x mod p mit x=log_mc als diskreten Logarithmus.

Um festzustellen, ob etwa m = 5 eine Primitivwurzel von p = 7 ist, muss man nacheinander die Potenzen 5^x mod 7 für alle Exponenten { 1,2,3,4,5,6 } berechnen.

Da alle Zahlen 1,2,...,p-1 als Ergebnis auftreten, ist 5 eine Primitivwurzeln modulo 7. Ab dem Exponenten 7 wiederholen sich alle Ergebnisse, was an dem letzten Ergebnis 5^61 zu erkennen ist.

Die Zahl m = 4 ist dagegen keine Primitivwurzel modulo 7, da nur drei unterschiedliche Ergebnisse auftreten.

Untersucht man für p = 7 alle Zahlen 1 ≤ m ≤ 6, erhält man

m1	m2	m3	m4	m5	m6	o(x)
1
2	4	1				3
3	2	6	4	5	1	6
4	2	1				3
5	4	6	2	3	1	6
6	1					2

Diese Tabelle zeigt, dass die Ordnung o(x), also die Anzahl der unterschiedlichen Ergebnisse, für 3 und 5 gleich p-1 = 6 ist. Daher sind nur diese beiden Zahlen Primitivwurzeln modulo 7.

Es lässt sich beweisen, dass für jede Primzahl p eine Primitivwurzel modulo p existiert. Die nachfolgende Tabelle zeigt die Primitivwurzeln bis 23.

m	Primitivwurzeln modulo m
2	1
3	2
5	2 3
7	3 5
11	2 6 7 8
13	2 6 7 11
17	2 3 5 6 7 10 11 12 14
19	2 3 10 13 14 15
23	5 7 10 11 14 15 17 19 20 21

Das Verschlüsselungsverfahren von Kliger benutzt Primitivwurzeln für die Codierung der Buchstaben. Da mindestens 26 unterschiedliche Ergebnisse für die Zuordnung zu den Buchstaben auftreten müssen, sind erst Primzahlen ab 29 für die Verschlüsselung geeignet.

Die Berechnung der Potenzen zeigt, dass für p = 29 insgesamt zwölf Primitivwurzeln existieren. Die Tabelle gibt für die ersten zehn Primzahlen, die größer als 26 und damit für die Verschlüsselung geeignet sind, die Primitivwurzeln an.

m	Primitivwurzeln modulo m
29	2 3 8 10 11 14 15 18 19 21 26 27
31	3 11 12 13 17 21 22 24
37	32 2 35 5 13 15 17 18 19 20 22 24
41	6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
43	33 34 3 5 12 18 19 20 26 28 29 30
47	5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45
53	2 3 5 8 12 14 18 19 20 21 22 26 27 31 32 33 34 35 39 41 45 48 50 51
59	2 6 8 10 11 13 14 18 23 24 30 31 32 33 34 37 38 39 40 42 43 44 47 50 52 54 55 56
61	2 6 7 10 17 18 26 30 31 35 43 44 51 54 55 59
67	2 7 11 12 13 18 20 28 31 32 34 41 44 46 48 50 51 57 61 63

Da sich jede Primzahl mit einer zugehörigen Primitivwurzel als Schlüssel für das Verfahren benutzen lässt, ergibt sich theoretisch eine unendliche Anzahl von Schlüsseln. Sollen aber die Klartextbuchstaben durch zweistellige Zifferncodes verschlüsselt werden, eignen sich nur die Primzahlen bis 100.

Im dargestellten Beispiel werden die kleinste geeignete Primzahl p = 29 und die Primitivwurzel m = 11 für die Verschlüsselung gewählt.

Klartext	Dies ist ein geheimer Text
Schlüssel	29 11

Unabhängig von den gewählten Schlüsseln werden den Buchstaben zunächst die Zahlen von 1 bis 26 zugeordnet.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26

Danach wird der Klartext durch die festgelegten Zahlencodes umgeformt.

D	I	E	S	I	S	T	E	I	N	G	E	H	E	I	M	E	R	T	E	X	T
4	9	5	19	9	19	20	5	9	14	7	5	8	5	9	13	5	18	20	5	24	20

Die endgültige Verschlüsselung erfolgt über den diskreten Logarithmus, also den Exponenten der Potenz m^x, bei dem der den Buchstaben zugeordnete Zahlencode auftritt. Für p = 29 und m = 11 ergeben sich die Potenzen in der Tabelle. Natürlich treten bei den Potenzen auch Zahlen größer als 26 als Ergebnis auf. Da diese aber nicht als Zahlencodes der Buchstaben auftreten, spielen sie keine Rolle bei der Bestimmung der Geheimtextcodes.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28
11	5	26	25	14	9	12	16	2	22	10	23	21	28	18	24	3	4	15	20	17	13	27	7	19	6	8	1

Der erste Klartextbuchstabe D besitzt den Zahlencode 4, der als Ergebnis der Potenz 11₁₈ auftritt. Damit ist 18 der zugehörige Geheimtextcode. Der zweite Buchstabe I mit dem Zahlencode 9 tritt als Ergebnis der Potenz 11₆ auf. Da alle Codes zweistellig sein müssen, lautet dieser 06. Verfährt man so mit allen Buchstaben des Klartextes, ergibt sich der Geheimtext.

D	I	E	S	I	S	T	E	I	N	G	E	H	E	I	M	E	R	T	E	X	T
4	9	5	19	9	19	20	5	9	14	7	5	8	5	9	13	5	18	20	5	24	20
18	06	02	25	06	25	20	02	06	05	24	02	27	02	06	22	02	15	20	02	16	20

Da der Klartext für Primzahlen kleiner als 100 mit zweistelligen Zahlen verschlüsselt wird, liegt es nahe, für den Geheimtext alle Zahlen { 01,02,...,99 } zu verwenden. Dies ist ohne Probleme möglich, da sich bei Primitivwurzeln die auftretenden Ergebnisse periodisch wiederholen. Für p = 29 bedeutet dies, dass für den diskreten Logarithmus der Geheimtextcode unter drei bis vier Codes beliebig gewählt werden kann. Die Differenz der zueinander gehörenden Codes ist immer ein Vielfaches von p-1. In diesem Beispiel betragen die Unterschiede jeweils 28 und die Verschlüsselung wird damit homophon.

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

Der Geheimtext kann damit auch mit einer anderen Zahlenfolge verschlüsselt werden.

D	I	E	S	I	S	T	E	I	N	G	E	H	E	I	M	E	R	T	E	X	T
4	9	5	19	9	19	20	5	9	14	7	5	8	5	9	13	5	18	20	5	24	20
74	90	02	81	90	53	76	86	06	05	24	86	27	30	06	22	02	43	76	58	44	20

Entschlüsselung

Für die Entschlüsselung geht man genau umgekehrt vor, wie an einem Beispiel für p = 31 und m = 21 dargestellt wird.

Geheimtext	42284 08603 90340 02898 02404 87028 79406 48200 1782
Schlüssel	31 21

Im ersten Schritt müssen für die Primitivwurzel m = 21 die 30 unterschiedlichen Ergebnisse der Potenzen m^x bestimmt werden.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
21	7	23	18	6	2	11	14	15	5	12	4	22	28	30	10	24	8	13	25	29	20	17	16	26	19	27	9	3	1

Der Geheimtext wird zunächst in Gruppen von jeweils zwei Ziffern unterteilt und wegen p=31 auf die Basiszahlen { 1,2,...,30 } reduziert. Dazu muss man von den gegebenen Geheimtextzahlen nur solange p-1 = 30 subtrahieren, bis man zu einer Basiszahl gelangt.

Über den diskreten Logarithmus dieser Zahl gelangt man dann zu den zugeordneten Buchstaben.

42	28	40	86	03	90	34	00	28	98	02	40	48	70	28	79	40	64	82	00	17	82
12	28	10	26	3	30	4	10	28	8	2	10	18	10	28	19	10	4	22	10	17	22
4	9	5	19	23	1	18	5	9	14	7	5	8	5	9	13	5	18	20	5	24	20
D	I	E	S	W	A	R	E	I	N	G	E	H	E	I	M	E	R	T	E	X	T

Damit lautet der entschlüsselte Klartext

Klartext

Dies war ein geheimer Text