Ansichten
Public Key Verfahren und Anwendungen
Inhaltsverzeichnis |
Public Key Verschlüsselung
Oftmals wird RSA und Public Key Verfahren synonym benutzt, obwohl das nicht ganz korrekt ist. Whitfield Diffie und Martin Hellman entwickelten eine Theorie des Public Key Verfahrens, welches durch seine asymmetrische Verschlüsselung das Problem des Schlüsseltausches eliminiert hatte. Die beiden entwickelten ein Arbeitspapier zu diesem Thema und legten darin die Anforderungen für eine Public-Key (asymmetrische) Verschlüsselung. Das ganze stellte aber noch keine Anwendung dar, sondern war reine Theorie.
Die Idee dahinter ist verblüffend einfach:
Alice schreibt einen geheimen Brief an Bob. Packt ihn in eine bombensichere Titankiste. Legt eine schwere Kette darum und verschliesst das Ganze mit einem Schloss zu dem NUR sie den Schlüssel hat. Dann geht's auf die Reise zu Bob. Dieser verschliesst die Kette mit seinem eigenen Schloss nocheinmal und schickt die Kiste wieder zu Alice. Diese entfernt dann ihr Schloss und schickt die Kiste wieder an Bob, der nun das einzige verbleibende Schloss entfernen kann und den Brief liest. Eve, die bei der Post arbeitet - und dort arbeiten nur Eves - hat keine Chance an den Brief zu kommen solange Bob und Alice ihre Schlüssel geheimhalten.
Obiges Beispiel hinkt imho ein bisschen, wird aber so in allen Büchern zur Kryptografie wiedergegeben. Eigentlich würde Alice die Kette mit dem Schloss von Bob verschliessen, zu dem nur er den Schlüssel hat. Damit liesse sich der unnötige Roundtrip verhindern. Das Schloss (Public-Key) ist vollkommen frei zugänglich. Nur der Schlüssel (Private-Key) muss geheimgehalten werden.
Heute weiss man, dass Diffie und Hellmann eigentlich nicht die wirklichen Erfinder des Public-Key Verfahrens waren. Bereits in den 60-iger Jahren wurde diese Methode der Verschlüsselung von englischen Kryptografen, die für das Militär arbeiteten, erfunden. Dies erfolgte jedoch unter grösster Geheimhaltung und Arbeiten der beteiligten Wissenschaftler dazu wurden erst Mitte der 80-iger Jahre freigegeben. Also konnten Diffie und Hellmann gar nichts davon gewusst haben
Anforderungen
Die Hauptanforderungen an das Verfahren waren folgende:
- einzigartige Beziehung zwischen Private und Public Key
- es muss sichergestellt sein, dass nur mit dem richtigen Private Key eine Entschlüsselung stattfinden kann
- die Einzigartigkeit muss mathematisch gesichert sein
- das Produkt aus zwei Primzahlen ist einzigartig
- keine Möglichkeit den Private Key aus dem Public Key zu errechnen
- diese Bedingung kann mit Einwegfunktionen erreicht werden
- keine Möglichkeit der Näherung beim Angriff auf die Chiffre
- es darf nicht möglich sein sich dem Resultat (Klartext oder Private Key) durch Try-and-Error anzunähern
- diese Bedingung kann durch modulare Arithmetik erreicht werden
Einwegfunktionen und modulare Arithmetik
Der Witz an Einwegfunktionen ist es, dass man das Resultat der Funktion sehr schnell berechnen kann. Jedoch ist es nicht möglich (bzw. nur mit enormsten Anstrengungen) aus dem Resultat auf die Parameter der Funktion zu schliessen.
Die Multiplikation ist eine Zwei-Weg-Funktion. Weil es zu ihr das Gegenstück Division gibt. Nennen wir die zwei geheimen Primzahlen x und y und den öffentlichen Schlüssel N
x * y = N (253)
Wenn jetzt also Carl den öffentlichen Schlüssel von Alice hat kann er mittels Division feststellen, dass die geheimen Zahlen 23 und 11 lauten müssen. Klar wird der Aufwand grösser je grösser die gewählten Primzahlen sind, aber grundsätzlich ist die Multiplikation durch die Division rückgängig zu machen.
Folgende Tabelle zeigt einen weiteren Schwachpunkt der Multiplikation. Über die Differenz von y zu einer ganzen Zahl kann man abschätzen wo sich die Lösung ungefähr befinden muss. In normaler Arithmetik kann man sehen ob es warm oder kalt ist mit der Annäherung an die Lösung.
<runphp>
| x | ';'.$i.' | ';
| y | ';'.$ret.' | ';
| Δ INT | ';'.$ret.' | ';
</runphp>
Hier kommt die modulare Arithmetik zum Zug. Mit ihr ist es nicht abschätzbar ob man sich der Lösung annäherd oder entfernt. Wir verwenden wieder die gleichen Werte wie oben (x=23 und y=11, wir setzen x als bekannt voraus)
x (mod y) = N (1)
<runphp>
| y | ';'.$i.' | ';
| N | ';'.$ret.' | ';
</runphp>
Schlüssel-Tausch-Problem
Das grundlegende Problem hierbei ist: Wie können sich Alice und Bob auf ein Geheimnis einigen (Schlüssel) über ein unsicheres Medium? Ohne dass Carl mit den Informationen etwas anfangen könnte? Dieses Problem bereitete Generationen von Kryptografen schlaflose Nächte. Hellman konzentrierte sich auf dieses Problem und sah folgende Einwegfunktion als optimal an:
Yx (mod P) = N
Alice und Bob sprechen miteiander erst die Werte für Y (7) und P (11) ab. Diese sind nicht geheim und Carl darf diese kennen. Solange P grösser als Y ist, sind eigentlich alle Zahlen erlaubt.
| Alice | Bob | |
| Stufe 1 | wählt einen Wert für x (3) Das ist der geheime Teil | wählt einen Wert für x (6) Das ist der geheime Teil |
| Stufe 2 | 73(mod 11)= 343(mod 11)= 2 | 76(mod 11)= 117649(mod 11)= 4 |
| Stufe 3 | Senden des Resultats an Bob | Senden des Resultats an Alice |
| Austausch | Normalerweise ist das der kritische Moment beim Austausch von sensitiven Informationen. Carl kann die jeweiligen Resultate abfangen. Es ist jedoch gerade der Clou dieser Idee, dass diese Informationen nicht ausreichen, weil sie eben nicht der Schlüssel sind. Carl kann damit überhaupt nichts anfangen, wie wir gleich sehen werden | |
| Stufe 4 | wendet Bob's Resultat mit ihrem geheimen x an 43(mod 11)=64(mod 11)=9 |
wendet Alice's Resultat mit seinem geheimen x an 26(mod 11)=64(mod 11)=9 |
| Schlüssel | Wie durch ein Wunder kommen Alice und Bob auf die gleiche Zahl, ohne diese Information ausgetauscht zu haben!! Das ist der Schlüssel für die sichere Kommunikation zwischen Alice und Bob | |
Schlüssel-Verteilungs-Problem
Hellman konzentrierte sich auf das Schlüssel-Tausch-Problem (obige Tabelle) und Diffie suchte nach einer völlig neuen Lösung der Schlüssel-Verteilung. Bis anhin war es so, dass die verwendeten Schlüssel der symmetrischen Verschlüsselung physisch überbracht werden mussten. Dazu wurden Kuriere eingesetzt, was natürlich sehr risikoreich war. z.B. mussten Banken tausende von Schlüsseln an Filialen und Kunden ausliefern und diese aus Sicherheitsgründen immer wieder zu erneuern. Wenn einer der Schlüssel kompromitiert wurde, dann mussten wieder neue Schlüssel an die Betroffenen ausgeliefert werden. Eine Übertragung der Schlüssel via Telefon (unsicheres Medium) kam nicht in Frage, da bei symmetrischen Verschlüsselungen der Schlüssel nicht nur zum Ver-sondern auch zum Entschlüsseln gebraucht wird. Carl könnte die Schlüssel sonst mithören und die Kommunikation zwischen Alice und Bob entschlüsseln. Auch könnte er den Kurier, der den Schlüssel von Alice zu Bob bringt, überfallen und ihm den Koffer klauen oder den Schlüssel unbemerkt kopieren!
Und genau hier kommt die volle Eleganz eines Public-Key-Verfahrens zum Tragen. Nicht nur, dass Alice und Bob sich auf einen Schlüssel einigen können ohne diesen austauschen zu müssen, die asymmetrische Methode und ihre zwei Schlüssel sorgt dafür, dass Alice ihren Public Key der ganzen Welt via ein unsicheres Medium (damals Telefon, heute Internet) bekanntmachen kann. Sie muss nicht befürchten, dass jemand mit diesem Schlüssel an sie gerichtete Meldungen entschlüsseln kann Alice und Bob können ihre öffentlichen Schlüssel der ganzen Welt zugänglich machen, damit ihnen diese verschlüsselte Mitteilungen senden können. Dazu werden vorzugsweise öffentliche Key-Server eingesetzt.
Diffie und Hellman lösten damit zwei der grössten Probleme der Kryptografie auf einen Schlag und legten den Grundstein für praktisch alle heute eingesetzten Kryptosysteme. Sie sorgten dafür, dass sich Alice und Bob auf ein Geheimnis einigen können ohne diese Information wirklich zu senden (Schlüssel-Austausch-Problem) und dafür, dass ein Schlüssel völlig risikolos öffentlich zugänglich gemacht werden kann (Schlüssel-Verteilungs-Problem). Die Sicherheit aller bisherigen Kryptosysteme kam an einem oder beiden dieser Probleme an die Grenzen
Anwendungen von Public-Key
RSA als erste Implementation des Public-Key Verfahrens
Geschichte
Nachdem Whitfield Diffie und Martin Hellman ihre Theorie zur Public-Key-Kryptografie veröffentlicht hatten, versuchten die drei Mathematiker Rivest, Shamir und Adleman, die Annahmen von Diffie und Hellman zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stießen sie schließlich auf eines, bei dem sie keinerlei Angriffspunkte fanden. Hieraus entstand dann RSA.
Verschlüsselung
Das Verfahren wurde 1977 entwickelt und basiert auf dem aktuellen Wissensstand, dass die Faktorisierung einer großen Zahl, also ihre Zerlegung in ihre Primfaktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen recht einfach ist. Wenn nun eine Nachricht einem Empfänger verschlüsselt zugeleitet werden soll, generiert dieser einen öffentlichen Schlüssel. Der Nachrichtenabsender verwendet diesen öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese „dekodieren“, da nur er die „Zusammensetzung“ des von ihm erzeugten (öffentlichen) Schlüssels kennt.
Digitale Signaturen
Bei Signaturen wird prinzipiell der umgekehrte Weg gegangen. Alice verschlüdselt ihre Nachricht an Bob mit ihrem privaten Schlüssel. Bob entschlüsselt den Text mit Alice's öffentlichen Schlüssel. Wenn dies gelingt, dann weiss Bob dass die Nachricht mit gr&oul;sster Wahrscheinlichkeit wirklich von Alice kommt. Praktischerweise, wiederum wegen der Langsamkeit von asymmetrischen Verfahren, wird nicht die gesamte Nachricht mittels dem privaten Key chiffriert. Sondern es wird erst ein sogenannter Hash Wert der Nachricht gebildet und dieser wird dann verschüsselt.
Solche Hash Werte werden durch Einwegfunktionen gebildet d.h. aus dem Hash Wert kann nicht auf den Inhalt geschlossen werden. Nur schon die Änderung eines einzelnen Bits wird einen völlig anderen Hash Wert produzieren. Eine sichere Hashfunktion wie SHA-256 erzeugt Funktionswerte mit einer Länge von ebenfalls 256 Bit. Damit lassen sich Signaturverfahren mittels RSA realisieren, die nur einen Verschlüsselungsschritt benötigen.
Wenn Bob jetzt also mit Sicherheit feststellen will, ob die Nachricht wirklich von Alice kam, dann wird er erst den verschlüsselten Hash Wert mit dem öffentlichen Schlüssel von Alice entschlüsseln. Dann bildet er von der Alice's Nachricht mit derselben Hash Funktion den Hash Wert und vegleicht ihn mit dem Hash, den Alice in ihrer Email als Signatur mitgeschickt hat. Wenn diese übereinstimmen dann weiss Bob, dass die Nachricht unverändert, wie von Alice geschrieben, angekommen ist.
PGP - Pretty Good Privacy
Ein gewisser Phil Zimmerman kam auf die Idee mit beiden Verfahren Emailtexte zu verschlüsseln und damit die Vorteile beider Techniken zu nutzen. Dabei werden die Inhalte der Email ganz normal symetrisch mit einem geheimen Schlüssel chiffriert. Erst der verwendete Schlüssel wird dann mittels eines asymetrischen Verfahrens mit dem öffentlichen Schlüssel des Empfängers verschlüsselt und mit übermittelt. Auf der Gegenseite entschlüsselt Zimmerman's Erfindung PGP erst den Schlüssel mit seinem privaten Key und entschlüsselt mit diesem dann die Nachricht zu Klartext
Faierweise muss angefügt werden, dass bereits die Entwickler von RSA das System als Hybridsystem gesehen haben. Mit einer symetrischen Verschlüsselung für die Nachricht mit entsprechenden Algorithmen.Als sehr sicher eingestufte Algorithmen zur symmetrischen Verschlüsselung gelten 3DES und AES. Diese verwenden 112, 128, 168 oder maximal 256 Bit. Dies entspricht bei 256 Bit ca. 77 Dezimalstellen. Damit ist ein Brute-Force-Angriff faktisch auszuschließen.
Zum Verschlüsseln des verwendeten Schlüssels wird dieser dann mit dem Public Key des Empfängers chiffriert