Die Mathematik hinter der Verschlüsselung

Geschichtliches

Die Gesetzmäßigkeiten der ganzen Zahlen, speziell die Aussagen über Teilbarkeit, Primzahlen und die Betrachtung von Restklassen bei der Division, wurden nach Einzelergebnissen im Altertum durch

• Euklid (300 vor Chr.) erst relativ spät, unter anderem durch die Mathematiker
• Pierre Fermat (1601 - 1666),
• Leonhard Euler (1707 - 1783) und
• Ernst Carl Friedrich Gauss (1777 - 1855)

Die Zahlentheorie bildet mit die Grundlage vieler moderner Verfahren im Umfeld der Kryptologie:

• Generierung von Pseudozufallsfolgen
• diverse Verschlüsselungsverfahren
• Digitale Unterschrift
• elektronisches Geld
• und viele weitere Verfahren

Primzahlen und zyklische Gruppen

Ist p eine Primzahl, so bildet

{1,2,3,...,p-1} mit der Multiplikation mod(p)

D.h. zunächst ist es eine Gruppe mit p-1 Elementen:

• zu je zwei Zahlen a und b aus M={1,2,3,..,p-1}
  gibt es eine eindeutige Zahl c aus M
  mit c = a * b mod (p).

• Es gibt ein neutrales Element 1 aus M, so daß
  a * 1 mod (p) = 1 * a mod(p) = a für alle a aus M.

• Es gilt (a * b mod(p)) * c mod (p) = a * (b * c mod(p))mod(p)

• Zu jedem a aus M gibt es ein Inverses a^-1 aus M
  mit a * a^-1 mod(p) = 1.

Neben der Gruppeneigenschaft, lassen sich alle Elemente 1,2,3,...,p-1 als
Ergebnis der Potenz mindestens eines Elementes a aus M erzeugen.

D.h. es gibt ein a aus M, so daß a, a²,a³,...a^r alle Elemente
aus {1,2,3,..,p-1} ergeben.

Nicht jedes a aus M erzeugt dabei M.
Aber für ein beliebiges a aus M
bilden die Potenten a, a², usw. zumindest eine Teilmenge
aus {1,2,3,...,p-1}, die selbst eine zyklische Gruppe darstellen.

1. Alle Elemente von {1,2,3,4} lasssen sich als Potenzen von 2^k mod(5) darstellen.

21mod(5) = 2

22mod(5) = 4

23mod(5) = 3

24mod(5) = 1

2. Für {1,2,3,4,5,6} erzeugen 3^k mod(7) und 5^k mod(7) alle Elemente.

31mod(7) = 3	32mod(7) = 2	33mod(7) = 6	34mod(7) = 4	35mod(7) = 5	36mod(7) = 1
51mod(7) = 5	52mod(7) = 4	53mod(7) = 6	54mod(7) = 2	55mod(7) = 3	56mod(7) = 1

3. Für {1,2,3,4,5,6,7,8,9,10} erzeugen a^k mod(11) a=2,6,7,8 alle Elemente.

21mod(11) = 2	22mod(11) = 4	23mod(11) = 8	24mod(11) = 5	25mod(11) = 10	26mod(11) = 9	27mod(11) = 7	28mod(11) = 3	29mod(11) = 6	210mod(11) = 1
61mod(11) = 6	62mod(11) = 3	63mod(11) = 7	64mod(11) = 9	65mod(11) = 10	66mod(11) = 5	67mod(11) = 8	68mod(11) = 4	69mod(11) = 2	610mod(11) = 1
71mod(11) = 7	72mod(11) = 5	73mod(11) = 2	74mod(11) = 3	75mod(11) = 10	76mod(11) = 4	77mod(11) = 6	78mod(11) = 9	79mod(11) = 8	710mod(11) = 1
81mod(11) = 8	82mod(11) = 9	83mod(11) = 6	84mod(11) = 4	85mod(11) = 10	86mod(11) = 3	87mod(11) = 2	88mod(11) = 5	89mod(11) = 7	810mod(11) = 1

Betrachtet man auch die anderen Basiszahlen,
so erkennt man, daß dadurch Untergruppen entstehen:

so erzeugt die 4 mod(5) die Untergruppe {1,4}

p=5	2	4	3	1
	3	4	2	1
(1,4)	4	1

oder die 2 und die 4 mod(7) die Untergruppe {1,2,4}
sowie die 6 mod(7) die Untergruppe {1,6}

p=7	2	4	1
	3	2	6	4	5	1
(1,2,4)	4	2	1
	5	4	6	2	3	1
(1,6)	6	1

und schließlich

die 3,4,5 und 9 mod(11) die Untergruppe {1,3,4,5,9}
sowie die 10 mod (11) die Untergruppe {1,10}

p=11	2	4	8	5	10	9	7	3	6	1
(1,3,4,5,9)	3	9	5	4	1
(1,3,4,5,9)	4	5	9	3	1
(1,3,4,5,9)	5	3	4	9	1
	6	3	7	9	10	5	8	4	2	1
	7	5	2	3	10	4	6	9	8	1
	8	9	6	4	10	3	2	5	7	1
(1,3,4,5,9)	9	4	3	5	1
(1,10)	10	1

Allgemein gilt für die Ordnung einer solchen Untergruppe,
daß sie ein Teiler der Ordnung der Gruppe ist (Satz von Lagrange).

In den Beispielen gilt:

p=5  => Ordnung {1,2,3,4}=4        Ordnung {1,4}=2 mit 2 Teiler von 4.
p=7  => Ordnung {1,2,3,4,5,6}=6  Ordnung {1,2,4}=3      Ordnung {1,6}= 2
p=11=> Ordnung Gruppe = 10       Ordnung {1,3,4,5,9}=5 Ordnung {1,10)=2

Mit p als Primzahl ist p-1 die Ordnung der zyklischen Gruppe und für ein beliebiges a aus {1,2,3,...,p-1} gilt:

Wenn a, a², a³, ..a^r-1 verschieden
und ergibt sich nach r-Schritten das bereits vorhandene Element a^s
a^r=a^s mit s < r

(Da es nur maximal p-1 Elemente als Ergebnisse gibt, muß sich
spätestens nach p Schritten ein Element wiederholen)

so gilt nach Multiplikation mit a^-s

a^r-s=1

Damit bilden a, a², a³, ..a^q=1 eine Untergruppe, womit q ein Teiler von p-1 ist.

also q*c=p-1 für eine natürliche Zahl c.

Da a^q=1 gilt: (a^q)c=1 also

a^q*c=a^p-1 = 1

also gilt der kleine Satz von Fermat.