Public-Key Verfahren

Bei den bisherigen Verfahren hatte man das Problem der Schlüsselübergabe. Man musste den Schlüssel stets geheimhalten, denn eine Veröffentlichung hätte es notwendig gemacht, einen neuen Schlüssel zu verwenden.

Das Public-Key Verfahren beruht deshalb auf zwei Schlüsseln. Einem öffentlichen (offen zugänglich) und einem privaten (geheim). Der eine Schlüssel wird vom anderen abgeleitet. Bei einem guten asymmetrischen Verfahren gibt es keine Möglichkeit aus einem Schlüssel den anderen zu berechnen.

Wenn man nun eine geheime Botschaft übermitteln will, verschlüsselt man sie mit dem Public Key des Empfängers. Das Entschlüsseln ist mit diesem nicht möglich. Der Empfänger kann die Botschaft nun mit seinem geheimen Private Key einfach entschlüsseln.

Die Schlüssel sind ein Produkt aus Primfaktoren. Der Code ist es zwar einfach durch mehrfache Divison bis zu den Primzahlfaktoren herauszufinden, aber dies ist bei langen Schlüsseln viel zu zeitaufwendig. Etwas schneller geht es mit Faktorisierungsalgorithmen. Der neueste dieser Art ist das so genannte Zahlenkörpersieb (Number Field Sieve, NFS), mit dem sich die Suchzeit um ein Zehnfaches verkürzt.

Momentan ist es möglich eine Zahl mit 130 Dezimalstellen (etwa 440 Bit) in ihre Primfaktoren zu zerlegen. Dies dauerte in einem Versuch, an dem 1600 Rechner, die über das Internet verbunden waren, beteiligt waren, ganze 8 Monate.

Ein Verfahren, mit dem es schneller geht, wird in nächster Zeit nicht erwartet.

Es gibt zwei Algorithmen, die zur Zeit sehr häufig benutzt werden: ElGamal und RSA.

ElGamal

Das Prinzip des Algorithmus zur asymmetrischen Verschlüsselung, der 1985 von Taher ElGamal entwickelt wurde, beruht auf dem zahlentheoretischen Problem "diskrete Logarithmen modulo einer Primzahl" zu berechnen. Die Primzahl kann eine Länge von 512 Bit (weniger sicher) bis zu 1024 Bit (sehr sicher) haben. Der ElGamal-Algorithmus unterliegt keinem Patent.

 

RSA

Das RSA Verfahren wurde 1977 von Ronald L. Rivest, Adi Shamir und Leonard Adleman entwickelt und nach den Nachnamen der Erfinder benannt. Das Verfahren ist ebenfalls frei von Patentrechten.

Erzeugung der Schlüssel:

Zur Erzeugung der Schlüssel braucht man zwei sehr große Primzahlen (mit p und q bezeichnet), die sich in der Länge deutlich unterscheiden müssen. Daraus errechnet man dann ein Produkt n = p x q. Die Faktoren sind so gewählt, dass es eine vorher angegebene Länge besitzt. Um einen sicheren Schlüssel zu erzeugenm sollten es mindestens 512 Bit sein. Je länger, desto sicherer.

Nun berechnet man das Produkt der Vorgänger von p und q:
z = (p - 1) x (q - 1)

Danach wählt man eine Zahl e, die keinen gemeinsamen Teiler mit z hat, außer der 1. E ist bestandteil des öffentlichen Schlüssels. Aus e und z wird der private Schlüssel d berechnet:
d = (1/e) mod (z).

Nun hat man den privaten Schlüssel (Private Key) d und den öffentlichen Schlüssel (Public Key), der sich aus e und n zusammensetzt.

Als Empfehlung für eine großte Zukunftssicherheit der Schlüssel wird ein Länge von 2048 Bit empfohlen. Mindestens bis 2004 sind auch noch 1024 Bit unmöglich zu entschlüsseln.

Verschlüsselung:

Der zu verschlüsselnde Text wird in Blöcke zerlegt, die kürzer als n sind. Buchstaben und sonstige Zeichen müssen erst mittels einer Tabelle in Zahlencodes umgewandelt werden. Danach werden die einzelnen Blöcke mit diesem Verfahren verschlüsselt:

Entschlüsselung:

Die Entschlüsselung funktioniert gerade andersherum mit dem privaten Schlüssel d:

Verschlüsselung des Wortes Jonathan:

Für die Beispielrechnung nehmen wir zwei kleinere Primzahlen 47 und 71.

n = 47 x 71 = 3337
z
= 46 x 70 = 3220

Nun wählen wir e. Diese Zahl darf keinen gemeinsamen Teiler mit z haben, also nehmen wir 79.

d = 1/79 mod 3220 = 1019

Daraus ergeben sich der öffentliche Schlüssel (e, n): 79, 3337 und der private Schlüssel (d): 1019.

Nun müssen wir das zu verschlüsselnde Wort "Jonathan" in Zahlencodes umschreiben. Dazu nehmen wir einfach die Position im Alphabet und erhalten so "10 15 14 01 20 08 01 14".

Das wird in Blöcke zerlegt, die kleiner als n sind, also 3 Stellen haben:
m 1 = 101
m 2 = 514
m 3 = 012
m 4 = 008
m 5 = 011
m 6 = 004

Bei m 6 wurden der 4 noch zwei Nullen vorgestellt, damit alle Blöcke gleich lang sind.

Nun können wir die Blöcke verschlüsseln:
c 1 = 101^79 mod 3337 = 1113
c 2 = 514^79 mod 3337 = 1111
c 3 = 012^79 mod 3337 = 0760
c 4 = 008^79 mod 3337 = 2807
c 5 = 011^79 mod 3337 = 2120
c 6 = 004^79 mod 3337 = 2497

Aus diesen Blöcken bekommen wir mit unserem privaten Schlüssel d(1019) wieder das ursprüngliche Wort:
m 1 = 1113^1019 mod 3337 = 101
m 2 = 1111^1019 mod 3337 = 514
m 3 = 0760^1019 mod 3337 = 012
m 4 = 2807^1019 mod 3337 = 008
m 5 = 2120^1019 mod 3337 = 011
m 6 = 2497^1019 mod 3337 = 004

Ergibt Jonathan. Ein Tipp zur Modulo-Rechnung: Den Windows-Rechner auf Wissenschaftlich umstellen, dann gibt es die Funktion Mod.

Hier kannst du das Verfahren selbst ausprobieren.

MultiPrime-Verfahren

Eine modifzierte RSA-Verschlüsselung aus dem Hause Compaq, die, statt nur zwei Primzahlen, drei oder mehr verwendet. Dadurch wird die Geschwindigkeit der Entschlüsselung um das 6-7 fache gesteigert. Besonders bei SmartCard ist dies ein wichtiger Punkt.

 

Pretty Good Privacy

Pretty Good Privacy oder kurz PGP ist das wahrscheinlich am weitesten verbreitete Verschlüsselungsprogramm. Es basiert auf einem Public-Key Verfahren und dient der Verschlüsselung von Emails. Bei der Installation werden ein öffentlicher und ein privater Schlüssel generiert. Der öffentliche Schlüssel kann jetzt entweder in einer zentralen Datenbank hinterlegt werden, in der jeder nach Schlüsseln von bestimmten Besitzern suchen kann, oder er muss dem Absender auf einem anderen Weg mitgeteilt werden. Mit diesem verschlüsselt der Absender nun seine Daten und kennzeichnet die Nachricht als PGP-Verschlüsselt.

Der Empfänger kann diesen jetzt mit seinem privaten Schlüssel wieder lesbar machen.

Pretty Good Privacy war zuerst nur in den USA verfügbar, da die Regierung einen Export verbot, weil militärisch sensible Technologien verwendet wurden. Der Export konnte nur ausgedruckt auf Papier erfolgen. Das musste dann wieder eingescannt werden und schon war PGP auch hier verfügbar. Heute besteht dieses Problem nicht mehr.

 

Die langsame Geschwindigkeit ist bei der asymetrischen Verschlüsselung noch ein großes Problem. Daher hat man ein neues System entwickelt, das symetrische und asymetrische Systeme kombiniert: das Hybridverfahren.