Der Diffie-Hellmann-Schlüsseltausch

Das ganze noch einmal graphisch:

Sender (A) Empfänger (B)

Der Diffie-Hellmann-Schlüsseltausch

Der Beweis

Nach diesem Vorgang haben nun beide eine gemeinsame geheime Zahl berechnet! Warum? Um die Behauptung nachzuweisen, müssen wie uns von zwei Dingen überzeugen, die mit den Begriffen „gemeinsam“ und „geheim“ umschrieben werden können:

p Der von A berechnete Wert stimmt mit dem von B erhaltenen Wert überein (k=k’). Dies ist tatsächlich so: Wenn wir die Berechnung der von A erhaltenen Zahl k bis zum Anfang zurückverfolgen, sehen wir: = β = = ba a b a mod mod ) ( mod p s p s p k

Entsprechend ergibt sich für die von B berechnete Zahl: = α = = ab b a b mod mod ) ( mod ' p s p s p k s = k = sein. Also haben A und B wirklich die ba ab ist, muss auch Da natürlich s ' k gleiche Zahl berechnet.

p Der gemeinsame Wert ist auch ein gemeinsames Geheimnis!

Mit anderen Worten: Kein Außenstehender kann k berechnen. Welche Möglichkeiten hat ein Angreifer? Er könnte zum Beispiel versuchen, aus der

abgehörten Zahl α auf a (oder aus β auf b) zu schließen. Dann hätte er die Möglichkeiten

wie A (oder B) und könnte mit der geheimen Zahl a (oder b) ebenfalls das Endprodukt herstellen.

Aber das geht nicht! Sagt die Mathematik. Zwar ist es vergleichsweise einfach, die β s a mod und a mod Potenzen p p auszurechnen, aber es ist extrem schwierig, die Gleichung: α = s a mod p

nach a aufzulösen - jedenfalls nach unserem heutigen Wissensstand. Man könnte natürlich auch einfach ausprobieren, die Zahl a zu finden, aber die Größenordnung der Zahlen, die in der Praxis eingesetzt werden, verbieten dies: Die

α β ) haben zwischen 100 und 200 Dezimalstellen.

Zahlen (also p, s, a, b, ,

Um a durch systematisches Probieren zu finden, müsste man also mindestens ¹⁰⁰ 10

Versuche machen - diese Zahl ist um ein Vielfaches größer als die Zahl der Nanosekunden seit der Entstehung des Universums!

Kryptographie - Ein kurzer Einblick by M.K. 12

Der Diffie-Hellmann-Schlüsseltausch

Ein Beispiel

A und B einigen sich auf p = 11 und s = 7 (Achtung! s muss primitives Element sein). A wählt sich die Zufallszahl a = 4. Er berechnet: α

B wählt sich die Zufallszahl b = 6.

Er berechnet:

α und β werden nun ausgetauscht!

A berechnet wieder: k

B berechnet dann:

! Wie man nun sieht ist k = k’ und dies ist auch der geheime Schlüssel von beiden.

Kryptographie - Ein kurzer Einblick by M.K. 13

Der Diffie-Hellmann-Schlüsseltausch

Das Schlusswort

heutigem Wissensstand - praktisch unmöglich auszuführen. Man drückt dieses Phänomen auch so aus, dass man sagt, die diskrete Exponentialfunktion sei eine Einwegfunktion.

Die Sicherheit des Diffie-Hellman-Schlüsseltauschs beruht entscheidend Fazit 2:

darauf, dass die diskrete Exponentialfunktion eine Einwegfunktion ist. Aber auch hier muss eine kleine Einschränkung gemacht werden: Es könnte auch noch andere Möglichkeiten eines Angriffs auf den Diffie-Hellmann Schlüsseltausch geben, also Angriffe, die nicht auf diskrete Logarithmusfunktionen führen - nur hat noch niemand einen solchen Angriff gefunden, wenn es ihn überhaupt gibt.

Kryptographie - Ein kurzer Einblick by M.K. 14

Das El-Gamal-Verfahren

Hintergrund

Bisher hab ich noch nichts Handfestes über El-Gamal gefunden. Wer was weiß, der kann mir ne E-Mail zukommen lassen, dann bring ich das hier rein.

Kryptographie - Ein kurzer Einblick by M.K. 15

Das El-Gamal-Verfahren

Zum Verfahren

Zunächst möchten wir auch hier wieder feststellen, dass das

El-Gamal Verfahren zu den asymmetrischen Verfahren gehört, da man auch hier nicht nur einen Schlüssel zum Ver- und Entschlüssel hat.

Schaut man sich das Vorgehen bei El-Gamal an, so stellt man fest, dass es ähnlich dem Diffie-Hellmann-Schlüsseltausch ist, nur das hier zwei verschlüsselte Werte ( C 1 , C 2 ) übergeben werden.

Wie auch bei Diffie-Hellmann vereinbaren Sender (A) und Empfänger (B) wieder eine Primzahl p, sowie ein primitives Element a.

Nun denkt sich der Empfänger (B) eine Zufallszahl X b aus, wobei gelten muss: Diese Zufallszahl X b wird dann der private Schlüssel von B. Mit dieser Zufallszahl X b berechnet er dann seinen öffentlichen Schlüssel Y b:

Mit diesem öffentlichen Schlüssel Y b ist dann ein Sender (A) in der Lage, Nachrichten an B verschlüsselt zu versenden.

Möchte nun ein Sender (A) eine Nachricht an B versenden, so hat auch er ein bestimmtes

− < ≤ Vorgehen. Zunächst denkt auch er sich eine Zufallszahl k aus, wobei für k gilt: . 1 1 p k

Mit dieser Zufallszahl k berechnet er dann seinen Schlüssel K auf folgende Weise:

Diesen Schlüssel benötigt er dann später um C 2 auszurechnen.

Nun sind die Vorarbeiten für A erst einmal getan und er kann sich an den Weg machen seine

− ≤ ≤ Nachricht M ( ) zu verschlüsseln. 1 1 p M

Wie wir bereits oben festgestellt haben wird eine im El-Gamal-Verfahren verschlüsselte Nachricht als ein Paar von zwei Werten ( C 1 ,C 2 ) versendet. Kommen wir also nun zu der Berechnung dieser zwei Werte. Um C 1 zu berechnen geht er folgendermaßen vor:

Das El-Gamal-Verfahren

Nun haben wir bereits unseren ersten Wert C 1, also die hälfte unserer Verschlüsselten Nachricht.

Was wir nun noch benötigen ist C 2 :

Wir sehen also, dass wir die Nachricht M einfach mit dem Schlüssel K von A multiplizieren und dann modulo p rechnen.

Nun ist A mit der Verschlüsselung seiner Nachricht M fertig. Er hat also aus der Ursprungsnachricht M einfach ein Verschlüsseltes Paar (C 1 , C 2 ) gemacht. Dieses Paar (C 1 , C 2 ) wird nun auch an den Empfänger (B) gesendet.

Erhält nun der Empfänger B eine nach dem El-Gamal-Verfahren verschlüsselte Nachricht (C 1 , C 2 ), so muss er nun dieses Wertepaar in seine Ursprungsnachricht M entschlüsseln. Auch dieser Prozess ist nicht sehr schwer. Zunächst benötigt er den Schlüssel K von A. Dieser Schlüssel K ist erforderlich, da wir ja wissen, dass der Sender (A) die Nachricht in C 2 mit K multipliziert hat. Hieraus kann der Empfänger (B) dann die Ursprungsnachricht M zurückleiten.

Doch wie schon gesagt, berechnet der Empfänger (B) zunächst den Schlüssel K:

Da nun B den Schlüssel K hat und weiß, dass A auf C 2 durch die Rechnung 2 = p M K C mod * gekommen ist, kann er nun leicht auf M zurückrechnen. Dazu wendet er folgende Formel an

Diese Formel besagt also, dass er i von eins bis zu einer Zahl hoch zählen muss, bis er ein Zahl i findet, so dass für M eine „glatte“ Zahl heraus kommt, also eine Zahl ohne Rest. Hat er dieses i dann gefunden, so hat er auch die Ursprungsnachricht M gefunden.

Kryptographie - Ein kurzer Einblick by M.K. 17

Das El-Gamal-Verfahren

Da ein Vorgang durch ein Beispiel jedoch immer klarer wird, rechnen wir doch einmal eine Aufgabe durch.

Beispiel 1 ( Die vollständige Version ):

Sagen wir haben die Zahlen p = 71 und a = 7 gewählt. (Achtung! a muss ein primitives Elements sein) Nun möchte A eine Nachricht M = 10 an B senden.

Zunächst einmal muss B seinen öffentlichen Schlüssel herausgeben.

Dazu geht er folgendermaßen vor:

Schritt 2: Nun muss B seinen öffentlichen Schlüssel Y b berechnen:

Yb

Da nun A den öffentlichen Schlüssel von B kennt, kann er nun seine Nachricht M Verschlüsselt an B senden. Wie wir ja wissen berechnet er dazu die Werte C 1 und C 2 . Das ganze sieht dann folgendermaßen aus:

Schritt 2: Nun berechnet er seinen Schlüssel K: k K = p Y b mod

Schritt 3: Jetzt kann er den seine Nachricht M = 10 verschlüsseln. Zunächst berechnet er dafür C 1 :

Das El-Gamal-Verfahren

Schritt 4: Nun benötigt A noch den Wert C 2 : C 2

Schritt 5: Nun hat A seine Nachricht M = 10 in das Paar (C 1 , C 2 ) = (49, 57) verschlüsselt. Nun kann er dies an B versenden.

B erhält nun das Paar (49, 57) und weiß, dass dieser Text mit El-Gamal verschlüsselt wurde. Er fängt nun also an die Nachricht wieder zu dechiffrieren. Schritt 1: Um die Nachricht (C 1 , C 2 ) = (49, 57) wieder zu entschlüsseln benötigt er den Schlüssel K, welchen sich A vorher berechnet hat. Er rechnet also:

K

Somit hat er nun den Schlüssel K mit K = 27 und kann wieder auf M

zurückrechnen. Schritt 2: B weiß ja nun, dass A (K*M) mod p gerechnet hat. Also rechnet er wieder nach M um:

M

Nun muss A das i (Laufvariable) von 1.. bis zu einer Zahl durchlaufen lassen, so dass für M eine glatte Zahl (ohne Rest) herauskommt.

Für i = 1 : für i = 2 : für i = 3 :

Somit hat B nun die Ursprungsnachricht M = 10 gefunden.

Kryptographie - Ein kurzer Einblick by M.K. 19

Das El-Gamal-Verfahren

Beispiel 2 :

Nun kommt es immer darauf an, was man als Variablen bereits gegeben hat. Im 1. Beispiel mussten wir ja noch den öffentlichen Schlüssel von B berechnen. Aber dies ist nicht immer so, rechnen wir also noch einmal eine Aufgabe durch, wo bereits mehrere Variablen gegeben sind. ( Siehe Kryptographie-Script von Prof. Vinck S.37 ) gegeben Wir haben p = 71 und a = 7. Die Nachricht ist M = 30; Empfänger (B) : öffentlicher Schlüssel Yb = 3 Sender (A) : Zufallszahl k = 2, privater Schlüssel K = 9

Nun muss natürlich auch in diesem Beispiel der Sender A die Nachricht M in das Paar (C 1 ,C 2 ) verschlüsseln. Also rechnet er:

Nun hat der Sender (A) alles was er benötigt und sendet (C 1 , C 2 ) = (49, 57) an den Empfänger (B).

Der Empfänger erhält nun das Zahlenpaar (49, 57) und macht sich gleich an die Arbeit diese Nachricht wieder zu entschlüsseln: 1.Schritt: Da wir die Zufallszahl X b von B nicht kennen, nehmen wir K einfach als gegeben a:

⇒ K = 9

2.Schritt: Da wir nun K haben, können wir direkt auf M schließen:

Das El-Gamal-Verfahren

Auch hier müssen wir wieder ein passendes i finden, damit unsere Rechnung „glatt“ aufgeht:

für i = 1 : für i = 2 : für i = 3 :

Somit hat nun B die Ursprungsnachricht M = 30 gefunden.

Kryptographie - Ein kurzer Einblick by M.K. 21

Der RSA-Algorithmus

Hintergrund

Kurze Zeit, nachdem Diffie und Hellman Ihre Arbeit „New Directions in Cryptographie“ herausgebracht haben, machte sich das Forscherteam: Ronald Rivest, Adi Shamir und Len Adleman an die Arbeit. Adi Shamir berichtet, sie wollten zunächst beweisen, dass es die gewissen „trapdoor Einwegfunktionen“ nicht geben kann.

Aber es kam anders. Nicht nur ist es Rivest, Shamir und Adleman nicht gelungen, die Nichtexistenz von „trapdoor Einwegfunktionen“ nachzuweisen, sie stießen vielmehr bei ihren Beweisversuchen tatsächlich auf trapdoor Einwegfunktionen!

Das führte 1977 zur Entwicklung des berühmtesten Public-Key-Algorithmus, des nach den Initialen seiner Erfinder so genannten RSA-Algorithmus.

Kryptographie - Ein kurzer Einblick by M.K. 22

Der RSA-Algorithmus

Zum Verfahren

Zunächst nehme man zwei große Primzahlen p und q. Von diesen Bildet man das Produkt:

Nun werden zwei natürliche Zahlen e und d bestimmt, so dass gilt:

Der Schlüssel d (decryption) wird für die Entschlüsselung benutzt und der Schlüssel e (encryption) für die Verschlüsselung einer Nachricht.

Zudem wird dem Teilnehmer d als sein geheimer Schlüssel zugeordnet. Mit diesem geheimen Schlüssel ist er in der Lage, seine verschlüsselt erhaltene Nachricht wieder zu entschlüsseln. E und n bildenden die zugehörigen öffentlichen Schlüssel, wobei mit dem öffentlichen Schlüssel e eine Nachricht an den Empfänger verschlüsselt wird. Wir stellen uns vor, dass nun jemand an einen Empfänger eine Nachricht verschlüsselt schicken möchte. Dazu muss er zunächst die Nachricht in eine natürliche Zahl m kleiner als n

m ≤ ). Hierzu kann man die Nachricht auch gut in kleine Häppchen aufteilen übersetzen ( n

und diese einzelnen Häppchen dann verschlüsselt auf den Weg schicken. Nun kann der Verschlüsselungsvorgang beginnen. Man erhält den Geheimtext c, indem man m mit dem öffentlichen Schlüssel e des Empfängers potenziert und modulo n reduziert; Dass heißt:

Diese Nachricht c kann nun öffentlich an den Empfänger geschickt werden. Der Empfänger entschlüsselt den Geheimtext c, indem er ihn mit seinem geheimen Schlüssel e potenziert und modulo n reduziert. Er erhält also:

Das heißt, er erhält wieder die Ursprungsnachricht m (m=m’).

Kryptographie - Ein kurzer Einblick by M.K. 23

Der RSA-Algorithmus

Auch dies soll einmal graphisch verdeutlicht werden:

Der RSA-Algorithmus

Der Beweis

Um uns davon zu überzeugen, müssen wir die beiden definierenden Eigenschaften nachweisen. 1.) Verschlüsselungseigenschaft

Dazu müssen wir nachweisen, dass der Empfänger korrekt entschlüsselt: Die Zahl m’ muss gleich dem ursprünglichen Klartext m sein. Um dies zu erreichen setzen wir doch einfach ein: = = = ed d e d . mod mod ) ( mod ' n m n m n c m

Nach der Wahl von e und d folgt mit dem Eulerschen Satz: = m ed ; mod m n somit ist m’=m.

p Public-Key-Eigenschaft

Kein Angreifer, der nur den öffentlichen Schlüssel, also die Zahlen e und n kennt, darf daraus den geheimen Schlüssel d berechnen können.

Wenn ein Angreifer in der Lage ist, die Zahl n in ihre Primfaktoren zu zerlegen, befindet er sich in der gleichen Lage, wie die Stelle, welche die Schlüssel erzeugt. Er kann genauso einfach wie diese den geheimen Schlüssel d berechnen. (Wenn man p und q kennt, kann man jede der Zahlen e und d aus der anderen berechnen.) Daher müssen die Zahlen p und q so gewählt werden, dass niemand das Produkt n=pq faktorisieren kann. Insbesondere muss n eine große Zahl sein. Kein Mensch kann heute eine RSA-Zahl n, die eine Länge von 512 Bits (ca.155 Dezimalstellen) hat, faktorisieren.. Um vor Überraschungen sicher zu sein, wird aber häufig empfohlen, n als 1024 Bit-Zahl (oder noch größer) zu wählen. Wir haben gesehen: Jeder der faktorisieren kann, kann den RSA-Algorithmus brechen. Mit anderen Worten: Die Sicherheit des RSA-Algorithmus ist höchstens so groß wie die Schwierigkeit, große Zahlen zu faktorisieren.

Man sagt auch, die Faktorisierung von n ist eine „trapdoor“. Eine trapdoor („Geheimtür“) ist eine geheime Möglichkeit, mit der man die Verschlüsselung doch rückgängig machen kann.

Auch die Zahl (p-1)(q-1) ist eine trapdoor. Und natürlich ist der Geheimschlüssel selbst eine trapdoor. Aber das sind keine „wesentlich neuen“ trapdoors, sie sind gleichwertig zu faktorisieren.

Niemand kennt eine wesentlich andere trapdoor. Das heißt: Niemand hat einen Weg gefunden, den RSA-Algorithmus zu brechen, ohne de facto die Zahl n zu faktorisieren. Daher liegt die Vermutung nahe, dass die Sicherheit des RSA-Algorithmus genau so groß ist wie die Schwierigkeit, große Zahlen zu faktorisieren.

Aber: Keiner weiß es. Es ist durchaus denkbar, dass es einen „einfachen“ Weg gibt, den RSA-Algorithmus zu knacken.

Kryptographie - Ein kurzer Einblick by M.K. 25

Der RSA-Algorithmus

Ein Beispiel

Sagen wir mal Steven hat es nun langsam satt, dass seine Liebes-Emails, welche er mit Brunhilde austauscht, immer von anderen gelesen werden. Daher betätigt er den Wunsch endlich Verschlüsselte Nachrichten empfangen zu können. Somit wendet er sich an irgend eine Zentrale und spricht dort, seinen Wunsch aus.

Diese werden Steven dann wohl sagen, dass er etwas Geduld haben soll, mal ein paar Kannen Kaffee zu sich nehmen, und dann solle er sich wieder melden. Warum?

Wie wir wissen, brauch man für RSA 3 Schlüssel. Wobei e (Verschlüsselung) und n öffentliche Schlüssel sind und d (Entschlüsselung) ein privater Schlüssel ist. Also rechnet die Zentrale (ich denke mal das dies so abläuft, auch wenn es nicht ganz so stimmt, so macht dies auch nichts, da wir hier nur einfach das Verfahren der Schlüsselberechnung zeigen!) erst einmal eifrig.

Berechnung der Schlüssel:

Wir nehmen p = 2 und q = 5.

⇒ also n = 10 1. Schritt: n = p * q = 2 * 5 = 10, 2. Schritt: (p-1)*(q-1) = (2-1)*(5-1) = 1 * 4 = 4 Nun wählen wir ein e, welches kleiner als 4 ist.

⇒ also e = 3 Nehmen wir für e einfach die 3,

Nun rufen die Jungs von der Zentrale den Kaffeeverseuchten Steven an und geben ihm seinen „Privaten Schlüssel d“. Mit diesem kann er dann später seine Nachrichten entschlüsseln. E und n werden nun „öffentliche Schlüssel“, wobei e für die Verschlüsselung und n einfach für die modulo n Berechnung genutzt werden.

Versenden einer Verschlüsselten Nachricht:

Nun hat Brunhilde heraus bekommen, dass Steven zur Verschlüsselung seiner Nachrichten die „öffentlichen Schlüssel“ e und n hat.

Also ist Sie nun in der glücklichen Lage, auch Steven ist darüber erfreut, Steven endlich verschlüsselte Nachrichten zukommen zu lassen.

Kryptographie - Ein kurzer Einblick by M.K. 26

Der RSA-Algorithmus

Sagen wir hier aber einmal, sie möchte ihm einfach die Uhrzeit des nächsten Treffens zusenden. Sie wollen sich nämlich um 7 Uhr treffen. Also: m = 7 (Achtung m muss kleiner als n sein, was hier auch der Fall ist!) Brunhilde berechnet nun eine verschlüsselte Nachricht c mit:

c = = = 3

Diese Nachricht c schickt Sie nun öffentlich an Steven.

Entschlüsseln einer Nachricht

Steven schaut nun vor voller Freude in sein E-Mail Fach und bemerkt den verschlüsselten Liebesbrief von Brunhilde.

Voller Freude, er will das Treffen ja auch nicht verpassen, macht er sich an die Arbeit. Er berechnet nun wieder die Ursprungsnachricht m:

m = = = 7

Somit weiß nun Steven, wann das nächste Treffen vor der Türe steht. Außerdem kann er sich nun sicher sein, dass niemand diese Nachricht mitgelesen hat.

Kryptographie - Ein kurzer Einblick by M.K. 27

Das Fiat-Shamir-Verfahren (Zero-Knowledge)

Hintergrund

Völlig unglaublich, paradox und zumindest absolut unwahrscheinlich?

Nachdem schon 1985 die Amerikaner Shafi Goldwasser und Silvio Micali zusammen mit dem Kanadier Charles Rackhoff die theoretischen Grundlagen veröffentlicht hatten, fanden der israelische Mathematiker Adi Shamir und sein Schüler Amos Fiat im Jahre 1986 das erste praktisch einsetzbare Zero-Knowledge Verfahren.

Kryptographie - Ein kurzer Einblick by M.K. 28

Das Fiat-Shamir-Verfahren (Zero-Knowledge)

Zum Verfahren

Für dieses Verfahren braucht man eine natürliche Zahl n, für die gilt:

Die Zahl n bzw. die Faktoren p und q sollen so gewählt werden, dass es praktisch unmöglich ist, n zu faktorisieren.

Der zu Prüfende hat als sein Geheimnis eine natürliche Zahl s, die kleiner als n ist und weder von p noch von q geteilt wird. (Dies kann man auch ohne Kenntnis von p und q nachprüfen: Man betrachtet einfach den größten gemeinsamen Teiler von s und n; dieser muss gleich 1 sein.)

Nun veröffentlicht der zu Prüfende (der Hüter des Geheimnisses), welcher s als Geheimnis hat, die Zahl v mit:

anhand dieser Zahl v kann das Geheimnis dann später verifiziert werden.

Zum Ablauf der Überprüfung

Schritt 1 : Der Hüter des Geheimnisses wählt nun zufällig eine natürliche Zahl r. Schritt 2 : Nun berechnet er:

Diese Zahl x wird dann dem Prüfer geschickt. Nun wissen wir, dass niemand aus x das r zurückgewinnen kann. Diese Gleichung ist also eine gute Art unser r zu verbergen

Schritt 3 : Nun trifft der Prüfer eine zufällige Wahl, er wählt z.B. ein Bit (0 oder 1) aus und teilt diese Endscheidung dann dem Prüfenden mit.

Schritt 4 : Nun muss der Geprüfte die richtige Antwort geben. Kryptographie - Ein kurzer Einblick by M.K. 29

Das Fiat-Shamir-Verfahren (Zero-Knowledge)

Dabei muss er die Antworten auf folgende Art geben:

„0“ : Der Geprüfte muss dem Prüfer die Zahl r mitteilen. „1“ : Der Geprüfte muss dem Prüfer die Zahl y zuschicken, mit:

Dies bedeutet also, im Falle dass der Prüfer die „0“ wählt, braucht der Geprüfte sein Geheimnis nicht zu verwenden.

Im Falle der „1“ muss er aber sehr wohl von seinem Geheimnis gebrauch machen und die Zahl y berechnen. Schritt 5 : Nun muss sich der Prüfer davon überzeugen, dass das Ergebnis, was er erhalten hat auch richtig ist.

Dabei kommt es auf seine vorherige Endscheidung an: = ² gilt. „0“ : Er muss sich davon überzeugen, dass mod n r x

„1“ : Er muss überprüfen, ob

gilt, da:

= = = = ^{2 2 2 2 2 2} n v x n s n r n s r n s r n y mod ) * ( mod * mod mod ) * ( mod ) * ( mod

Somit ist ein Zyklus der Überprüfung des Hüters des Geheimnisses absolviert worden. Es wird aber nicht nur ein mal überprüft, sondern öfters, wie wir gleich weiter unten noch sehen werden.

Kryptographie - Ein kurzer Einblick by M.K. 30

Das Fiat-Shamir-Verfahren (Zero-Knowledge)

Die Möglichkeiten des Betruges

Dies ist aber natürlich noch nicht ganz alles, denn wenn der zu Prüfende die richtige Antwort geschickt hat, so ist der Prüfende natürlich nur zu 50% davon überzeugt, dass der Hüter des Geheimnisses auch wirklich ein Geheimnis hat.

Denn wenn der Prüfer die „0“ gewählt hat, so musste der Geheimnishüter einfach nur die Zahl r schicken. Und diese hat nun gar nichts mit dem Geheimnis zu tun. Aber auch wenn der Hüter vorhersehen kann, dass der Prüfer eine „1“ schicken wird, so kann er ihn Betrügen.

Denn dann würde der Prüfer im 2.Schritt nicht das Quadrat einer Zufälligen Zahl schicken, sondern er würde zuerst ein y wählen und dann eine Zahl v’ berechnen, so dass:

Eine solche Zahl v’ existiert immer dann, wenn der größte gemeinsame Teiler von v und n gleich 1 ist). Dann würde er die Zahl:

Berechnen und dieses x dann dem Prüfer schicken.

Damit könnte er dem Prüfer auf die Frage mit „1“ sofort eine Antwort geben, denn es gilt: = = ^{2 2} . mod mod ) '* * ( mod ) * ( n y n v v y n v x

Somit könnte man also stets auf ein Bit im voraus raten und dann jeweils auf eine, aber auch nur eine der Fragen des Prüfers richtig antworten. Daher gibt es bei diesem Verfahren zwei Fragen und auch zwei Antworten. Somit ist man nach einer Frage auch nur zu 50% sicher, dass der Hüter auch wirklich das Geheimnis kennt.

Die Lösung dieses Problems ist jedoch ganz einfach. Das Spiel wird einfach öfter gespielt. Nach zwei Spielen kann man schon zu 75% sicher sein, nach drei spielen zu 87,5% usw. Für n Spiele gilt somit:

Bereits nach 10 erfolgreichen Spielen (n = 10) kann man sich zu 99,99% sicher sein, dass der Hüter das Geheimnis kennt. Kryptographie - Ein kurzer Einblick by M.K. 31

Mathematik - Natürliche Zahlen Teil 1

Die moderne Kryptographie lebt von natürlichen Zahlen und deren Eigenschaften. Wir betrachten die natürlichen Zahlen, also die Zahlen 0, 1, 2, 3, 4, ... Wir brauchen aber nicht alle unendlich vielen natürlichen Zahlen, sondern nur die unterhalb einer festen Größe n, also nur die Zahlen 0, 1, 2, 4, ... , n-1.

Zum Beispiel brauchen wir im Fall n = 15 die Zahlen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.

Manchmal ist die Grenze auch eine Primzahl p, also eine Zahl, die nur durch 1 und sich selbst ohne Rest teilbar ist.

Wenn z.b. p = 11 ist, erhalten wir die elf Zahlen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Mit diesen Zahlen müssen wir auch rechnen, genauer gesagt addieren und multiplizieren. Dann muss es so sein, dass die „Summe“ und das „Produkt“ zweier solcher Zahlen wieder eine solche Zahl ist.

Die Addition

Wenden wir uns zunächst der Addition zu. Manchmal macht das keine Probleme. Wenn wir im Fall p = 11 die Summe 5 + 3 bilden, so rechnen wir „ganz normal“ 5 + 3 = 8; Da 8 in unserer Menge vorkommt, gilt auch in unserer neuen Struktur 5 + 3 = 8. Wenn wir aber 7 + 5 ausrechnen wollen, stoßen wir zunächst auf ein Problem. Wenn wir „ganz normal“ rechnen, erhalten wir 7 + 5 = 12, und 12 ist nicht in unserer Menge erhalten. Jetzt kommt der Trick! Wir ersetzen dieses Ergebnis durch den Rest, der sich bei Division durch p ergibt.

Da wir hier in unserem Beispiel p = 11 haben, müssen wir also unser Ergebnis durch p und somit durch 11 dividieren und den Rest dann notieren. Wenn wir 12 durch 11 dividieren, ergibt sich als Rest die Zahl 1. Geschrieben wird dass ganze dann so: 5 + 7 = 1 (mod 11)

(sprich: „5 plus 7 ist 1 modulo 11“), oder auch einfacher 5 + 7 mod 11 = 1 („5 plus 7 modulo 11 ist 1“).

Kryptographie - Ein kurzer Einblick by M.K. 32

Mathematik - Natürliche Zahlen Teil 1

Noch ein Beispiel:

9 + 6 ist 15; liegt somit auch nicht in unserer Menge. Bei Division durch 11 erhalten wir den Rest 4 (liegt nun in unserer Menge); also gilt: 9 + 6 = 4 (mod 11) oder einfacher 9 + 6 mod 11 = 4.

Die Multiplikation

Mit der Multiplikation geht es ganz entsprechend. Das Produkt 2 * 4 = 8 bietet kein Problem. Das Produkt 7 * 5 bestimmen wir, indem wir zunächst „ganz normal“ 7 * 5 = 35 rechnen und dann von 35 so oft p (auch in diesem Beispiel ist p = 11) abziehen, bis wir eine natürliche

≤ erhalten; diese ist 2 (denn es gilt 35 = 3 * 11 + 2). Zahl 11 Also schreiben wir 7 * 5 = 2 (mod 11) oder 7 * 5 mod 11 = 2.

Das Potenzieren

2 ⁶ = , der Auch das Potenzieren ist jetzt kein Problem mehr. ⁶ 2 wird wie folgt berechnet: 64

Rest der Division durch 11 ist 9 ( denn 64 = 5 * 11 + 9 ), also gilt 2 ⁶ = ) 11 (mod 9 oder

Mathematik - Natürliche Zahlen Teil 2

Wir betrachten jetzt natürliche Zahlen n, die das Produkt von zwei verschiedenen Primzahlen sind, also n = p * q mit zwei verschiedenen Primzahlen p, q

Die Zahlen 15, 55, 851 ( = 23 * 37 ) sind von dieser Art, während 17 (Primzahl), 105 (Produkt von drei Primzahlen), 49 (Produkt einer Primzahl mit sich selbst) nicht dazu gehören.

Grundlegend für die moderne Kryptographie ist ein Satz, der auf den großen Schweizer Mathematiker Leonhard Euler (1707-1783) zurückgeht. Wir formulieren ihn nur für Zahlen des Typs n = p * q.

Dies bedeutet also: Wenn man eine beliebige Zahl m mit der riesigen Zahl s(p-1)(q-1)+1 potenziert (also eine riesige Potenz berechnet), dann diese Potenz durch n dividiert, so erhält man als Rest wieder die Ausgangszahl m.

Ein Beispiel:

Nehmen wir s = 1, p = 7 und q = 11. Dann erhalten wir für n = pq: n = p * q ! n = 7 * 11 ! n = 77 Weiterhin berechnen wir: s * (p-1) * (q-1) + 1 = 1 * (7-1) * (11-1) + 1 = 1 * 6 * 10 + 1 = 61

Nun sagt die Formel folgendes: Wenn wir nun eine beliebige natürliche Zahl m, die kleiner als n ( hier n = 77) ist, mit 61 potenzieren, dann den Rest bei Division durch 77 betrachten, so erhalten wir wieder unsere Ausgangszahl m. m=10: + − − 1 ) 1 )( 1 ( q p s n m mod 10 ⁶¹ = 77 mod = 10

Kryptographie - Ein kurzer Einblick by M.K. 34

Mathematik - Natürliche Zahlen Teil 2

m=53:

+ − − 1 ) 1 )( 1 ( q p s n m mod 53 ⁶¹ = 77 mod = 53

m=80:

Achtung: Dies ist ein Fehler, da nun m > n ist!! + − − 1 ) 1 )( 1 ( q p s n m mod 80 ⁶¹ = 77 mod = 3 (ist nicht gleich m!)

m ≤ ist! Wir müssen also darauf achten, dass n

In unserer Formulierung des Eulerschen Satzes kann man schon fast ein Verschlüsselungsschema ahnen: Man macht mit der Nachricht m etwas Kompliziertes, und es ergibt sich wieder m. Wir müssen jetzt nur noch dieses Komplizierte in eine Ver- und Entschlüsselung aufteilen. Und das geht so:

Wir wählen irgendeine Zahl e, welche die Eigenschaft haben muss, dass sie mit (p-1)(q-1) den größten gemeinsamen Teiler 1 hat (man sagt dazu auch, dass e und (p-1)(q-1) „teilerfremd“ sind).

Wenn z.B. p = 23 und q = 37 ist, so ist (p-1)(q-1)=22 * 37 =792,

und für e könnte man die folgenden Zahlen wählen: 5, 7, 13, 17, 19, 23, 25, 29, 31, 35, ... Das zweite (und letzte) fundamentale mathematische Ergebnis für uns ist das folgende:

Wobei s eine natürliche Zahl ist, die sich bei der Berechnung von d automatisch ergibt.

Kryptographie - Ein kurzer Einblick by M.K. 35

Mathematik - Natürliche Zahlen Teil 2

Machen wir ein Beispiel:

Wie oben wählen wir p = 23 und q = 37. Dann berechnen wir: (p-1)(q-1) = (23-1)(37-1) = (22)(36) = 792

Eine teilerfremde Zahl zu 792 ist nun z.B. 5! Wir wählen somit e = 5. Nun rechnen wir aus: e * d = s * (p-1) * (q-1) + 1 ! 5 * d = s * (23-1) * (37-1) + 1 ! 5 * d = s * (22) * (36) + 1 ! 5 * d = s * 792 + 1 ( nehmen wir nun s = 2! ) ! 5 * d = 2 * 792 + 1 ! 5 * d = 1585 ! d = 1585 / 5 ! d = 317

Wir müssen also mit der Wahl von s darauf achten, dass das Ergebnis von s(p-1)(q-1)+1 durch e teilbar ist. In unserem Beispiel hätten wir für s z.B. auch die Zahl 7 wählen können, da 7 * 792 + 1 = 5545 ist und somit für d = 5545 / e = 5545 / 5 = 1109 herausgekommen wäre.

Die Methode mit der man d berechnet wird euklidscher Algorithmus genannt (nach dem Mathematiker Euklid (um 300 v. Chr.). Endscheidend ist, dass man d nur dann berechnen kann, wenn man die Faktoren p und q von n kennt.

Kurz: Wenn man die Zahl n = p * q in ihre Primfaktoren zerlegen kann, dann findet man leicht die Zahlen e und d mit e * d = s * (p-1) * (q-1) + 1.

Es bleibt die Frage: „Wie leicht kann man eine gegebene natürliche Zahl n faktorisieren?“

Kryptographie - Ein kurzer Einblick by M.K. 36

Mathematik - Natürliche Zahlen Teil 3

In diesem Abschnitt bereiten wir den Fiat-Shamir-Algorithmus vor. Dabei spielen Quadratzahlen (kurz: Quadrate) modulo n eine endscheidende Rolle. Selbstverständlich kann man jede Zahl modulo n quadrieren, aber nicht jede natürliche Zahl hat eine Quadratwurzel modulo n.

Das ist so wie bei den reellen Zahlen: Nur die nichtnegativen reellen Zahlen haben eine Quadratwurzel (sind Quadrate); jede positive reelle Zahl hat genau zwei Quadratwurzeln. Zum Beispiel hat 4 die Quadratwurzel 2 und -2. Wir müssen somit zwei Fragen diskutieren:

• Einerseits geht es darum, wie viele Quadratwurzeln eine natürliche Zahl modulo n haben

kann.

• Andererseits fragen wir uns, wie schwer es ist, Quadratwurzeln modulo n zu finden.

Zuerst behandeln wir Quadratwurzeln modulo p, wobei p eine Primzahl ist. In diesem Fall hat jedes Quadrat genau zwei Quadratwurzeln modulo p.

Das heißt: Jede Positive natürliche Zahl hat modulo p entweder 0 oder genau 2 Quadratwurzeln. Beispiel:

Betrachten wir als Beispiel den Fall p = 19;

Man kann diese Tabelle leicht berechnen, indem man alle Zahlen modulo 19 quadriert. Wir beobachten, dass genau die Hälfte der Elemente Quadrate sind; ferner sind die Quadratwurzeln einer Zahl a stets der Form b und p-b, die größer als 2 ist. Man kann die Quadratwurzeln einer Zahl a modulo p auch berechnen. Wenn p die Eigenschaft hat, dass p + 1 durch 4 teilbar ist, dann erhält man eine Quadratwurzel von a, indem man:

Mathematik - Natürliche Zahlen Teil 3

Bei unserem Beispiel

Für p = 19 muss man also mit (p+1)/4 = 20/4 = 5 potenzieren. Zum Beispiel ist

b = =

= = = 6 * 9 mod 19 = 16

Also ist 16 eine Quadratwurzel von 9, die andere ist 19-16 = 3. Nun betrachten wir die Quadrate modulo n, wobei n wie immer bei uns der Form n = p * q mit zwei verschiedenen Primzahlen p und q ist. Wie viele Quadratwurzeln hat ein Quadrat modulo n?

Betrachten wir dazu das Beispiel n = 5 * 7 = 35. Wenn man eine Tabelle macht, stellt man fest, dass es nicht nur zwei Sorten von Zahlen gibt (Quadrate und Nichtquadrate), sondern drei:

• Die meisten Zahlen, nämlich (2, 3, 5, 6, 7, 8, 10, 13, 17, 18, 19, 20, 22, 23, 24, 26, 27,

28, 31, 32, 33 und 34 sind keine Quadrate.

• Die Zahlen 1, 4, 9, 16 und 29 sind Quadrate - und haben vier Quadratwurzeln. Wenn

man modulo 35 rechnet, ergibt sich:

• Die restlichen Zahlen (14, 15, 21, 25, 30) sind Quadrate und haben nur zwei

Quadratwurzeln.

Die Quadrate vom letzten Typ sind Zahlen, die durch eine der beiden Faktoren p oder q teilbar sind (5, 10, 15, 20 und 25 sind Vielfache von 5; 7, 14, 21 und 28 sind durch 7 teilbar). Diese betrachten wir hier nicht. Die „wichtigsten“ Zahlen modulo n sind diejenigen, die weder durch p noch durch q teilbar sind (in unserem Beispiel sind dies die Zahlen 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34).

Kryptographie - Ein kurzer Einblick by M.K. 38

Mathematik - Natürliche Zahlen Teil 3

Von diesen Zahlen sind nicht etwa die Hälfte Quadrate, sondern nur ein Viertel - dafür hat jedes Quadrat vier Quadratwurzel! Eine Überraschung!

Wir beobachten auch, dass die vier Quadratwurzeln einer Zahl in zwei Hälften eingeteilt werden können: Wenn b eine Quadratwurzel ist, ist n-b eine andere; wenn b’ eine der anderen Quadratwurzeln ist, ist n-b’ die vierte. Die Quadratwurzeln b und n-b bzw. b’ und n-b’ unterscheiden sich nicht wesentlich, während jede Quadratwurzel aus der ersten Gruppe wesentlich verschieden von jeder aus der zweiten Gruppe ist.

Diese Tatsache gilt immer, wenn n ein Produkt von zwei verschiedenen Primzahlen ist, von denen keine gleich 2 ist.

(Wenn eine Zahl von mehr als zwei Primzahlen geteilt wird, hat ein Quadrat im allgemeinen auch mehr als vier Quadratwurzeln.)

Kryptographie - Ein kurzer Einblick by M.K. 39

Mathematik - Natürliche Zahlen Teil 4

Oft ist davon die Rede: primitive Elemente. Benötigt werden Sie für den Diffie-Hellmann-Schlüsseltausch und für das El-Gamal-Verfahren. Doch man weiß nicht so richtig wie man dies verstehen soll, geschweige denn was dies überhaupt ist.

Doch enthüllt man den Schleier dieser „Mysteriösen Zahlen“, so sieht man dass diese Zahlen doch auch wieder nichts besonderes sind. Fangen wir also gleich mal an.

Wie wir ja wissen, haben Primzahlen nur die „1“ und sich selbst als Teiler. Nun können wir einer Menge M die teilerfremden Elemente von 1..p-1 zuordnen. Halten wir also fest:

Nehmen wir z.B. die Primzahl p = 5, so werden ihr die Elemente { 1, 2, 3, 4 } zugeordnet. Der Primzahl p = 11 die Elemente { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }. Unter diesen Elementen gibt es nun eine Zahl a, welches durch die Rechnung a mod p ( 0 ≤ i ≤ p-2 ) i

alle Elemente aus M darstellen kann. Dieses a nennt sich dann primitives Element. Dies bedeutet also, dass kein Element in dieser Rechnung doppelt vorkommen darf. = ^{0 0} Nun wissen wir ja, dass (für jedes a) ist, so ist auch p a mod = 1. Kommt nun die „1“ 1 a

bei obiger Rechnung noch einmal vor, so handelt es sich nicht mehr um ein primitives Element.

a mod p, 0 < i ≤ p-2 muss! stets verschiedene Elemente Anders ausgedrückt: die Reihe i

ergeben, wobei alle „teilerfremden Elemente“ von p dargestellt werden müssen. Man kann diese Reihe auch folgendermaßen aufschreiben: − 2 2 1 0 p { p a p a p a p a mod ,..., mod , mod , mod } Ein Beispiel: Nehmen wir die Primzahl p = 5.

Die Menge der teilerfremden Elemente ist { 1, 2, 3, 4, }

Nun müssen wir für unser a zuerst die „1“, dann die „2“, dann die „3“ und zuletzt die „4“ ^{3 2 1 0} nehmen. Dann rechnen wir , , , a a a a stets mod p aus. Wird dabei Menge { 1, 2, 3, 4 } dargestellt, so haben wir ein primitives Element gefunden.

Kryptographie - Ein kurzer Einblick by M.K. 40

Mathematik - Natürliche Zahlen Teil 4

Also:

Wie wir nun sehen kommt die „1“ doppelt vor. Also ist 1 kein primitives Element von p = 5 („1“ ist von keiner Zahl ein primitives Element)

Man sieht nun, dass alle teilerfremden Elemente dargestellt werden. Somit ist „2“ ein primitives Element von p = 5.

Auch hier wird die Menge { 1, 2, 3, 4 } abgebildet. Somit ist auch „3“ ein primitives Element von p = 5.

Wie wir nun sehen, kommt die „1“ zwei mal heraus. Somit ist „4“ kein primitives Element von p = 5.

Fassen wir alles zusammen, so stellen wir fest, dass die Primzahl p = 5 die Menge der primitiven Element { 2, 3 } besitzt.

Kryptographie - Ein kurzer Einblick by M.K. 41

Mathematik - Natürliche Zahlen Teil 4

Kommen wir nun noch zu einer Formel:

Diese Formel besagt also folgendes: wenn wir für a ein primitives Element von p nehmen, dieses a hoch (p-1) rechnen und dann denn modulo p nehmen, stets 1 herauskommt. Dies ist ja auch klar, denn da wir bei einem primitiven Element durch − 2 1 0 p p a p a p a mod ,..., mod , mod schon die ganze Reihe der teilerfremden Elemente von p

dargestellt haben, sich ein Element ja nun wiederholen muß. Und zwar ist es die „1“.

Zu guter letzt stellen wir obige Formel noch einmal etwas anders (komplizierter) dar:

Auch hierzu eine kleine Erklärung, da diese Mysteriöse Formel ja nicht im Raum stehen soll: b ist also eine beliebige Zahl aus den Elementen der Primzahl p. Das a ist immer noch unser primitives Element und das i ist eine beliebige Zahl. So, nun wissen wir ja auch, dass man mit diesen primiten Elementen ( i a ) jedes Element der teilerfremden Elemente von p darstellen kann. Also gilt: ^{− − −} = = = = 1 1 1 i i p p i p mod 1 1 ) ( ) ( p a a b

Somit haben wir diesen Teil der Mathematik wieder geschafft. Ich hoffe, dass nun das Geheimnis um diese „primitiven Elemente“ ein für alle mal gelüftet ist und wir es nun wissen, womit wir es da zu tun haben.

Kryptographie - Ein kurzer Einblick by M.K. 42

Mathematik - Primitive Elemente bis p = 71

In dieser Liste sehen Sie die primitiven Elemente der Primzahlen von 1 bis 71.