Kryptographie und Zugriffskontrolle - Asmmetrische Verfahren

Asymmetrische Verfahren

Mitte der 1970er Jahre hatten Whitfield Diffie und Martin Hellman sowie Ralph Merkle unabhängig voneinander die Idee eines asymmetrischen Verfahrens beziehungsweise Public Key Systems . Das Prinzip beruht darauf, dass jeder Kommunikationspartner ein eigenes Schlüsselpaar besitzt, welches sich aus einem privaten und einem öffentlichen Schlüssel zusammensetzt. Der öffentliche Schlüssel kann natürlich öffentlich zugänglich gemacht werden. Der Plaintext wird vom Sender mit dem öffentlich zugänglichen Schlüssel des Empfängers verschlüsselt. Nur der Empfänger selbst ist mit seinem privaten Schlüssel in der Lage den Ciphertext wieder zu entschlüsseln. Die wesentlichen Vorteile und Nachteile von asymmetrischen Verfahren sind :

• Es ist kein aufwendiger Schlüsselaustausch über unsichere Kanäle notwendig. Der öffentliche Schlüssel ist ohnehin nicht geheim. Es muss nur sichergestellt werden, dass der öffentliche Schlüssel auch nur jenem zuzuordnen ist, der auch im Besitz des privaten Schlüssels ist. Siehe dazu auch Kapitel [PGP].
• Bei einem symmetrischen Verfahren musste mit jedem Kommunikationspartner ein eigener Schlüssel vereinbart beziehungsweise ausgetauscht werden. Mittels eines Public Key Verfahrens müssen keine geheimen Schlüssel verwaltet werden. Es ist ausreichend den öffentlichen Schlüssel des Kommunikationspartners zu kennen.
• Asymmetrische Verfahren bieten eine relativ hohe Stufe der Sicherheit. Sie basieren auf einer sogenannten Falltür-Funktion. Diese sind in angemessener Zeit nicht invertierbar, außer man kennt den geheimen Schlüssel. Da es allerdings keinen mathematischen Beweis für Falltür-Funktionen gibt, wäre es aber in der Zukunft theoretisch möglich, dass ein schnelles Verfahren gefunden wird, welches eine Umkehrung ermöglicht.
• Durch die Funktionsweise mit privaten und öffentlichen Schlüsseln bieten diese Verfahren auch die Möglichkeit für digitale Unterschriften beziehungsweise Signaturen, siehe dazu Kapitel [certificates].
• Asymmetrische Verfahren sind durch den hohen Aufwand beim Ver- beziehungsweise Entschlüsseln im Gegensatz zu symmetrischen Verfahren sehr langsam. In der Praxis wird daher oft ein hybrider Ansatz gewählt. Der Schlüsselaustausch erfolgt asymmetrisch, die weitere Kommunikation wird symmetrisch verschlüsselt.

Diffie-Hellman Schlüsselaustausch

Der Diffie-Hellman Schlüsselaustausch (DH) (engl. Diffie Hellman Key Exchange, DHKE) ist ein Protokoll zum Austausch beziehungsweise zur Vereinbarung eines Secret Keys. Das Protokoll adressiert das Problem von symmetrischen Verfahren, dass zuerst ein gemeinsamer Schlüssel ausgetauscht werden muss, siehe Kapitel [symmetrischeVerfahren]. Mit dem DH - Verfahren ist es möglich einen Secret Key zwischen zwei Kommunikationspartnern über einen unsicheren Kanal hinweg auszutauschen. Das Verfahren wurde von 1976 von Diffie und Hellman veröffentlicht. Da auch Ralph Merkle Vorarbeit geleistet hat, wird es auch manchmal als Diffie-Hellman-Merkle Schlüsselaustausch (DHM) bezeichnet

Funktionsweise:
Der Diffie-Hellman Schlüsselaustausch verwendet eine Einweg-Funktion (ohne Falltür), welche auf dem diskreter Exponentialfunktion basiert. Für eine Umkehrung ist der diskrete Logarithmus notwendig, der dieses Problem allerdings nicht in polynomialer Laufzeit (und damit schnell genug) lösen könnte. Die Funktionsweise wird anhand eines Beispiels in Tabelle 1.1 erläutert.

Diffie-Hellman Schlüsselaustausch anhand eines Beispiels

	Alice und Bob haben gemeinsames Wissen über eine Primzahl ${\textstyle p=23}$
	und eine natürliche Zahl ${\textstyle g}$, wobei ${\textstyle g<p}$ ist
	Alice	Bob
1.	Alice sucht sich eine geheime	Bob sucht sich eine geheime
	zufällige Zahl aus: ${\textstyle a=6}$	zufällige Zahl aus: ${\textstyle b=5}$
2.	Alice berechnet A:	Bob berechnet B:
	${\textstyle A=g^{a}\mod p}$	${\textstyle B=g^{b}\mod p}$
	${\textstyle A=11^{6}\mod 23=9}$	${\textstyle B=11^{5}\mod 23=5}$
3.	Alice übermittelt ${\textstyle A=9}$ an Bob	Bob übermittelt ${\textstyle B=5}$ an Alice
4.	Alice berechnet den secret key:	Bob berechnet den secret key:
	${\textstyle K=B^{a}\mod p}$	${\textstyle K=A^{b}\mod p}$
	${\textstyle K=5^{6}\mod 23=8}$	${\textstyle K=9^{5}\mod 23=8}$

RSA-Verfahren

Nachdem das Konzept zu asymmetrischen Verfahren von Whitfield Diffie und Martin Hellman beziehungsweise Ralph Merkle veröffentlicht wurde, wurde RSA als erstes Verfahren dazu entwickelt. Es wurde von Ronald Rivest, Adi Shamir und Leonard Adleman im Jahr 1978 publiziert. RSA ist mittlerweile defacto Standard und weit verbreitet.

RSA basiert auf dem Faktorisierungsproblem großer natürlicher Zahlen. Es gilt als mathematisch sehr schwierig das Produkt zweier Primzahlen zu faktorisieren. Genau diese Tatsache macht man sich bei RSA zum Vorteil. Ein solches Problem wird auch als Einweg-Funktion mit Falltür oder Falltür-Funktion bezeichnet (engl. Trapdoor One Way Function). Um die Funktionsweise von RSA zu verstehen werden folgende mathematische Grundlagen benötigt:

• Der Modulo Operator beziehungsweise das Rechnen mit Restklassen.
• Die Eulersche ${\textstyle \varphi }$ - Funktion einer Zahl ${\textstyle N}$, welche angibt wie viele natürliche es gibt die kleiner als ${\textstyle N}$ und teilerfremd zu ${\textstyle N}$ sind.
• Der Satz von Euler - Fermat, welcher besagt, dass ${\textstyle a^{\varphi (N)}\equiv 1\mod N}$

Funktionsweise:
Die Funktionsweise wird anhand eines Beispiels mit kleinen Zahlen erklärt. Angenommen Bob will Alice eine Nachricht zukommen lassen, wird bei RSA vereinfacht wie folgt vorgegangen:

1. Alice wählt zwei Primzahlen ${\textstyle p}$ und ${\textstyle q}$ aus und ermittelt deren Produkt ${\textstyle n}$:

   $$n=p*q$$
   Angenommen Alice wählt für ${\textstyle p=5}$ und für ${\textstyle q=13}$ aus, dann ist:
   $$n=5*13=65$$

   ${\textstyle n}$ wird auch als RSA-Modul bezeichnet. In der Praxis verwendet man natürlich möglichst große und unterschiedliche Primzahlen.

2. Alice berechnet für ${\textstyle n}$ die Eulersche ${\textstyle \varphi }$ - Funktion mit der Formel:

   $$\varphi (n)=m=(p-1)*(q-1)$$
   $$m=(5-1)*(13-1)=48$$

3. Alice sucht sich nun eine zu ${\textstyle m}$ teilerfremde Zahl

   Daher der größte gemeinsame Teiler ist 1

   a aus, welche größer als 1 ist, daher ${\textstyle 1<a<m}$. ${\textstyle a}$ wird auch als Verschlüsselungsexponent bezeichnet. In diesem Beispiel wählt Alice ${\textstyle a=7}$

4. Die Zahlen ${\textstyle n=65}$ und ${\textstyle a=7}$ stellen den öffentlichen Schlüssel von Alice dar. Diese kann sie nun Bob zur Verfügung stellen.

5. Bob möchte nun eine Nachricht an Alice schicken. Seine Nachricht ist eine Zahl kleiner als ${\textstyle n}$, daher ${\textstyle x=19}$.

6. Bob verschlüsselt seine Nachricht gemäß der Formel:

   $$y=x^{a}\mod n$$
   $$y=19^{7}\mod 65$$
   $$y=59$$

7. Bob sendet seinen ciphertext ${\textstyle y=59}$ an Alice.

8. Alice berechnet mit Hilfe des erweiterten euklidischen Algorithmus das modulare Inverse, die Zahl ${\textstyle b}$:

   $$b=a^{-1}\mod m$$
   $$b=7^{-1}\mod 48$$
   $$b=7$$

9. Nun kann Alice die Nachricht von Bob mit dem Satz von Euler entschlüsseln:

   $$x=y^{b}\mod n$$
   $$x=59^{7}\mod 65$$
   $$x=19$$

Kennt ein Angreifer nur den öffentlichen Schlüssel bestehend aus den Zahlen ${\textstyle n}$ und ${\textstyle a}$, müsste dieser aus diesen zwei Zahlen den privaten Schlüssel errechnen. Das einzig bekannte Verfahren zurzeit ist die Primfaktorenzerlegung, mit welchem dies prinzipiell machbar wäre, allerdings nicht in angemessener Zeit. Zu beachten sind bei einer RSA Implementierung allerdings 2 Punkte:

• die Wahl auf entsprechend große Primzahlen ${\textstyle p}$ und ${\textstyle q}$.
• ${\textstyle p}$ und ${\textstyle q}$ sollen möglichst weit auseinander liegen. Eine sequentielle Suche nach Primzahlen kann auch bei hohen Primzahlen starten und rückwärts laufen. Ein klassischer Ausgangspunkt ist ${\textstyle {\sqrt[{}]{n}}}$. Je näher sich die Zahlen ${\textstyle p}$ und ${\textstyle q}$ sind, desto näher befinden sie sich auch bei ${\textstyle {\sqrt[{}]{n}}}$ und desto kürzer wäre eine systematische Suche nach Primzahlen.

In der Praxis sollte auch sichergestellt werden, dass nach Generierung des RSA Moduls, die Variablen welche ${\textstyle p}$ und ${\textstyle q}$ enthalten, gelöscht werden. Sie werden in der weiteren Berechnung nicht mehr benötigt.

Für RSA beziehungsweise auch andere Verschlüsselungs-Verfahren, welche auf mathematischen Falltür-Funktionen basieren, ist zu beachten, dass es theoretisch auch Gefahren gibt. Zum einen könnte ein Algorithmus entwickelt werden, der ohne große Mühen das Problem der verwendeten Falltür-Funktion löst. Zum anderen auch technische Aspekte, wie die Entwicklung von Quantencomputern, für welche diese mathematischen Probleme wahrscheinlich weniger Aufwand bedeuten.

Elliptic Curve Cryptography

Im Bereich der Primfaktorenzerlegung wurden bessere und schnellere Verfahren entwickelt und auch die Hardware wurde schneller. So wurde klar, dass nach alternativen Falltür-Funktionen gesucht werden musste, falls eines Tages eine effiziente Umkehrfunktion gefunden wird. Im Jahr 1985 wurden von Victor Miller und Neil Koblitz unabhängig voneinander Elliptische Kurven über endlichen Körpern vorgeschlagen.

graphische Darstellung der elliptischen Kurve y2 = x3 + 17

Eine elliptische Kurve ist ein Menge an Punkten die eine spezielle mathematische Funktion erfüllen. Über diese Punkte lässt sich eine additive zyklische Gruppe bilden . Innerhalb dieser Gruppe gelten bestimmte Rechenregeln. Die Verfahren aus dem diskreten Logarithmus lassen sich auf die Punkte einer elliptischen Kurve übertragen. Hier ist die nicht umkehrbare Funktion allerdings die Division eines Punktes.

Bei wesentlich kürzeren Operanden und Schlüsseln bietet ECC die gleiche Sicherheit wie bei Verfahren welche auf dem diskreten Logarithmus oder RSA beruhen . Als Vergleich, ein Verfahren mit 1024 bis 3072-Bit basierend auf dem diskreten Logarithmus oder RSA ist äquivalent mit ECC von 160 bis 256-Bit.

Vergleich des rechnerischen Aufwands von ECC, symmetrischen und asymmetrischen Verfahren aus [17]