Asymmetrische Schlüsselkryptografie

In dieser Lektion betrachten wir die asymmetrische Schlüsselkryptografie, die heute die Grundlage vieler sicherer Netzwerkinteraktionen bildet.

Am Ende der Lektion haben wir folgende Themen behandelt:

Was asymmetrische Schlüsselkryptografie ist
Anwendungen der asymmetrischen Schlüsselkryptografie, einschließlich Schlüsselaustausch und digitaler Signaturen
Sicherheit der asymmetrischen Schlüsselkryptografie im Allgemeinen
Weitere Details zu den Algorithmen RSA, DSA und Elliptische Kurven sowie deren Sicherheit
Einige Python-Codebeispiele, die zeigen, wie die Algorithmen in der Praxis funktionieren
Bedrohungen für diese Algorithmen durch klassische und Quantencomputer

Einführung in die asymmetrische Schlüsselkryptografie

Wie wir in der letzten Lektion gelernt haben, ist die symmetrische Schlüsselkryptografie sehr schnell und effizient zum Schutz von Informationen, hat aber einige Einschränkungen:

Mit zunehmender Anzahl von Parteien, die sichere Informationen austauschen möchten, wächst die Anzahl der benötigten Schlüssel kombinatorisch. Es gibt keinen Mechanismus, um diese Schlüssel sicher zwischen Sendern und Empfängern zu verteilen.
Es gibt keine Möglichkeit zur Non-Repudiation. Jede Partei kann Nachrichten entschlüsseln oder verschlüsseln, ohne dass nachgewiesen werden kann, ob eine Nachricht empfangen wurde oder woher sie stammt.

Die Lösung für beide Probleme bietet die asymmetrische Schlüsselkryptografie (AKC), auch bekannt als Public-Key-Kryptografie (PKC), die daher einen Grundpfeiler der modernen digitalen Sicherheit bildet.

Die asymmetrische Schlüsselkryptografie (AKC) verwendet ein Schlüsselpaar – einen öffentlichen und einen privaten Schlüssel. Der öffentliche und der private Schlüssel sind kryptografisch miteinander verknüpft und werden in der Regel gleichzeitig als Schlüsselpaar mithilfe eines spezialisierten mathematischen Algorithmus erzeugt. Der öffentliche Schlüssel soll, wie der Name andeutet, frei verteilt werden, während der private Schlüssel von der erzeugenden Partei geheim gehalten wird. Die Sicherheit der Kommunikation mit asymmetrischen Schlüsselpaaren ist gewährleistet, solange der private Schlüssel vertraulich bleibt.

Abbildung 1. Asymmetrische Schlüsselverschlüsselung

Abbildung 1. Asymmetrische Schlüsselverschlüsselung

AKC bietet mehrere nützliche Funktionen, darunter:

Verschlüsselung und Entschlüsselung zur Gewährleistung der Vertraulichkeit der Kommunikation.
Digitale Signaturen zur Sicherstellung von Authentizität, Integrität und Non-Repudiation.
Sicherer Schlüsselaustausch zur Ermöglichung der anschließenden Nutzung symmetrischer Kryptosysteme.

In modernen Anwendungen wird AKC hauptsächlich für digitale Signaturen und den sicheren Schlüsselaustausch eingesetzt. In dieser Lektion stellen wir diese beiden Schlüsselfunktionen vor und erörtern anschließend verschiedene Varianten kryptografischer Protokolle für diese Funktionen.

Schlüsselaustausch mit asymmetrischer Schlüsselkryptografie

Eines der grundlegenden Probleme in der Kryptografie ist der sichere Schlüsselaustausch. Wenn zwei Parteien zum Beispiel symmetrische Verschlüsselung verwenden möchten, benötigen beide denselben Schlüssel zum Ver- und Entschlüsseln von Nachrichten. Aber wie tauschen sie den Schlüssel sicher aus? Die asymmetrische Schlüsselkryptografie löst dies durch interaktive und nicht-interaktive Schlüsselaustauschmechanismen.

Interaktiver Schlüsselaustausch

Ein interaktives Schlüsselaustauchprotokoll bezeichnet eine Methode, bei der zwei Parteien zusammenarbeiten, um über einen unsicheren Kommunikationskanal einen gemeinsamen geheimen Schlüssel zu erstellen. Dieser gemeinsame geheime Schlüssel kann dann für symmetrische Ver- und Entschlüsselungsaufgaben verwendet werden.

Das bekannteste dieser Protokolle ist der Diffie-Hellman-Algorithmus (DH), der speziell für den Schlüsselaustausch entwickelt wurde. Bei diesem Protokoll erzeugt jede Partei ein Schlüsselpaar (öffentlich und privat) und veröffentlicht ihren öffentlichen Schlüssel. Anschließend verwendet jede Partei ihren eigenen privaten Schlüssel und den öffentlichen Schlüssel der anderen Partei, um einen gemeinsamen geheimen Schlüssel zu erzeugen. DH nutzt die Prinzipien der modularen Arithmetik, um sicherzustellen, dass beide Parteien am Ende denselben gemeinsamen Schlüssel erhalten, obwohl jede Partei nur Zugang zum öffentlichen Schlüssel der anderen hat.

Moderne Kryptosysteme auf Basis der Elliptische-Kurven-Kryptografie (ECC) erweitern dieses Konzept mit dem Elliptic Curve Diffie-Hellman (ECDH) Schlüsselaustausch. ECDH funktioniert ähnlich wie DH, nutzt jedoch die Eigenschaften elliptischer Kurven, was zu einem sichereren und effizienteren System führt.

Abbildung 2. Schlüsselaustauchprotokoll

Abbildung 2. Schlüsselaustauchprotokoll

Nicht-interaktiver Schlüsselaustausch

Im Gegensatz zu Schlüsselaustauchprotokollen wie DH und ECDH, die interaktiv sind und eine Hin- und Her-Kommunikation erfordern, um den symmetrischen Schlüssel festzulegen, bietet AKC auch nicht-interaktive Wege zur Vereinbarung eines gemeinsamen geheimen Schlüssels. Bei solchen Verfahren erzeugt eine Partei ein Schlüsselpaar (öffentlich und privat) und teilt den öffentlichen Schlüssel mit der anderen Partei. Diese zweite Partei erzeugt dann einen zufälligen symmetrischen Schlüssel, verschlüsselt ihn mit dem erhaltenen öffentlichen Schlüssel und sendet ihn zurück an die erste Partei. Die erste Partei verwendet ihren privaten Schlüssel, um die empfangene Nachricht zu entschlüsseln und so den gemeinsamen symmetrischen Schlüssel zu erhalten. Dieses Verfahren ist nicht-interaktiv, da der symmetrische Schlüssel von einer Partei bestimmt und der anderen Partei lediglich sicher verschlüsselt übermittelt wird.

Ein wichtiger Aspekt beim nicht-interaktiven Schlüsselaustausch betrifft den Längenunterschied in Bits zwischen dem symmetrischen Schlüssel, den die Parteien austauschen möchten, und den empfohlenen Nachrichtengrößen in AKC. Typischerweise liegen moderne symmetrische Schlüssel im Bereich von 128–256 Bit, während asymmetrische Kryptosysteme wie RSA mit Nachrichtengrößen von etwa 1024–4096 Bit arbeiten. Daher muss der symmetrische Schlüssel bei der Übertragung per AKC aus Sicherheitsgründen in eine längere Nachricht von 1024–4096 Bit eingebettet werden. Dies kann auf zwei Arten erreicht werden:

Padding-basierter Schlüsselaustausch: Bei diesem Ansatz wird zunächst der kürzere (128–256 Bit) symmetrische Schlüssel erzeugt, und anschließend wird ein vereinbartes, umkehrbares Padding-Verfahren wie OAEP verwendet, um ihn in eine längere (1024–4096 Bit) Nachricht einzubetten. Diese längere Nachricht wird mit AKC verschlüsselt und als Ciphertext übertragen. Der Empfänger entschlüsselt zunächst den Ciphertext und entfernt dann das Padding, um den kürzeren symmetrischen Schlüssel zu extrahieren.
Schlüssel-Kapselungsmechanismen (KEMs): Beim KEM-basierten Schlüsselaustausch wird zunächst eine zufällige, lange (1024–4096 Bit) Klartextnachricht erzeugt, aus der mithilfe einer vereinbarten Schlüsselableitungsfunktion (KDF) ein kürzerer (128–256 Bit) symmetrischer Schlüssel abgeleitet werden kann. Der längere Klartext wird mit AKC verschlüsselt und als Ciphertext an den Empfänger übertragen. Der Empfänger entschlüsselt den Ciphertext mit seinem privaten Schlüssel und verwendet dann die KDF, um den kürzeren (128–256 Bit) symmetrischen Schlüssel zu extrahieren. Populäre Kryptosysteme wie RSA, die Daten direkt verschlüsseln können, lassen sich zur Implementierung von KEMs einsetzen.

Abbildung 3. Schlüsselkapselungsmechanismus

Abbildung 3. Schlüsselkapselungsmechanismus

Digitale Signaturen mit asymmetrischer Schlüsselkryptografie

Digitale Signaturen sind eine weitere leistungsstarke Anwendung der asymmetrischen Schlüsselkryptografie. Sie bieten Authentifizierung, Integrität und Non-Repudiation, ermöglicht durch die Tatsache, dass Entitäten in AKC über einzigartige private Schlüssel verfügen. Die grundlegende Idee hinter Signaturprotokollen ist, dass Absender sicherer Nachrichten diese zusätzlich mit ihrem einzigartigen privaten Schlüssel digital signieren. Der Empfänger verifiziert dann die digitale Signatur mit dem öffentlichen Schlüssel des Absenders. In AKC können digitale Signaturen durch speziell dafür entwickelte Algorithmen oder durch generische Kryptosysteme implementiert werden.

Abbildung 4. Digitale Signaturen mit asymmetrischer Schlüsselkryptografie

Abbildung 4. Digitale Signaturen mit asymmetrischer Schlüsselkryptografie

Dedizierte digitale Signaturalgorithmen

Derzeit ist der US Federal Information Processing Standard (FIPS) für digitale Signaturen ein dediziertes Verfahren namens Digital Signature Algorithm (DSA). Ähnlich wie das Diffie-Hellman-Protokoll nutzt der DSA die algebraischen Eigenschaften der modularen Exponentiation und multiplikativer Inversen zur Signaturerzeugung und -verifizierung.

Der Elliptic Curve Digital Signature Algorithm (ECDSA) ist eine ECC-Variante des DSA, die dieselbe Funktionalität bei deutlich kürzeren Schlüsseln bietet. Dies führt zu einer verbesserten Effizienz und macht ihn zu einer beliebten Wahl für Systeme mit Ressourcenbeschränkungen.

Sowohl DSA als auch ECDSA werden weiter unten ausführlicher erläutert.

Digitale Signaturverfahren mit generischen Kryptosystemen

Neben dedizierten Algorithmen können digitale Signaturen auch mit generischen asymmetrischen Kryptosystemen wie RSA erzeugt werden.

RSA, das in einem späteren Abschnitt ausführlich besprochen wird, nutzt ebenfalls modulare multiplikative Inverse und modulare Exponentiation als grundlegende Operationen, kombiniert sie jedoch in einer anderen Reihenfolge als DSA. Bei RSA erstellt der Unterzeichner typischerweise einen Hash der Nachricht und verschlüsselt diesen dann mit seinem privaten Schlüssel, wodurch die digitale Signatur entsteht. Jede Partei kann diese Signatur dann verifizieren, indem sie sie mit dem öffentlichen Schlüssel des Unterzeichners entschlüsselt und mit der gehashten Nachricht vergleicht.

Anwendungen der asymmetrischen Schlüsselkryptografie

Asymmetrische Schlüsselkryptografie ist allgegenwärtig in modernen digitalen Technologieanwendungen. Die oben beschriebenen grundlegenden Funktionalitäten von AKC bilden die Bausteine vieler übergeordneter Anwendungsprotokolle, darunter:

Internetkommunikation: Sichere Kommunikation über das Internet, wie HTTPS, stützt sich stark auf asymmetrische Schlüsselkryptografie. Transport Layer Security (TLS) und sein Vorgänger Secure Sockets Layer (SSL) nutzen asymmetrische Schlüsselkryptografie während des ersten Handshakes, um einen symmetrischen Schlüssel zu vereinbaren, der dann für den Rest der Kommunikationssitzung verwendet wird.
Authentifizierung: Asymmetrische Schlüsselkryptografie wird zur Erstellung digitaler Signaturen eingesetzt, sodass eine Entität ein digitales Dokument oder eine Nachricht als von einem bestimmten Absender stammend authentifizieren kann. Dies wird in vielen Szenarien eingesetzt, von der Verifizierung von Software-Updates bis hin zu rechtlich bindenden digitalen Verträgen.
E-Mail-Verschlüsselung: E-Mail-Verschlüsselungsprotokolle wie PGP (Pretty Good Privacy) und seine Open-Source-Alternative GPG (GNU Privacy Guard) nutzen asymmetrische Schlüsselkryptografie, um sicherzustellen, dass nur der vorgesehene Empfänger den E-Mail-Inhalt lesen kann.
Secure Shell (SSH): SSH ist ein Protokoll für sichere Remote-Anmeldung und andere sichere Netzwerkdienste über ein unsicheres Netzwerk. Es verwendet asymmetrische Schlüsselkryptografie, um den Server gegenüber dem Client zu authentifizieren und optional auch den Client gegenüber dem Server.
VPN (Virtuelles Privates Netzwerk): Asymmetrische Schlüsselverschlüsselung wird verwendet, um sichere Verbindungen in VPNs herzustellen und so eine sichere Kommunikation über öffentliche Netzwerke zu gewährleisten.
Blockchain und Kryptowährungen: Blockchain-Technologien, einschließlich Bitcoin und Ethereum, nutzen asymmetrische Schlüsselkryptografie. So wird beispielsweise der Besitz von Bitcoin durch digitale Signaturen mittels asymmetrischer Schlüsselkryptografie nachgewiesen.
Zertifizierungsstellen: Asymmetrische Schlüsselkryptografie wird von Zertifizierungsstellen (CAs) verwendet, um digitale Zertifikate auszustellen und zu signieren, die bei TLS-Kommunikation, Code-Signierung, E-Mail-Verschlüsselung und mehr eingesetzt werden. Ein digitales Zertifikat verknüpft einen öffentlichen Schlüssel mit einer bestimmten Entität (zum Beispiel einer Person oder einem Server).

Abbildung 5. Ausstellung und Signierung digitaler Zertifikate mit asymmetrischer Schlüsselkryptografie

Abbildung 5. Ausstellung und Signierung digitaler Zertifikate mit asymmetrischer Schlüsselkryptografie

Sicherheit der asymmetrischen Schlüsselkryptografie

Mehrere kryptografische Konzepte wirken zusammen, um eine sichere asymmetrische Schlüsselkryptografie zu ermöglichen, darunter:

Geheimhaltung des privaten Schlüssels: Die grundlegendste Sicherheitsanforderung von AKC ist, dass der private Schlüssel geheim bleibt. Da der private Schlüssel jedoch mathematisch mit dem öffentlichen Schlüssel verknüpft sein muss, erfordert die Geheimhaltung des privaten Schlüssels auch, dass es rechnerisch nicht durchführbar ist, den privaten Schlüssel aus dem Wissen über den öffentlichen Schlüssel abzuleiten. Schlüsselerzeugungsverfahren in AKC stützen sich auf rechnerisch schwere mathematische Probleme, um diese Anforderung zu erfüllen.

Trapdoor-Funktionalität: In AKC verwenden die Verschlüsselungs- und Entschlüsselungsoperationen unterschiedliche, komplementäre Schlüssel aus einem einzigen Schlüsselpaar. Ein durch Verschlüsselung mit einem der Schlüssel (z. B. dem öffentlichen Schlüssel) erzeugter Ciphertext muss für Dritte unlesbar sein, während er vom Inhaber des komplementären Schlüssels (in diesem Fall dem privaten Schlüssel) leicht entschlüsselt werden kann. Mit anderen Worten: Die Verschlüsselung sollte einer Trapdoor-Einwegfunktion ähneln, sodass Dritte die Operation nicht umkehren und den Klartext wiederherstellen können, der private Schlüssel jedoch eine geheime Trapdoor bereitstellt, die eine einfache Umkehrung ermöglicht. Populäre AKC-Algorithmen verwenden modulare Exponentiation, um das Verhalten von Trapdoor-Einwegfunktionen zu implementieren.

Zufälligkeit: Der Schlüsselerzeugungsprozess sollte ebenfalls Zufälligkeit nutzen, um sicherzustellen, dass Schlüssel unvorhersehbar sind, da jedes Muster oder jede Vorhersagbarkeit bei der Schlüsselerzeugung von einem Angreifer ausgenutzt werden könnte. Zufälligkeit wird auch beim Padding während der Verschlüsselung verwendet, um semantisch sichere Ciphertexte zu erzeugen, sowie innerhalb digitaler Signaturverfahren, um eindeutige Signaturen zu erzeugen, selbst wenn dieselbe Nachricht mehrfach signiert wird. Aus diesem Grund ist die Verwendung starker Zufallszahlengeneratoren ein wichtiger Bestandteil von AKC.

Große Schlüsselgröße: Wie bei SKC gewährleisten große Schlüsselgrößen den Schutz gegen Brute-Force-Angriffe. Da große Schlüsselgrößen jedoch auch die Rechenkosten des Ver- und Entschlüsselungsprozesses erhöhen, muss eine optimale Lösung Sicherheits- und Effizienzaspekte abwägen. Die folgende Tabelle zeigt typische Schlüsselgrößen für verschiedene asymmetrische Schlüsselkryptografieprotokolle und Anwendungen:

Protokoll	Typische Schlüsselgrößen (in Bit)	Anwendung
RSA	1024 (veraltet), 2048, 3072, 4096	Verschlüsselung, digitale Signaturen
DSA	1024 (veraltet), 2048, 3072	Digitale Signaturen
DH	2048, 3072, 4096	Schlüsselaustausch
ECDH	224, 256, 384, 521	Schlüsselaustausch
ECDSA	224, 256, 384, 521	Digitale Signaturen

Public-Key-Infrastruktur: In AKC müssen die privaten Schlüssel von den Eigentümern geheim gehalten werden, während die öffentlichen Schlüssel geteilt werden. Es bedarf eines sicheren Mechanismus zur Verwaltung und Verteilung dieser öffentlichen Schlüssel zwischen den Nutzern. Die Public-Key-Infrastruktur (PKI) bietet hierfür einen Weg mithilfe von digitalen Zertifikaten. Ein digitales Zertifikat liefert den Identitätsnachweis des Inhabers des öffentlichen Schlüssels und wird von einer vertrauenswürdigen Instanz wie einer Zertifizierungsstelle (die Teil einer PKI ist) ausgestellt. PKI spielt daher eine wesentliche Rolle für die Sicherheit moderner Anwendungen, die AKC nutzen, indem sie eine großangelegte Schlüsselverwaltung ermöglicht (durch Erstellung, Verwaltung, Verteilung und Widerruf digitaler Zertifikate).

Sicherheitsrisiken für die asymmetrische Schlüsselkryptografie

Wie aus der obigen Tabelle hervorgeht, verwenden moderne asymmetrische Schlüsselalgorithmen wie RSA typischerweise deutlich größere Schlüsselgrößen als gängige symmetrische Gegenstücke wie AES-128. Selbst die ECC-basierten Protokolle (ECDH und ECDSA), die kleinere Schlüsselgrößen haben, verwenden mindestens 224 Bit für Schlüssel. Dies impliziert, dass ein Brute-Force-Angriff, der den privaten Schlüsselraum erschöpfend durchsucht, um den richtigen Schlüssel zu finden, in absehbarer Zukunft rechnerisch nicht durchführbar ist. Dies gilt selbst dann, wenn Quantencomputer für diese Aufgabe eingesetzt würden. Daher konzentrieren sich Angriffe auf AKC in der Regel auf die Ausnutzung anderer potenzieller Schwachstellen spezifischer Kryptosysteme. Einige gut dokumentierte Angriffsmodi zielen auf:

Algorithmische Schwächen durch den Einsatz ausgefeilter mathematischer und rechnerischer Mittel, um die Härteannahmen, auf denen asymmetrische Schlüsselalgorithmen basieren, zu untergraben. So beruht beispielsweise die Sicherheit von RSA auf der Schwierigkeit der Faktorisierung großer Primzahlen, und jüngste rechnerische Fortschritte haben die erfolgreiche Faktorisierung von 829-Bit-RSA-Schlüsseln ermöglicht. Daher gilt 1024-Bit-RSA derzeit als veraltet. Wie später erläutert wird, fällt das primäre Risiko, das Quantencomputer für AKC darstellen, ebenfalls in diese Kategorie.
Unvollkommene Zufälligkeit, die zu Schwachstellen im Schlüsselerzeugungsprozess führen kann. Wenn zum Beispiel der Zufallszahlengenerator zur Schlüsselerzeugung fehlerhaft ist und keine wirklich zufälligen Schlüssel erzeugt, könnte ein Angreifer in der Lage sein, die Schlüssel vorherzusagen.
Implementierungsfehler wie Fehler in der Implementierung kryptografischer Algorithmen, die versehentlich Informationen über die Schlüssel preisgeben. So kann zum Beispiel falsches Padding Details über Schlüssel offenbaren.
Seitenkanäle, die sich auf Informationslecks aus dem physischen System beziehen, das die Kryptografie durchführt. Solche Lecks können in Form von Timing-Informationen, Stromverbrauch oder sogar Geräuschen auftreten, die in einem sogenannten Seitenkanalangriff ausgenutzt werden können. So könnte beispielsweise die Analyse der Ausführungsdauer kryptografischer Operationen die Anzahl der '1'-Bits in einem binären Schlüssel verraten. Dieses scheinbar harmlose Leck schränkt den Suchraum erheblich ein und enthüllt potenzielle Lösungen für Probleme, die zunächst unüberwindbar erschienen.
Schlüsselaustausch durch das Abfangen von Schlüsseln während des Austauschs, beispielsweise bei einem Man-in-the-Middle-Angriff (MITM). Das DH-Protokoll ist anfällig für MITM-Angriffe, wenn keine zusätzlichen Authentifizierungsschritte eingebaut werden.
Schlüsselspeicherung durch den Versuch, Schlüssel aus schlecht gesichertem Speicher zu stehlen. Dies umfasst physische Angriffe wie die Manipulation oder den Diebstahl von Speichermedien.

Die Absicherung asymmetrischer Schlüsselkryptosysteme gegen die Vielzahl möglicher Angriffe ist daher eine bedeutende Aufgabe, die mathematische, hardware-, software-, logistische und rechtliche Überlegungen umfasst.

RSA

Der RSA-Algorithmus (Rivest-Shamir-Adleman) ist eines der ersten Public-Key-Kryptosysteme und wird häufig für die sichere Datenübertragung eingesetzt. Es handelt sich um ein vielseitiges Kryptosystem, das die nötigen Operationen für Verschlüsselung, Entschlüsselung, digitale Signaturen und Schlüsselaustausch in einem gemeinsamen Rahmen bereitstellt.

In diesem Abschnitt veranschaulichen wir die asymmetrische Schlüsselkryptografie (AKC) anhand von RSA durch einfache Beispiele.

Wir verwenden das übliche Szenario zweier Parteien, Alice und Bob, die über AKC sicher kommunizieren möchten.

Der RSA-Algorithmus

Der grundlegende RSA-Algorithmus umfasst vier Operationen: Schlüsselerzeugung, Schlüsselverteilung, Verschlüsselung und Entschlüsselung:

Schlüsselerzeugung:

Öffentliche und private Schlüssel werden auf Basis mathematischer Prinzipien rund um Primzahlen erzeugt: Das Berechnen ist einfach, die Umkehrung jedoch schwer.

Wir bezeichnen sie wie folgt:
- Öffentlicher Schlüssel: $(e, n)$
- Privater Schlüssel: $(d, n)$
Beachte, dass $n$ beiden Schlüsseln gemeinsam ist und als Modulus bezeichnet wird. Wir werden ihn später benötigen.

Mathematische Details

Wähle zwei verschiedene Primzahlen $p$ $p$ und $q$ $q$ .
- Zufällig gewählt (aus Sicherheitsgründen).
- Sie sollten ähnlich groß sein, sich aber in ihrer Stellenanzahl leicht unterscheiden, um die Faktorisierung zu erschweren.
- Primzahlen lassen sich effizient mithilfe eines Primzahltests finden.
Berechne $n = p*q$ $n = p * q$ .
- $n$ ist der Modulus für den öffentlichen und den privaten Schlüssel.
Berechne die Totientfunktion $φ$ $(n) = (p-1)*(q-1)$ $(n) = (p - 1) * (q - 1)$ .
- Der Totient soll geheim bleiben und wird nach der Schlüsselerzeugung typischerweise verworfen.
Wähle eine ganze Zahl $e$ $e$ mit $1 < e <$ $1 < e <$ $φ$ $(n)$ $(n)$ und $gcd$ $(e,$ $(e,$ $φ$ $(n)) = 1$ $(n)) = 1$ .
- Das heißt, $e$ und $φ$ $(n)$ müssen teilerfremd sein.
- Diese Zahl $e$ bildet den Exponenten des öffentlichen Schlüssels und wird zur Effizienz typischerweise klein gewählt.
- Die Primzahl $65537 = 2^{16} + 1$ wird häufig verwendet.
- Berechne $d$ $d$ so, dass die Kongruenzrelation $d*e ≡ 1 ($ $d * e \equiv 1 ($ $mod$ $φ$ $(n))$ $(n))$ gilt.
  - Das heißt, $d$ ist das multiplikative Inverse von $e$ modulo $φ$ $(n)$ .
  - Dies lässt sich effizienter mit dem erweiterten euklidischen Algorithmus berechnen.
  - Diese Zahl $d$ ist der Exponent des privaten Schlüssels.
Der öffentliche Schlüssel besteht aus $(e, n)$ , der private Schlüssel ist $(d, n)$ .

Schlüsselverteilung:
- Der öffentliche Schlüssel $(e, n)$ wird für alle veröffentlicht, die eine Nachricht senden möchten.
- Der private Schlüssel $(d, n)$ wird geheim gehalten.
Verschlüsselung:
- Alice möchte eine Nachricht $M$ an Bob senden – in diesem Fall eine einfache ganze Zahl.
- Alice verwendet Bobs öffentlichen Schlüssel $(e, n)$ , um die Nachricht in den Geheimtext $C$ zu verschlüsseln.
Mathematische Details
- $M$ ist eine ganze Zahl mit $0 ≤ M < n$ .
- $C ≡ M^e (mod n)$ , wobei $C$ der Geheimtext ist.
Entschlüsselung:
- Bob empfängt den Geheimtext $C$ .
- Bob verwendet seinen privaten Schlüssel $(d, n)$ , um die Nachricht zurück in $M$ zu entschlüsseln.
Mathematische Details
- $M ≡ C^d (mod n)$ .

Dies ist die grundlegende Übersicht von RSA. In der Praxis werden auf den Klartext $M$ vor der Verschlüsselung ausgefeiltere Padding-Verfahren angewendet, um sicherzustellen, dass gleiche Klartexte zu unterschiedlichen Geheimtexten führen. Dies verhindert eine Reihe möglicher Angriffe auf naive RSA-Implementierungen und ermöglicht semantische Sicherheit.

RSA in Python veranschaulicht

In den folgenden Code-Zellen veranschaulichen wir ein einfaches Beispiel des RSA-Algorithmus mit kleinen ganzen Zahlen und demonstrieren anschließend praktische Anwendungen zur Schlüsselverteilung und digitalen Signatur mithilfe von Python-Bibliotheken, die RSA implementieren.

hinweis

Hinweis: In diesem Abschnitt zeigen wir die mathematischen Berechnungen als Teil des Python-Codes im Detail.

RSA-Schlüsselerzeugung

Gehen wir Schritt für Schritt durch eine einfache Instanz des RSA-Algorithmus mit kleinen Primzahlen.

Wir müssen den größten gemeinsamen Teiler zweier ganzer Zahlen berechnen können, da er benötigt wird, um zu testen, ob zwei ganze Zahlen teilerfremd sind.

Wir erklären eine einfache Berechnungsmethode, aber bei größeren ganzen Zahlen ist die Python-Funktion math.gcd deutlich effizienter.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

Die erste Phase des RSA-Workflows ist die Schlüsselerzeugung. Sie beginnt mit der Wahl zweier Primzahlen, die von der schlüsselerzeugenden Partei geheim gehalten werden müssen.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Als Nächstes wird der Modulus $n$ berechnet, der einfach das Produkt der beiden gewählten Primzahlen ist. Dieser Modulus wird als Teil des öffentlichen Schlüssels veröffentlicht.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

Als Nächstes wird die Eulersche Totientfunktion $\varphi(n)$ berechnet, da sie für die modulare multiplikative Inverse benötigt wird, mit der die Schlüssel in RSA bestimmt werden. $phi$ wird ebenfalls geheim gehalten und nach der Schlüsselerzeugung typischerweise verworfen.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Wir sind nun bereit, den öffentlichen und den privaten Schlüssel zu berechnen. In RSA wird jeder durch ein Tupel aus zwei ganzen Zahlen angegeben. Der erste Eintrag jedes Tupels ist eine eigene ganze Zahl, der zweite Eintrag ist der Modulus $n$ , der beiden Schlüsseln gemeinsam ist.

Der erste Eintrag des öffentlichen Schlüssels kann eine beliebige ganze Zahl größer als 1 sein, die zu $phi$ teilerfremd ist. Zwei ganze Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist. Daher verwenden wir die Funktion math.gcd, um eine zu $phi$ teilerfremde ganze Zahl $e$ zu finden.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

Der private Schlüssel erfordert eine ganze Zahl $d$ , die das multiplikative Inverse von $e$ modulo $phi$ ist – also die Kongruenzrelation $d*e\equiv 1 \pmod{\varphi(n)}$ erfüllt. Bei dieser einfachen Illustration mit kleinen ganzen Zahlen können wir die positiven ganzen Zahlen einfach durchlaufen, um ein geeignetes $d$ zu finden. In der Praxis wird für diesen Zweck der rechnerisch effiziente erweiterte euklidische Algorithmus verwendet.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Wir bilden nun die Tupel $(e, n), (d, n)$ , die den öffentlichen bzw. privaten Schlüssel darstellen. Der öffentliche Schlüssel wird dann veröffentlicht, der private Schlüssel geheim gehalten.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

Verschlüsselung und Entschlüsselung in RSA nutzen die modulare Exponentialoperation. Dabei sind der öffentliche und der private Schlüssel komplementär: Jeder kann verwendet werden, um eine Nachricht zu verschlüsseln, die der andere dann entschlüsseln kann.

Hier veranschaulichen wir den Fall, bei dem der öffentliche Schlüssel $(e,n)$ zur Verschlüsselung und der private Schlüssel $(d, n)$ zur Entschlüsselung verwendet wird, indem wir für jede Operation eine Python-Funktion definieren.

Anschließend verschlüsseln und entschlüsseln wir eine ganzzahlige Nachricht $msg$ .

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Während die obigen kleinen ganzen Zahlen nützlich sind, um die Kernideen des RSA-Algorithmus leicht zu veranschaulichen, erfordert RSA in realen Anwendungen den Einsatz sehr großer ganzer Zahlen. Beispielsweise verwendet 2048-Bit-RSA einen Modulus $n$ mit einer Länge von 2048 Bit; die dezimalen Äquivalente liegen bei etwa 10 $^{616}$ . Diese enormen Zahlen sind für die praktische Sicherheit von RSA unerlässlich.

Symmetrischer Schlüsselaustausch mit RSA

Wie bereits erläutert, ermöglicht AKC zwei Parteien, die kommunizieren möchten, sicher ein gemeinsames Geheimnis zu etablieren, das zum Beispiel als geheimer Schlüssel für die anschließende symmetrische Verschlüsselung großer Klartextmengen dienen kann.

Betrachten wir folgendes Szenario: Alice und Bob möchten SKC verwenden, um Nachrichten zu verschlüsseln und zu entschlüsseln. Bevor dieser Prozess jedoch initialisiert werden kann, müssen sie sich auf einen gemeinsamen geheimen Schlüssel einigen. Eine Möglichkeit besteht darin, dass eine Partei – zum Beispiel Alice – einen geheimen Schlüssel erzeugt und ihn dann sicher an Bob überträgt. Um diese sichere Übertragung zu erreichen, entscheidet sich Alice, RSA als Schlüsselkapselungsmechanismus (KEM) zu verwenden.

Dabei sind folgende Schritte erforderlich:

Zunächst erzeugt Alice einen zufälligen symmetrischen Schlüssel, den sie mit Bob teilen möchte.
Dann erzeugt Bob ein asymmetrisches Schlüsselpaar und macht seinen öffentlichen Schlüssel über einen geeigneten Kanal verfügbar.
Als Nächstes verwendet Alice Bobs öffentlichen Schlüssel, um den symmetrischen Schlüssel zu verschlüsseln und so in einem Geheimtext zu kapseln.
Dann überträgt Alice den Geheimtext über einen zuverlässigen, aber nicht notwendigerweise sicheren Kanal.
Schließlich empfängt Bob den Geheimtext und entschlüsselt ihn mit seinem privaten Schlüssel. Er hat nun Zugriff auf den von Alice erzeugten symmetrischen Schlüssel.

Abbildung 1. Symmetrischer Schlüsselaustausch mit RSA

Abbildung 1. Symmetrischer Schlüsselaustausch mit RSA

Padding-basiertes Schlüsselaustausch-Beispiel in Python

Ein praktischer Workflow, der RSA für den padding-basierten nicht-interaktiven Schlüsselaustausch nutzt, wird nun mithilfe der Python-Bibliothek cryptography veranschaulicht.

Importiere die notwendigen Module aus der Python-Bibliothek cryptography. Bei Bedarf kann diese Bibliothek mit dem Befehl pip install cryptography installiert werden.

Alice erzeugt dann einen zufälligen geheimen Schlüssel, den sie an Bob übertragen möchte.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Mit dem Modul rsa aus der Bibliothek cryptography erzeugt Bob ein Schlüsselpaar und veröffentlicht dann seinen öffentlichen Schlüssel. Jeder kann den öffentlichen Schlüssel abfangen und die öffentlichen Zahlen $(e,n)$ auslesen, die den Schlüssel bilden.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

Zu diesem Zeitpunkt nehmen wir an, dass Alice den von Bob veröffentlichten öffentlichen Schlüssel erhalten hat. Alices symmetric_key von oben kann nun mit Bobs öffentlichem Schlüssel verschlüsselt werden, um den Geheimtext zu erzeugen. In einem realistischen Szenario wird Alice zusätzliche Padding-Methoden wie OAEP verwenden, um semantische Sicherheit ihrer Kommunikation mit Bob zu gewährleisten.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice überträgt dann den Geheimtext über einen offenen Kanal, im Vertrauen darauf, dass nur Bob mit dem entsprechenden privaten Schlüssel ihn entschlüsseln kann. Wir nehmen an, dass Bob den Geheimtext erhalten hat und ihn nun mit seinem vertraulichen privaten Schlüssel entschlüsseln kann.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

Zu diesem Zeitpunkt haben Alice und Bob beide Zugriff auf den geheimen symmetrischen Schlüssel, den sie für SKC-Anwendungen nutzen können.

Simulation eines Schlüsselkapselungsmechanismus mit RSA in Python

Im folgenden Workflow veranschaulichen wir den Einsatz von RSA zur Simulation eines Schlüsselkapselungsmechanismus (KEM), bei dem ein ausreichend langes zufälliges Geheimnis sicher ausgetauscht und anschließend mithilfe einer KDF in ein gemeinsames Geheimnis der passenden Länge umgewandelt wird.

Auch hier möchten Alice und Bob ein gemeinsames Geheimnis nicht-interaktiv etablieren, und Alice ist die Partei, die entscheidet, welches Geheimnis verwendet wird.

Wir beginnen mit dem Import einiger benötigter Python-Bibliotheken.

Bob erzeugt dann sein RSA-Schlüsselpaar und veröffentlicht seinen öffentlichen Schlüssel.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice erzeugt zunächst ein langes zufälliges Geheimnis, aus dem das gemeinsame Geheimnis schließlich abgeleitet wird. In einem reinen KEM wäre das lange Geheimnis ein zufälliges Element aus der algebraischen Struktur, die dem Kryptosystem zugrunde liegt. Im Fall von 2048-Bit-RSA wäre das eine zufällige ganze Zahl modulo dem 2048-Bit-RSA-Modulus. Ein solches reines KEM benötigt kein zusätzliches Padding, aber in diesem Beispiel simulieren wir nur ein KEM mit RSA, und die Bibliothek cryptography erfordert die Verwendung von Padding bei der Verschlüsselung mit RSA. Deshalb verwenden wir ein etwas kürzeres langes Geheimnis, das dennoch deutlich länger als ein standardmäßiger 256-Bit-AES-Schlüssel ist.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Als Nächstes verschlüsselt Alice das lange Geheimnis mit Bobs öffentlichem Schlüssel und das verschlüsselte Geheimnis wird an Bob übermittelt.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob entschlüsselt das von Alice empfangene verschlüsselte Geheimnis mit seinem privaten Schlüssel.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Schließlich wenden sowohl Alice als auch Bob getrennt voneinander eine vereinbarte Schlüsselableitungsfunktion (KDF) auf das lange Geheimnis an, um den symmetrischen Schlüssel abzuleiten.

Beachte, dass der Prozess ein Hashing-Protokoll und die Verwendung eines zufälligen Salt umfasst, was die Einzigartigkeit und Unvorhersehbarkeit des gemeinsamen symmetrischen Schlüssels sicherstellt, falls das lange Geheimnis jemals wiederverwendet wird (nicht empfohlen). Der Salt selbst muss jedoch nicht geheim sein, und sobald er zufällig erzeugt wurde – zum Beispiel von Alice in diesem Beispiel –, kann er zusammen mit dem verschlüsselten langen Geheimnis an Bob übertragen werden.

Wir nehmen daher an, dass beide, Alice und Bob, Zugriff auf denselben zufälligen Salt haben.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Digitale Signaturen mit RSA

Wir werden nun das oben beschriebene Szenario der vertraulichen Kommunikation zwischen Alice und Bob um die Validierung mithilfe einer digitalen Signatur erweitern.

Wie zuvor wird Alice eine Nachricht, die einen symmetrischen Schlüssel kapselt, vertraulich an Bob senden, aber sie wird die Nachricht auch digital signieren, damit Bob nach dem Empfang verifizieren kann, dass sie von Alice stammt und dass der Inhalt der Nachricht während der Übertragung nicht manipuliert wurde.

Allgemeiner gesagt ist es wünschenswert, Validierung zu ermöglichen, ohne die Vertraulichkeit zu gefährden, sodass jede interessierte Partei die Integrität, die Authentizität verifizieren und die Nichtabstreitbarkeit in Bezug auf eine bestimmte Kommunikation feststellen kann, selbst wenn diese Partei keinen Zugriff auf den eigentlichen Klartext hat.

Wir betrachten dieses allgemeine Szenario, das folgende Schritte umfasst:

Zunächst machen sowohl Bob als auch Alice ihre öffentlichen Schlüssel über einen offenen Kanal verfügbar.
Dann verschlüsselt Alice den Klartext mit Bobs öffentlichem Schlüssel und erzeugt einen Geheimtext.
Als Nächstes erstellt Alice einen Hash des Geheimtexts mit einer Hashfunktion und verschlüsselt den resultierenden gehashten Geheimtext mit ihrem privaten Schlüssel. Dieser verschlüsselte Hash ist die Signatur.
Dann überträgt Alice sowohl den Geheimtext als auch die Signatur über einen offenen Kanal.
Dann verwendet Bob Alices öffentlichen Schlüssel, um die Signatur zu entschlüsseln und so den gehashten Geheimtext zu enthüllen.
Da Bob auch Zugriff auf den Geheimtext selbst hat, verwendet er dieselbe Hashfunktion wie Alice, um eine zweite Instanz des gehashten Geheimtexts zu erstellen. Wenn diese mit der durch Entschlüsseln von Alices Signatur erhaltenen übereinstimmt, ist die Nachricht validiert – auch wenn der Geheimtext selbst noch nicht entschlüsselt wurde.
Schließlich entschlüsselt Bob, nachdem er die Nachricht validiert hat, den Geheimtext mit seinem eigenen privaten Schlüssel.

Abbildung 2. Digitale Signaturen mit RSA

Abbildung 2. Digitale Signaturen mit RSA

Dieser Workflow für eine digitale Signatur wird als Nächstes veranschaulicht.

Wir importieren erneut einige nützliche Module aus der Bibliothek cryptography. Wie zuvor beabsichtigt Alice, einen symmetrischen Schlüssel vertraulich an Bob zu senden, möchte ihn aber auch digital signieren. In diesem Fall benötigen wir öffentliche Schlüssel für sowohl Alice als auch Bob. Daher ist der erste Schritt, dass sowohl Alice als auch Bob mit RSA ihr eigenes Schlüsselpaar erstellen und ihren öffentlichen Schlüssel veröffentlichen.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

Im nächsten Schritt verwendet Alice, wie zuvor, Bobs öffentlichen Schlüssel, um den symmetrischen Schlüssel zu verschlüsseln, und bereitet den Geheimtext vor.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

In dieser Phase beabsichtigt Alice, anstatt nur den Geheimtext zu übertragen, eine digitale Signatur anzuhängen, damit sie Bob beweisen kann, dass sie die Absenderin der Nachricht war. Dies geschieht in zwei Schritten:

Erstelle einen Hash des Geheimtexts mit einem Hash-Algorithmus.
Verschlüssele den Hash mit Alices privatem Schlüssel – das ergibt die Signatur.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice überträgt dann den Geheimtext und die Signatur über ein Netzwerk, sodass Bob beide empfangen kann.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Auf Bobs Seite besteht die erste Aufgabe darin, die Integrität und Authentizität des Geheimtexts zu verifizieren. Dazu erstellt Bob einen Hash des empfangenen Geheimtexts mit demselben Hash-Algorithmus, den Alice verwendet hat.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Dann entschlüsselt Bob die empfangene Signatur mit Alices öffentlichem Schlüssel. Da Alice ihren privaten Schlüssel verwendet hat, um die Signatur zu erstellen, kann Bob sie mit Alices öffentlichem Schlüssel entschlüsseln. Die entschlüsselte Signatur ist nichts anderes als ein Hash des Geheimtexts, der auf Alices Seite erstellt wurde. Wenn der von Bob erstellte Hash mit der entschlüsselten Signatur übereinstimmt, hat Bob verifiziert, dass der empfangene Geheimtext nicht manipuliert wurde und dass Alice den Geheimtext signiert hat.

Im folgenden Python-Code werden diese Operationen in eine nützliche Hilfsfunktion namens verify kombiniert, die von einem Objekt bereitgestellt wird, das mit Alices öffentlichem Schlüssel verknüpft ist.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Nachdem er die Integrität und Authentizität des empfangenen Geheimtexts verifiziert hat, kann Bob ihn mit seinem privaten Schlüssel entschlüsseln, da Alice den Geheimtext mit Bobs öffentlichem Schlüssel erstellt hat.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

Im obigen Szenario mit digitaler Signatur kann jede Partei – nicht nur Bob – verifizieren, dass Alice die Absenderin des Geheimtexts ist, da jeder Zugriff auf Alices öffentlichen Schlüssel, den Geheimtext und die digitale Signatur hat. Darüber hinaus kann Alice nach dem Senden des Geheimtexts und der Signatur nicht abstreiten, dies getan zu haben, da die Signatur nur mit ihrem öffentlichen Schlüssel zu einem sinnvollen Hash entschlüsselt werden kann. Dies stellt Nichtabstreitbarkeit sicher.

Durch die Ermöglichung einer sicheren Schlüsselverteilung und die Unterstützung von Nichtabstreitbarkeit legt die Public-Key-Kryptografie eine starke Grundlage für sichere digitale Kommunikation.

RSA brechen

Die Nützlichkeit und Sicherheit des oben beschriebenen RSA-Algorithmus beruht auf zwei mathematischen Annahmen:

Das Auffinden des modularen multiplikativen Inversen $d$ , wenn nur Zugang zu $(e, n)$ besteht, ist rechnerisch nicht machbar.
Im RSA-Kontext verhält sich die modulare Exponentiation wie eine Einwegfunktion mit Falltür. Bei der Verschlüsselung erzeugt sie Geheimtext, der nicht zu entziffern ist, und ohne Zugang zum privaten Schlüssel ist es nicht möglich, die Operation umzukehren und den Klartext aus dem Geheimtext wiederzugewinnen. Mit Zugang zum privaten Schlüssel jedoch, der als Falltür fungiert, lässt sich der Geheimtext problemlos entschlüsseln.

Der bekannteste Angriff auf den RSA-Algorithmus zielt darauf ab, Annahme 1 zu untergraben, indem der private Schlüssel $d$ durch Faktorisierung des Modulus $n$ effizient wiederhergestellt wird. Wie unten gezeigt wird, lässt sich $d$ leicht zurückgewinnen, wenn man Zugang zu den Primfaktoren $p$ und $q$ von $n$ oder dem Totient $φ$ $(n)$ hat. Zur Erinnerung: $p$ , $q$ und $φ$ $(n)$ werden während der Schlüsselgenerierung geheim gehalten und danach verworfen. Eine dritte Partei, die diese Informationen mithilfe eines klassischen oder Quantencomputers wiederherstellt, legt im Wesentlichen den privaten Schlüssel frei und bricht RSA. Daher ist die Primfaktorzerlegung die entscheidende rechnerische Grundoperation, die zum Brechen von RSA erforderlich ist.

Klassische Computer und RSA

Die Primfaktorzerlegung großer ganzer Zahlen ist auf klassischen Computern bekanntermaßen superpolynomiell oder subexponentiell skalierend. Der bekannteste klassische Algorithmus zur Faktorisierung von ganzen Zahlen größer als $10^{100}$ ist das Allgemeine Zahlkörpersieb (GNFS)

Mathematische Details

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

als Funktion der zu faktorisierenden ganzen Zahl $n$ .

Diese Skalierung ist superpolynomiell in der Anzahl der Bits, die zur Darstellung von $n$ benötigt werden.

Daher gilt die Primfaktorzerlegung auf klassischen Computern als ineffizient.

Derzeit liegen die größten auf klassischer Hardware faktorisierten ganzen Zahlen im Bereich von 829 Bits oder 250 Dezimalstellen. Angesichts des exponentiellen Wachstums der klassischen Rechenleistung der letzten Jahrzehnte gilt 1024-Bit-RSA kurzfristig nicht mehr als sicher und ist inzwischen veraltet. Dennoch gilt die Faktorisierung von 2048-Bit-Zahlen in der Größenordnung von $10^{617}$ auf klassischen Systemen in absehbarer Zukunft als nicht durchführbar, was auf eine anhaltende Tauglichkeit hindeutet. Das Aufkommen von Quantencomputern macht diese Einschätzung jedoch hinfällig.

Shors Quantenalgorithmus und RSA

Der wohl bekannteste Quantenalgorithmus heute ist Shors Algorithmus zur Bestimmung der Primfaktoren ganzer Zahlen. Als Peter Shor ihn 1994 vorstellte, wurde er als der erste Quantenalgorithmus anerkannt, der eine superpolynomielle Beschleunigung gegenüber klassischen Algorithmen bei einem Problem von großer praktischer Bedeutung bot, nämlich der Primfaktorzerlegung.

Shors Algorithmus kann Primzahlen mit $O(n^2)$ faktorisieren, wobei $n$ die Anzahl der Bits ist.

Mathematische Erklärung von Shors Algorithmus

Im Kontext von RSA macht sich Shors Algorithmus die Periodizität der modularen Exponentialfunktion $f(x) = a^x (mod~n)$ zunutze und stellt ein quantenmechanisches Perioden-Suchverfahren bereit, das eine effiziente Primfaktorzerlegung des Modulus $n$ ermöglicht.

Eine vereinfachte Übersicht über Shors Gesamtverfahren zum Brechen von RSA lautet wie folgt:

Gegeben sei der Modulus $n$ , der als Teil des öffentlichen Schlüssels veröffentlicht wird. Wähle eine Zahl $a$ teilerfremd zu $n$ , d. h. $gcd(a,n) = 1$ . Da wir wissen, dass $n = p*q$ genau zwei Primfaktoren $(p, q)$ hat, ist fast jede zufällig gewählte Zahl kleiner als $n$ mit hoher Wahrscheinlichkeit teilerfremd zu $n$ .
Nachdem $a$ gewählt wurde, finde den Exponenten $r$ , sodass $a^r \equiv 1 (mod~n)$ . Dies bedeutet $a^r - 1 \equiv 0 (mod~n)$ . Die Existenz eines Exponenten $r$ , für den die obige Kongruenz gilt, ist durch die Periodizitätseigenschaft der modularen Exponentiation garantiert.
Wenn $r$ gerade ist, gilt $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ für eine ganze Zahl $\gamma$ . Die linke Seite dieser letzteren Gleichung muss $p$ und $q$ als zwei ihrer Primfaktoren enthalten, da die rechte Seite dies tut. Wenn $r$ ungerade ist, gehe zurück zu Schritt 1 und wähle ein anderes $a$ .
Verwende den erweiterten Euklidschen Algorithmus zur Berechnung von $gcd((a^{r/2} - 1), n)$ oder $gcd((a^{r/2} + 1), n)$ . Der berechnete GGT wird mit hoher Wahrscheinlichkeit einen der Primfaktoren $p$ oder $q$ identifizieren. Dividiere $n$ durch diesen Primfaktor, um den anderen zu erhalten.
Sobald $p, q$ bekannt sind, verwende die Schritte aus dem ursprünglichen RSA-Algorithmus, um den Totient $\phi(n)$ zu rekonstruieren und die private Schlüsselzahl $d$ als das modulare Inverse der bekannten öffentlichen Schlüsselzahl $e$ zu erzeugen.

Im August 2023 veröffentlichte Oded Regev eine Verbesserung von Shors Originalversion unter Verwendung eines mehrdimensionalen Ansatzes, der zu $O(n^{1.5})$ führt. Es gibt weiterhin Forschungsarbeiten in diesem Bereich, unter anderem von Ragavan und Vaikuntanathan, die Zeit, Kosten oder die Anzahl der benötigten Qubits verbessern könnten. Wir können zwar nicht sagen, wann der Einsatz solcher Algorithmen gegen reale RSA-Verschlüsselung tatsächlich praktikabel wird, aber es rückt immer näher.

Python-Beispiel zur Demonstration des Brechens von RSA-Verschlüsselung

In den folgenden Code-Zellen veranschaulichen wir ein Beispiel, bei dem ein privater Schlüssel nur anhand des öffentlichen Schlüssels gefunden wird. Dabei wird klassische Brute-Force-Berechnung verwendet, aber es zeigt, wie Shors Algorithmus eingesetzt werden könnte – auch für große Schlüssel.

hinweis

In diesem Abschnitt zeigen wir die mathematischen Berechnungen im Detail als Teil des Python-Codes

In dem Beispiel haben wir einen öffentlichen Schlüssel $(5, 247)$ und werden den privaten Schlüssel wiederherstellen.

Schritt 1: Der erste Schritt besteht darin, eine zu 247 teilerfremde Zahl zu wählen. Fast jede Zahl, die wir raten, wird das tun. Wählen wir 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Schritt 2: Als Nächstes müssen wir die Periode $r$ finden, sodass $6^r \equiv 1 (mod~247)$ . In diesem Beispiel berechnen wir $r$ klassisch per Brute-Force, aber wir könnten auch Shors Algorithmus auf einem Quantencomputer mit Qiskit verwenden.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Schritt 3: Da die Periode $r = 36$ gerade ist, können wir $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$ berechnen.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Schritt 4: Finde den GGT eines dieser Faktoren mit $n$ . Dividiere $n$ einfach durch den bereits gefundenen Primfaktor, um den zweiten Primfaktor zu erhalten.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Schritt 5: Nachdem wir die Primfaktoren von $n = 247$ als $p_{found}=13$ und $q_{found}=19$ wiederhergestellt haben, berechnen wir den Totient $\phi_{found} = (p_{found}-1)*(q_{found}-1)$ .

Der private Schlüssel ist das modulare Inverse der öffentlichen Schlüsselzahl $e=5$ .

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

Im obigen Schema ist Schritt 2 die entscheidende Perioden-Suchoperation, für die Shors Algorithmus zwei grundlegende Quantenprimitive verwendet, nämlich die Quanten-Fourier-Transformation und die Quantenphasenschätzung. Eine ausführliche Erklärung der Quantenaspekte von Shors Algorithmus findest du in der Lektion zur Phasenschätzung und Faktorisierung im Kurs Grundlagen der Quantenalgorithmen. Die Schritte 1 und 3 bis 5 umfassen verhältnismäßig günstige Operationen, die einfach auf klassischen Computern durchgeführt werden können.

Optional gibt es hier eine detaillierte visuelle Schritt-für-Schritt-Anleitung zur Implementierung von Shors Algorithmus.

Auf Quantencomputern kann Shors Algorithmus eine polylogarithmische Skalierung von bis zu $O((log~n)^2 (log~log~n))$ in Bezug auf den Modulus $n$ aufweisen, oder eine polynomielle Skalierung in Bezug auf die Anzahl der Bits, die zur Darstellung von $n$ benötigt werden. Dies ist eine superpolynomielle Beschleunigung im Vergleich zum klassischen GNFS-Algorithmus.

Aktuelle Ressourcenschätzungen zeigen, dass je nach bestimmten Annahmen zur Hardware-Konfiguration einige Zehntausend bis mehrere Millionen Qubits erforderlich sein werden, um 2048-Bit-RSA mit Shors Algorithmus zu brechen. Es ist nicht undenkbar, dass Quantencomputer mit mehreren Zehntausend Qubits in den nächsten Jahren verfügbar werden, wodurch das untere Ende des Ressourcenaufwands erreichbar wird.

Diffie-Hellman-Schlüsselaustausch und der Digital Signature Algorithm

Im vorherigen Abschnitt haben wir das RSA-Kryptosystem besprochen, dessen Sicherheit auf der rechnerischen Schwierigkeit der Primfaktorzerlegung beruht. Hier werden wir zwei populäre asymmetrische kryptografische Protokolle besprechen: den Diffie-Hellman-Schlüsselaustausch (DH) und den Digital Signature Algorithm (DSA), die beide auf einem anderen mathematischen Problem basieren, nämlich dem diskreten Logarithmusproblem (DLP).

Das diskrete Logarithmusproblem

In der folgenden Gleichung müssen wir $a$ finden, wenn nur $e$ , $M$ , $c$ bekannt sind:

$a^e$ $mod$ $M = c$

Aufgrund der Verwendung von Modulo-Arithmetik gilt dies mit klassischen Computern als schwierig und ist daher eine gute mathematische Grundlage für einen Verschlüsselungsalgorithmus.

Dies ist als das diskrete Logarithmusproblem (DLP) bekannt.

Mathematische Details des diskreten Logarithmusproblems

Das DLP wird typischerweise im Kontext von zyklischen Gruppen formuliert und lautet wie folgt.

Betrachte eine zyklische Gruppe $G$ , erzeugt durch ein Gruppenelement $g \in G$ , und gegeben ein beliebiges Element $h \in G$ , finde eine ganze Zahl $k$ so, dass $h = g^{k}$ .

Hier ist die ganze Zahl $k \equiv log_{g}h$ der diskrete Logarithmus. Die zyklische Eigenschaft von $G$ garantiert, dass für jedes $h$ eine gültige ganze Zahl $k$ existiert.

Für die Kryptografie erweist sich das DLP auf der multiplikativen Gruppe der ganzen Zahlen modulo einer Primzahl $p$ , bezeichnet als $(\mathbb{Z}_p)^{\times}$ , als nützlich. Die Elemente von $(\mathbb{Z}_p)^{\times}$ sind Kongruenzklassen, die durch ganze Zahlen modulo $p$ bezeichnet werden, die teilerfremd zu $p$ sind.

Zum Beispiel:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{und}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

Die Multiplikation $(\times)$ auf diesen Gruppen ist schlicht die gewöhnliche ganzzahlige Multiplikation gefolgt von einer Reduktion modulo $p$ , und die Potenzierung mit einer ganzen Zahl $k$ ist die $k$ -fach wiederholte Multiplikation mit Reduktion modulo $p$ .

Veranschaulichen wir eine Instanz des DLP auf $(\mathbb{Z}_7)^{\times}$ .

Diese multiplikative Gruppe hat zwei Erzeuger $\{[3],[5]\}$ , auch bekannt als primitive Wurzeln. Wir verwenden $[5]$ als Erzeuger, das heißt, wir erzeugen jedes Element von $(\mathbb{Z}_7)^{\times}$ durch aufeinanderfolgende ganzzahlige Potenzen von 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Wir sehen, dass in der Modulo-7-Arithmetik das Potenzieren von 5 mit aufeinanderfolgenden ganzzahligen Potenzen jedes Element von $(\mathbb{Z}_7)^{\times}$ genau einmal ergibt, bevor sich der Zyklus mit der Periode $p-1 = 6$ unendlich wiederholt.

Das DLP auf $(\mathbb{Z}_7)^{\times}$ mit dem Erzeuger [5] lautet also:

$\mathrm{Gegeben~sei~}h \in (\mathbb{Z}_7)^{\times} \mathrm{, finde~} k \mathrm{~so~dass~} 5^{k} \equiv h~(mod~7)$ .

Aus der obigen Python-Zellenausgabe sehen wir:

$h = 2 \implies k=4 \mathrm{~oder~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~oder~} 3 = log_5(6) (mod~7)$

In der gewöhnlichen reellen Arithmetik ist die Potenzierung eine monotone Funktion, und das Berechnen des Logarithmus einer beliebigen Zahl zu einer beliebigen Basis ist rechnerisch einfach. Im Gegensatz dazu ist, wie am einfachen Beispiel $(\mathbb{Z}_7)^{\times}$ zu erkennen ist, die modulare Exponentiation nicht-monoton, und obwohl sie periodisch mit der Periode $p-1$ ist, ist sie ansonsten höchst nichttrivial. Daher erweist sich die Berechnung ihres Inversen, des diskreten Logarithmus, auf klassischen Computern für große $p$ als ineffizient.

Diese Beobachtung bildet die Grundlage sowohl für den Diffie-Hellman (DH)-Schlüsselaustausch als auch für den Digital Signature Algorithm (DSA), die im nächsten Abschnitt besprochen werden.

Das DLP kann wie folgt auf zyklische Untergruppen ausgedehnt werden:

Betrachte $(\mathbb{Z}_p)^{\times}$ wie oben definiert und ein Element $g \in (\mathbb{Z}_p)^{\times}$ von Primordnung $r$ , das heißt $g^r \equiv 1 (~mod~p)$ .
Die Menge der ganzzahligen Potenzen von $g$ : $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ ist eine zyklische Untergruppe von $(\mathbb{Z}_p)^{\times}$ mit der Gruppenordnung $r$ .
Ein DLP kann auf $\langle g \rangle$ spezifiziert werden, indem man ein $h \in \\langle g \rangle$ wählt und $1 \le a \le r$ sucht, sodass $g^a~(mod~p) = h$

Diffie-Hellman-Schlüsselaustausch

Im Jahr 1976 schlugen Whitfield Diffie und Martin Hellman ein Schlüsselaustauschprotokoll vor, um die Erstellung eines gemeinsamen geheimen Schlüssels über unsichere Kommunikationskanäle zu ermöglichen. Der geheime Schlüssel konnte dann von den ihn teilenden Parteien für die symmetrische Verschlüsselung verwendet werden. Der Algorithmus stützt sich auf das DLP.

Abbildung 1. Diffie-Hellman-Schlüsselaustausch

Abbildung 1. Diffie-Hellman-Schlüsselaustausch

Mathematische Details des Diffie-Hellman-Schlüsselaustauschs

Mit Alice und Bob als den beiden kommunizierenden Parteien funktioniert das Protokoll wie folgt:

Zunächst einigen sich Alice und Bob auf eine große Primzahl $p$ und eine primitive Wurzel oder einen Erzeuger $a$ .
Dann wählt Alice zufällig einen geheimen Exponenten $k_A$ mit $1 \le k_A \le p-2$ und berechnet $h_A = a^{k_A}~(mod~p)$ . $k_A, h_A$ sind Alices privater bzw. öffentlicher Schlüssel.
Als Nächstes wählt Bob zufällig einen geheimen Exponenten $k_B$ mit $1 \le k_B \le p-2$ und berechnet $h_B = a^{k_B}~(mod~p)$ . $k_B, h_B$ sind Bobs privater bzw. öffentlicher Schlüssel.
Dann sendet Alice Bob $h_A$ und Bob sendet Alice $h_B$ über einen zuverlässigen, aber nicht notwendigerweise sicheren Kanal.
Anschließend verwendet Alice das empfangene $h_B$ , um den gemeinsamen geheimen Schlüssel $\kappa = h_B^{k_A}~(mod~p)$ zu berechnen.
Schließlich verwendet Bob das empfangene $h_A$ , um den gemeinsamen geheimen Schlüssel $\kappa = h_A^{k_B}~(mod~p)$ zu berechnen.

Mit diesem Protokoll gilt:

Alice und Bob erhalten garantiert denselben geheimen Schlüssel $\kappa$ , da $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$ .
Eine dritte Partei, die $h_A$ oder $h_B$ abfängt, kann den geheimen Schlüssel $\kappa$ nicht konstruieren, da sie keinen Zugang zu $k_B$ bzw. $k_A$ hat.
Das Extrahieren von $k_A$ oder $k_B$ mithilfe der öffentlichen Informationen $a$ , $p$ , $h_A$ und $h_B$ ist rechnerisch aufwändig, da es dem Lösen des DLP auf $(\mathbb{Z}_p)^{\times}$ entspricht.

Illustration des Diffie-Hellman-Protokolls in Python

Schauen wir uns ein einfaches Beispiel des DH-Protokolls in Python mit kleinen Primzahlen an:

hinweis

In diesem Abschnitt zeigen wir die mathematischen Berechnungen im Detail als Teil des Python-Codes

Schritt 1: Alice und Bob einigen sich auf eine Primzahl $p$ und eine primitive Wurzel $a$ . Wählen wir $p=11, a=7$ .

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Schritte 2, 3: Alice wählt einen geheimen Exponenten $k_A$ und berechnet $h_A = a^{k_A}~(mod~p)$ . Ebenso wählt Bob einen geheimen Exponenten $k_B$ und berechnet $h_B = a^{k_B}~(mod~p)$ .

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Schritt 4: Beide Parteien veröffentlichen ihre öffentlichen Schlüssel $h_A$ und $h_B$ .

Schritte 5, 6: Jede Partei kombiniert ihren privaten Schlüssel mit dem öffentlichen Schlüssel der anderen Partei, um den gemeinsamen geheimen Schlüssel zu erstellen.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice und Bob können nun den gemeinsamen geheimen Schlüssel für die symmetrische Verschlüsselung verwenden.

Sicherheit des Diffie-Hellman-Schlüsselaustauschs

Wie bereits erwähnt, beruht die Sicherheit von DH auf der rechnerischen Schwierigkeit, das DLP mit großen Primzahlen $p$ zu lösen. In typischen Anwendungen empfiehlt NIST 2048- oder 3072-Bit-Primzahlen für den DH-Schlüsselaustausch, was als ausreichend sicher gegenüber Versuchen gilt, das DLP mit klassischen Computern zu lösen.

Man-in-the-Middle-(MITM)-Angriffe: Die Tatsache, dass DH ein interaktives Schema ist, bei dem das gemeinsame Geheimnis davon abhängt, den privaten Schlüssel einer Partei mit dem öffentlichen Schlüssel der anderen Partei zu kombinieren, macht es anfällig für einen sogenannten Man-in-the-Middle-(MITM)-Angriff.

Mathematische Details zur DH-Sicherheit und MITM-Angriffen

In diesem Szenario fängt eine dritte Partei – beispielsweise Eve – die öffentlichen Schlüssel $h_A, h_B$ während der Übertragung ab und ersetzt jeweils $h_A$ und $h_B$ durch ihren eigenen öffentlichen Schlüssel $h_E$ , bevor sie diese an Bob bzw. Alice weiterleitet.

Anstatt $h_B$ zur Erstellung ihres gemeinsamen Geheimnisses zu verwenden, verwendet Alice dann $h_E$ , in der Annahme, Bobs öffentlichen Schlüssel zu verwenden. Ebenso verwendet Bob statt $h_A$ den Schlüssel $h_E$ , in der Annahme, Alices öffentlichen Schlüssel zu verwenden.

Da $h_E$ zur Erstellung von Alices (Bobs) gemeinsamen Geheimnis verwendet wurde, kann der von Alice (Bob) verschlüsselte Klartext von Eve entschlüsselt werden.

Daher wird der DH-Schlüsselaustausch typischerweise in Verbindung mit einem digitalen Signaturalgorithmus verwendet, um sicherzustellen, dass jede Partei einen authentifizierten öffentlichen Schlüssel zur Erstellung ihres gemeinsamen Geheimnisses verwendet.

Der Digital Signature Algorithm (DSA)

Obwohl generische Kryptosysteme wie RSA digitale Signaturfunktionalität bieten, verabschiedete NIST 1994 ein spezialisiertes Signaturverfahren auf Basis der modularen Exponentiation und des diskreten Logarithmusproblems als föderalen Standard für digitale Signaturen. Dieses Verfahren, das schlicht als Digital Signature Algorithm (DSA) bekannt wurde, umfasst vier verschiedene Phasen:

Schlüsselgenerierung:

DSA-Schlüssel werden erzeugt aus:
- 2 Primzahlen, die bestimmte Regeln erfüllen
  - $p$ – typischerweise 256 Bits (wir nennen diese Länge $N$ )
  - $q$ – typischerweise 3072 Bits (wir nennen diese Länge $L$ )
- Einer kryptografischen Hashfunktion, die von Zeichenketten der Länge $L$ auf $N$ abbildet
- Einem zusätzlichen Parameter $g$ (siehe Details unten)
Daraus wählen wir eine zufällige Zahl $x$ als privaten Schlüssel und können einen öffentlichen Schlüssel $y$ berechnen.
Mathematische Details der Schlüsselgenerierung
- Parametergenerierung: Mathematisch gesehen umfasst DSA eine zyklische Untergruppe von $(\mathbb{Z}_p)^{\times}$ , erzeugt durch ein Element $g$ von Primordnung $q < p$ . Der erste Schritt beim DSA besteht daher darin, zwei Primzahlen $p$ , $q$ auszuwählen, um die notwendigen mathematischen Strukturen aufzubauen.
  
  Wähle eine $N$ -Bit-Primzahl $q$ .
  
  Wähle eine $L$ -Bit-Primzahl $p$ so, dass $p-1$ ein Vielfaches von $q$ ist. Die Wahl von $p$ legt die Gruppe $(\mathbb{Z}_p)^{\times}$ fest.
  
  Wähle zufällig eine ganze Zahl $1 < h < p-1$ und berechne $g = h^{(p-1)/q}~mod~p$ . Falls $g=1$ , was selten vorkommt, versuche ein anderes $h$ .
  
  Überprüfe, ob $g^q~mod~p = 1$ . $g$ ist damit ein Erzeuger einer zyklischen Untergruppe $\langle g \rangle$ von $(\mathbb{Z}_p)^{\times}$ mit der Primordnung $q$ .
  
  Die Parameter $(q, p, g)$ legen eine Instanz des Algorithmus fest und sind öffentliche Information. Typischerweise gilt in realistischen Anwendungen $N \sim 256$ und $L \sim 3072$ .
  
  Das Protokoll erfordert auch eine kryptografische Hashfunktion $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ , die binäre $L$ -Bit-Zeichenketten auf $N$ -Bit-Zeichenketten abbildet, zum Beispiel SHA-256.
- Schlüsselpaar-Generierung: Der Unterzeichner muss auf seiner Seite ein Schlüsselpaar erzeugen.
  
  Wähle zufällig eine geheime ganze Zahl $x \in \{1,2...q-1\}$ . $x$ ist der private Schlüssel.
  
  Berechne $y = g^{x}~mod~p$ . $y$ ist der öffentliche Schlüssel des Unterzeichners.
Schlüsselverteilung:

Die folgenden Informationen werden mit allen geteilt, die eine Signatur validieren möchten:
- Die verwendeten Parameter $(p,q,g)$ , die den Algorithmus beschreiben
- Die Hashfunktion $H$
- Der öffentliche Schlüssel $y$
Signieren:
- Der Unterzeichner kann nun eine Nachricht $m$ signieren. Die resultierende Signatur ist $(r,s)$ .
- Die Nachricht und die Signatur werden nun beide an den Empfänger gesendet.
Mathematische Details des Signierens einer Nachricht
Der Unterzeichner signiert eine Nachricht $m$ wie folgt:
- Wähle zufällig eine geheime ganze Zahl $k$ aus $\{1,2...q-1\}$ .
- Berechne $r = (g^k~mod~p)~mod~q$ . Im seltenen Fall, dass $r=0$ , versuche ein anderes zufälliges $k$ .
- Berechne $s = (k^{-1} (H(m) + xr))~mod~q$ . Im seltenen Fall, dass $s=0$ , versuche ein anderes zufälliges $k$ .
- Die Signatur ist das Tupel $(r, s)$ .
- Der Unterzeichner überträgt die Nachricht $m$ sowie die Signatur $(r,s)$ an den Prüfer.
Da sowohl $r$ als auch $s$ ganze Zahlen modulo $q$ sind, liegt die Signaturgröße in der Größenordnung von $N$ Bits und nicht der längeren $L$ Bits.
Verifizierung:

Der Empfänger möchte nun die Authentizität des Absenders überprüfen. Er hat Zugang zu den öffentlichen Informationen $(q, p, g, H, y, (r,s), m)$ und kann eine Berechnung durchführen, die beweist, dass der Absender Zugang zum privaten Schlüssel $x$ hatte.

Dabei soll festgestellt werden, ob der Unterzeichner jemand mit Zugang zum privaten Schlüssel $x$ ist.
Mathematische Details des DSA-Verifizierungsverfahrens
- Überprüfe, ob $0 \lt r \lt q$ und $0 \lt s \lt q$ , das heißt, $r, s$ sind gültige ganze Zahlen modulo $q$ .
- Berechne $w = s^{-1}~mod~q$ .
- Berechne $u_1 = H(m)w~mod~q$ .
- Berechne $u_2 = rw~mod~q$ .
- Berechne $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$ .
- Die Signatur ist verifiziert, wenn $v = r$ .
Für legitime Signaturen lässt sich die Korrektheit des DSA-Algorithmus leicht wie folgt zeigen:
- Auf Seiten des Unterzeichners: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
- Mit Blick auf die rechte Seite der letzteren Gleichheit kann ein Prüfer $s^{-1}, H(m)$ berechnen, da $s, q, m, H$ öffentliche Informationen sind.
- Der Prüfer berechnet also $w = s^{-1}~mod~q$ und $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$ .
- Der Prüfer berechnet auch $u_2 = rw~mod~q = rs^{-1}~mod~q$ , da $r$ ebenfalls öffentlich ist.
- Beachte, dass $k = (u_1 + xu_2)~mod~q$ .
- Ein Prüfer hat jedoch keinen Zugang zu $x$ , da es der private Schlüssel des Unterzeichners ist, sodass $k$ selbst nicht direkt berechnet werden kann. Das Verfahren beruht stattdessen darauf, dass der Prüfer zwar $k$ nicht berechnen kann, aber bei einem legitimen Unterzeichner $(g^k~mod~p)~mod~q = r$ mithilfe des öffentlichen Schlüssels des Unterzeichners $y = g^{x}~mod~p$ neu berechnen können sollte.
- Der Prüfer berechnet daher $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$ .
- Die letzte Gleichheit folgt daraus, dass $g$ die Ordnung $q$ hat, und belegt $v = r$ für gültige Signaturen.

Illustration des DSA in Python

In diesem Beispiel verwenden wir kleine Primzahlen, um den DSA-Prozess in einem Szenario zu veranschaulichen, in dem Alice eine signierte Nachricht an Bob sendet. Wir verwenden in diesem Beispiel kleine ganze Zahlen. Ein reales Szenario würde wesentlich größere Primzahlen in der Größenordnung von 2048–3072 Bits verwenden.

hinweis

Du kannst dieses Beispiel mit verschiedenen Werten erneut ausführen, um zu sehen, wie sich der Algorithmus verhält. Stelle jedoch sicher, dass du von der ersten Zelle in diesem Abschnitt aus beginnst.

Wir beginnen mit dem Import der notwendigen Bibliotheken und der Wahl unserer Parameter. Die ganzzahligen Parameter $p$ , $q$ , $g$ sind öffentliche Information und erfüllen folgende Regeln:

$p$ , $q$ sind beide prim
$(p-1) \mod\ q = 0$
$g \ge 2$
$g \le (p-2)$
$g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Als Nächstes generiert die Unterzeichnerin Alice ihren privaten Schlüssel.

Der private Schlüssel $k$ (alice-private-key im Python-Code) muss folgendes erfüllen:

$k \ge 2$
$k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice hält ihren privaten Schlüssel geheim.

Als Nächstes berechnet Alice ihren öffentlichen Schlüssel mittels modularer Exponentiation. Diesen Schritt umzukehren, um den privaten Schlüssel wiederzugewinnen, ist eine Instanz des DLP und daher auf klassischen Computern mit großen Primzahlen schwer zu berechnen.

Aus der mathematischen Erklärung oben wissen wir, dass dies mit der Formel berechnet werden kann:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Wie üblich macht Alice ihren öffentlichen Schlüssel über einen nicht notwendigerweise geheimen Kanal verfügbar.

Nun kann Alice eine Nachricht signieren.

Für das digitale Signaturverfahren müssen wir einen Hash $H(m)$ der zu signierenden Nachricht $m$ erzeugen.

Nehmen wir an, Alice und Bob einigen sich auf einen bestimmten Hashalgorithmus mit einer Hashlänge $N$ , die der Bitanzahl von $q$ entspricht. In diesem einfachen Beispiel begrenzen wir die Ausgaben unserer Pseudohashfunktion auf $q$ . Die Hashfunktion hier ist trivial und erzeugt lediglich eine zufällige ganze Zahl.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Als Nächstes muss Alice eine zufällige nachrichtenspezifische Geheimzahl $k$ sowie ihr multiplikatives Inverses modulo $q$ erzeugen, um die Signatur zu berechnen.

Ein einfacher Brute-Force-Algorithmus kann zur Berechnung des modularen Inversen verwendet werden. Es ist jedoch besser, die eingebaute Python-Funktion pow wie unten gezeigt zu verwenden.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice kann nun die Signatur berechnen.

$r = (g^{k} \mod p) \mod\ q$
$s = (k^{-1} (H(m) + xr)) \mod q$

Beachte, dass es bestimmte Bedingungen gibt, die erfordern, einen anderen Wert für $k$ zu wählen, falls entweder $r$ oder $s$ zu $0$ berechnet werden. In diesem Fall erzeugen wir einen neuen Wert und wiederholen den Vorgang.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice übermittelt die Nachricht und ihre Signatur an den Empfänger oder Prüfer, Bob.

Bob hat zuvor Alices öffentlichen Schlüssel abgerufen und kann nun die Signatur überprüfen, um ihre Nachricht zu authentifizieren.

Dazu führt er einige Prüfungen durch, erzeugt dann erneut einen Hash von Alices übertragener Nachricht und berechnet die Hilfsgrößen $w, u_1, u_2$ und $v$ .

$0 < r < q$
$0 < s < q$
$w = s^{-1} \mod\ q$
$u_{1} = H(m) . w \mod\ q$
$u_{2} = r . w \mod\ q$
$v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Schließlich prüft Bob, ob $v$ gleich $r$ ist. Sind sie gleich, ist die Signatur verifiziert.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Sicherheit des DSA

Bei klassischer Berechnung kann die Sicherheit des DSA von mehreren Faktoren beeinflusst werden:

Schlüsselgröße: Wie immer bietet die Schlüsselgröße grundlegenden Schutz gegen Brute-Force-Angriffe. Moderne Anwendungen, die DSA verwenden, nutzen Schlüsselgrößen von mindestens 2048 Bits.
Qualität von $k$ : Beim DSA benötigt jede Signatur einen eindeutigen, zufälligen und geheimen $k$ -Wert (siehe oben). Die Einzigartigkeit, Entropie und Geheimhaltung von $k$ sind entscheidend, und Schwächen in einem dieser Aspekte könnten dazu führen, dass der private Schlüssel $x$ kompromittiert wird. Die zur Erzeugung von $k$ verwendeten Zufallszahlengeneratoren müssen selbst sicher sein.
Stärke der Hashfunktion: Da DSA eine Hashfunktion als Teil der Signaturerstellung und des Verifizierungsprozesses verwendet, könnte eine schwache Hashfunktion die Sicherheit der digitalen Signatur gefährden. Zum Beispiel ist die Verwendung von SHA-1 mit DSA veraltet, und SHA-2 oder höher wird empfohlen.

Zusätzlich sollte eine robuste DSA-Implementierung auch gegen andere Arten von Angriffen auf asymmetrische Kryptografie schützen, wie zuvor beschrieben.

Authentifizierter Schlüsselaustausch mit Diffie-Hellman und DSA

Moderne Netzwerksicherheitsprotokolle wie Transport Layer Security (TLS) und viele andere kombinieren die Funktionalitäten des Schlüsselaustauschs und der Authentifizierung. Im Kontext von Diffie-Hellman wird Authentifizierung benötigt, um MITM-Angriffe abzuwehren. In den folgenden Code-Zellen veranschaulichen wir ein Beispiel, bei dem Alice und Bob einen authentifizierten Schlüsselaustausch durchführen, indem sie die Diffie-Hellman- und DSA-Protokolle kombinieren. Dazu verwenden wir die Python-Bibliothek cryptography.

Abbildung 2. Authentifizierter Schlüsselaustausch mit Diffie-Hellman und DSA

Abbildung 2. Authentifizierter Schlüsselaustausch mit Diffie-Hellman und DSA

Zunächst einigen sich Alice und Bob auf eine Reihe von DH-Parametern und erzeugen jeweils ein DH-Schlüsselpaar.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Die DH-öffentlichen Schlüssel werden veröffentlicht. Als Nächstes erzeugen sowohl Alice als auch Bob jeweils ein separates Schlüsselpaar zur Verwendung mit DSA. Diese Schlüssel werden wiederum verwendet, um die auszutauschenden DH-öffentlichen Schlüssel zu signieren.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice signiert ihren DH-öffentlichen Schlüssel mit ihrem DSA-privaten Schlüssel.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Ebenso signiert Bob seinen DH-öffentlichen Schlüssel mit seinem DSA-privaten Schlüssel.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Die DH-öffentlichen Schlüssel und die entsprechenden Signaturen werden nun von Alice und Bob veröffentlicht. Nachdem jede Partei den öffentlichen Schlüssel und die Signatur der Gegenseite erhalten hat, verifiziert sie die Gültigkeit der Signatur. Auf diese Weise kann ein MITM-Angriff verhindert werden, da Alice beispielsweise weiß, dass Bobs DH-öffentlicher Schlüssel tatsächlich von Bob signiert wurde und umgekehrt.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Nach der Signaturverifizierung erzeugen Alice und Bob das gemeinsame Geheimnis, womit der Schlüsselaustausch abgeschlossen ist.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Optional können Alice und Bob zur zusätzlichen Sicherheit eine spezialisierte Schlüsselableitungsfunktion wie HKDF verwenden, um mithilfe von Key-Stretching-Techniken einen sichereren symmetrischen Schlüssel aus ihrem gemeinsamen Geheimnis zu erzeugen.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Diffie-Hellman und DSA brechen

Sowohl das Diffie-Hellman-Protokoll (DH) als auch DSA beinhalten die Erzeugung öffentlicher Schlüssel der Form $y = g^{x}~mod~p$ , wobei der private Schlüssel $x$ der diskrete Logarithmus ist.

Ein Angreifer, der eine Instanz des DLP lösen kann, legt den privaten Schlüssel einer der beiden Parteien offen und erhält durch Kombination mit dem öffentlichen Schlüssel der zweiten Partei Zugang zum gemeinsamen Geheimnis. Im Fall von DSA kann ein Angreifer, der das DLP lösen kann, den privaten Schlüssel des Unterzeichners wiederherstellen und damit die Grundprämisse einer digitalen Signatur aushebeln.

Auf klassischen Rechensystemen gilt für das DLP, dass es keine Lösung in Polynomialzeit gibt. Wie Peter Shor jedoch in seinem Originalartikel von 1994 gezeigt hat, löst Shors Algorithmus das DLP ebenfalls in Polynomialzeit auf Quantencomputern.

Shors Algorithmus und das Problem des diskreten Logarithmus

Shors Algorithmus kann das Problem des diskreten Logarithmus in Polynomialzeit lösen. Seine Effizienz erreicht er vor allem durch den Einsatz von Quantenalgorithmen, die die Periode einer Funktion finden können, die vom Eingabewert des Problems abhängt – diese wird dann mit konventionelleren Operationen kombiniert.

Mathematische Details von Shors Algorithmus

Shors Algorithmus bietet eine effiziente Lösung für das DLP, indem er es auf ein allgemeineres Problem der Gruppentheorie abbildet, bekannt als das Hidden-Subgroup-Problem (HSP).

Beim HSP wird eine algebraische Gruppe $G$ und eine Funktion $f: G \rightarrow X$ von $G$ in eine Menge $X$ gegeben, sodass $f$ auf jedem Nebenkoset einer Untergruppe $H$ von $G$ konstant ist (und auf verschiedenen Nebenkosets unterschiedliche Werte annimmt). Die Aufgabe besteht dann darin, $H$ zu bestimmen. Es ist bekannt, dass Quantencomputer das HSP auf endlichen abelschen Gruppen in einer Zeit lösen können, die polynomiell in $log~|G|$ ist, wobei $|G|$ die Gruppenordnung ist.

Im Fall des ganzzahligen DLP aus dieser Lektion lautet die Abbildung auf das HSP wie folgt:

Sei $p$ eine Primzahl und betrachte das DLP gegeben durch $y = g^r~mod~p$ , wobei $g$ ein Erzeuger von $(\mathbb{Z}_p)^{\times}$ ist. Da $g^{p-1} \equiv 1~mod~p$ , hat $g$ die Ordnung $p-1$ .
Wähle $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ , wobei $\mathbb{Z}_{p-1}$ die Gruppe der ganzen Zahlen modulo $(p-1)$ ist.
Wähle $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ definiert als $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
Der Kern von $f$ ist dann die Untergruppe $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$ .
$f$ ist konstant auf den Nebenkosets $(\delta, 0) + H_0$ und „versteckt" die Untergruppe $H_0$ , wodurch ein HSP entsteht.

Basierend auf dem Obigen verwendet Shors Quantenalgorithmus für das ganzzahlige DLP ein Quantenorakel, um die Funktion $f$ auf einem Zustand auszuwerten, der eine gleichmäßige Superposition über $G$ darstellt, und nutzt dann die Quanten-Fourier-Transformation und Messungen mit Phasenschätzung, um Quantenzustände zu erzeugen, die die Identifikation des Erzeugers $(r, 1)$ von $H_0$ ermöglichen. Daraus lässt sich $r$ , der gesuchte diskrete Logarithmus, extrahieren.

Shors Originalartikel enthält eine detaillierte Beschreibung des Algorithmus.

Elliptische-Kurven-Kryptographie

Die Elliptische-Kurven-Kryptographie (ECC), die auf der Mathematik elliptischer Kurven basiert, bietet einen leistungsstarken Ansatz für asymmetrische Kryptographie. ECC ist dafür bekannt, ein ähnliches Sicherheitsniveau wie Verfahren wie RSA zu bieten, jedoch mit kürzeren Schlüsseln, was es effizienter und besonders gut geeignet für ressourcenbeschränkte Systeme wie eingebettete Systeme und Mobilgeräte macht, wo die Speicher- und Rechenersparnisse kleinerer Schlüsselgrößen sehr erwünscht sind.

Grundprinzipien der Elliptischen-Kurven-Kryptographie

Eine elliptische Kurve hat typischerweise die Form $y^2 = x^3 + ax + b$ und besitzt einige interessante Eigenschaften.

Sie ist horizontal symmetrisch. Für jeden Punkt $(x,y)$ auf der Kurve liegt daher auch sein Spiegelbild $(x,-y)$ auf der Kurve.
Jede nicht-vertikale Gerade schneidet die Kurve in höchstens drei Punkten.

Abbildung 1. Operationen der Addition und der Punktverdopplung auf einer elliptischen Kurve. Facette 1 definiert P + Q = -R. Facette 2 illustriert die Punktverdopplung 2Q = -P. Facette 3 definiert das additive Inverse eines Punktes als dessen Spiegelung an der x-Achse, d. h. P = -Q

Abbildung 1. Operationen der Addition und der Punktverdopplung auf einer elliptischen Kurve. Facette 1 definiert P + Q = -R. Facette 2 illustriert die Punktverdopplung 2Q = -P. Facette 3 definiert das additive Inverse eines Punktes als dessen Spiegelung an der x-Achse, d. h. P = -Q

Die Elliptische-Kurven-Kryptographie nutzt eine Reihe von arithmetischen Operationen auf Punkten der Kurve. Jede Operation führt effektiv zu einem neuen Punkt auf der Kurve. In eine Richtung ist dieser Prozess einfach nachzuvollziehen und mit kürzeren Schlüsselgrößen effizienter als andere Algorithmen wie RSA – die Umkehrung hingegen ist sehr schwierig, weshalb er in der Kryptographie eingesetzt wird.

Mathematische Prinzipien der Elliptischen-Kurven-Kryptographie

Eine elliptische Kurve über einem algebraischen Körper $K$ wird durch eine mathematische Gleichung definiert, typischerweise in der Form $y^2 = x^3 + ax + b$ mit Koeffizienten $a, b \in K$ , und beschreibt Punkte $(x, y) \in K \otimes K$ mit der zusätzlichen Anforderung, dass die Kurve keine Knicke oder Selbstüberschneidungen aufweist.

Die Eigenschaften elliptischer Kurven ermöglichen die Definition von „Additions"- und „skalaren Multiplikations"-Operationen auf Punkten der Kurve.

Addition: Sind $P$ und $Q$ zwei Punkte auf einer elliptischen Kurve, so bezeichnet $P + Q$ einen eindeutigen dritten Punkt, der wie folgt bestimmt wird: Man zeichnet die Gerade durch $P$ und $Q$ und sucht den dritten Punkt $R$ , an dem diese Gerade die Kurve schneidet. Dann definiert man $P + Q = −R$ , den Punkt gegenüber $R$ , gespiegelt an der $x$ -Achse (siehe Abbildung unten). Wenn die Gerade durch $P, Q$ die Kurve an keinem endlichen Punkt $(x, y)$ schneidet, sagt man, sie schneidet die Kurve im unendlich fernen Punkt $\mathbf{O}$ .

Die Addition auf elliptischen Kurven erfüllt algebraische Gruppen-Eigenschaften, wobei der unendlich ferne Punkt das additive neutrale Element ist.

Verdopplung und skalare Multiplikation: Die Punktverdopplungsoperation, die der skalaren Multiplikation mit $2$ entspricht, ergibt sich durch Setzen von $P = Q$ in der Additionsoperation und beinhaltet grafisch die Tangente an $P$ . Die allgemeine skalare Multiplikation mit einer ganzen Zahl $n$ , definiert als $nP = P + P + ...~n$ mal, wird durch wiederholte Verdopplung und Addition erhalten.

Das elliptische-Kurven-Problem des diskreten Logarithmus

Das elliptische-Kurven-Problem des diskreten Logarithmus (ECDLP) weist viele Ähnlichkeiten mit dem zuvor besprochenen Problem des diskreten Logarithmus auf, da es auf den Schwierigkeiten beim Finden von Faktoren basiert.

Die Operation der skalaren Multiplikation auf elliptischen Kurven ermöglicht die Definition des elliptischen-Kurven-Problems des diskreten Logarithmus:

Gegeben die Punkte $P, Q$ auf einer elliptischen Kurve mit $Q = nP$ , bestimme $n$ .

Dieses Problem gilt für große $n$ auf klassischen Computern als unlösbar und bildet die Grundlage für kryptographische Sicherheit.

Mathematische Beschreibung des ECDLP

Die Elliptische-Kurven-Kryptographie basiert primär auf dem ECDLP, das über bestimmten algebraischen endlichen Körpern formuliert wird. 1999 empfahl NIST zehn endliche Körper für den Einsatz in ECC. Diese sind:

Fünf Primkörper $\mathbb {F} _{p}$ für Primzahlen $p$ der Größe $\{192, 224, 256, 384, 521\}$ Bits.
Fünf binäre Körper $\mathbb {F} _{2^{n}}$ für $n \in \{163, 233, 283, 409, 571\}$ .

Mit dem obigen Aufbau lässt sich ein ECC-basiertes asymmetrisches Kryptosystem für Primkörper wie folgt spezifizieren:

Wähle ein $p$ aus der von NIST empfohlenen Liste, um $\mathbb {F} _{p}$ festzulegen.
Wähle die Parameter $a, b$ der elliptischen Kurve.
Wähle einen Basispunkt $G$ , der eine zyklische Untergruppe auf der Kurve mit der Ordnung $n$ „erzeugt"; das heißt, die kleinste ganze Zahl, für die $nG = \mathbf{O}$ gilt.
Berechne den Kofaktor $h = |E(\mathbb {F} _{p})|/n$ , wobei $|E(\mathbb {F} _{p})|$ die Anzahl der Punkte auf der Kurve ist. $h$ ist typischerweise eine kleine ganze Zahl.
Die Domänenparameter $(p, a, b, G, n, h)$ ermöglichen die Spezifikation asymmetrischer Schlüssel auf folgende Weise:
- Der private Schlüssel ist eine zufällig gewählte ganze Zahl $d$ mit so vielen Bits wie die Primzahl $p$ . Er sollte geheim gehalten werden.
- Der öffentliche Schlüssel ist das Ergebnis der „Multiplikation" des Basispunkts $G$ mit dem privaten Schlüssel $d$ . Dies wird üblicherweise als $Q = dG$ bezeichnet.

Die Wiederherstellung von $d$ ist äquivalent zur Lösung des ECDLP, das für große $d$ als unlösbar gilt. Das ECDLP bildet daher die Grundlage für Schlüsselaustausch- und digitale Signaturverfahren in direkter Analogie zu den über $(\mathbb{Z}_p)^{\times}$ definierten Diffie-Hellman- und DSA-Verfahren, die zuvor besprochen wurden.

Schlüsselaustausch mit ECC

Eine der wichtigsten Anwendungen von ECC ist das Schlüsselaustauschprotokoll, das als elliptisches Kurven Diffie-Hellman (ECDH) bekannt ist. Bei ECDH erzeugt jede Partei ein privates-öffentliches Schlüsselpaar und tauscht dann öffentliche Schlüssel aus. Jede Partei verwendet anschließend ihren eigenen privaten Schlüssel und den öffentlichen Schlüssel der anderen Partei, um ein gemeinsames Geheimnis zu berechnen, das als Schlüssel für die symmetrische Verschlüsselung verwendet werden kann.

Obwohl es relativ einfach ist, Punktaddition auf einer elliptischen Kurve durchzuführen und einen öffentlichen Schlüssel aus einem privaten Schlüssel abzuleiten, ist es rechnerisch nicht machbar, den Prozess umzukehren und einen privaten Schlüssel aus einem öffentlichen Schlüssel abzuleiten. Dieses „Einweg"-Verhalten gewährleistet die Sicherheit des ECDH-Schlüsselaustauschs.

Hier veranschaulichen wir ein Beispiel, wie man einen ECDH-Schlüsselaustausch mit Python und der Bibliothek cryptography durchführen könnte.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Digitale Signaturen mit ECC

ECC kann auch verwendet werden, um digitale Signaturen mit dem Elliptic Curve Digital Signature Algorithm (ECDSA) zu erzeugen. Bei ECDSA erstellt der Unterzeichner eine Signatur mit seinem privaten Schlüssel, und andere können die Signatur mit dem öffentlichen Schlüssel des Unterzeichners verifizieren. Genau wie bei ECDH beruht die Sicherheit von ECDSA auf dem ECDLP. Es ist für niemanden rechnerisch machbar, eine Signatur zu fälschen, ohne Zugang zum privaten Schlüssel des Unterzeichners zu haben.

Das Folgende ist ein Beispiel für eine einfache Signier- und Verifizierungstransaktion mit ECDSA unter Verwendung von Python und cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

Im obigen Code schlägt die Verifizierung fehl, wenn die Nachricht nach dem Signieren geändert wird, was eine Garantie für Authentizität und Integrität der Nachricht bietet.

ECDH und ECDSA brechen

Analog zum ganzzahligen Problem des diskreten Logarithmus erweist sich das ECDLP auf klassischen Computern als schwierig, hat jedoch erneut eine effiziente Lösung auf Quantencomputern via Shors Algorithmus. Für eine Diskussion zur Verallgemeinerung von Shors Algorithmus auf den ECDLP-Fall verweisen wir auf aktuelle Fachliteratur.

Zusammenfassung

In dieser Lektion haben wir zunächst die wichtigsten Eigenschaften der asymmetrischen Kryptographie (AKC) betrachtet und grundlegende Sicherheitsüberlegungen besprochen, die asymmetrischen Kryptosystemen zugrunde liegen. Insbesondere haben wir die beiden Hauptanwendungen von AKC eingeführt – nämlich Schlüsselaustausch und digitale Signaturen –, die beide wesentliche Bestandteile moderner internetbasierter Kommunikation sind.

Anschließend haben wir das RSA-Kryptosystem betrachtet, das seit den 1970er Jahren einen immensen Beitrag zur Sicherung moderner digitaler Kommunikation geleistet hat, indem es Schlüsselaustausch und digitale Signaturen in einem einfachen und vielseitigen Rahmen ermöglicht. Die kryptographische Sicherheit von RSA gegenüber klassischem Computing basiert auf der Schwierigkeit, große ganze Zahlen zu faktorisieren, und erfordert Schlüsselgrößen im Bereich von 2048 Bit, um sicherzustellen, dass die in praktischen Anwendungen verwendeten Zahlen groß genug sind, um einer Faktorisierung zu widerstehen.

Dann haben wir den Diffie-Hellman-Schlüsselaustausch (DH) und den Digital Signature Algorithm (DSA) betrachtet. Die Sicherheit dieser Verfahren basiert auf dem ganzzahligen Problem des diskreten Logarithmus (DLP): Der private Schlüssel ist bei gegebenem öffentlichen Schlüssel rechnerisch schwer zu extrahieren, ohne eine Lösung in Polynomialzeit auf klassischen Computern. Die Verwendung zufälliger und eindeutiger Schlüssel bietet zusätzlichen Schutz gegen Angriffe. Sowohl die ganzzahligen endlichen-Körper- als auch die elliptischen-Kurven-Varianten der DH- und DSA-Protokolle finden derzeit weite Verbreitung in vielen modernen digitalen Kommunikationsprotokollen wie TLS, SSH und anderen.

Schließlich haben wir die Elliptische-Kurven-Kryptographie betrachtet. Mit ihrer effizienten Schlüsselgröße und starken Sicherheitseigenschaften stellt sie derzeit eine ausgezeichnete Wahl für viele kryptographische Anwendungen dar, vom Schlüsselaustausch bis hin zu digitalen Signaturen.

Alle diese Algorithmen sind anfällig für Angriffe durch Quantenalgorithmen, da Lösungen für die mathematischen Probleme entwickelt werden können, die ihrer Konzeption zugrunde lagen. Ein solches Beispiel ist Shors Algorithmus. Daher müssen sie durch quantensichere asymmetrische Kryptosysteme ersetzt werden, die widerstandsfähiger gegen Angriffe durch Quantencomputer sind – und gleichzeitig so sicher wie klassische Algorithmen bleiben. Die mathematischen Probleme, auf die sie sich stützen, lassen sich von Quantencomputern effizient lösen, was die Entwicklung quantensicherer asymmetrischer Kryptosysteme notwendig macht, die Quantenangriffen standhalten und gleichzeitig klassische Sicherheit gewährleisten.

Einführung in die asymmetrische Schlüsselkryptografie​

Schlüsselaustausch mit asymmetrischer Schlüsselkryptografie​

Interaktiver Schlüsselaustausch​

Nicht-interaktiver Schlüsselaustausch​

Digitale Signaturen mit asymmetrischer Schlüsselkryptografie​

Dedizierte digitale Signaturalgorithmen​

Digitale Signaturverfahren mit generischen Kryptosystemen​

Anwendungen der asymmetrischen Schlüsselkryptografie​

Sicherheit der asymmetrischen Schlüsselkryptografie​

Sicherheitsrisiken für die asymmetrische Schlüsselkryptografie​

RSA​

Der RSA-Algorithmus​

RSA in Python veranschaulicht​

RSA-Schlüsselerzeugung​

Symmetrischer Schlüsselaustausch mit RSA​

Padding-basiertes Schlüsselaustausch-Beispiel in Python​

Simulation eines Schlüsselkapselungsmechanismus mit RSA in Python​

Digitale Signaturen mit RSA​

RSA brechen​

Klassische Computer und RSA​

Shors Quantenalgorithmus und RSA​

Python-Beispiel zur Demonstration des Brechens von RSA-Verschlüsselung​

Diffie-Hellman-Schlüsselaustausch und der Digital Signature Algorithm​

Das diskrete Logarithmusproblem​

Mathematische Details des diskreten Logarithmusproblems​

Diffie-Hellman-Schlüsselaustausch​

Illustration des Diffie-Hellman-Protokolls in Python​

Sicherheit des Diffie-Hellman-Schlüsselaustauschs​

Der Digital Signature Algorithm (DSA)​

Illustration des DSA in Python​

Sicherheit des DSA​

Authentifizierter Schlüsselaustausch mit Diffie-Hellman und DSA​

Diffie-Hellman und DSA brechen​

Shors Algorithmus und das Problem des diskreten Logarithmus​

Elliptische-Kurven-Kryptographie​

Grundprinzipien der Elliptischen-Kurven-Kryptographie​

Das elliptische-Kurven-Problem des diskreten Logarithmus​

Schlüsselaustausch mit ECC​

Digitale Signaturen mit ECC​

ECDH und ECDSA brechen​

Zusammenfassung​

Einführung in die asymmetrische Schlüsselkryptografie

Schlüsselaustausch mit asymmetrischer Schlüsselkryptografie

Interaktiver Schlüsselaustausch

Nicht-interaktiver Schlüsselaustausch

Digitale Signaturen mit asymmetrischer Schlüsselkryptografie

Dedizierte digitale Signaturalgorithmen

Digitale Signaturverfahren mit generischen Kryptosystemen

Anwendungen der asymmetrischen Schlüsselkryptografie

Sicherheit der asymmetrischen Schlüsselkryptografie

Sicherheitsrisiken für die asymmetrische Schlüsselkryptografie

RSA

Der RSA-Algorithmus

RSA in Python veranschaulicht

RSA-Schlüsselerzeugung

Symmetrischer Schlüsselaustausch mit RSA

Padding-basiertes Schlüsselaustausch-Beispiel in Python

Simulation eines Schlüsselkapselungsmechanismus mit RSA in Python

Digitale Signaturen mit RSA

RSA brechen

Klassische Computer und RSA

Shors Quantenalgorithmus und RSA

Python-Beispiel zur Demonstration des Brechens von RSA-Verschlüsselung

Diffie-Hellman-Schlüsselaustausch und der Digital Signature Algorithm

Das diskrete Logarithmusproblem

Mathematische Details des diskreten Logarithmusproblems

Diffie-Hellman-Schlüsselaustausch

Illustration des Diffie-Hellman-Protokolls in Python

Sicherheit des Diffie-Hellman-Schlüsselaustauschs

Der Digital Signature Algorithm (DSA)

Illustration des DSA in Python

Sicherheit des DSA

Authentifizierter Schlüsselaustausch mit Diffie-Hellman und DSA

Diffie-Hellman und DSA brechen

Shors Algorithmus und das Problem des diskreten Logarithmus

Elliptische-Kurven-Kryptographie

Grundprinzipien der Elliptischen-Kurven-Kryptographie

Das elliptische-Kurven-Problem des diskreten Logarithmus

Schlüsselaustausch mit ECC

Digitale Signaturen mit ECC

ECDH und ECDSA brechen

Zusammenfassung