Asymmetrische Chiffren

Definition

Asymmetrische Chiffren verfolgen einen anderen Ansatz als die oben erläuterten symmetrischen Chiffren. Es wird nicht der gleiche Schlüssel sowohl zu Ver- wie auch zur Entschlüsselung verwendet,sondern es gibt bei asymmetrischen Chiffren zwei oder mehr verschiedene Schlüssel⁴. Im Fall von asymmetrischen Chiffren mit zwei Schlüsseln spricht man oft auch von public key Algorithmen, da üblicherweise ein Schlüssel veröffentlicht wird und ein Schlüssel geheim bleibt. Bei einer Kommunikation dient der öffentliche Schlüssel (public key) zum Chiffrieren der Daten und der geheime Schlüssel (private key) zum Dechiffrieren. So ist es möglich, dass jeder dem Besitzer des geheimen Schlüssels verschlüsselte Nachrichten zukommen lassen kann, ohne dass vorher ein gemeinsamer Schlüssel vereinbart werden mußte. Man verwendet einfach den öffentlichen Schlüssel der betreffenden Person, welcher auch auf unsicheren Kanälen übermittelt werden kann und verschlüsselt die zu sendenden Daten mit diesem. Der so entstandene Chiffretext kann einzig und allein mit dem geheimen Schlüssel dechiffriert werden, der nur dem Empfänger bekannt sein darf. Damit dies auch funktioniert, muß aber gewährleistet sein, dass durch Kenntnis des öffentlichen Schlüssels und des Algorithmus keine Möglichkeit entsteht, den geheimen Schlüssel zu ermitteln. Mit anderen Worten: Es muß unmöglich (bzw. unverhältnismäßig schwer) sein, unter Kenntnis des öffentlichen Schlüssels den geheimen Schlüssel zu berechnen.

Die Rollen (öffentlich/privat) der Schlüssel sind nicht bei allen Algorithmen von vornherein festgelegt, sondern häufig ist es egal mit welchem Schlüssel ver- und mit welchem entschlüsselt wird.

RSA:

Der wohl am weitesten verbreitetste public-key-Algorithmus ist RSA⁵. Anders als bei symmetrischen Chiffren wie dem DES, die auf geschickter Bit-Ersetzung und Permutation beruhen, ist das Funktionsprinzip des RSA ein rein zahlentheoretisches. Seine Schlüssellänge ist variabel, wobei Größen zwischen 512 und 1024 Bit üblich sind. Der RSA ermöglicht sowohl Verschlüsselung wie auch digitale Signatur (siehe 2.5.6) und hat sich weltweit zu einem Quasi-Standard für asymmetrische Verschlüsselung entwickelt.

RSA - Funktionsweise

Der Algorithmus des RSA ist verblüffend einfach, deswegen will ich ihn kurz skizzieren.

Schlüsselgenerierung:

1. Wähle zwei etwa gleich große Primzahlen $p$,$q$.
2. Diese bestimmen den Modul $n = p*q$.
3. Wähle Zahl $e$ mit ggt $(e, (p-1)(q-1)) = 1$.
4. Wähle Zahl $d$ mit $e*d \bmod (p-1)(q-1) = 1$.
5. $e$ und $n$ werden öffentlich gemacht und bilden den public key.
6. $d$, $p$ und $q$ bleiben geheim ($p$ und $q$ werden üblicherweise aus Sicherheitsgründen nach der Schlüsselerzeugung gelöscht). $d$ bildet den private key.

Die Ver- und Entschlüsselung funktionieren wie folgt:

Verschlüsselung: $C = M^{e} \bmod n$

Entschlüsselung: $M = C^{d} \bmod n$

Die Reihenfolge der Anwendung der Schlüssel ist beliebig, was aus der Kommutativität der Multiplikation folgt ( $M = C^{d} = (M^{e})^{d} = M^{ed} = M^{de} = (M^{d})^{e} = C'^{e} = M$). Dies ist jedoch eine spezifische Eigenschaft des RSA.

Andere Ansätze für asymmetrische Chiffren:

Neben dem oben beschriebenen Ansatz für asymmetrische Chiffren, deren Sicherheit auf der Schwierigkeit des Faktorisierens großer Zahlen beruht, existieren weitere Ansätze für asymmetrische Chiffren, in denen andere, nur mit großem Aufwand zu lösende Probleme, als Grundlage benutzt wurden:

• Berechnen des diskreten Logarithmus über endlichen Gruppen: Ähnlich wie das Problem des Faktorisierens ist das Berechnen des diskreten Logarithmus über endlichen Gruppen ein hartes Problem. Asymmetrische Chiffren wie z.B. der ElGamal-Algorithmus benutzen als Gruppe die ganzen Zahlen modulo einer Primzahl. Für diese Gruppe hat das Problem subexponentiellen Aufwand.

• Lösen von NP-Vollständigen Problemen: Es existieren mehrere Ansätze, NP-Vollständige Probleme für asymmetrische Chiffren zu verwenden. Hierbei versucht man das Problem so zu modifizieren, dass es mit Hilfe einer zusätzlichen Information einfach zu lösen ist, ohne die Information der Aufwand aber weiterhin NP-Vollständig bleibt. Man spricht in solchen Fällen auch davon, dass man eine Hintertür in das Problem einbaut (trapdoor). Das modifizierte Problem bildet den öffentlichen Schlüssel, die Zusatzinformation den geheimen. Die zu verschlüsselnden Daten werden in eine Instanz (bzw. in eine Aufgabestellung) des NP-Vollständigen Problems transformiert. Um die Daten zurückzugewinnen, muß man das Problem lösen. Das Lösen des Problems ist ohne die Kenntnis der Zusatzinformation (also dem geheimen Schlüssel) ab einer gewissen Größe des Problems unmöglich, bei Kenntnis der Information aber im Idealfall mit linearem Zeitaufwand zu erledigen. Leider wurde bis jetzt noch kein überzeugender Algorithmus dieses Ansatzes gefunden.

• Elliptische Kurven: Asymmetrische Chiffren, deren Sicherheit auf der Schwierigkeit des Lösens des diskreten Logarithmus über endlichen Gruppen beruht, benutzen als Gruppe i.A. die ganzen Zahlen modulo einer Primzahl. Diese Gruppe hat leider einige Besonderheiten, durch die das Berechnen des diskreten Logarithmus' nur subexponentiellen Aufwand hat. Um ausreichende Sicherheit zu bieten, ist es nötig, relativ große Schlüssel zu verwenden. Dieses wiederum erschwert den Einsatz solcher Chiffren in Anwendungen, die nur über beschränkten Speicherplatz verfügen, wie es z.B. bei Chipkarten der Fall ist. Darüber hinaus wird ein Zusammenhang zwischen dem Problem der Faktorisierung und dem des diskreten Logarithmus vermutet. Falls sich dieses als wahr herausstellt und darüber hinaus ein Durchbruch im Lösen eines der beiden Probleme erzielt wird, werden mit einem Schlag fast alle verwendeten asymmetrischen Chiffren nutzlos.

  Mit den elliptischen Kurven, deren Punkte eine ``Abelsche Gruppe'' bilden, glaubt man, einen potenten Ersatz für die Gruppe der ganzen Zahlen modulo einer Primzahl gefunden zu haben. Das so gewonnene Problem hat exponentiellen Aufwand und kommt somit mit kleineren Schlüsseln aus. Darüber hinaus ist das Problem des Lösens des Logarithmus über einer elliptischen Kurve unabhängig vom Problem des Faktorisierens großer Zahlen. Weiter kommt positiv hinzu, dass die bekannten und bereits als sicher bewerteten Algorithmen, die momentan noch die Gruppe der ganzen Zahlen modulo einer Primzahl verwenden, auch mit der Gruppe der Punkte einer elliptischen Kurve funktionieren. Der verbreiteten Benutzung dieses Ansatzes steht aber noch im Weg, dass die Schlüsselgenerierung für derartige Algorithmen ein noch nicht befriedigend gelöstes Problem ist.

  Als Beispiel für einen Algorithmus, der erfolgreich mit elliptischen Kurven als Gruppe arbeitet, sei hier der Elliptic Curve Digital Signature Algorithm (ECDSA) (1992) genannt. Wie der Name schon vermuten lässt, handelt es hierbei um eine Variante des DSA (siehe 2.5.6). ECDSA wurde 1999 als ANSI-Standard (ANSI x9.62) akzeptiert.