Die asymmetrischen Verfahren, auch Public Key Cryptography Verfahren genannt, ermöglichen es mehreren Parteien ihre Daten zu schützen, ohne dass dazu geheime Informationen ausgetauscht werden müssen. Der geheime Schlüsselaustausch wird durch einen Mechanismus ersetzt, der keinerlei Geheimhaltung erfordert. Die Besonderheit ist, dass es zwei Schlüssel gibt, die zueinander passen, d.h. eine Berechnung mit dem einen Schlüssel kann nur durch eine Berechnung mit dem anderen Schlüssel wieder rückgängig gemacht werden. Diese Eigenschaft erlaubt es, einen Schlüssel öffentlich zu machen und den anderen privat zu halten - und zu schützen.

Die Algorithmen basieren auf der Ausnutzung schwieriger mathematischer Probleme, konkret um Berechnungen, die sich in einer Richtung durchführen lassen, in der umgekehrten Richtung jedoch extrem schwierig sind, wenn man ein bestimmtes Wissen nicht hat. Also sozusagen eine Einwegfunktion mit Hintertür (Trapdoor One Way Function).

=

Faktorisierungsproblem

Bekanntlich ist es leicht, zwei Primzahlen miteinander zu multiplizieren. Hingegen ist es extrem schwer, dieses Produkt in seine Primfaktoren zu zerlegen. Man versucht daher, die Verfahren so zu konstruieren, dass nur die Kenntnis dieser Primfaktoren die Entschlüsselung erlaubt. Man benötigt dazu sehr große Primzahlen. Anwendung findet dieses Problem bei Pseudo-Zufallsgeneratoren wie Blum Blum Shub (BBS), vor allem aber für asymmetrische Algorithmen wie RSA.

RSA ist das Paradebeispiel für das Faktorisierungsproblem und wurde von Ron Rivest, Adi Shamir und Len Adleman 1977 am MIT entwickelt. Die Sicherheit beruht darauf, dass das modulare Potenzieren mit einem festen Exponenten und einem festen Modul eine Falltür-Einwegfunktion darstellt, bzw. das Faktorisierungsproblem ein schwieriges Problem ist und bleibt.

Der RSA besteht aus drei numerischen Werten, die paarweise zur Ver- und Entschlüsselung benutzt werden, dem Schlüssel e, dem Schlüssel d und des Moduls n, wobei die öffentlichen Schlüsseldaten e und n, die privaten Schlüsseldaten d und n sind. Den Chiffretext C erhält man

C = P hoch e (mod n),

die Entschlüsselung erfolgt analog mit dem privaten Schlüssel

P = C hoch d (mod n)

=

Berechnung der Schlüssel und des Modul

Als erstes generiert man zwei Primzahlen p und q etwa gleich großer Stelligkeit und berechnet daraus die Zahl

n = pq

Typische Werte für die Länge liegen bei 1024 oder 2048 Bit.

Als öffentlichen Schlüssel e wählt man eine Zahl die zu m = (p-1)(q-1) relativ prim ist, also 1 als kleinsten gemeinsamen Teiler besitzt. Meist werden dazu 3, 17 oder 65637 als Konstante verwendet, was für Low Exponent Attacken anfällig macht.

e relativ prim zu (p-1)(q-1)

Mit e und n und des erweiterten euklidischen Algorithmus kann der private Schlüssel d errechnet werden.

d ist die multiplikativ Inverse von e modulo m d.h. de (mod m) = 1 muss erfüllt sein.

Die Primfaktoren p und q können danach vernichtet werden.

=

diskrete Logarithmen

Die Berechnung einer diskreten Exponentialfunktion zur Basis a ist leicht, die Umkehrung, die diskrete Logarithmusfunktion, dagegen ist schwer.

Der Diffie Hellman Schlüsselaustausch zeigt das Prinzip:

1. Alice und Bob einigen sich auf Primzahl n und eine natürliche Zahl g<n. Dies kann ohne weiteres über offene Kanäle erfolgen.

2. Alice wählt eine natürliche Zahl x<n während B dies ebenfalls durchführt y<n.

3. Alice berechnet a=g hoch x (mod n) und übermittelt diese Bob

4. Bob berechnet b=g hoch y (mod n) und übermittelt diese Alice

5. Alice berechnet k1=b hoch x (mod n)

6. Bob berechnet k2=a hoch y (mod n)

Jetzt gilt, das k = k1 = k2, während ein Angreifer, welcher die gesamte Kommunikation abgehört hat, dieses k nicht ermitteln kann. Die Zahlen a bzw. b können dabei als öffentlicher Schlüssel, während x und y als jeweiliger privater Schlüssel betrachtet werden.

=

Rucksackproblem

Wird auch Untersummenproblem genannt.

Man hat eine gewisse Anzahl von Gegenständen mit unterschiedlichem Gewicht zur Verfügung. Die Aufgabe besteht nun darin, genau jene Gegenstände in einen Rucksack zu packen, so dass der Rucksack ein vorgegebenes Gewicht erreicht.z.B. basiert der Merkle Hellman Algorithmus darauf, der aber weitestgehend gebrochen ist.

=

elliptische Kurven

Der Nachteil der Rechenaufwendigkeit von herkömmlichen Public Key Verfahren führte zum Ansatz von Kryptosystemen auf Basis von elliptischen Kurven.

Besonderes Merkmal dieser Klasse von Verfahren, ist, dass die notwendigen Berechnungen in diesem Fall nicht direkt mit Zahlen, sondern mit anderen Objekten, den Punkten auf so genannten Elliptischen Kurven durchgeführt werden. Damit lassen sich die verwendeten Schlüssel- und Parameterlängen ohne Sicherheitseinbuße deutlich reduzieren. Dies macht die Algorithmen insbesondere interessant für den Einsatz innerhalb Umgebungen mit beschränkten Rechen- oder Speicherkapazitäten wie z.B. Smart Cards.

=

Anwendung: Sicherstellen der Vertraulichkeit

Alice kann mittels asymmetrischer Verschlüsselung Bob nun eine vertrauliche Nachricht senden, ohne dass die beiden vorher denselben symmetrischen Schlüssel besitzen müssen. Alice verschlüsselt mit dem öffentlichen Schlüssel von Bob, damit kann nur mehr Bob, der im Besitz vom privaten Schlüssel ist, die Nachricht wieder entschlüsseln. Mallory scheitert daran, da der öffentliche Schlüssel nutzlos ist. Bob weiß nun, dass niemand anderer als er und der Absender diese Nachricht kennt, aber ist Alice tatsächlich der Absender?

=

asymmetrische Verschlüsselung 2 Schlüssel sind an Ver- und Entschlüsselung beteiligt.
asymmetrische Verschlüsselung 2 Schlüssel sind an Ver- und Entschlüsselung beteiligt.

Anwendung: Sicherstellen der Authentizität

Will Alice eine Nachricht als von ihr stammend authentisieren, wendet sie ihren eigenen Schlüssel auf die Nachricht an. Der Empfänger, z.B. Bob, kann mit dem öffentlichen Schlüssel von Alice erkennen, dass diese Nachricht von Alice stammt. Mallory kann dies ebenso, schafft es aber nicht, die Nachricht unerkennbar zu verändern, da er den privaten Schlüssel von Alice nicht besitzt. Eine Sicherstellung von Vertraulichkeit und Authentizität ist daher durch Kombination beider Anwendungen erreichbar.

=

Prinzip der digitalen Signatur
Prinzip der digitalen Signatur

Anwendung: Digital Envelope

Dadurch, das RSA und die anderen Public Key Verfahren den großen Nachteil der großen Schlüssellängen und der aufwendigen, langsamen Rechenoperationen haben, werden diese fast immer dazu verwendet, den Schlüssel für ein symmetrisches Kryptoverfahren zu übersenden. Der öffentliche Schlüssel wird als KEK (Key Encrypting Key) für den symmetrischen DEK (Data Encrypting Key) verwendet. Man nennt dies hybrides Verfahren oder "digital envelope". Deshalb gibt es zwischen den beiden Ansätzen keine Konkurrenzkämpfe, sondern sie ergänzen sich gegenseitig. 

=

Hybride Verschlüsselung: der symmetrische Schlüssel wird asymmetrisch verschlüsselt.
Hybride Verschlüsselung: der symmetrische Schlüssel wird asymmetrisch verschlüsselt.