Kryptographie von Cäsar bis RSA. Klassische und moderne Verfahren im Vergleich

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

1 Einleitung
1.1 Zielsetzung
1.2 Gliederung

2 Grundlagen der Kryptographie

3 Klassische Kryptographie
3.1 Cäsar-Verschlüsselung
3.1.1 Beispiel
3.1.2 Varianten
3.2 Vigenère-Verschlüsselung
3.2.1 Prinzip
3.2.2 Beispiel
3.3 Kryptoanalyse: Kasiski-Test . .
3.3.1 Historie
3.3.2 Grundprinzip
3.4 Kryptoanalyse: Friedman-Test .
3.4.1 Definition des Koinzidenzindexes .
3.4.2 Schlüssellänge eines Vigenére-Textes ermitteln

4 Moderne Kryptographie
4.1 RSA-Kryptosystem
4.1.1 Historisches
4.1.2 Effektivität der Sicherheit
4.1.3 Algorithmus und Beispiel

5 Authentifizierung
5.1 Zero-Knowledge
5.1.1 Die geheime Tür
5.1.2 Fiat-Shamir-Protokoll

6 Zusammenfassung und Ausblick

Anhang

Quellenverzeichnis

Abbildungsverzeichnis

1 Prinzip der RSA-Verschlüsselung

2 Zero Knowledge: Die geheime Tür

Tabellenverzeichnis

1 Cäsar-Verschlüsselung

2 Revertierte Cäsar-Verschlüsselung

3 Kasiski-Test

4 Friedman-Test

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Schon vor Jahrtausenden verschlüsselten Menschen Nachrichten, damit sie nicht für jedermann lesbar waren. Vor allem Könige und andere Hegemonen wollten sicher sein, den Inhalt ihrer oft wichtigen Nachrichten nicht in den Händen ihrer Feinde zu wissen. Besonders in Kriegen, seien es die überlieferten cäsarischen Kriege (u.a. Gallischer Krieg 58-51 v. Chr.) oder Kriege im 20. Jahrhundert, wie der Zweite Weltkrieg (1939-1945), spielte das Können von Kryptologen und ihren Verschlüsselungen eine wichtige Rolle. Ihnen entgegen standen stets die Kryptoanalysten und ihre Methoden, die Verschlüsselungen zu brechen. Oftmals trug entweder die eine oder die andere Seite entscheidend zum Ausgang des Krieges - Sieg oder Niederlage - bei. So lieferten sich beide Seiten über Jahrhunderte ein Kopf-an-Kopf-Rennen der Bessere von beiden zu sein.

Aber auch in der Gegenwart hat Kryptographie im Zuge der exponentiell steigenden Verbreitung von Computern, Internet und dem Zeitalter der digitalen Kommunikation einen essentiellen Stellenwert, um private Informationen sicher verbreiten und schützen zu können. Kryptographie ist alltäglich und allgegenwärtig.

1.1 Zielsetzung

Das Thema Kryptographie ist zu mächtig, um es auf diesen wenigen Seiten ausführlich zu beschreiben. Deshalb beschränkt sich diese Praxisarbeit den Vorgaben entsprechend, einen Einblick auf einige der prägnantesten Vertreter der klassischen und modernen Kryptographie, sowie der klassischen Kryptoanalyse zu geben.

1.2 Gliederung

Kapitel 2 beschreibt die elementaren Grundzüge der Kryptographie und gibt eine Synopsis relevanter Begriffe dieses Themengebietes. Das nachfolgende Kapitel 3 erläutert zwei Vertreter der klassischen Kryptographie: Die Cäsar- und die Vigènere-Verschlüsselung. Weiterhin wird auch die klassische Kryptoanalyse nach Kasiski und Friedman beschrieben. Während in Kapitel 4 ein modernes Verfahren der Kryptographie, das RSA-Kryptosystem, vor- gestellt wird, resümiert Kapitel 5 die Funktionen des Zero-Knowledge-Paradigmas am Beispiel des Fiat-Shamir-Protokolls.

Das abschließende Kapitel 6 fasst diese Arbeit zusammen und gibt einen Ausblick auf die künftige Bedeutung der Kryptographie.

2 Grundlagen der Kryptographie

Der Begriff Kryptographie, vom griechischen kryptós (dt. „verborgen“) sowie gráphein (dt. „schreiben“) stammend, bezeichnet die Wissenschaft des Verschlüsselns. Die Kryptoanalyse bezeichnet einen weiteren Teilbereich der Kryptologie. Diese hat zum Ziel, anhand verschiedener Techniken Informationen über verschlüsselte Texte zu erlangen, um diese zu brechen, d. h. in den Besitz der eigentlichen Information zu gelangen, ohne der eigentliche Empfänger zu sein.

Um eine Information bzw. einen Text zu verschlüsseln, wird neben der unverschlüsselten Nach- richt, oftmals als Klartext bezeichnet, ein Schlüssel benötigt. Anhand dieses Schlüssels, sowie bestimmten Methoden und Techniken, kann dann ein sogenannter Geheimtext, auch Chiffre genannt, erstellt werden. Dieser ergibt für einen nicht bestimmten Leser augenscheinlich zu- nächst keinen Sinn. Einzig derjenige, der im Besitz des entsprechenden Schlüssels ist, kann den verschlüsselten Text wieder in eine leserliche Form bringen. Über die Jahrtausende wurden viele verschiedene Methoden entwickelt, Nachrichten zu ver- schlüsseln und vor Dritten - insbesondere Feinden - versteckt zu halten. Genauso wurden durch Kryptoanalysten aber auch immer wieder Methoden gefunden und entwickelt, die verwendeten Geheimschlüssel zur Entzifferung der Geheimschrift herauszufinden oder die Geheimschrift auf andere Weise (z. B. durch Analyse von Häufigkeiten) zu brechen.

Seit jeher hatten die meisten Verschlüsselungsalgorithmen einen entscheidenden Vorteil, nicht oder zumindest nicht allzu schnell entschlüsselt zu werden: Die Zeit. Doch mit jeder Dekade, mit jedem Jahrhundert, das verging, erlangten die Menschen - oder prägnanter: der Kryptologe - mehr mathematisches und logisches Wissen. Im 20. Jahrhundert kam eine weitere, starke Unterstützung durch Computer zum Einsatz. Unsere aktuellen Computer werden immer schneller, immer leistungsfähiger und somit ist es wahrscheinlich wieder nur eine Frage der Zeit, bis der Faktor Zeit auch für die aktuell gängigen und als vermeintlich sicher eingestuften Algorithmen keine oder zumindest nur noch eine geringe Rolle spielt. Ein Wettlauf zwischen Kryptologen und Kryptoanalysten, welcher seit jeher existiert.

So manifestierte sich vor allem in den letzten Jahren ein Paradigma, dass bereits 1883 vom nie- derländischen Kryptologen und Linguisten Auguste Kerckhoff in seinem Werk La Cryptographie Militaire erwähnt wurde: „Die Sicherheit eines Kryptosystems darf nicht von der Geheimhal- tung des Algorithmus abhängen. Die Sicherheit gründet sich nur auf die Geheimhaltung des Schlüssels.“¹ Viele Entwickler von Verschlüsselungssystemen entschieden sich in den letzten Dekaden, ihre Algorithmen öffentlich zugänglich zu machen und ihre Sicherheit somit der breiten Masse zu unterziehen². Vor allem der Geheimhaltung des Schlüssels wurde größte Aufmerksamkeit bemessen.

Grundsätzlich unterscheidet man zwischen symmetrischen und asymmetrischen Kryptosystemen.

Während bei ersterem der gleiche Schlüssel zum Ver- und Entschlüsseln verwendet wird, ist bei asymmetrischen Verschlüsselungen ein anderer Schlüssel zum Entschlüsseln des Geheimtextes notwendig, als zum Verschlüsseln.

3 Klassische Kryptographie

3.1 Cäsar-Verschlüsselung

Die heute als Cäsar-Verschlüsselung bekannte monoalphabetische Substitution wird durch den römischen Schriftsteller Gaius Suetonius Tranquillus (70-120 n.Chr.) in seinem Werk D E V I TA CAESARUM (Cäsarenleben)³ wie folgt beschrieben [...] si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset; quae si qui investigare et persequi velit, quartam elementorum litteram, id est D pro A et perinde reliquas commutet.“

Übersetzt heißt dies soviel wie: „[...] wenn etwas Geheimes zu überbringen war, schrieb er in Zeichen, das heißt er ordnete die Buchstaben so, dass kein Wort gelesen werden konnte: Um diese zu lesen, tauscht man den vierten Buchstaben, also D für A aus und ebenso mit den Restlichen.“⁴

Cäsar verwendete eine aus heutiger Sicht einfache Verschlüsselung, bei welcher jeder Buchstabe um eine feste Länge (nämlich immer n = 3), verschoben und durch den n-ten Nachfolger ersetzt wird. Auf diese Weise konnte er durch Substitution eine Geheimschrift erstellen, welche zu entziffern die Gegner wahrscheinlich nicht im Stande waren.

Abbildung in dieser Leseprobe nicht enthalten

Tab. 1: Cäsar-Verschlüsselung

Man definiert unter dem Klartextalphabet ein Geheimtextalphabet, welches jeweils um die entsprechende Anzahl der Stellen verschoben ist. Möglich sind insgesamt 25 verschiedene Verschiebemöglichkeiten⁵.

3.1.1 Beispiel

Für folgendes Beispiel wurde, wie von Sueton beschrieben, die Verschiebelänge n = 3 gewählt, ein A wird also durch ein D ersetzt, ein B durch eine E und so weiter.

Der Klartext

„Greift im Morgengrauen an"

würde dann als Geheimtext wie folgt aussehen:

„JUHLIW LP PRUJHQJUDXHQ DQ"

Anschließend wird dieser in gleichlange Blöcke unterteilt, auch, um keine Rückschlüsse auf die

einzelnen Wortlängen zuzulassen:

„JUHLI WLPPR UJHQJ UDXHQ DQ"

3.1.2 Varianten

Die klassische Cäsar-Verschlüsselung wird auch heute noch eingesetzt: Die als ROT13 bekannte Verschiebechiffre ersetzt dabei jeden Buchstaben um dreizehn Stellen versetzt und wurde oftmals in den früheren Usenets⁶ eingesetzt. Jedoch nicht, um sicher zu verschlüsseln, sondern vielmehr um den Text zu verschleiern und den Leser somit zur Interaktion zu zwingen.

Eine Variante zur klassischen Cäsar-Verschlüsselung ist beispielsweise die revertierte CäsarVerschlüsselung⁷, bei welcher das verschobene Geheimtextalphabet in umgekehrter Reihenfolge unter das Klartextalphabet geschrieben wird.

Abbildung in dieser Leseprobe nicht enthalten

Tab. 2: Revertierte Cäsar-Verschlüsselung

3.2 Vigenère-Verschlüsselung

„Le Chiffre indéchiffrable“ (dt. “Die unentzifferbare Verschlüsselung“) Bei der Vigenère-Verschlüsselung, benannt nach dem französischen Diplomaten Blaise de Vi- genère (1523-1596), handelt es sich genau wie bei der Cäsar-Verschlüsselung (s. 3.1) um ein symmetrisches Verfahren, d. h. eine Nachricht wird mit dem gleichen Schlüssel sowohl ver-, als auch entschlüsselt.

Sie basiert zwar im Grundprinzip auf der Cäsar-Verschlüsselung, allerdings handelt es sich um eine polyalphabetische Verschlüsselung, d.h. jeder Buchstabe wird mit einer anderen Cäsar- Chiffre verschlüsselt. Damit soll die Analyse einer Buchstabenhäufigkeit und somit die Möglich- keit die Chiffre zu brechen, erschwert werden.

Lange Zeit galt diese Variante auch als sicher und „unentzifferbar“⁸. Das Gegenteil wurde erst über 300 Jahre später unabhängig voneinander durch Kasiski (s. 3.3) und Friedman (s. 3.4) bewiesen.

3.2.1 Prinzip

Die wesentliche Sicherheit der Vigenère-Verschlüsselung liegt in der Länge und Komplexität des Schlüssels. Um eine Nachricht zu verschlüsseln, wird die als Vigenère-Quadrat geläufige Tabula Recta (s. Anhang A.1) benötigt. Bei der Tabula recta werden alle Buchstaben des Alphabets quadratisch dargestellt, pro Zeile jeweils um einen Buchstaben weiter nach links verschoben. Erstmals Erwähnung fand sie im Werk „POLYGRAPHIAE LIBRI SE“ (dt. SECHS BÜCHER ZUR POLYGRAPHIE) des Benediktinerabts Johannes Trithemius (1462-1516)⁹.

3.2.2 Beispiel

Mittels der Tabula recta wird der in 3.1.1 verwendete Klartext wie folgt verschlüsselt. Als Schlüsselwort wird „HONIG“ gewählt. HONIGH ON IGHONIGHONIG HO Greift im Morgengrauen an NFRQLA WZ UUYURVMYOHMT HB Es lässt sich erkennen, dass ein Klartextbuchstabe nun (in den meisten Fällen) bei einer Wieder- holung nicht nach dem selben Buchstaben verschlüsselt wird. Im oben dargestellten Beispiel wird das „r“ aus „Greift“ z. B. nach „O“ verschlüsselt, was in einem „F“ resultiert. Bei dem Wort „Morgengrauen“ wird das erste „r“ nach „H“ verschlüsselt, was chiffriert ein „Y“ ergibt.

Eine erste Wiederholung zeigt sich aber zufälligerweise bereits beim „r“ im Teilwort „grauen“. Auch hier wird nach „H“ chiffriert, was ebenfalls ein „Y“ ergibt.

Genau an diesen „zufällig“ auftretenden Wiederholungen setzt der im nachfolgenden Abschnitt beschriebene Kasiski-Test an, um verschlüsselte Botschaften ohne Kenntnis über das Schlüssel- wort zu brechen.

Eine Vigenère-Verschlüsselung gilt nur dann als nicht zu brechen, wenn

1. der Schlüssel mindestens genau so lang wie der zu verschlüsselnde Text selbst ist
2. und der Schlüssel „zufällig“ verteilt ist, er soll also keinen Sinn ergeben (z. B. abgeschrie- bene Absätze aus einem Buch o. Ä.)

Das folgende Beispiel weist keine Wiederholungen im Schlüsselwort auf und erfüllt die genannten

Bedingungen:

Abbildung in dieser Leseprobe nicht enthalten

3.3 Kryptoanalyse: Kasiski-Test

3.3.1 Historie

Die Grundidee des Kasiski-Tests beruht auf der Wiederholung einzelner Codeblöcke.

Bereits 1854 hatte der englische Mathematiker Charles Babbage (1791-1871) eine ähnliche Methode zum Entschlüsseln des Viginère-Codes entdeckt, diese jedoch nie veröffentlicht¹⁰. So erlangte das Verfahren unter dem Namen Kasiski-Test Bekanntheit, benannt nach dem pensio- nierten preußischen Offizier Friedrich Wilhelm Kasiski (1805-1881). Dieser entwickelte das Verfahren unabhängig von Babbage und veröffentlichte es 1863 in seinem Buch Die Geheim- schriften und die Dechiffrierkunst.

3.3.2 Grundprinzip

Unter der Prämisse, die Chiffre sei nach Vigenère verschlüsselt, wird der verschlüsselte Text nach sich wiederholenden Zeichenfolgen mit einer Mindestlänge von drei Zeichen oder mehr durchsucht. Anschließend wird ihr Abstand ermittelt, indem bei der ersten Folge einschließlich des ersten Buchstabens bis zum ersten Buchstaben der zweiten Folge gezählt wird¹¹.

Hat man dies für alle gefundenen Folgen durchgeführt, werden die einzelnen Werte in ihre Primfaktoren zerlegt, womit sich gleiche Teiler relativ schnell ermitteln lassen. Ausreißer, also zufällig entstandene Übereinstimmungen, werden nicht weiter betrachtet. Nachteilig am Kasiski-Test: Es lässt sich nicht die genaue Schlüssellänge der Chiffre ermitteln, vielmehr erhält man nur das Vielfache der Schlüsselllänge. Aus diesem Grund wird der Kasiski- Test oftmals auch in kombinierter Form mit dem Friedman-Test verwendet. Zusammen ergeben sie eine recht genaue Methode, um an das Schlüsselwort zu gelangen¹².

Im Anhang B.1 wird die Analyse einer Chiffre exemplarisch beschrieben.

3.4 Kryptoanalyse: Friedman-Test

Einen anderen Ansatz verfolgt der nach dem bekannten Kryptologen William Frederick Friedman (1891-1969) benannte Friedman-Test: Zur Dechiffrierung des verschlüsselten Textes bzw. Erhalt der Schlüssellänge greift man auf mathematisch-statistische Methoden sowie einem Koinzidenz- index zurück, welchen Friedman in seiner 1922 veröffentlichten Arbeit „The index of coincidence and its applications in cryptography“ beschreibt.

3.4.1 Definition des Koinzidenzindexes

Der Koinzidenzindex I (auch IC oder κ) gründet auf der Frage nach der Wahrscheinlichkeit, dass zwei beliebig aus dem Text gegriffene Buchstaben gleich sind. Sei die Länge des Alphabetes 26 (lateinisches Alphabet) und sei n1 die Anzahl aller auftretenden „a“ , n2 die aller „b“, . . ., sowie n26 die aller auftretenden „z“¹³.

Die Länge n eines Textes definiert sich dann wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Des Weiteren gilt, die Gesamtzahl aller Buchstabenpaare sei durch

die Reihenfolge keine Rolle spielt. n1 ×(n1 −1)

Abbildung in dieser Leseprobe nicht enthalten

definiert, wobei

Für das Buchstabenpaar a . . . a gilt dann bspw.

, wobei n1 die Anzahl der Möglich-

keiten das erste „a“ und (n1 − 1) die Möglichkeiten ein weiteres „a“ zu wählen, repräsentiert.

Über das gesamte Alphabet ergibt sich damit für die Gesamtzahl aller gleichen Buchstabenpaa- re:

Abbildung in dieser Leseprobe nicht enthalten

Die Annahme, zwei beliebig gewählte Buchstaben seien gleich, berechnet sich nach dem von

Friedman definierten Koinzidenzindex damit wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Für die deutsche Sprache und einem „durchschnittlichen“ Text liegt der Koinzidenzindex bei ca. 7,62 % (κD ≈ 0, 07619), im Englischen beträgt er ca. 6,6 % (κE ≈ 0, 06577)¹⁴.

Bei zufällig verteilten Texten erhält man durch ungefähres Auflösen der Gleichung 3.3 ca. 3,85 % (s. Anhang B.2).

3.4.2 Schlüssellänge eines Vigenére-Textes ermitteln

Unter der Annahme, dass es sich um eine deutsche Vigenère-Chiffre handelt und dass I kleiner als 0,0762 ist (wäre I = 0,0762, so wäre der Text offensichtlich monoalphabetisch verschlüsselt), zerlegt man den verschlüsselten Text nun in einzelne Spalten (s. Anhang B.2.2). Jede Spalte bildet dabei eine monoalphabetische Chiffre.

Sei n die Länge des Textes und l die Schlüsselwortlänge, so ergibt sich zur annähernden Berechnung von l folgende Formel (Herleitung s. Anhang B.2.3):

Abbildung in dieser Leseprobe nicht enthalten

4 Moderne Kryptographie

4.1 RSA-Kryptosystem

Bei der RSA-Verschlüsselung, ein Public-Key Kryptosystem, handelt es sich um ein asymmetrisches Verfahren, d. h. es basiert auf dem Einsatz von Schlüsselpaaren, wobei dieses zum einen aus einem geheimen bzw. einem privaten Schlüssel (engl.: private key) und zum anderen aus einem öffentlichen Schlüssel (engl.: public key) besteht¹⁵.

Man verschlüsselt dabei mit dem öffentlich zugängigen Public Key, entschlüsselt werden kann die Nachricht jedoch nur mit dem geheimen Private Key (vgl. Anhang C).

4.1.1 Historisches

Das Prinzip der RSA-Verschlüsselung wurde 1977 von Ronald L. Rivest, Adi Shamir and Leonard M. Adleman am Massachusetts Institute of Technology (MIT) entwickelt. Ihre Überlegungen basierten dabei auf der Theorie der Public-Key-Kryptographie¹⁶ von Whitfield Diffie und Martin Hellman.

4.1.2 Effektivität der Sicherheit

Die Effektivität von Public-Key-Kryptosystemen, und damit auch die von RSA, basiert unter anderem auf mathematischen Problemen, Berechnungen in eine Richtung relativ einfach durchführen zu können, vice versa jedoch nicht¹⁷.

Dies gilt z. B. für die Multiplikation von Primzahlen, deren Produkt sich meist einfach berechnen lässt, die Zerlegung des Produktes in Primfaktoren ist bei sehr großen Primzahlen aber nicht mehr möglich. Besser gesagt, ist bis heute kein angemessener Algorithmus bekannt, der dieses in angemessener Zeit bewerkstelligen kann.

4.1.3 Algorithmus und Beispiel

Angenommen, Bob möchte an Alice¹⁸ eine Nachricht übermitteln, die von Eve¹⁹ nicht entziffert werden darf, sollte sie diese abfangen.

Die Funktionsweise des RSA-Verfahrens lässt sich nun exemplarisch am folgenden Beispiel erläutern²⁰:

1. Zunächst muss Alice zwei sehr große Primzahlen wählen. Zur vereinfachten Darstellung wird für p = 17 und für q = 11 angenommen.

2. Nun müssen diese beiden Primzahlen miteinander multipliziert werden, um das benötigte n zu erhalten:

Abbildung in dieser Leseprobe nicht enthalten

3. Als Nächstes muss ein e gefunden werden, dass als Bedingung die Teilerfremdheit mit

ϕ (n) besitzt, d. h.

Abbildung in dieser Leseprobe nicht enthalten

Sei ϕ (n) = (p − 1)(q − 1) = (17 − 1)(11 − 1) = 16 × 10 = 160, dann ergibt sich z. B. e = 3, womit beide genannten Bedingungen erfüllt sind²¹.

4. e und n stellen den öffentlichen Schlüssel (engl.: public key) dar. In Abhängigkeit von e

und ϕ (n) wird nun der private Schlüssel (engl.: private key) d wie folgt errechnet

Abbildung in dieser Leseprobe nicht enthalten

Seien e = 3 ∧ ϕ (187) = 160, so ergibt sich für d = 107.

5. Die benötigten Randbedingungen sind erfüllt und Bob kann nun mittels dem öffentlichen Schlüssel von Alice eine Nachricht wie folgt verschlüsselt übertragen:

Abbildung in dieser Leseprobe nicht enthalten

Die Nachricht wird numerisch codiert, d. h. für jeden Buchstaben bzw. jedes Zeichen wird der ASCII-Wert verwendet:

Abbildung in dieser Leseprobe nicht enthalten

F bzw. die numerische Codierung 06 wird nun verschlüsselt.

21 Es hätte u. a. für e auch jede andere Primzahl gewählt werden können, für die 1 < e < ϕ(n) gilt.

Die Bedingung m1 < n = 6 < 187 ist erfüllt.

Abbildung in dieser Leseprobe nicht enthalten

Bob erhält für c1 = 29 und verfährt mit dem restlichen Teil der Nachricht genauso. Das Ergebnis übermittelt er dann erschließend an Alice.

6. Alice kann ihrerseits die erhaltene Nachricht nun wie folgt entschlüsseln:

Abbildung in dieser Leseprobe nicht enthalten

Auch sie verfährt mit dem restlichen Teil der Nachricht (m2, m3, · · · , mn) genauso wie für m1 und erhält am Schluss die entschlüsselte Nachricht.

Da Exponenten in der modularen Arithmetik Einwegfunktionen darstellen, kann Eve die unter

Umständen abgefangene, verschlüsselte Nachricht nicht entschlüsseln. Es ist nach heutigem Stand sehr schwer bis unmöglich, von c1 = 29 auf das ursprüngliche m1 = 6 zu schließen.

5 Authentifizierung

5.1 Zero-Knowledge

Die grundlegende Idee des Zero-Knowledge-Verfahrens basiert auf dem Paradigma, das ver- wendete Geheimnis nicht preiszugeben, sondern dem Gegenüber lediglich zu zeigen, im Besitz dessen zu sein. Es dient einzig zur eindeutigen Identifizierung.

5.1.1 Die geheime Tür

Jean-Jacques Quisquater beschreibt in „HOW TO EXPLAIN ZERO-KNOWLEDGE PROTO- COLS TO YOUR CHILDREN“²² recht anschaulich die Funktionalität von Zero Knowledge.

Im Folgenden möchte Peggy Victor²³ beweisen, dass sie im Besitz des Geheimnisses ist, um durch die geheime Tür in der Höhle zu gehen. Dabei soll das Geheimnis selbst aber nicht genannt werden.

Vielmehr nimmt Peggy einen der beiden Gänge, wobei Victor nicht sehen kann, ob sie nun den linken oder den rechten Gang wählt (vgl. Anhang D). Sobald sie auf der anderen Seite angekommen ist, teilt Victor ihr mit, durch welchen Gang sie wieder zurückkommen soll. Peggy kann Glück haben und „zufällig“ genau den Gang wählen, durch welchen Victor sie zurückruft.

Beim ersten Durchgang liegt die Wahrscheinlichkeit dafür bei 50 %.

Aus diesem Grund wird das Prozedere n-fach wiederholt. Mit jedem Durchlauf, bei dem Peggy aus dem richtigen Gang wieder zurückkommt, steigt die Wahrscheinlichkeit, dass sie tatsächlich im Besitz des Geheimnisses ist, um die Tür zu öffnen, auch wenn es sich um keinen tatsächlichen Beweis handelt (z. B. könnte ein Dritter behaupten, die beiden hätten sich für alle Versuche zuvor abgesprochen).

Sei n die Anzahl der Durchläufe, bei denen Victor Peggy durch einen Gang zurückruft, dann beträgt die Wahrscheinlichkeit, dass Peggy bei 100 Wiederholungen²⁴ Glück hat und Victor täuschen kann:

Abbildung in dieser Leseprobe nicht enthalten

5.1.2 Fiat-Shamir-Protokoll

Historisches

Zu den bekanntesten Algorithmen des Zero-Knowledge-Verfahrens zählt sicherlich das Fiat- Shamir-Protokoll. Zusammen mit Amos Fiat entwarf Adi Shamir 1986 den ersten praktischen Ansatz des Zero-Knowledge-Verfahrens. Die theoretische Grundlage dafür hatten ein Jahr zuvor die amerikanischen Informatiker Shafrira „Shafi“ Goldwasser, Silvio Micali und Charles Rackoff in ihrer Abhandlung „TH E KN OW L E D G E CO M P L E X I T Y O F I N T E R AC T I V E PRO O F - SYSTEMS“ geliefert²⁵.

Das Fiat-Shamir-Protokoll basiert grundlegend auf der Schwierigkeit, Quadratwurzeln modulo n zu berechnen, wenn die Faktorisierung von n nicht bekannt ist²⁶.

Algorithmus und Beispiel

Angenommen, Peggy möchte sich gegenüber Victor authentisieren, ohne das eigentliche ver- einbarte Geheimnis preisgeben zu müssen. Das Fiat-Shamir-Protokoll definiert dabei folgende

Vorgehensweise:

1. Peggy lässt sich zunächst von Trent²⁷ ein n ausstellen, das sich als Produkt von p und q definiert. Beide Faktoren sind wie beim RSA-Verfahren sehr große Primzahlen.

Abbildung in dieser Leseprobe nicht enthalten

Zur vereinfachten Darstellung seien p = 17 und q = 11.

2. Nun muss sie ein zu n primes Geheimnis s ∈ N wählen, dass einzig ihr bekannt ist.

3. Anhand von s und n berechnet sie nun v, wobei s = 69 sei:

Abbildung in dieser Leseprobe nicht enthalten

Das erstellte v hinterlegt sie bei Trent.

4. Im Folgenden wählt Peggy eine Zufallszahl r = 34 und berechnet x, welches sie an Victor übermittelt:

Abbildung in dieser Leseprobe nicht enthalten

5. Victor wählt seinerseits nun ein Zufallsbit e ∈ {0, 1}, welches er an Peggy zurückschickt. Sei e = 1.

6. Nun muss Peggy wieder einen Wert berechnen, nämlich y, welches anschließend erneut an Victor geschickt wird.

Abbildung in dieser Leseprobe nicht enthalten

7. Victor kann Peggy nun mittels ihrem öffentlichen Schlüssel v, welchen er von Trent erhält, verifizieren. Dazu berechnet er:

Abbildung in dieser Leseprobe nicht enthalten

Peggy wurde also erfolgreich verifiziert.

Das Prozedere wird beliebig oft wiederholt. Mit jedem erfolgreichen Durchlauf n steigt bei Victor die Glaubwürdigkeit von Peggy, tatsächlich im Besitz des Geheimnisses zu sein. Angenommen n sei der Einfachheit halber 10, so ist Victor bereits zu 99,9 % sicher, dass Peggy glaubwürdig ist:

Abbildung in dieser Leseprobe nicht enthalten

[...]

---

¹ Zitiert bei: Singh (2006), S. 27

² Vgl. Hansen et al. (2009), S. 392

³ Vgl. Tranquillus, Kapitel 56, Vers 6

⁴ Vgl. Hebisch (2010b)

⁵ Das klassische römische Alphabet besteht aus 23 Buchstaben, ergo ergaben sich 22 Verschiebemöglichkeiten. Vgl. Hebisch (2010)

⁶ Vgl. Schneier (1996), S. 11

⁷ Vgl. Hebisch (2010b)

⁸ Vgl. Beutelspacher (2002), S. 31 f.

⁹ Vgl. Hebisch (2010a)

¹⁰ Vgl. Singh (2006), S. 105 f.

¹¹ Vgl. Ertel (2007), S. 38 f.

¹² Vgl. Bronstein et al. (2008), S. 389 f.

¹³ Vgl. Ertel (2007), S. 42 f.; und Völler (2003), S. 80 ff.

¹⁴ Vgl. Bauer (2000), S. 326

¹⁵ Vgl. Hansen et al. (2009), S. 393 f.

¹⁶ DIFFIE, WHITFIELD UND HELLMANN, MARTIN: New directions in cryptography (1976)

¹⁷ Vgl. Zimmermann (1998), S. 111

¹⁸ Die Namen Bob und Alice symbolisieren in der Literatur Sender und Empfänger.

¹⁹ Eve (vom engl. eavesdropper, dt. Lauscher.) stellt in der Literatur einen passiven Angreifer dar. Sie versucht, Nachrichten abzuhören, kann diese jedoch nicht verändern

²⁰ Das Beispiel basiert auf den Angaben von Singh (2006), S. 436 ff.; sowie Hansen et al. (2009), S. 394

²¹ Es hätte u. a. für e auch jede andere Primzahl gewählt werden können, für die 1 [Abbildung in dieser Leseprobe nicht enthalten] gilt.

²² Vgl. Quisquater et al. (1989), S. 628 ff.

²³ Peggy: vom engl. prover, steht für den Beweiser; Victor: vom engl. verifier, steht für den Prüfer

²⁴ Vgl. Ertel (2007), S. 105

²⁵ Vgl. Beutelspacher (2002), S. 91

²⁶ Vgl. Fiat et al. (1987), S. 187

²⁷ Vom engl. TRusted ENTity, steht für eine dritte, vertrauenswürdige Instanz wie bspw. ein Notar