Benutzer:Didia/DHM

Diffie-Hellman-Schlüsselaustausch

Geschichte und Bedeutung

Beim Diffie-Hellman-Schlüsseltausch handelt es sich um das erste der sogenannten asymmetrischen Kryptoverfahren (auch Public-Key-Kryptoverfahren), das veröffentlicht wurde. Es löst das Schlüsseltauschproblem, indem es ermöglicht, geheime Schlüssel über nicht-geheime, also öffentliche Kanäle zu vereinbaren.

Den ersten Schritt zur Entwicklung asymmetrischer Verfahren machte Ralph Merkle 1974 mit dem nach ihm benannten Merkles Puzzle, das aber erst 1978 veröffentlicht wurde. Unter dem Einfluss dieser Arbeit entwickelten Whitfield Diffie und Martin Hellman im Jahr 1976 den Diffie-Hellman-Schlüsselaustausch. Sie veröffentlichten die Forschungsarbeit unter dem Titel „New Directions in Cryptography“. Das Verfahren sorgte für einen gewaltigen Schub in der Kryptographie, eine Wissenschaft, die damals noch nicht sehr lange öffentlich betrieben wurde. Ursprünglich nannten die Forscher das Verfahren ax1x2. Martin Hellman schlug 2002 vor, das Verfahren Diffie-Hellman-Merkle-Schlüsseltausch zu nennen, „wenn schon Namen damit verbunden werden“, in Anerkennung von Ralph Merkles Anteil an der Entwicklung asymmetrischer Verfahren.

Badach und Hoffmann beurteilen die Bedeutung dieser Entwicklung folgendermassen:

„Die Entwicklung der asymmetrischen Verschlüsselung hat für die Kryptographie eine vergleichbare Bedeutung wie die Kopernikanische Wende für die Astronomie und stellt neben der Digitalisierung der Informationen und dem Internet als Kommunikationsplattform ein Fundament des dritten Jahrtausends dar.“

Whitfield Diffie und Martin Hellman prägten mit dem Verfahren auch einen neuen Sicherheitsbegriff in der Kryptographie, der darauf basiert, dass kein effizienter Algorithmus für die Kryptoanalyse existiert: Ein Kommunikationsprotokoll ist sicher, wenn dessen Kryptoanalyse so viel Zeit und Arbeit bedeutet, dass diese in der Praxis nicht ausgeführt werden kann. Die Sicherheit des Diffie-Hellman-Schlüsseltauschs beruht entscheidend darauf, dass die diskrete Exponentialfunktion eine Einwegfunktion (engl. one-way function) ist, d.h. eine Funktion, die „leicht“ berechenbar, aber nur „schwer“ umzukehren ist.

Die Forscher führten in der fundamentalen „New Directions“-Arbeit auch das Konzept einer digitalen Signatur ein: Ein Sender berechnet mit Hilfe eines geheimen Signaturschlüssels (dem Private Key) zu einer digitalen Nachricht (d. h. zu beliebigen Daten) einen Wert, der digitale Signatur genannt wird. Dieser Wert ermöglicht es jedem, mit Hilfe des öffentlichen Verifikationsschlüssels (dem Public Key) die nichtabstreitbare Urheberschaft und Integrität der Nachricht zu prüfen. So entstand als Weiterentwicklung des Diffie-Hellman-Schlüsseltauschs eine vielfältige Familie an digitalen Signaturen auf Basis des diskreten Logarithmus. Zu den Bekanntesten gehören das Elgamal-Signaturverfahren und der Digital Signature Algorithm.

Neben der Einwegfunktion entwickelten Whitfield Diffie und Martin Hellman auch das Konzept der Falltür (engl. trapdoor). Das ist eine „versteckte Abkürzung“ durch eine Zusatzinformation, mit der die ansonsten schwierige Umkehrung einfach gemacht wird. Auf der Basis von Falltürfunktionen lassen sich asymmetrische Verfahren entwickeln, bei denen die Übertragung eines gehemen Schlüssels nicht mehr notwendig ist. Damit leisteten sie auch wichtige Vorarbeiten zur Entwicklung des RSA-Kryptosystem. Ronald L. Rivest, Adi Shamir und Leonard Adleman versuchten eigentlich zu beweisen, dass es ebensolche Falltürfunktionen nicht geben kann. Bei den Beweisversuchen stiessen sie jedoch tatsächlich auf eine solche Einwegfunktion mit Falltür. Das führte 1977 zur Entwicklung des berühmtesten Public-Key-Algorithmus, des nach den Initialen seiner Erfinder so genannten RSA-Kryptosystems.

Unterschiedliche Varianten des Diffie-Hellman-Verfahrens werden heute für die Schlüsselverteilung in den Kommunikations- und Sicherheitsprotokollen des Internet eingesetzt, wie z.B. IPSec (Internet Protocol Security), IPv6 (Internet Protocol Version 6) und TLS (Transport Layer Security). Diese dienen zur Sicherung bei der Übertragung von Datenpaketen der IP-Protokollschicht bzw. von Daten der Anwendungsebene, beispielsweise in den Bereichen des elektronischen Handels. Dieses Prinzip der Schlüsselverteilung besitzt damit eine wichtige praktische Bedeutung. Der hier automatisch berechnete Schlüssel wird dann als Schlüssel für ein schnelles symmetrisches Verfahren wie Data Encryption Standard (DES) oder Advanced Encryption Standard (AES) verwendet.

Das Konzept der Public-Key-Kryptographie und einige spezifische Methoden waren bis 1997 durch die U.S. Patente 4'200'770 (Hellman, Diffie, Merkle, 1980) und 4'218'582 (Hellman, Merkle, 1980) geschützt, die der Stanford University gehören. Für die Entwicklung der Public-Key-Kryptographie und der digitalen Signatur erhielten Whitfield Diffie und Martin Hellman im Jahr 2015 den Turing Award verliehen, der als höchste Auszeichnung in der Informatik gilt, vergleichbar dem Nobelpreis oder der Fields-Medaille.

Wie erst 1997 bekannt wurde, hatte das britische Government Communications Headquarters (GCHQ) schon in den 1960er Jahren den Auftrag erteilt, zur Vermeidung der hohen Kosten bei der damals üblichen Schlüsselverteilung einen anderen Weg für die Schlüsselverteilung zu finden. Die hierzu von James H. Ellis, Clifford Cocks und Malcolm J. Williamson geäußerten Ideen ähnelten dem Diffie-Hellman-Verfahren. Das GCHQ hat einerseits wegen der Geheimhaltung, andererseits wegen des für die Briten aus Sicht der frühen 1970er Jahre fraglichen Nutzens nie ein Patent beantragt.

• 
  Ralph Merkle
• 
  Whitfield Diffie
• 
  Martin Hellman

Theoretische Grundlagen

Schlüsseltauschproblem

Verschlüsselung und Entschlüsselung mit demselben Schlüssel

Alice und Bob sind Synonyme für Sender und Empfänger einer Nachricht. Mallory steht für einen Lauscher oder Angreifer, der versucht Nachrichten mitzuhören oder zu manipulieren.

Verschlüsselungsverfahren, bei denen zwei Teilnehmer denselben geheimen Schlüssel verwenden, nennt man symmetrische Verfahren. Seien Alice und Bob Sender und Empfänger von Nachrichten über einen abhörbaren Kanal und sei Mallory ein „Bösewicht“, der Nachrichten mitlesen und manipulieren kann. Bei einem guten Verschlüsselungsverfahren ist es für Mallory unmöglich, eine Nachricht ohne Kenntnis des Schlüssels zu entschlüsseln, selbst wenn er das Verschlüsselungsverfahren genau kennt. So besagt Kerckhoffs’ Prinzip, dass die Sicherheit eines Verfahrens allein auf der Geheimhaltung eines Schlüssels beruhen muss (und nicht auf der Geheimhaltung des Verschlüsselungsalgorithmus). Eine Nachricht, die Verschlüsselt wird, heisst Klartext, der verschlüsselte Text Geheimtext.

Wichtige Voraussetzung für eine sichere symmetrische Kommunikation ist also, dass der Schlüssel zwischen Alice und Bob bereits über einen sicheren Weg ausgetauscht wurde, beispielsweise durch einen vertrauenswürdigen Kurrier oder bei einem direkten Treffen. Beim Schlüsseltauschproblem stellt sich nun folgendes Problem: Alice will mit Bob, der sich beispielsweise in Übersee befindet, mit einem symmetrischen Verschlüsselungsverfahren kommunizieren. Die beiden sind über eine unsichere Leitung verbunden und haben noch keinen Schlüssel ausgetauscht. Wie tauscht nun Alice mit Bob über einen unsicheren Kanal einen Schlüssel aus?

Der manuelle Schlüsselaustausch hat ausserdem den Nachteil, dass er recht unübersichtlich wird, wenn eine grössere Anwendergruppe untereinander verschlüsselt kommunizieren will. Bei $n$ Kommunikationspartnern sind $n*(n-1)/2$ Schlüssel erforderlich, wenn jeder mit jedem kommunizieren will. Bei 50 Kommunikaitonspartnern wären somit insgesamt 1'225 Schlüssel nötig.

Das Deffie-Hellman-Verfahren liefert eine elegante Lösung für diese Probleme: Es erlaubt Alice und Bob, einen geheimen Schlüssel über die öffentliche, nicht gesicherte Leitung zu berechnen, ohne dass Mallory den Schlüssel erfährt.

Einwegfunktionen

Funktion und Umkehrfunktion

Eine Einwegfunktion ist eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist. Eine mathematische Einwegfunktion $f:X\to Y$ muss folgende Eigenschaften aufweisen:

• Die Berechnung des Funktionswerts $y=f(x)$ ist „einfach“, d. h. es existiert ein Algorithmus, der ihn in Polynomialzeit berechnen kann.
• Die Berechnung der Umkehrfunktion zu einem gegebenen Funktionswert $y$, d. h. einem $x$, sodass $f^{-1}(y)=x$, ist allerdings „schwer“, d. h. es existiert kein „schneller“ Algorithmus für dieses Problem. „Schnell“ meint hier einen probabilistischen Algorithmus, der in Polynomialzeit läuft.

Eine Einwegfunktion funktioniert wie eine Einbahnstrasse: Eine Richtung geht einfach, die andere nicht.

Einen anschaulichen Vergleich bietet ein klassisches Papier-Telefonbuch einer größeren Stadt: Die auszuführende Funktion ist die, einem Namen die entsprechende Telefonnummer zuzuordnen. Da die Namen alphabetisch geordnet sind, lässt sich dies ziemlich schnell durchführen. Aber ihre Invertierung, also die Zuordnung eines Namens zu einer gegebenen Telefonnummer, ist offensichtlich viel schwieriger.

Man kann zeigen, dass Einwegfunktionen genau dann existieren, wenn die berühmte Vermutung aus der Komplexitätstheorie P ≠ NP gilt (siehe P-NP-Problem). Obwohl die Einwegfunktionen in der Kryptographie eine wichtige Rolle spielen, ist also bis heute nicht bekannt, ob sie im streng mathematischen Sinne überhaupt existieren.

Die Sicherheit des Diffie-Hellman-Schlüsseltauschs basiert auf der Verwendung des diskreten Logarithmus als Einwegfunktion. Es gibt auch keine Falltür, d.h. eine Zusatzinformation, mit der die Umkehrfunktion leicht zu berechnen wäre. Im Gegensatz dazu verwendet beispielsweise das RSA-Kryptosystem mit der Faktorisierung eine Einwegfunktion mit Falltür.

Diskrete Exponentialfunktion und diskreter Logarithmus

Die diskrete Exponentialfunktion

$b^{x}\ {\bmod {\ }}m$

liefert den Rest bei Division von $b^{x}$ durch m. Die Umkehrung der diskreten Exponentialfunktion heißt diskreter Logarithmus.

Die diskrete Exponentialfunktion ist auch für große Exponenten effizient berechenbar. Selbst für über hundert Bit lange Zahlen ist bei geschickter Implementierung eine Sekunde auf einem PC ausreichend. Zur effizienten Berechnung kann der Satz von Euler und das Square & Multiply-Verfahren verwendet werden.

Für die Umkehrung, also die Berechnung des Exponenten $x$, bei gegebener Basis $b$, Modul $m$ und gewünschtem Ergebnis, ist allerdings bis heute kein schneller Algorithmus bekannt: Selbst mit grösstem Hardwareaufwand und den besten bekannten Algorithmen erreicht man bei mehreren Tausend Bit schnell Berechnungszeiten, die über die Lebensdauer unseres Universums hinausgehen.

Bei der diskreten Exponentialfunktion $f(x)=b^{x}\ {\bmod {\ }}m$ handelt es sich nach heutigem Kenntnisstand somit um eine Einwegfunktion. Da es jedoch keinen mathematischen Beweis für deren Existenz gibt, wäre es theoretisch möglich, dass eines Tages ein schnelles Verfahren zur Berechnung des diskreten Logarithmus gefunden wird. Da dies jedoch schon seit längerem erfolglos versucht wird, kann man annehmen, dass dieser Fall nie eintreten wird.

Beispiel:

Die diskrete Exponentialfunktion $f(x)=3^{x}\ {\bmod {\ }}7$ ordnet einem $x$ das Ergebnis von $3^{x}\ {\bmod {\ }}7$ zu. Bei der Rechnung ${\bmod {\ }}7$ wird jeweils der Rest bezüglich des Moduls $m=7$ gebildet. Dadurch entsteht ein endlicher Zahlenraum $[0,6]$. Für die Werte $x\neq 0$ ist die Abbildung eindeutig. Der diskrete Logarithmus ist die Umkehrfunktion, also die Zuordnung von $f(x)$ nach $x$.

Gruppentheorie

Eine Gruppe ist ein Paar $(G,*)$, bestehend aus einer Menge $G$ und einer assoziativen Verknüpfung $*$ auf $G$, die ein neutrales Element hat und für die jedes Element von $G$ ein inverses Element besitzt. Wenn für eine Gruppe zusätzlich das Kommutativgesetz gilt, spricht man von einer abelschen Gruppe. Eine Untergruppe $(U,*)$ einer Gruppe $(G,*)$ ist eine Teilmenge $U$ von $G$, die bezüglich der Verknüpfung $*$ selbst wieder eine Gruppe ist.

Beispielsweise bildet die Menge der ganzen Zahlen mit der Addition als Verknüpfung die (abelsche) Gruppe $(\mathbb {Z} ,+)$. Das neutrale Element der Addition ist die $0$ (Null) und das additiv Inverse einer Zahl $a$ ist ihre Gegenzahl $-a$. Die ganzen Zahlen $\mathbb {Z}$ sind bezüglich der Addition wiederum eine Untergruppe der rationalen Zahlen $\mathbb {Q}$. Demgegenüber bilden die rationalen (und ganzen) Zahlen zusammen mit der Multiplikation keine Gruppe, weil die Zahl $0$ kein inverses Element bezüglich der Multiplikation besitzt. Wenn man jedoch $0$ aus $\mathbb {R}$ entfernt, erhält man die (abelsche) Gruppe $(\mathbb {R} -\{0\},\cdot )$.

Eine zyklische Gruppe ist eine Gruppe, deren Elemente als Potenz eines ihrer Elemente dargestellt werden können. Unter Verwendung der multiplikativen Notation lauten die Elemente einer zyklischen Gruppe

$\ldots ,a^{-3},a^{-2},a^{-1},e=a^{0},a,a^{2},a^{3},\ldots$,

wobei $a^{-2}=a^{-1}\cdot a^{-1}$ meint und $e$ das neutrale Element der Gruppe bezeichnet. Das Element $a$ wird Erzeuger oder Primitivwurzel der Gruppe genannt. Eine zyklische Gruppe besteht also nur aus Potenzen des Erzeugers $a$:

$\left\langle a\right\rangle :=\lbrace a^{n}\mid n\in \mathbb {Z} \rbrace .$

Die prime Restklassengruppe ist die Gruppe der primen Restklassen bezüglich eines Moduls $n$. Sie wird als $\mathbb {Z} _{n}^{*}$ oder $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ notiert. Die primen Restklassen sind genau die multiplikativ invertierbaren Restklassen und sind daher endliche abelsche Gruppen bezüglich der Multiplikation. Die Menge $\mathbb {Z} _{8}=\{0,...,7\}$ bildet beispielsweise mit der Multiplikation modulo $8$ als Verknüpfung keine Gruppe, selbst wenn die $0$ ausgenommen wird. Es gibt noch weitere Zahlen, die kein inverses Element haben, nämlich $2$, $4$ und $6$. Dies sind genau die Zahlen, die einen echten Teiler mit $8$ gemeinsam haben. Die verbleibenden Elemente bilden schliesslich die Multiplikative Gruppe $\mathbb {Z} _{8}^{*}$.

In der Kryptographie sind vor allem jene Zahlen $n$ von Interesse, für die alle Zahlen zwischen $1$ und $n-1$ ein inverses Element modulo $n$ haben. Dies ist genau dann der Fall, wenn $n$ eine Primzahl ist (weshalb man $p$ statt $n$ schreibt). Die Zahlen zwischen $1$ und $p-1$ bilden also zusammen mit der Modulo-Multiplikation die Gruppe $Z_{p}^{*}$. Eine weitere Aussage, die sich beweisen lässt: Nimmt man ein beliebiges Element $a$ aus $Z_{p}^{*}$ und betrachtet die Menge $\{a,a^{2},a^{3},...,a^{p-1}({\bmod {\ }}p)\}$, dann erhält man eine Untergruppe (mit $a$ als Generator der Untergruppe). Jede Untergruppe von $Z_{p}^{*}$ hat mindestens einen Generator, und damit auch $Z_{p}^{*}$ selbst. Die Gruppe $Z_{p}^{*}$ ist also zyklisch. Zum Beispiel ist $Z_{13}^{*}$ eine zyklische Gruppe mit der $2$ als Generator, denn jede Zahl von $1$ bis $12$ lässt sich als Potenz von $2$ darstellen:

Darstellung der zyklischen Gruppe $\mathbb {Z} _{13}^{*}$ mit Exponent $a$ ausserhalb und den entsprechenden Werten innerhalb der Knoten.

• $1=2^{12}\ {\bmod {\ }}13$
• $2=2^{1}\ {\bmod {\ }}13$
• $3=2^{4}\ {\bmod {\ }}13$
• $4=2^{2}\ {\bmod {\ }}13$
• $5=2^{9}\ {\bmod {\ }}13$
• $6=2^{5}\ {\bmod {\ }}13$
• $7=2^{11}\ {\bmod {\ }}13$
• $8=2^{3}\ {\bmod {\ }}13$
• $9=2^{8}\ {\bmod {\ }}13$
• $10=2^{10}\ {\bmod {\ }}13$
• $11=2^{7}\ {\bmod {\ }}13$
• $12=2^{6}\ {\bmod {\ }}13$

Für $a=3$ als Generator erhält man dagegen nur die Untergruppe mit den Elementen $\{1,3,9\}$:

• $1=3^{3}\ {\bmod {\ }}13=3^{6}\ {\bmod {\ }}13=3^{9}\ {\bmod {\ }}13=3^{12}\ {\bmod {\ }}13$
• $3=3^{1}\ {\bmod {\ }}13=3^{4}\ {\bmod {\ }}13=3^{7}\ {\bmod {\ }}13=3^{10}\ {\bmod {\ }}13$
• $9=3^{2}\ {\bmod {\ }}13=3^{5}\ {\bmod {\ }}13=3^{8}\ {\bmod {\ }}13=3^{11}\ {\bmod {\ }}13$

Es lässt sich nun leicht nachvollziehen, dass die Gleichung $a^{x}=b\ {\bmod {\ }}p$ immer lösbar ist, wenn $a$ ein Generator von $\mathbb {Z} _{p}^{*}$ ist, wobei dann $b$ ein Element von $\mathbb {Z} _{p}^{*}$ ist (ausser $0$). Der diskrete Logarithmus existiert also in $Z_{p}^{*}$ immer dann, wenn die Basis ein Generator von $Z_{p}^{*}$ ist. Stellt man die Zahlen in einem Kreis (Zyklus) der Potenzen dar, scheinen sie willkürlich verteilt zu sein. Dies gibt zumindest eine Vorstellung davon, weshalb der diskrete Logarithmus so aufwändig zu bestimmen ist.

Funktionsweise

Prinzip des Diffie-Hellman-Schlüsselaustauschs

Die beiden Kommunikationspartner Alice und Bob wollen über ein unsicheres Medium, etwa eine Kabel- oder Funkverbindung, verschlüsselt kommunizieren. Dazu soll ein symmetrisches Kryptosystem eingesetzt werden, für das beide jedoch zunächst einen gemeinsamen geheimen Schlüssel benötigen. Das Diffie-Hellman-Kommunikationsprotokoll sorgt dafür, dass sie einen geheimen Schlüssel berechnen können, ohne dass Dritte (Mallory) diesen erfahren können. Den auf diese Weise errechneten Schlüssel können sie dann in Zukunft verwenden, um verschlüsselt mit einem symmetrischen Kryptosystem zu kommunizieren.

1. Alice und Bob einigen sich zunächst öffentlich auf eine grosse Primzahl $p$ und eine natürliche Zahl $g$, die kleiner als $p$ ist. Sich öffentlich darauf einigen bedeutet, dass jeder diese beiden Zahlen kennen darf (also auch der potenzielle Lauscher Mallory). Idealerweise handelt es sich bei $g$ um einen Erzeuger der zyklischen Gruppe $\mathbb {Z} _{p}$, das Verfahren funktioniert aber auch, wenn $g$ einen anderen Wert kleiner $p$ annimmt. In der Praxis ist es ohnehin meist so, dass $g$ und $p$ vorgegeben sind und von vielen Anwendern verwendet werden.
2. Alice und Bob erzeugen jeweils eine geheimzuhaltende Zufallszahl (privater Schlüssel) $a$ bzw. $b$ aus der Menge $\{1,\ldots ,p-1\}$. $a$ und $b$ werden nicht übertragen, bleiben also dem jeweiligen Kommunikationspartner, aber auch potenziellen Lauschern, unbekannt. Nur Alice kennt die Zahl $a$ und nur Bob kennt die Zahl $b$.
3. Alice berechnet mit ihrer geheimen Zahl den öffentlichen Schlüssel $A=g^{a}\ {\bmod {\ }}p$ und schickt $A$ an Bob. Bob berechnet mit seiner geheimen Zahl den öffentlichen Schlüssel $B=g^{b}\ {\bmod {\ }}p$ und schickt $B$ an Alice.
4. Alice erhält $B$ von Bob und berechnet mit ihrem privaten Schlüssel $a$ die Zahl $K_{1}=B^{a}\ {\bmod {\ }}p$. Bob berechnet mit dem erhaltenen $A$ und seinem privaten Schlüssel $b$ ebenfalls die Zahl $K_{2}=A^{b}\ {\bmod {\ }}p$. Da $K_{1}=K_{2}$ gilt, haben beide die gleiche Zahl berechnet. Diese ist somit der gesuchte gemeinsame Schlüssel $K$.

Nur Alice und Bob kennen $K$. Mallory kann aus der abgehörten Kommunikation $K$ nicht berechnen. Dazu müsste er den diskreten Logarithmus lösen, was nach heutigem Kenntnisstand nicht möglich ist, wenn die Zahlen genug gross sind. Alice und Bob können also $K$ gefahrlos für eine symmetrische Verschlüsselung nutzen.

Dass beide Kommunikationspartner denselben Wert für $K$ berechnen, zeigen die folgenden beiden Restklassengleichungen:

$K_{1}=B^{a}\ {\bmod {\ }}p=(g^{b}\ {\bmod {\ }}p)^{a}\ {\bmod {\ }}p=(g^{b})^{a}\ {\bmod {\ }}p=g^{ba}\ {\bmod {\ }}p$.

$K_{2}=A^{b}\ {\bmod {\ }}p=(g^{a}\ {\bmod {\ }}p)^{b}\ {\bmod {\ }}p=(g^{a})^{b}\ {\bmod {\ }}p=g^{ab}\ {\bmod {\ }}p$.

Da die Multiplikation kommutativ ist, gilt des weiteren

$g^{ba}\ {\bmod {\ }}p=g^{ab}\ {\bmod {\ }}p$

und somit

$K_{1}=K_{2}$.

Alice und Bob erhalten also nach ihren jeweiligen Berechnungen die genau gleiche Zahl, nämlich den geheimen Schlüssel $K=K_{1}=K_{2}$.

Beispiel:

TBD

Sicherheit

Diffie-Hellman-Problem

Computational-Diffie-Hellman-Problem (CDH)

Angenommen, der Lauscher Mallory erfährt an der unsicheren Leitung die Zahlen $p$, $g$, $A$ und $B$, aber nicht die diskreten Logarithmen $a$ von $A$ und $b$ von $B$ zur Basis $g$. Mit der Kenntnis von $a$ und $b$ wäre es für ihn eine leichte Aufgabe, den Schlüssel $K=g^{ab}\ {\bmod {\ }}p$ zu bestimmen. Die Zahlen $a$ und $b$ herauszufinden ist jedoch sehr schwer, wenn die Zahlen $p$, $a$ und $b$ sehr gross sind, beispielsweise Zahlen mit mehreren hundert Dezimalstellen. Aus dieser Problemstellung ergibt sich das Computational-Diffie-Hellman-Problem:

Wenn ein Element $g$ einer Gruppe und die Werte $A=g^{a}$ und $B=g^{b}$ gegeben sind, welchen Wert hat dann $K=g^{ab}$, mit $a,b$ unbekannt ?

Da dieses Problem in bestimmten Gruppen nur mit enormem Rechenaufwand zu lösen ist, kann ein Angreifer aus den beiden beim Diffie-Hellman-Schlüsselaustausch übertragenen Nachrichten nicht den erzeugten Schlüssel berechnen.

Das Diffie-Hellman-Problem ist eng verwandt mit dem Diskreter-Logarithmus-Problem. Diskrete Logarithmen zu berechnen ist die einzige bekannte Methode, um das Diffie-Hellman-Verfahren zu brechen. Solange dies nicht in vertretbarer Zeit lösbar ist, ist es für einen Angreifer unmöglich, den geheimen Schlüssel zu bestimmen. Es ist allerdings nicht bewiesen, dass dies tatsächlich die einzige Methode ist, ob also jemand, der das Diffie-Hellman-Problem lösen könnte, auch diskrete Logarithem effizient berechnen könnte. Ueli Maurer hat gezeigt, dass beide Probleme zumindest unter bestimmten Voraussetzungen äquivalent sind.

Decisional-Diffie-Hellman-Problem (DDH)

Soll es für einen Angreifer unmöglich sein, aus den öffentlich verfügbaren Inforamtionen irgendwelche Informationen über den transportierten Schlüssel zu gewinnen, muss das Decisional-Diffie-Hellman-Problem (DDH) unangreifbar sein. Dieses Problem lässt sich folgendermassen beschreiben:

Ein Angreifer erhält drei Zahlen: $A=g^{a}\ {\bmod {\ }}p$, $B=g^{b}\ {\bmod {\ }}p$ und $C=g^{c}\ {\bmod {\ }}p$. Dabei wurden entweder $a$, $b$ und $c$ zufällig und gleichverteilt in $\{0,...,p-2\}$ gewählt oder $c=ab\ {\bmod {\ }}(p-1)$ gesetzt. Im zweiten Fall heisst $(A,B,C)$ Diffie-Hellman-Tripel. Der Angreifer muss entscheiden, ob ein solches Tripel vorliegt oder nicht. Kann er das nicht, ist es ihm unmöglich, aus $g^{a}$ und $g^{b}$ Rückschlüsse auf $g^{ab}$ zu ziehen.

Das Problem besteht also darin, bei gegebenem $g^{a}\ {\bmod {\ }}p$, $g^{b}\ {\bmod {\ }}p$ und $g^{c}\ {\bmod {\ }}p$ zu entscheiden, ob $g^{c}=g^{ab}$ ist.

Wer das Computational-Diffie-Hellman-Problem lösen kann, ist offensichtlich auch dazu in der Lage, das Decisional-Diffie-Hellman-Problem zu lösen. Für den umgekehrten Fall ist das nicht klar.

Bei einer Auswahl von $g$ als Primitivwurzel kann das Decisional-Diffie-Hellman-Problem angegriffen werden. Dies liegt in folgendem Theorem begründet:

Sei $p$ eine Primzahl, sei $g$ eine Primitivwurzel modulo $p$ und seien $a,b\in \{0,...,p-2\}$. Dann ist $g^{ab}$ genau dann ein quadratischer Rest modulo $p$, wenn $g^{a}$ oder $g^{b}$ ein quadratischer Rest ist modulo $p$.

Das Theorem folgt daraus, dass eine Potenz von $g$ genau dann ein quadratischer Rest modulo $p$ ist, wenn der Exponent gerade ist.

Ein Angreiffer kann also prüfen, ob das Kriterium aus diesem Theorem erfüllt ist. Er kann zwar nicht immer entscheiden, ob ein Diffie-Hellman-Tripel vorliegt, er antwortet aber zu 75% richtig. Sein Vorteil gegenüber reinem Raten beträgt also 50%.

Wahl der Zahlen

Diffie-Hellman-Primzahl p

Die Sicherheit des Verfahrens basiert nicht zuletzt auf der Länge der gewählten Zahlen. So muss die Primzahl $p$ dermassen gewählt werden, dass diskrete Logarithmen modulo $p$ mit derzeit bekannten Methoden nicht (effizient genug) berechnet werden können. Je grösser die verwendete Primzahl, desto sicherer das Verfahren, aber auch desto aufwendiger. Das Bundesamt für Sicherheit in der Informationstechnik empfiehlt für $p$ eine Schlüssellänge von mindestens 2000 Bit (Stand 2016).

Die Diffie-Hellman-Primzahl $p$ muss zudem so gewählt werden, dass Algorithmen zur Berechnung des diskreten Logarithmus kein leichtes Spiel haben. So muss beispielsweise vermieden werden, dass $p-1$ nur kleine Primfaktoren hat. Ansonsten kann nämlich der Pohlig-Hellman-Algorithmus angewendet werden, der nicht von der Gruppenordnung, sondern vom größten Faktor der Gruppenordnung abhängt. Ausserdem sollte $p$ für das Zahlkörpersieb möglichst ungeeignet sein. Dies ist der Fall, wenn es ein irreduzibles Polynom vom Grad 5 gibt, das sehr kleine Koeffizienten und eine Nullstelle ${\bmod {\ }}p$ hat.

Generator g

Die Zahl $g$ sollte so gewählt werden, dass alle Zahlen zwischen $1$ und $p-1$ als Resultat der modularen Potenz $g^{a}\ {\bmod {\ }}p$ in Frage kommen. Erst dann ist es zu aufwändig, alle Zahlen durchzuprobieren, wenn ausserdem die Primzahl $p$ gross genug gewählt worden ist. Diese Eigenschaft erfüllt die Zahl $g$, wenn sie ein Generator der Gruppe $\mathbb {Z} _{p}^{*}$ ist. Wenn Alice und Bob beispielsweise $g=1$ wählen, so funktioniert das Verfahren zwar noch immer, doch der Schlüssel $K$ ist auf jeden Fall $1$, denn $1$ ist genau der Generator der Untergruppe von $\mathbb {Z} _{p}^{*}$ mit einem Element. Ähnlich unsicher ist das Verfahren, wenn Alice und Bob für $g$ einen Generator einer anderen kleinen Untergruppe wählen. Bei einem Generator einer grossen Untergruppe ist das Verfahren sicherer, am besten wird aber gleich ein Generator der ganzen Gruppe gewählt. Da die Hälfte aller Zahlen kleiner $p$ solche Generatoren sind, gibt es genug Auswahl.

Seitenkanalangriffe

Ein Seitenkanalangriff bezeichnet eine kryptoanalytische Methode, die die physische Implementierung eines Kryptosystems in einem Gerät (z. B. einer Chipkarte, eines Security-Tokens oder eines Hardware-Sicherheitsmoduls) oder in einer Software ausnutzt. Dabei wird nicht das kryptographische Verfahren selbst, sondern nur eine bestimmte Implementierung angegriffen. Das Prinzip beruht darauf, ein kryptographisches Gerät bei der Ausführung der kryptologischen Algorithmen zu beobachten und Korrelationen zwischen den beobachteten Daten und dem verwendeten Schlüssel zu finden.

Zeitangriff

Im Jahr 1995 veröffentlichte Paul Kocher eine neuartige Methode, mit der es ihm gelang, Implementierungen von Diffie-Hellman, RSA und DSA zu brechen: der Zeitangriff (timing attack).

Ziel des Zeitangriffs ist die diskrete Exponentialfunktion. Wenn eine Krypto-Implementierung $g^{a}\ {\bmod {\ }}p$ für irgendwelche grösseren Zahlen $g$, $a$ und $p$ berechnet, dann geschieht dies fast immer mit dem Square-and-Multiply-Algorithmus. Bei diesem ist für jedes Bit von $a$ eine Aktion festgesetzt: Hat das gerade bearbetete Bit den Wert $1$, dann ist diese Aktion eine Multiplikation, ansonsten eine Quadrierung. Da die Rechenzeiten für die Multiplikationen länger dauern als für die Quadrierungen, kann Mallory aus Zeitmessungen Rückschlüsse auf die Zahl der Einsen in $a$ ziehen. Variiert er die Zahl $g$, reichen irgendwann die Informationen aus, um $a$ zu berechnen. Schon mit einigen Tausend Zeitmessungen lassen sich entsprechende Implementierungen mit 1024-Bit-Schlüsseln brechen.

Um solche Zeitangriffe zu verhindern, müssen jedoch bei der Implementierung lediglich Verzögerungen in den Ver- bzw. Entschlüsselungsprozess eingebaut werden. Mit dem als Blinding genannten Verfahren wird zum Beispiel an einer Stelle des Verfahrens eine Zufallszahl eingerechnet, die an anderer Stelle wieder herausgerechnet wird. Eine andere Möglichkeit besteht darin, den Prozess so zu gestalten, dass er unabhängig vom Eingabewert immer gleich lange dauert.

Stromangriff

Im Jahr 1998 stellten Paul Kocher, Joshua Jaffe und Benjamin Jun erstmals das Konzept des Stromangriffs vor. Bei Stromangriffen wird nicht nur die Verarbeitungszeit gemessen, sondern mit einem Oszilloskop auch der Stromverbrauch. Besonders Smartcards sind gegenüber Stromangriffen anfällig, da diese auf eine externe Stromversorgung angewiesen sind. Ein Angreiffer misst die Ver- und Entschlüsselungsvorgänge und versucht bestimmte Stellen der Stromverbrauchskurve einzelnen Bestandteilen des Verfahrens zuzuordnen. Auch hier ist der Square-and-Multiply-Algorithmus ein geeignetes Ziel, da sich bei diesem Multiplikationen und Quadrierungen am Stromverbrauch oft gut unterscheiden lassen. Stromangriffe sind etwas aufwendiger in der Durchführung als Zeitangriffe, gelten jedoch als wirkungsvoller.

Als Gegenmassnahme gegen Stromangriffe kann der Hersteller von Krypto-Modulen den Stromverbrauch verschleiern, indem er Dummy-Operationen in einen Ver- bzw. Entschlüsselungsvorgang einbaut. Eine weitere Möglichkeit besteht darin, ein künstliches Stromrauschen zu erzeugen, das den eigentlichen Stromverbrauch überlagert.

Literatur

Allgemeiner Überblick

• Klaus Schmeh: Kryptografie. Verfahren, Protokolle, Infrastrukturen. 5., aktualisierte Auflage, dpunkt.verlag: Heidelberg, 2013.

Fachartikel

• Dan Boneh: The Decision Diffie–Hellman Problem. In: Proceedings of the Third Algorithmic Number Theory Symposium (Lecture Notes in Computer Science, Vol. 1423) Springer-Verlag, 1998, S. 48-63. (Online)
• Whitfield Diffie, Martin E. Hellman: New Directions in Cryptography. In: IEEE Transactions on Information Theory 22, Nr. 6, 1976, S. 644–654. (Online)
• Martin E. Hellman: An overview of public key cryptography. In: IEEE Communications Magazine 40, Nr. 5, 2002, S. 42−49 (Online). Originalartikel: An overview of public key cryptography. In: IEEE Communications Magazine 16, Nr. 6, 1978, S. 24-32 (Online)
• Paul C. Kocher: Cryptanalysis of Diffie-Hellman, RSA, DSS, and Other Systems Using Timing Attacks. In: Advances in Cryptology, CRYPTO '95 (15th Annual International Cryptology Conference), Springer-Verlag, 1995, S. 27-31. (Online)
• Paul C. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Advances in Cryptology, CRYPTO '96 (Lecture Notes in Computer Science, Vol. 1109), Springer-Verlag, 1996, S. 104-113. (Online)
• Paul Kocher, Joshua Jaffe, Benjamin Jun: Introduction to Differential Power Analysis and Related Attacks. In: Advances in Cryptology—CRYPTO ’99, 19th Annual International Cryptology Conference. (Lecture Notes in Computer Science, Vol. 1666) Springer-Verlag: Berlin, 1999, S. 388-397. (Online)
• Ueli Maurer: Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms. In: Advances in Cryptology – Crypto '94. Springer-Verlag, 1994, S. 271–281. (Online)
• Ralph C. Merkle: Secure Communications over Insecure Channels. In: Communications of the ACM 21, Nr. 4, April 1978, S. 294–299. (Online)