Der kleine Fermat und die Schlüssel

Ein Krimi?

Nein, ein kleines Praktikum über die
"Mathematik hinter den Public-Key-Verfahren."

Public- und Private Key's

Public - Key - Verfahren werden u. a. bei der Verschlüsselung und bei der Erzeugung digitaler Signaturen eingesetzt.

Zurück

Einige Verfahren

Das wohl bekannteste Public-Key-Verfahren ist das RSA-Verfahren, welches Ronald L. Rivest, Adi Shamir und Leonard M. A dlman 1977 veröffentlicht haben, und welches seinen Namen aus den Anfangsbuchstaben der Professoren vom MIT erhalten hat.

Ein jüngeres Verfahren mit öffentlichen Schlüssel ist der DIGITAL S IGNATURE STANDARD (DSS), welches das National Institute of Standards and Technology im U.S. DEPARTMENT OF COMMERCE 1994 veröffentlicht hat.(FIPS PUB 186, FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION)

Sowohl der RSA-Algorithmus, als auch DSS finden neben anderen Verfahren ihren Einsatz bei

einem Verschlüsselungsprogramm,das im nicht kommerziellen Bereich weit verbreitet,als Freeware und mit Source-Code verfügbar ist und dieses trotz massiver Widerstände (oder gerade aus diesem Grund) seitens der Behörden in USA.

Zurück


Das Prinzip der Falltürfunktionen

Damit diese Art "öffentlicher Verschlüsselung", bei der im Prinzip davon ausgegangen wird, daß jeder die verschlüsselte Nachricht mitlesen kann und das Verschlüsselungsverfahren samt öffentlichen Schlüssel des Empfängers kennt, einerseits praktikabel und andererseit sicher ist, müssen die Chiffrierfunktion einfach und schnell, ihre Umkehrung schwierig und langwierig sein.

Solche Funktionen haben den Spitznamen Falltürfunktionen.

Die zentrale Falltürfunktion bei der Verschlüsselung mit öffentlichen Schlüssel, die hier näher betrachtet wird, beruht auf der Multiplikation großer Zahlen, für welche schnelle Algorithmen bekannt sind.

Die Berechnung des geheimen Schlüssels aus den öffentlich bekannten Werten erfordert jedoch eine Primfaktorzerlegung, für welche bis heute jedoch keine "schnellen Algorithmen" bekannt sind!

Rechnen mit Resten

Die nachfolgende Beschränkung der Multiplikation auf endliche Zahlenräume, d.h. auf Zahlen mit einer maximalen Anzahl von Bit's, hat u.a. einen mathematischen Hintergrund.

Innerhalb der Verschlüsselung mit öffentlichen Schlüssel spielt die Potenzierung und anschließende Bildung von Resten bei der ganzzahligen Division eine hervorragende Rolle.

Schluck!???

Keine Panik, mit ganzen Zahlen rechnen ist für viele lange her aber sicher nicht vergessen.

Betrachten wir als Beispiel die Zahlen 0,1,2,3,...,14 und definieren für diese Zahlen eine Multiplikation, welche zunächst wie die gewohnte Multiplikation das Produkt bildet aber dann, wenn das Ergebnis größer als 14 ist, wird durch 15 ganzzahlig geteilt und der entstehende Rest als Ergebnis genommen:

Beispiele:

2 * 11 = 22 22 = 1 * 15 Rest 7
5 * 7  = 35 35 = 2 * 15 Rest 5
7 * 11 = 77 77 = 5 * 15 Rest 2

d.h.

2 * 11 mod (15) = 7

5 * 7  mod (15) = 5

7 * 11 mod (15) = 2

Zurück

Zwei kleine Beispiele mit öffentlichen Schlüssel

1.Verschlüsselungsbeispiel:

Nehmen wir an, daß der öffentliche Schlüssel von Frank 11 und
sein geheimer Schlüssel 3 sei und alle Rechnungen Modulo 15 durchgeführt werden.

Wenn nun Werner die Zahl 2 verschlüsselt per mail an Frank senden möchte, so muß er die Zahl 2 mit dem öffentlichen Schlüssel 11 von Frank potenzieren und den Rest bei der ganzzahligen Division durch 15 an Frank senden.

Heraus kommt:

D.h. Werner übermittelt Frank die Zahl 8 und den "Modulus" 15.

Zum Dechiffrieren potenziert Frank die Zahl 8 mit seinem geheimen Schlüssel 3 und erhält

also erhält Frank wieder die ursprüngliche Zahl 2.

2.Signierbeispiel:

Sicher überflüssig zu erwähnen, dennoch dient die Verwendung der Quersumme als Hashfunktion im nachfolgenden Beispiel natürlich ebenso, wie die verwendeten kleinen Zahlen nur der Demonstration!
Beispiel für eine "echte" Hashfunktion im Umfeld der Nachrichtenautentifizierung ist z.B. der oben aufgeführte Message Digest 5, unter dem Namen MD5, beschrieben in RFC1321

Frank möchte die "Nachricht" 121

unterzeichnen und bildet zunächst den Hashwert der Nachricht:

Diesen Wert 4 unterschreibt er, indem er ihn mit seinem geheimen Schlüssel 3 verschlüsselt.
Die Nachricht, der chiffrierte Hashwert der Nachricht und der Modulus wird als "unterzeichnetes Dokument" versendet. Um die Nachricht zu überprüfen, wird Werner zunächst selbst aus der Nachricht den Hashwert ermitteln:
1+2+1 = 4

Dann wird Werner mit dem öffentlichen Schlüssel 11 von Frank den mitgelieferten Hashcode dechiffrieren:
411 mod(15)=4194304 mod(15) =4

(Hierbei sind sowohl der verschlüsselte, als auch der unverschlüsselte Wert zufällig gleich 4 .)

Stimmen diese Zahlen, wie in diesem Fall, überein, geht man davon aus ,daß die Nachricht unverfälscht ist, und vom Besitzer des zum öffentlichen Schlüssel gehörigen geheimen Schlüssel erstellt wurde.

Wieso klappt dies?

Eine Zahl mod(15) potenzieren mit dem öffentlichen Schlüssel des Empfängers und anschließend das Ergebnis wieder mod(15) potenzieren, diesmal mit dem geheimen Schlüssel des Empfängers ergibt, zumindest in den Beispielen, wieder die Ausgangszahl!!

Was steckt dahinter?

rechnen wir zunächt einmal nicht mit den Resten beim Teilen durch 15, also mod(15),
sondern normal:


Wenn man jetzt mit den besagten Resten beim Teilen durch 15 rechnet, so ergibt sich,

falls nur n und 15 teilerfremd sind!
und damit =>

2 113 mod (15) = 2 bzw.

4 311 mod (15) = 4 gilt.

Zurück

Der Zusammenhang zwischen Schlüsselpaar und Modul

Wie sicher bereits vermutet, sind

voneinander abhängig.

Kern dieser Abhängigkeit sind bestimmte, auf Teilbarkeits-Relationen basierende Gesetzmäßigkeiten.

Dazu betrachte man zu einer natürlichen Zahl m die Anzahl der natürlichen Zahlen, die kleiner sind als m und mit m keinen gemeinsamen echten Teiler haben:

Beispiele:

m=3 (1,2) als Primzahl hat 3 keine echten Teiler
m=5 (1,2,3,4) auch 5 hat als Primzahl keine echten Teiler
m=6 (1,5) 2 und 3 teilen 6, 4 hat mit 6 den Teiler 2 also bleiben 1 und 5
m=15 (1,2,4,7,8,11,13,14) 3,5 sind Teiler, 6,9 und 12 haben 3 als Teiler, 10 die 5

Jeder Zahl m kann man so die Anzahl zu m teilerfremden kleineren Zahlen zuordnen.

Diese Zuordnung ist eine besondere zahlentheoretische Funktion und wird als

Eulersche phi-Funktion bezeichnet.

Berechnen läßt sich die phi-Funktion wegen der beiden folgenden Eigenschaften:

Da Primzahlen per Definition keine echten Teiler haben gilt für sie:

also phi(7)=6, phi(17)=16 u.s.w.

Weiter gilt:

womit sich dann phi(m) ausrechnen läßt, indem man m in seine Primfaktoren zerlegt.

Nach diesen Vorbemerkungen läßt sich nun der zentrale Satz formulieren, der die mathematische Basis des hier betrachteten Public-Key-Verfahrens darstellt.

Er sagt aus , daß bei der Modulo-Multiplikation bestimmte Potenzen immer wieder die 1 ergeben, woraus folgt, daß man durch Potenzieren (chiffrieren) und anschließendem nochmaligen Potenzieren (dechiffrieren) wieder bei der ursprünglichen Zahl ankommt.

Zurück

Der kleine Satz von Fermat:

Sind a und m teilerfremd und bezeichnet phi(m) die Eulersche Funktion von m,
so gilt:
aphi(m) mod(m) = 1

mit den Zahlen in den obigen Beispielen


aphi(15)mod(15)=a8mod(15) = 1

Mathematisch Interessierte finden hier weitere Informationen.

Zurück

Nun zum Kochrezept

Nach diesen Ausführungen sind zur Erzeugung eines Public - Key - Schlüsselpaares folgende Schritte durchzuführen:

In unserem Beispiel sind

Nun sind e und d so zu bestimmen ,daß

In diesem Beispiel sieht man, daß es durchaus mehrere Schlüsselpaare bei gegebenem p und q geben kann:

Zurück

Große Primzahlen

In unserem Beispiel könnte Werner mit Franks öffentlichen Schlüssels 11 und des mitgegeben Moduls 15 zurückrechnen:

und mit k=4 wäre (1+4*8)/11=3 der geheime Schlüssel von Frank gefunden!

Damit dies nicht funktioniert, werden für p und q sehr große Primzahlen benötigt, da zur Primfaktorzerlegung keine schnellen Verfahren bekannt sind.

Die Bestimmung von Primzahlen beschäftigte bereits 275 - 194 vor Christus den griechischen Mathematiker Eratosthenens von Cyrene (heute Shahhat in Lybien), dessen Algorithmus ,

"Das Sieb des Eratostenes",

bei einer gegebenen Zahl p die Primzahleigenschaft prüft, indem ausgeschlossen wird, daß keine der bereits erkannten kleineren Primzahlen als Teiler von p vorkommt.

Ist die Primzahl sehr groß, 100 und mehr Stellen, so sind die zur Zerlegung benötigten Rechenoperationen praktisch nicht in angemessener Zeit durchführbar.

Gott sei Dank!

Darin liegt das Prinzip der Falltürfunktion.

Wie sollen aber nun zwei große Primzahlen p und q gefunden werden, wenn zum Nachweis der Primzahleigenschaft die Faktorzerlegung ebenfalls nicht in angemessener Zeit erfolgen kann?

Zur Verschlüsselung werden heute große Zahlen bereits als Primzahlen angenommen,
wenn es sich "mit hoher Wahrscheinlichkeit" um solche handelt?!?

D.h. Primzahlen werden mit einer Art "Restrisiko" ermittelt:

Ausgehend von einer großen Zahl, wird zunächst mit kleinen Primzahlen geprüft, ob diese Teiler sind.
Ist dies nicht der Fall, so unterstellt man, daß es sich um eine Primzahl handelt und es muß der kleine Satz von Fermat gelten.
Gilt dieser Satz für hinreichend viele Zahlen a, dann unterstellt man, daß es sich um eine Primzahl handelt.

Dies sei an zwei weiteren Beispielen mit etwas gößeren Zahlen erläutert:

6273 ist mit der Quersumme 18 durch 3 teilbar also keine Primzahl. Also versuchen wir es mit der nächsten Zahl.
6274 muß man nicht betrachten, da sie durch 2 teilbat ist. Also zur nächsten Zahl
6275 ist durch 5 teilbar.
6276 ist durch 2 teilbar.
6277 könnte eine Primzahl sein.

Also unterstellen wir, daß es sich um eine Primzahl handelt.

Nach dem kleinen Satz von Fermat gilt dann mit phi(p)=p-1

probieren Sie mit dem Modulo - Potenzrechner z.B.


es ergibt 1.
versuchen Sie es mit anderen Basiszahlen a z.B. 3,5,7,11,...

Alle ergeben 1, so daß wir davon ausgehen, daß es sich um eine Primzahl handelt.(Wobei bei solch kleinen Zahlen natürlich auch der "Beweis" über die Anwendung des Siebes von Eratostens möglich ist.)

nächstes Beispiel:

7917 ist wieder durch 3 teilbar (Quersumme 24)
7919 scheint wieder eine Primzahl zu sein.
Die Prüfung mit dem Modulo Potenzierer scheint dies zu bestätigen.

So nun zurück zum Thema:

Gibt es zu einer Zahl e eine inverse Zahl d mod(m), so kann man sie mittels einer Erweiterung des Euklidschen Algorithus berechnen.

Lassen Sie dazu den Kryptorechner solche Schlüsselpaare suchen, die Sie anschließend mit dem Modulo-Potenzierer auf verifizieren können:

Wählen Sie dazu im Teil erweiterter Euklid für

u1=49693368

u2=7090 (oder einen beliebigen anderen Wert)

Die Option "Versuche nächste 10"

und klicken Sie berechnen.

In der zweiten Spalte erscheint nach einiger Zeit der inverse Wert 784669

zu der Zahl u2=7093, welche zwischenzeitlich vom Kryptorechner ausprobiert wurde.

Ergebnis: (784669,7093) ist ein Schlüsselpaar zum Modulus 49707563

Mittels des Krypto-Potenzierers, läßt sich dies verifizieren.

z.B. b=131, p=784669, m=49707563 ergibt 131pmod(m) = 31990944

b=31990944, p=7093 m=49707563 ergibt 319909447093 mod(m)=131

Zurück

Größenordnung praktisch verwendbarer Primzahlen

Um eine Vorstellung von der Größe praktisch verwendbarer Schlüssel zu bekommen werden nachfolgend die Zahlen p,q,m,e und d für ein vom Programm PGP erzeugtes Schlüsselpaar für 384 Bit Länge gezeigt:

p=
55797555556840524954
22475270998881006433
215475718477923499

q=
58128867332863922506
27669916229067559634
788016912599321027

m=
32434487044616870241
86145051830701599441
26670505128653187770
49835923261496307427
98409485230669980174
5967076248113473

d=
16217243522308435120
93072525915350799720
63335252564326593828
28596817145525780688
91945381217906686687
1237222585434491

e=17

Diese "untere Grenze" einsatzfähiger Schlüssel zeigt, daß
die Berechnungen bei den meisten Programmiersprachen oder Rechenprogrammen nicht mit den Basis - Datentypen durchgeführt werden kann.

Ausnahme bildet z.B. die Programmiersprache JAVA, die neben der Klasse BigInteger, welche beliebig lange Integerzahlen u.a. mit Modulo - Aritmetik abhandeln kann, auch Algorithmen zur Verschlüsselung beinhaltet.

Zurück

Erweiterter Euklidscher Algorithmus

Wie im Abschnitt Kochrezept gezeigt , sind der öffentliche Schlüssel e und der geheime Schlüssel d zueinander invers bezüglich der Multiplikation modulo (phi(m)):

D.H. wenn p und q gewählt sind und damit der Modulus m=p*q und auch phi(p*q)=(p-1)*(q-1) feststeht, benötigt man ein Verfahren, das zu einem vorgegebenen e ein d berechnet, mit e * d mod(phi(p*q))=1

Mittels des nachfolgend beschrieben erweiterten Euklid'schen Algorithmus kann zu einem gegebenen e ein inverses d berechnet werden.

Zunächst jedoch zur berühmten Vorstufe dieses Verfahrens, dem

Euklid'schen Algorithmus

Der Euklid'sche Algorithmus berechnet den größten gemeinsamen Teiler zweier positiver ganzen Zahlen.
Dieser Algorithmus ist einer der ältesten, nicht trivialen Algorithmen, die bis heute überlebt haben.
Eine Form des Algorithmus wurde 300 vor Christus in Euklid's Buch über die Elemente veröffentlicht.

Beispiel 1:

===> ggT(120,35) = 5

Beispiel 2:

===> ggT(120,35) = 1 ===> 63 und 8 sind relativ prim

Euklid'scher Algorithmus:

Der erweiterte Euklid'scher Algorithmus:

Neben diesen Schritten werden im erweiterten Algorithmus
weitere Hilfsfelder berechnet:

In der 3. Spalte sind die gleichen Werte, wie beim Euklid'schen Algorithmus.

in der 4. Spalte jeweils der ganzzahlige Quotient q der Werte aus der 3. Spalte vorletzte Zeile durch letzte Zeile:

Die ersten beiden Zeilen sind vorgegeben, mit den konstanten 1 und 0 Werten,
sowie den beiden Zahlen (im Beispiel 120 und 35)

Um eine neue Zeile zu berechnen, wird zunächst q, wie beschrieben als ganzzahliger Quotient der vorletzten und letzten Zeile, Spalte 3, berechnet.

in den ersten 3 Spalten der neuen Zeile i
kommt dann jeweils der Wert

also der Wert aus der vorletzten Zeile vermindert um den mit q multiplizierten Wert der letzen Zeile.

Wählt man nun für die erste Zahl den Modul (Beispiel 8) und für die zweite e (Beispiel 11),
so ergibt sich ein Inverses zu e modulo in der 2. Spalte dann, wenn der erweiterte Euklid'sche Algorithmus in der 3. Spalte mit 1 endet:

Zurück
Krypto - Rechner

Obwohl schon an mehreren Stellen dieses Praktikums darauf verwiesen wurde möchte ich an dieser Stelle noch einmal ganz deutlich herausstellen:

Die hier im Kryptorechner verwendete Arithmetik von Java-Skript läßt
weniger als 10 Dezimalstellen zu,

ist also nur zu Demozwecken verwendbar!!!!!!!!!!!!!

Wesentlicher Bestandteil der in der Praxis verwendbaren "Cryptoprogramme" sind die Implemtationen der Grundrechenarten und Modulo-Rechenalgorithmen mit beliebig großen Zahlen!.

Nun zum Krypto-Rechner, der nur dazu da ist, die Beispielrechnungen durchzuführen: