2. Das RSA Verfahren

Das RSA Verfahren ist ein asymmetrisches Verfahren, da öffentlicher und privater Schlüssel unterschiedlich sind. Es ist ein Public-Key Verfahren, da die Entschlüsselungsfunktion durch den öffentlichen Schlüssel jedermann zugänglich gemacht wird die Verschlüsselungsfunktion, der private Schlüssel, geheim gehalten werden muß. Die beiden Funktionen sind so angelegt, daß ein unbekannter aus dem öffentlichen Schlüssel zwar grundsätzlich den privaten Schlüssel berechnen kann, diese Berechnung aber soviel Aufwand erfordert, daß die Berechnung selbst mit Computerunterstützung nicht in vernünftiger Zeit vollendet werden kann.

Der Vertrauenswürdige Dritte (Schlüsselvergabestelle) hat dabei folgende Aufgaben.

2.1 Algorithmus

• Es werden zwei große Primzahlen p und q gewählt (ca. 150 Dezimalstellen = ca. 512 Bit) und das Produkt n=pq gebildet (ca. 1024 Bit).
• Es wird die (später beschriebene) Eulersche Funktion Phi(n)=(p-1)(q-1) gebildet.
• Es werden zwei Zahlen e und d bestimmt, so daß gilt e*d mod Phi_(n)=1 wobei e eine natürliche Zahl zwischen 1 und n und der größte gemeinsame Teiler ggT(e, Phi_(n))=1, wobei d eine natürliche Zahl ist und gilt e*d=1 mod Phi_(n)
• Die Zahlen e und n bilden den öffentlichen Schlüssel (Verschlüsselungsfunktion), die Zahlen n und d bilden den privaten Schlüssel (Entschlüsselungsfunktion)
• Die Primzahlen p und q werden von der Schlüsselvergabestelle gelöscht.

Die Eulersche Funktion Phi_(x):

Sie gibt für die natürliche Zahl x die Anzahl der zu x teilerfremden Zahlen an die kleiner sind als die Zahl x selbst.

Berechnungsbeispiel:

Phi₍₈₎=4, da die Zahlen 1,3,5 und 7 keinen gemeinsamen Teiler mit 8 haben

Phi₍₁₈₎=6, da die Zahlen 1,3,5,7,11 und 17 keinen gemeinsamen Teiler mit 18 haben

Sind p₁ und p₂ Primzahlen, so gilt speziell:

Satz von Euler:

Für zwei teilerfremde Zahlen a und b gilt die Beziehung:

Wählt man speziell für b=p1*p2, dann gilt:

2.2 Ablauf der Verschlüsselungs- und Entschlüsselungsfunktionen

Bemerkung: Nach [2] wird hier die Entschlüsselung mit dem privaten Schlüssel und die Verschlüsselung mit dem öffentlichen Schlüssel geleistet.

Ein (vorher in Zahlen umgewandelter) Klartext w wird verschlüsselt durch die Abbildung

mit dem öffentlichen Schlüssel (n, e).

Die Entschlüsselung leistet die Abbildung

mit dem privaten Schlüssel (n, d) über den Schlüsseltext w.

Beispiel:

und

Man wählt für e zwischen 1 und n und ggT(e, 2668)=1 z.B. die Zahl 17

für d wählt man die Zahl 157, da gilt: e*d=2669 und 2669 mod 2668=1.

Dadurch sind die Verschlüsselungs- und die Entschlüsselungsfunktion gegeben.

Um den Text zu verschlüsseln müssen noch die Buchstaben in Zahlen umgewandelt werden.

Man setzt A=01 B=02, C=03 ... Leerzeichen = 00.

Das als Zahl dargestellte Wort wird anschließend in Blöcke gleicher Größe zerlegt, die getrennt verschlüsselt werden. Für die Blockgröße empfiehlt sich die Zahl i, für die gilt

Hier

Die Zahldarstellung von "Wort" lautet z.B.

Zerlegung in Blöcke der Länge 4:

Durch Anwendung der Verschlüsselungsfunktion folgt für den Schlüsseltext

denn es gilt z.B.

Mit Hilfe der Entschlüsselungsfunktion erhält man den Klartext zurück:

Die bei der Ver- und Entschlüsselung auftretenden hohen Potenzen brauchen nicht effektiv ausgerechnet zu werden. Es gibt Algorithmen , mit denen das Ergebnis indirekt berechnet werden kann(stochastischer Algorithmus).[2]

Da die Zahl e den öffentlichen Schlüssel darstellt und der Allgemeinheit bekannt gemacht wird, kann die Zahl e auch frei gewählt werden. Sinnvoller Weise wählt man den öffentlichen Schlüssel so, daß der Chiffrieraufwand klein ist. Eine sinnvolle Wahl ist z.B. e=2¹⁶+1, da die Registerbreite von 16 bzw. 32 Bit Rechenzeitvorteile hat. Eine Benutzergruppe kann so beispielsweise denselben öffentlichen Schlüssel verwenden, ohne daß die Sicherheit dadurch in Gefahr wäre. Der öffentliche Schlüssel kann aber auch gesondert und als Geheimtext übermittelt werden, da das Verfahren sowohl für die Digitale Signatur als auch zur Schlüsselübermittlung funktioniert.

2.3 Unterschriften mit dem RSA-Verfahren und Einweg-Hashfunktionen

Beim obigen Beispiel sind alle Punkte für die Sicherheit erfüllt.

Diese Methode hat allerdings immer noch gravierende Nachteile:

• Asymmetrisch Verfahren sind außerordentlich langsam. Umfangreiche Dokumente können damit nicht unterzeichnet werden.
• Das Unterschriebene Dokument ist zunächst nicht lesbar, es muß erst mit dem öffentlichen Schlüssel zeitaufwendig chiffriert werden. In der Praxis wird der unterzeichnete Text daher meist lesbar kursieren. Die Unterschrift ist daher nicht mehr überprüfbar. Die Gefahr nachträglicher Manipulationen ist hoch.
• Beim Unterzeichnen fremder Dokumente ist mit ausgewähltem Geheimtext ein Angriff auf das RSA-Verfahren möglich. Zum signieren sollte daher ein anderes Schlüsselpaar verwendet werden als zur Schlüsselübermittlung .

Einweg-Hashfunktionen

Hier sind nur die wichtigsten Eigenschaften von Einweg-Hashfunktionten aufgeführt. Über das komplexe Gebiet gibt es im Rahmen dieser Semesterarbeit ein separates Kapitel.

Einweg-Hashfunktionen bilden den Klartext in einer Prüfsumme (Hash-Summe) ab.

Die Abbildung ist nicht umkehrbar.

Wird nur ein Zeichen des Klartextes verändert so entsteht eine andere Prüfsumme.

Es ist unmöglich für verschiedene Klartexte die gleichen Prüfsummen zu erzeugen.

Die Prüfsumme hat immer die gleiche Länge und ist wesentlich kleiner als der Klartext.

Es ist möglich mit einem Schlüssel auch individuelle Prüfsummen zu erzeugen.

Die Prüfsumme ist somit eine Art komprimierter Klartext.

Der Empfänger einer Nachricht kann mit der Prüfsumme und dem zugehörigen Schlüssel für die Hash-Funktion überprüfen ob das erhaltene Dokument während der Übertragung verändert wurde.

Die Übermittlung eines Dokument ist dann in folgende Schritte eingeteilt

• Alice bildet die Hash-Summe ihres Dokuments und verschlüsselt die Hash-Summe mit ihrem privaten Schlüssel. Der verschlüsselte Hash-Summe bildet dabei Ihre Signatur.
• Alice hängt die Signatur an ihren Klartext an und schickt das Paket über den Datenkanal.
• Bob entschlüsselt dann zuerst die Signatur mit Alices öffentlichen Schlüssel und erhält die Hash-Summe. Nun bildet er ebenfalls die Hash-Summe des Klartextes und vergleicht die beiden Hash-Summen miteinander. Sind die Hash-Summen gleich, so kann er davon ausgehen, daß der Klartext nicht verändert wurde. Er kann auch davon ausgehen, daß die Nachricht von Alice stammt. Wäre das Dokument zum Beispiel eine Warenbestellung, könnte Alice diese später auch nicht leugnen.

Damit sind die obigen Nachteile ausgeschaltet:

• Hash-Summen sind in der Regel relativ kurz (ca. 20 Byte lang). Die Anwendung von RSA auf die Prüfsumme ist von der Textlänge unabhängig und kostet wenig Zeit.
• Hash-Summen sind nicht voraussagbar. Deshalb ist ein Angriff mit ausgewähltem Geheimtext nicht möglich.
• Das Dokument ist für jedermann lesbar und bei Kenntnis des öffentlichen Schlüssels auch jederzeit überprüfbar.

Digitale Signatur mit RSA

2.4 Unterschriften mit dem RSA-Verfahren und öffentlichem Schlüsseltausch

In der Anwendung lassen sich viele Fälle finden, bei denen das chiffrieren des Klartextes zu einem Geheimtext erforderlich ist. Das unten aufgeführte Beispiel zeigt ein mögliches Protokoll, wie ein Dokument unleserlich über einen Datenkanal verschickt werden kann. Dabei müssen die öffentlichen Schlüssel der Partner ausgetauscht werden.

Das Protokoll hat folgenden Ablauf

• Der Sender entschlüsselt einen Text mit seinem privaten Schlüssel und erzeugt damit seine Signatur.
• Dokument und Signatur werden dann gemeinsam mit dem öffentlichen Schlüssel des Empfängers verschlüsselt und über den Kanal geschickt.
• Der Empfänger entschlüsselt dann die erhaltenen Daten mit seinem privaten Schlüssel und erhält den Klartext und die Signatur in entschlüsselter Form.
• Jetzt wendet der Empfänger noch den öffentlichen Schlüssel des Senders auf die Signatur an und erhält den Klartext der Unterschrift.

Digitale Signatur und öffentlicher Schlüsseltausch mit RSA