PGP

RSA hat das Problem der Schlüsselverteilung gelöst, indem es die geheime Übermittlung eines Schlüssels überflüssig machte. Man muss nur einen öffentlichen Schlüssel publizieren, den jeder sehen darf und mit dem jeder verschlüsseln kann. Entschlüsseln kann jedoch nur derjenige mit dem privaten Schlüssel.

Der Nachteil dabei ist, dass bei asymmetirschen Verschlüsselungsverfahren viel leistungsfähigere Computer benötigt werden als bei symmetrischen Verfahren; je nach Länge der Botschaft dauert der Vorgang mehrere Minuten. Symmetrische Chiffrierungen setzen aber die Kenntnis des Schlüssels für alle Parteien voraus.

Um die Vorteile beider Verfahren zu kombinieren, verwendet man heute eine hybride Verschlüsselung. Ein bekanntes Beispiel ist das von Phil Zimmermann entwickelte Verfahren PGP.

Pretty Good Privacy

Pretty Good Privacy (PGP) benutzt ein sogenanntes Public-Key-Verfahren; benutzt wird ein öffentlicher Schlüssel, mit dem jeder Daten für den Empfänger verschlüsseln und dessen Signaturen prüfen kann. Der Empfänger besitzt einen privaten, geheimen Schlüssel. Nachrichten an einen Empfänger werden mit dessen öffentlichem Schlüssel verschlüsselt und können dann ausschliesslich mittels seines privaten Schlüssels entschlüsselt werden. Die erste Version wurde im Jahr 1991 geschrieben und verwendete einen RSA-Algorithmus zur Verschlüsselung der Daten.

Bei PGP wird aber nicht die ganze Nachricht asymmetrisch verschlüsselt; dies wäre viel zu rechenintensiv und nicht praktikabel. Stattdessen wird nur der verwendete Schlüssel asymmetrisch verschlüsselt und die eigentliche Nachricht symmetrisch (Hybride Verschlüsselung). Dazu wird jedes Mal ein symmetrischer Schlüssel - ein Session Key - zufällig erzeugt. Dieser symmetrische Schlüssel wird dann z.B. per RSA-Kryptosystem mit dem öffentlichen Schlüssel des Empfängers verschlüsselt und der Nachricht hinzugefügt. Dadurch ist es möglich, eine Nachricht für mehrere Empfänger gleichzeitig zu verschlüsseln. (Quelle: Wikipedia, 2020)

Elektronische Unterschrift

Wie kann Bob sicher sein, dass die Nachricht wirklich von Alice stammt und nicht von Eve abgefangen und durch eine andere ersetzt wurde? Das wäre möglich, weil Eve ja ebenfalls den öffentlichen Schlüssel von Bob kennt!

Mit dem RSA-Verfahren kann eine elektronische Unterschrift berechnet werden. Zuerst wird mithilfe einer Hashfunktion der Hashwert der Nachricht generiert. Dieser ist wie ein Fingerabdruck der Daten, auf die die Hashfunktion angewendet wurde.

Den Hash $h$ der Nachricht signiert Alice mit ihrem privaten Schlüssel $d$ .

s\equiv hd \mod n

Weil $(h^d)^e(\mod n)\equiv h$ gilt, kann Bob den signierten Hashwert $s$ mit dem öffentlichen Schlüssel $e$ von Alice entschlüsseln.

h\equiv s^e\mod n

Damit erhält er wieder den Hashwert und kann sich jetzt sicher sein, dass er von Alice stammt - weil er mit ihrem privaten Schlüssel signiert wurde, den nur sie kennt.

Exercise 1: Verschlüssle mit RSA

Alice hat dir eine Nachricht $c$ geschickt. Sie ist mit Caesar verschlüsselt. Den Schlüssel $k$ für Caesar hast du ebenfalls erhalten. Er ist mit deinem öffentlichen RSA-Schlüssel verschlüsselt. Zudem hat sie den Hashwert $h_A$ generiert und mit ihrem privaten RSA-Schlüssel signiert. Berechne deinen privaten Schlüssel, bestimme $k$ und die Nachricht $m$ , generiere den Hashwert $h$ von $m$ und vergleiche ihn mit dem von Alice.

Verschlüsseltes $k= 243$

$c =$ DOOHVRN

Signiertes $h_A = 262$

Öffentlicher Schlüssel Alice $= (N, E) = (341, 11)$

Deine Zahlen: $p= 37$ , $q= 163$ , $e = 5$

Dein privater Schlüssel $= (n, d) = (6031, ?)$

$d=$ ?, $k=$ ?, $m =$ ?, $h=$ ?

Solution

Verschlüsseltes $k = 243$

$c = \text{DOOHVRN}$

Signiertes $h_A = 262$

Öffentlicher Schlüssel von Alice: $(N, E) = (341, 11)$

Deine Zahlen: $p = 37$ , $q = 163$ , $e = 5$

Privater Schlüssel: $(n, d) = (6031, \ ?)$

Zuerst bestimmen wir den privaten Schlüssel $d$ :
$n = 37 \cdot 163 = 6031$

$\varphi(n) = (p - 1) \cdot (q - 1) = 36 \cdot 162 = 5832$

$5832 = 1166 \cdot 5 + 2 \Rightarrow 2 = 5832 − 1166 \cdot 5$

$5 = 2 \cdot 2 + 1 \Rightarrow 1 = 5 − 2 \cdot 2$

Rückwärts eingesetzt:

\begin{align*} 1 &= 5 − 2 \cdot 2 \\ 1 &= 5 − 2 \cdot (5832 − 1166 \cdot 5) \\ &= 5 − 2 \cdot 5832 + 2332 \cdot 5 \\ &= 2333 \cdot 5 − 2 \cdot 5832 \end{align*}

$\Rightarrow d = 2333$

Jetzt können wir den verschlüsselten Caesar-Schlüssel $k_v$ entschlüsseln:

k = k_v^d \mod n \equiv 243^{2333} \mod 6031 \equiv 3

Damit sind wir in der Lage, die Nachricht $m$ auszurechnen. Die Verschiebung um $k = 3$ Buchstaben ergibt: $c = \text{DOOHVRN} \Rightarrow m = \text{alles ok}$

Hashwert $h$ berechnen: $m = \text{alles ok} \Rightarrow (1+12+12+5+19+15+11) \mod 11 = 75 \mod 11 \equiv 9$

Hashwert von Alice $h_A$ aus dem signierten Hashwert $h_s$ berechnen:

h_A = h_s^E \mod N = 262^{11} \mod 341 \equiv 9

Zusammenfassung:

$d = 2333$
$k = 3$
$m = \text{alles ok}$
$h = 9$
$h_A = 9$

Da $h = h_A$ , wurde die Nachricht unverfälscht von Alice übermittelt. ✅

Note 1

Den Hashwert $h$ generierst du in Aufgabe 19, indem du bei der Nachricht $m$ die Buchstaben $a = 1$ , $b = 2$ , $\dots$ , $z = 26$ setzt und die Zahlen addierst. Die erhaltene Zahl rechnest du $(\text{mod}\ 11)$ und erhältst den Hashwert $h$ .

Example 1

Der Hashwert von "du" ist: $d + u = (4 + 21) \mod 11 \equiv 25 \mod 11 \equiv 3$

PGP schematisch

Schematisch habe ich dies so wie in folgender Abbildung illustriert:

(PGP kommentiert)

Wir simulieren das Verfahren mit RSA als Übung und verwenden als Hash/Fingerprint die Check-Digit aus der ISBN-10 Nummer aus dem Abschnitt Barcode.

Zertifikate

Ein Fall wurde bisher ausgeklammert: Es kann sein, dass der Betrug schon zu Beginn geschah. Eve könnte in Bobs Namen ihren eigenen Schlüssel Alice unterjubeln. Jetzt kann Eve sich als Bob ausgeben und in seinem Namen alle Nachrichten abfangen, lesen und beantworten. Alice realisiert nichts, weil sie ja davon ausgeht, mit Bob zu kommunizieren.

Damit das nicht geschieht, gibt es sogenannte Zertifikate. Ein Zertifikat ist wie ein Personalausweis und enthält den Namen und den öffentlichen Schlüssel des Inhabers - dazu gehört immer eine Zertifizierungsstelle (CA), die den Schlüsselinhaber authentisiert und das Zertifikat ausstellt.

Je nach Geschäftsart können noch weitere Merkmale enthalten sein. Signiert wird der Hashwert des Zertifikats mit dem privaten Schlüssel der Zertifizierungsstelle und diese bürgt für die Richtigkeit der Informationen auf dem Zertifikat. Jeder kann bei der Zertifizierungsstelle das Zertifikat von Alice oder Bob verlangen und weil es von der CA verifiziert ist, kann er sich sicher sein, dass er mit jener Person kommuniziert, auf welche das Zertifikat ausgestellt ist. Die Zertifikate der wichtigsten Zertifizierungsstellen sind auf dem Computer vorinstalliert.

Vertraulichkeit; niemand kann sich unerlaubt Informationen beschaffen – Übergabe des IDEA-Schlüssels mit RSA – Verschlüsselung mit IDEA
Integrität; jede Datenmanipulation wird bemerkt – Übermittlung des signierten Hashwertes der Nachricht
Authentizität; Identitätsnachweis des Kommunikationspartners – Von der CA signiertes Zertifikat mit Personalien und öffentlichem RSA-Schlüssel

Will Alice eine Mail an Bob schreiben, funktioniert das so:

Alice: Der Computer fragt die oberste Zertifizierungsstelle nach dem Zertifikat von Bob. Diese leitet ihn an eine Tochter-CA weiter. Die CA schickt Alice das Zertifikat von Bob und den mit dem eigenen privaten Schlüssel signierten Hashwert. Alice entschlüsselt den Hashwert des Zertifikats mit dem öffentlichen Schlüssel der CA und vergleicht ihn mit dem selbst erzeugten Hash. Danach schreibt sie ihre Nachricht und verschlüsselt sie mit IDEA. Den Schlüssel zu IDEA chiffriert sie mit Bobs öffentlichem Schlüssel, den sie auf dem Zertifikat findet, und sendet ihn zusammen mit der chiffrierten Nachricht an Bob. Zuletzt generiert sie den Hashwert der Nachricht, signiert ihn mit ihrem privaten Schlüssel und lässt auch diesen ihrem Kommunikationspartner zukommen.
Bob: entschlüsselt den IDEA-Schlüssel mit seinem privaten Schlüssel. Danach dechiffriert er die Nachricht mit dem Schlüssel, den er eben entschlüsselt hat. Er berechnet den Hashwert der Nachricht und vergleicht ihn mit dem Hashwert, den ihm Alice geschickt hat. Diesen dechiffriert er mit dem öffentlichen Schlüssel von Alice, den er ihrem Zertifikat entnommen hat.

Exercise 2: Default Public Exponent

Der Public Exponent wird gerne $65'537$ gesetzt; wieso? (Hint: Checke $2$ er Potenzen.)

Solution

Es ist $65'537=2^{16}+1$ und damit hat diese Zahl eine Binärdarstellung mit vielen Nullen, was das Potenzieren erleichtert.

Beim E-Banking und Online-Bestellungen geschieht all dies mittlerweile automatisch. Wird etwas mit der Kreditkarte bezahlt, verschlüsselt der Computer die PIN und die Kartennummer, ohne dass man etwas dafür tun muss.