Verschlüsselung mit öffentlichem Schlüssel
Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings
Asymmetrische Schlüssel
Public-Key-Zertifikat
Public-Key (asymmetrischer) kryptografischer Algorithmus
Public-Key-Infrastruktur (PKI)
Zwei zusammengehörige Schlüssel, ein öffentlicher und ein privater Schlüssel, die zur Durchführung komplementärer Operationen verwendet werden, z. B. Ver- und Entschlüsselung oder Signaturerstellung und Signaturprüfung.
Ein digitales Dokument, das mit dem privaten Schlüssel einer Zertifizierungsstelle (eng:Certification Authority) ausgestellt und digital signiert wird und den Namen eines Teilnehmers an einen öffentlichen Schlüssel bindet. Das Zertifikat gibt an, dass der im Zertifikat genannte Teilnehmer die alleinige Kontrolle und den Zugriff auf den entsprechenden privaten Schlüssel hat.
Ein kryptographischer Algorithmus, der zwei zusammengehörige Schlüssel verwendet, einen öffentlichen und einen privaten Schlüssel. Die beiden Schlüssel haben die Eigenschaft, dass die Ableitung des privaten Schlüssels aus dem öffentlichen Schlüssel rechnerisch nicht machbar ist bzw. sein sollte (vgl. Quantenkryptografie).
Eine Reihe von Richtlinien, Prozessen, Serverplattformen, Software und Workstations, die für die Verwaltung von Zertifikaten und öffentlich-privaten Schlüsselpaaren verwendet werden, einschließlich der Möglichkeit, Public-Key-Zertifikate auszustellen, zu pflegen und zu widerrufen.
Public-Key-Verschlüsselung ist sicherer vor Kryptoanalyse als die symmetrische Verschlüsselung.
Public-Key-Kryptografie (d. h. die Verschlüsselung mit öffentlichen Schlüsseln) ist eine Allzwecktechnik, die die symmetrische Verschlüsselung überflüssig gemacht hat.
Man hat das Gefühl, dass die Schlüsselverteilung bei der Verschlüsselung mit öffentlichen Schlüsseln trivial ist, verglichen mit dem mühsamen Handshaking, das bei der symmetrischen Verschlüsselung mit Schlüsselverteilungszentren verbunden ist.
Das Konzept der Public-Key-Kryptographie (d. h. der Kryptografie mit öffentlichen Schlüsseln) entstand aus dem Versuch, zwei der schwierigsten Probleme im Zusammenhang mit der symmetrischen Verschlüsselung zu lösen:
KDC = Key Distribution Center
Whitfield Diffie und Martin Hellman von der Stanford University erzielten 1976 einen Durchbruch, indem sie eine Methode entwickelten, die beide Probleme löste und sich radikal von allen bisherigen Ansätzen der Kryptografie unterschied.
Die lesbare Nachricht oder Daten, die dem Algorithmus als Eingabe dienen.
Führt verschiedene Umwandlungen des Klartextes durch.
Wird für Verschlüsselung oder Entschlüsselung verwendet.
Verwendet für Verschlüsselung oder Entschlüsselung.
Die verschlüsselte Nachricht, die als Ausgabe produziert wird.
Nimmt den Geheimtext und den passenden Schlüssel entgegen und erzeugt den ursprünglichen Klartext.
Konventionelle Verschlüsselung
Benötigt zur Anwendung:
Es wird derselbe Algorithmus mit demselben Schlüssel für die Ver- und Entschlüsselung verwendet.
Der Sender und der Empfänger müssen den Algorithmus und den Schlüssel kennen bzw. besitzen.
Notwendig für die Sicherheit:
Der Schlüssel muss geheim gehalten werden.
Es muss unmöglich oder zumindest unpraktisch sein, eine Nachricht zu entschlüsseln, wenn der Schlüssel geheim gehalten wird.
Die Kenntnis des Algorithmus und von (ggf. vielen) Geheimtexten ist nicht ausreichend, um den Schlüssel zu ermitteln.
Public-Key Verschlüsselung
Benötigt zur Anwendung:
Zwei Algorithmen: je einer für die Ver-/Entschlüsselung. Weiterhin ein Paar von Schlüsseln; je einer für die Ver-/Entschlüsselung.
Der Absender und der Empfänger müssen jeweils einen der passenden Schlüssel besitzen (nicht den gleichen).
Notwendig für die Sicherheit:
Einer der Schlüssel muss geheim bleiben.
Es muss unmöglich sein, eine Nachricht zu entschlüsseln, wenn ein Schlüssel geheim gehalten wird.
Die Kenntnis des Algorithmus und eines Schlüssels sowie von Geheimtexten ist nicht ausreichend, um den anderen Schlüssel zu ermitteln.
Kryptosysteme mit öffentlichen Schlüsseln lassen sich in drei Kategorien einteilen:
Ver-/Entschlüsselung: Der Absender verschlüsselt eine Nachricht mit dem öffentlichen Schlüssel des Empfängers.
Digitale Unterschriften: Der Absender „unterschreibt“ eine Nachricht mit seinem privaten Schlüssel.
Schlüsselaustausch: Zwei Seiten arbeiten zusammen, um einen Sitzungsschlüssel (d. h. einen symmetrischen Schlüssel) auszutauschen.
Einige Algorithmen eignen sich für alle drei Anwendungen, während andere nur für eine oder zwei verwendet werden können:
Algorithmus |
Ver-/ Entschlüsselung |
Digitale Signaturen |
Schlüssel-austausch |
|---|---|---|---|
RSA |
✓ |
✓ |
✓ |
Elliptic Curve |
✓ |
✓ |
✓ |
Diffie-Hellman |
✗ |
✗ |
✓ |
DSS |
✗ |
✓ |
✗ |
DSS = Digital Signature Standard, entwickelt von der NSA (National Security Agency)
Für eine Partei \(B\) ist es rechnerisch einfach, ein Schlüsselpaar (bestehend aus öffentlicher Schlüssel \(PU_b\) und privater Schlüssel \(PR_b\)) zu erzeugen.
Für einen Absender \(A\) ist es rechnerisch einfach, bei Kenntnis des öffentlichen Schlüssels von \(B\) und der zu verschlüsselnden Nachricht den entsprechenden Chiffretext zu erzeugen.
Für den Empfänger \(B\) ist es rechnerisch einfach, den resultierenden Chiffretext mit Hilfe des privaten Schlüssels zu entschlüsseln, um die ursprüngliche Nachricht wiederherzustellen.
Für einen Angreifer, der den öffentlichen Schlüssel kennt, ist es rechnerisch unmöglich, den privaten Schlüssel zu ermitteln.
Für einen Angreifer, der den öffentlichen Schlüssel und einen Chiffretext kennt, ist es rechnerisch unmöglich, die ursprüngliche Nachricht wiederherzustellen.
Die beiden Schlüssel können in beliebiger Reihenfolge verwendet werden.
Benötigt wird eine Falltürfunktion (Trapdoor one-way function)
Eine Einwegfunktion ist im Allgemeinen eine Funktion, bei der jeder Funktionswert eine eindeutige Umkehrung hat, wobei die Berechnung der Funktion einfach ist, während die Bestimmung der Umkehrfunktion praktisch undurchführbar ist.
\(Y = f(X)\) einfach
\(X = f^{–1}(Y)\) „unmöglich“
Eine Einwegfunktion mit Falltür ist eine Familie invertierbarer Funktionen \(f_k\), für die gilt:
\(Y = f_k(X)\) einfach, wenn \(k\) und \(X\) bekannt sind.
\(X = f_k^{–1}(Y)\) einfach, wenn \(k\) und \(Y\) bekannt sind.
\(X = f_k^{–1}(Y)\) unmöglich, wenn \(Y\) bekannt ist, aber k nicht.
Ein praktisches Public-Key-Verfahren hängt von einer geeigneten Trapdoor-Einwegfunktion ab.
Ein Falltürfunktion lässt sich nicht trivial umkehren; bzw. die Umkehrung erfordert spezielle (weitergehende) Informationen; d. h. die Falltür.
Ein Verschlüsselungsverfahren mit öffentlichem Schlüssel ist anfällig für einen Brute-Force-Angriff.
Gegenmaßnahme: große Schlüssel verwenden!
Die Schlüsselgröße muss klein genug sein, um eine praktische Ver- und Entschlüsselung zu ermöglichen.
Vorgeschlagene Schlüsselgrößen führen zu Verschlüsselungs-/Entschlüsselungsgeschwindigkeiten, die für den allgemeinen Gebrauch zu langsam sind.
Die Verschlüsselung mit öffentlichen Schlüsseln ist derzeit auf die Schlüsselverwaltung und Signaturanwendungen beschränkt.
Eine andere Form des Angriffs besteht darin, einen Weg zu finden, den privaten Schlüssel anhand des öffentlichen Schlüssels zu berechnen.
Bislang konnte nicht mathematisch bewiesen werden, dass diese Form des Angriffs für einen bestimmten Public-Key-Algorithmus nicht durchführbar ist.
Schließlich gibt es noch einen Angriff mit wahrscheinlicher Nachricht.
Dieser Angriff kann vereitelt werden, indem einige zufällige Bits an einfache Nachrichten angehängt werden.
Bei einem Angriff mit „wahrscheinlicher Nachricht“, verschlüsselt der Angreifer eine Reihe von Nachrichten (z. B. alle DES Schlüssel mit dem öffentlichen Schlüssel des Adressaten) und analysiert die resultierenden Chiffretexte, um den privaten Schlüssel zu ermitteln.
Entwickelt 1977 am MIT von Ron Rivest, Adi Shamir und Len Adleman.
Universeller Ansatz zur Verschlüsselung mit öffentlichen Schlüsseln.
Ist eine Chiffre, bei der Klartext und Chiffretext ganze Zahlen zwischen \(0\) und \(n - 1\) für ein bestimmtes \(n\) sind.
Eine typische Größe für \(n\) waren 1024 Bits oder 309 Dezimalziffern.
Solch kleine Zahlen werden heute als äußerst unsicher angesehen, insbesondere angesichts der bevorstehenden Quantencomputer und der Entwicklung von Quantenalgorithmen (vgl. Shors Algorithmus (1994)), die Zahlen effizient faktorisieren können, wenn genügend QBits in hinreichender Qualität[1] zur Verfügung stehen.
RSA verwendet einen Ausdruck mit Exponentialen
Der Klartext wird in Blöcken verschlüsselt, wobei jeder Block einen Binärwert hat, der kleiner als eine bestimmte Zahl \(n\) ist[2].
Die Ver- und Entschlüsselung erfolgt für einen Klartextblock \(M\) und einen Chiffretextblock \(C\) in der folgenden Form:
\(C = M^e\; mod\; n \qquad M = C^d\; mod\; n \qquad (M^e)^d\; mod\; n = M^{ed}\; mod\; n\)
Sowohl der Sender als auch der Empfänger müssen den Wert von \(n\) kennen.
Der Absender kennt den Wert von \(e\), und nur der Empfänger kennt den Wert von \(d\)
Dies ist ein Public-Key-Verschlüsselungsalgorithmus mit dem öffentlichen Schlüssel \(PU=\lbrace e,n \rbrace\) und dem privaten Schlüssel \(PR=\lbrace d,n \rbrace\).
\(M = C^d\; mod\; n \Rightarrow M = (M^e\; mod\; n)^d\; mod\; n = (M^e)^d\; mod\; n\)
Damit dieser Algorithmus für die Verschlüsselung mit öffentlichen Schlüsseln geeignet ist, müssen die folgenden Anforderungen erfüllt sein:
Es ist möglich, Werte für \(e\), \(d\), \(n\) so zu finden, dass \(M^{ed}\,mod\, n = M\) für alle \(M < n\).
Es ist relativ einfach, \(M^e\;mod\; n\) und \(C^d\, mod\, n\) für alle Werte von \(M < n\) zu berechnen.
Es ist nicht möglich, \(d\) zu bestimmen, wenn \(e\) und \(n\) gegeben sind.
Schlüsselgenerierung von Alice
Wähle \(p, q\) |
\(p\) und \(b\) beide prim, \(p \neq q\) |
Berechne \(n\) |
\(n = p \times q\) |
Berechne \(\phi (n)\) |
\(\phi(n) = (p - 1)(q - 1)\) |
Wähle \(e\) |
\(GGT(\phi(n),e) = 1; \qquad 1 < e < \phi(n)\) |
Berechne \(d\) |
\(d \equiv e^{-1}\; (mod\; \phi(n)) \Leftrightarrow ed\; mod\; \phi(n)= 1\) |
Public-Key |
\(PU = \lbrace e,n \rbrace\) |
Private-Key |
\(PR = \lbrace d,n \rbrace\) |
Verschlüsselung von Bob mit Alices öffentlichen Schlüssel
Klartext |
\(M<n\) |
Chiffretext |
\(C=M^e\; mod\; n\) |
Entschlüsselung von Alice mit ihrem privaten Schlüssel
Chiffretext |
\(C\) |
Klartext |
\(M = C^d\; mod\; n\) |
Der Wert von \(d\) wird mit Hilfe des erweiterten Euklidischen Algorithmus[3] berechnet.
Wir wissen dass \(GGT(\phi(n),e) = 1\) gilt; d. h. \(e\) und \(\phi(n)\) sind teilerfremd/coprime.
\(p = 11;\quad q = 17;\quad n = 187\qquad\qquad (\phi(n) = 10 \times 16 = 160)\)
\(88\)
\(PU =\lbrace e= 7, n= 187 \rbrace\):
\(88^7\;mod\; 187 = 11 = C\)
\(PR =\lbrace d= 23, n = 187 \rbrace\):
\(11^{23}\; mod\; 187 = 88 = P\)
\(e = 137 \Rightarrow d = 153\)
\(\qquad 88^{137}\; mod\; 187 = 99 = C\qquad\qquad 99^{153}\; mod\; 187 = 88\)
Sowohl bei der Verschlüsselung als auch bei der Entschlüsselung in RSA wird eine ganze Zahl potenziert mit einer weiteren ganzen Zahl \(mod\; n\).
Weiterhin haben wir es mit potenziell großen Exponenten zu tun, so dass die Effizienz der Potenzierung eine wichtige Rolle spielt.
Eine Eigenschaft der modularen Arithmetik kann genutzt werden:
\([(a\; mod\; n) \times (b\; mod\; n)]\; mod\; n =(a \times b)\; mod\; n\)
Beispiel:
\([11 = 1011_b]\qquad 2^{11} = 2^1 \times 2^2 \times 2^8 = 2 \times 4 \times 256\)
\([09 = 1001_b] \qquad 2^9\; mod\; 13 = [(2^1\; mod\; 13) \times (2^8 \; mod\; 13)]\; mod\; 13\)
Wiederholung
Quadrieren und Multiplizieren (Square and Multiply)
Die Ganzzahl \(b\) wird als Binärzahl b[k]b[k-1]...b[0] ausgedrückt:
c := 0; f := 1
for i := k downto 0
do c := 2 * c
f := (f * f) mod n
if b[i] = 1
then c := c + 1
f := (f * a) mod n
return f\(a=7; b = 560 = 1000110000_b\), und \(n=561\)
i |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|---|---|---|---|---|---|---|---|---|---|---|
\(b_i\) |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
c |
1 |
2 |
4 |
8 |
17 |
35 |
70 |
140 |
280 |
560 |
f |
7 |
49 |
157 |
526 |
160 |
241 |
298 |
166 |
67 |
1 |
Um den RSA-Algorithmus bei Verwendung des öffentlichen Schlüssels zu beschleunigen, wird in der Regel eine bestimmte Wahl von \(e\) getroffen:
Die häufigste Wahl ist 65537 (\(2^{16} + 1\)).
Zwei weitere beliebte Wahlmöglichkeiten sind \(e=3\) und \(e=17\).
Jede dieser Möglichkeiten hat nur zwei 1-Bits, so dass die Anzahl der Multiplikationen, die für die Potenzierung erforderlich sind, minimiert wird.
Mit einem sehr kleinen öffentlichen Schlüssel, wie \(e = 3\), wird RSA jedoch anfällig für einen einfachen Angriff.
Die Entschlüsselung verwendet die Potenzierung mit \(d\).
Ein kleiner Wert von \(d\) ist jedoch anfällig für einen Brute-Force-Angriff und für andere Formen der Kryptoanalyse.
Der Chinesischen Restsatz (CRT) kann verwendet werden, um Berechnungen zu beschleunigen:
Die Größen \(d\; mod\; (p - 1)\) und \(d\; mod\; (q - 1)\) können vorberechnet werden.
Das Ergebnis ist, dass die Berechnung etwa viermal so schnell ist wie die direkte Berechnung von \(M = C^d\; mod\; n\).
Vor der Anwendung des Public-Key-Kryptosystems muss jeder Teilnehmer ein Schlüsselpaar erzeugen:
Bestimmung der Primzahlen \(p\) und \(q\).
Wahl von \(e\) oder \(d\) und Berechnung der anderen.
Da der Wert von \(n = pq\) jedem potenziellen Gegner bekannt sein wird, müssen die Primzahlen aus einer ausreichend großen Menge ausgewählt werden.
Die Methode, die zum Finden großer Primzahlen verwendet wird, muss einigermaßen effizient sein.
Es kann z. B. der Miller-Rabin-Algorithmus verwendet werden.
Dabei werden alle möglichen privaten Schlüssel ausprobiert.
Es gibt mehrere Ansätze, die vom Aufwand her alle dem Faktorisieren des Produkts aus zwei Primzahlen entsprechen.
Diese hängen von der Laufzeit des Entschlüsselungsalgorithmus ab.
Hier geht es darum, Hardware-Fehler in den Prozessor zu induzieren, der digitale Signaturen erzeugt.
Ziel ist es Eigenschaften des RSA-Algorithmus auszunutzen.
Es gibt drei Ansätze für einen mathematischen Angriff auf RSA:
Faktorisierung von \(n\) in seine beiden Primfaktoren. Dies ermöglicht die Berechnung von \(\phi(n) = (p - 1) \times (q - 1)\), was wiederum die Bestimmung von \(d = e^{-1} (mod\; ø(n))\) ermöglicht.
Direkte Bestimmung von \(\phi(n)\), ohne vorher \(p\) und \(q\) zu bestimmen. Dies ermöglicht wiederum die Bestimmung von \(d = e^{-1} (mod\; \phi(n))\).
Direkte Bestimmung von \(d\), ohne vorher \(\phi(n)\) zu bestimmen.
Paul Kocher, ein IT-Sicherheits-Berater, demonstrierte, dass ein Schnüffler einen privaten Schlüssel ermitteln kann, indem er verfolgt, wie lange ein Computer braucht, um Nachrichten zu entschlüsseln.
Diese Angriffe sind nicht nur auf RSA, sondern auch auf andere Verschlüsselungssysteme mit öffentlichen Schlüsseln anwendbar.
Solche Angriffe sind aus zwei Gründen alarmierend:
Es kommt aus einer völlig unerwarteten Richtung.
Es handelt sich um einen reinen Chiffretext-Angriff.
Es gilt sicherzustellen, dass alle Potenzierungen die gleiche Zeit benötigen, bevor ein Ergebnis zurückgegeben wird; dies ist eine einfache Lösung, die jedoch die Leistung beeinträchtigt.
Eine bessere Leistung könnte erreicht werden, indem man dem Potenzierungsalgorithmus eine zufällige Verzögerung hinzufügt, um den Zeitangriff zu verwirren.
Multiplikation des Chiffriertextes mit einer Zufallszahl vor der Potenzierung; dieser Vorgang verhindert, dass der Angreifer erfährt, welche Bits des Chiffriertextes im Computer verarbeitet werden, und verhindert somit die für den Timing-Angriff erforderliche Bit-für-Bit-Analyse.
Ein Angriff auf einen Prozessor, der digitale RSA-Signaturen erzeugt.
Verursacht Fehler in der Signaturberechnung, indem er die Leistung des Prozessors reduziert.
Diese Fehler führen dazu, dass die Software ungültige Signaturen erzeugt, die dann vom Angreifer analysiert werden können, um den privaten Schlüssel wiederherzustellen.
Der Angriffsalgorithmus besteht darin, Ein-Bit-Fehler zu erzeugen und die Ergebnisse zu beobachten.
Obwohl dieser Angriff eine Überlegung wert ist, scheint er in vielen Anwendungen keine ernsthafte Bedrohung für RSA darzustellen.
Er setzt voraus, dass der Angreifer physischen Zugriff auf den Zielcomputer hat und in der Lage ist, die Eingangsleistung des Prozessors direkt zu kontrollieren.
(Fault-based attack)
(Chosen Ciphertext Attack (CCA))
Der Angreifer wählt eine Reihe von Chiffretexten aus und erhält dann die entsprechenden Klartexte, die mit dem privaten Schlüssel des Ziels entschlüsselt wurden.
Der Angreifer könnte also einen Klartext auswählen, ihn mit dem öffentlichen Schlüssel des Ziels verschlüsseln und dann den Klartext zurückerhalten, indem er ihn mit dem privaten Schlüssel entschlüsselt.
Der Angreifer macht sich die Eigenschaften von RSA zunutze und wählt Datenblöcke aus, die, wenn sie mit dem privaten Schlüssel des Ziels verarbeitet werden, die für die Kryptoanalyse benötigten Informationen liefern.
Um solche Angriffe abzuwehren, empfiehlt RSA Security Inc., den Klartext mit einem Verfahren zu modifizieren, das als optimales asymmetrisches Verschlüsselungs-Padding (OAEP) bekannt ist.
Die Idee bei OAEP ist, dass der Klartext vor der Verschlüsselung mit dem öffentlichen Schlüssel des Empfängers mit einem zufälligen Padding versehen wird, um ein Element des Zufalls in den sonst deterministischen Verschlüsselungsvorgang einzuführen.
Hashes dienen der Gewährleistung der Integrität von Daten.
Macs dienen der Authentifizierung von Daten. Da jedoch ein gemeinsamer Schlüssel vom Sender und Empfänger verwendet wird, können beide Seiten Nachrichten fälschen. Sie bieten keine Nichtabstreitbarkeit.
Digitale Signaturen bieten Integrität, Authentizität und Nichtabstreitbarkeit. Sie basieren auf asymmetrischen Verschlüsselungsalgorithmen und sind daher langsamer als Macs.
Square-and-Multiply
Führen Sie den Square-and-Multiply Algorithmus Schritt-für-Schritt für \(3^{17}\, mod\, 23\) aus.
Nachrichtenentschlüsselung
Entschlüsseln sie die folgende mit RSA verschlüsselte Nachricht
Berechnen Sie \(d\) und wandeln Sie die (Klartext)zahl in Text (ASCII 7-Bit pro Zeichen) um. (Nutzen Sie ggf. das Jupyter Notebook als Hilfestellung.)
Um einen Integer-Wert (m) in einen String umzuwandeln, können Sie den folgenden Pyhton-Code verwenden:
bstr = bin(m) # the string will start with '0b'
chars = [bstr[i:i+7] for i in range(2, len(bstr)-1, 7)] # Segmentierung in 7-Bit-Blöcke
"".join(list(map(lambda x : chr(int(x,2)), chars))) # Umwandlung in ASCII-Zeichen und KonkatenationVerschlüsselung mit RSA
Verschlüsseln Sie eine Nachricht mit RSA mit selber gewählten Parametern.
D. h., wählen Sie 2 kleine Primzahlen, berechnen Sie dann \(e\), \(d\), \(n\). Verschlüsseln Sie dann die Nachricht (d. h. einen (eher) kleinen Wert) mit dem öffentlichen Schlüssel einer anderen Person und senden Sie der Person die verschlüsselte Nachricht. Die Zielperson soll Ihre Nachricht entschlüsseln.