RSA und Ganzzahlfaktorzerlegung

RSA ist das bekannteste Public-Key-Kryptosystem, das Verschlüsselung und digitale Signaturen bereitstellt, deren Sicherheit auf der Schwierigkeit beruht, das Produkt zweier großer Primzahlen zu faktorisieren.

Definition

RSA ist ein Public-Key-Kryptosystem, bei dem ein öffentlicher Modul n das Produkt zweier geheimer Primzahlen ist; die Verschlüsselung erhöht die Nachricht auf einen öffentlichen Exponenten modulo n, und die Entschlüsselung verwendet einen privaten Exponenten, der nur aus der Faktorisierung von n ableitbar ist.

Scope

Dieses Thema behandelt den RSA-Algorithmus – Schlüsselerzeugung, Verschlüsselung, Entschlüsselung und Signierung mittels modularer Exponentiation – zusammen mit dem Problem der Ganzzahlfaktorzerlegung, auf dem er basiert, den Faktorisierungsalgorithmen, die ihn bedrohen, und den Padding-Schemata (OAEP, PSS), die das Lehrbuch-RSA in der Praxis sicher machen. Es befasst sich mit Empfehlungen zur Schlüssellänge und Implementierungsangriffen wie Timing- und Fehlerangriffen. Es schließt diskrete Logarithmus-basierte Schemata und elliptische Kurvenkryptographie aus, die separat behandelt werden.

Core questions

• Wie entstehen die öffentlichen und privaten RSA-Exponenten aus der Struktur der modularen Arithmetik?
• Warum hängt die Sicherheit von RSA von der Schwierigkeit der Faktorisierung des Moduls ab?
• Wie schnell können große Ganzzahlen faktorisiert werden, und was bedeutet das für die Schlüssellängen?
• Warum ist Lehrbuch-RSA unsicher, und wie beheben Padding-Schemata wie OAEP und PSS dies?
• Welche Implementierungsangriffe (Timing, Fehler, schwache Zufälligkeit) bedrohen RSA in der Praxis?

Key concepts

• modulare Exponentiation
• öffentliche und private Exponenten
• Eulersche Totientenfunktion und Carmichael-Funktion
• Faktorisierungsproblem
• allgemeines Zahlkörper-Sieb
• OAEP-Padding
• PSS-Signatur-Padding
• Schlüssellänge und Sicherheitsniveau

Key theories

RSA-Falltür-Permutation

RSA definiert eine Falltür-Einweg-Permutation: Das Erhöhen auf den öffentlichen Exponenten modulo n ist einfach, aber die Invertierung erfordert den privaten Exponenten, der nur aus der Primfaktorzerlegung von n berechnet werden kann – der Falltür.

Faktorisierungsannahme und Schlüssellänge

Die praktische Sicherheit von RSA folgt den besten Faktorisierungsalgorithmen (derzeit das allgemeine Zahlkörper-Sieb, subexponentiell in der Modullänge); ihnen zu widerstehen ist der Grund, warum modernes RSA 2048-Bit oder größere Moduli verwendet.

Mechanisms

Die Schlüsselerzeugung wählt zwei große zufällige Primzahlen p und q, setzt n = p*q, wählt einen öffentlichen Exponenten e, der teilerfremd zu (p-1)(q-1) ist, und berechnet den privaten Exponenten d als das modulare Inverse von e. Die Verschlüsselung berechnet c = m^e mod n; die Entschlüsselung stellt m = c^d mod n wieder her. Die Korrektheit folgt aus dem Satz von Euler. Eine sichere Bereitstellung umschließt den Klartext mit OAEP-Padding für die Verschlüsselung und verwendet PSS für Signaturen, da das rohe 'Lehrbuch'-RSA formbar und deterministisch ist.

Clinical relevance

RSA sichert jahrzehntelang eingesetzte Infrastrukturen: TLS-Serverzertifikate, Code-Signierung, SSH-Schlüssel, PGP/S-MIME-E-Mails, Smartcards und Dokumentensignierung. Obwohl elliptische Kurven-Schemata für neue Systeme aufgrund kleinerer Schlüssel zunehmend bevorzugt werden, bleibt RSA in Zertifikaten und älteren Protokollen weit verbreitet, und sein Verständnis ist für die Bewertung realer kryptographischer Risiken unerlässlich.

Evidence & guidelines

RSA ist in PKCS #1 (RFC 8017) standardisiert, das OAEP und PSS spezifiziert. NIST (SP 800-57) empfiehlt einen minimalen 2048-Bit-Modul, mit 3072-Bit für höhere Sicherheitsstufen. Bemerkenswerte Fehler (der Debian-Fehler bei schwachen Schlüsseln, der ROCA-Fehler bei der Infineon-Schlüsselerzeugung und die FREAK-Herabstufung auf 512-Bit-Export-RSA) unterstreichen die Bedeutung einer korrekten Schlüsselerzeugung und Parametergrößen.

History

RSA wurde 1977-1978 von Rivest, Shamir und Adleman am MIT veröffentlicht, die erste praktische Realisierung des von Diffie und Hellman vorgeschlagenen Public-Key-Konzepts. (Clifford Cocks hatte ein äquivalentes Schema 1973 heimlich bei GCHQ entdeckt.) Fortschritte bei der Faktorisierung – das quadratische Sieb und dann das Zahlkörper-Sieb in den 1980er-1990er Jahren – erhöhten schrittweise die sichere Schlüssellänge, und die RSA Factoring Challenges verfolgten den praktischen Fortschritt.

Key figures

• Ronald Rivest
• Adi Shamir
• Leonard Adleman
• Carl Pomerance
• Arjen Lenstra

Seminal works

• rivest1978
• katz2020
• menezes1996

Frequently asked questions

Ist RSA gebrochen?

Nein, kein klassischer Angriff bricht korrekt implementiertes RSA mit einem ausreichend großen Modul (2048 Bit oder mehr). Reale RSA-Fehler resultieren aus zu kleinen Schlüsseln, schwacher Zufallszahlengenerierung oder fehlendem/falschem Padding, nicht aus einem Bruch des Algorithmus selbst. Ein großer Quantencomputer würde RSA jedoch über Shors Algorithmus brechen.

Warum kann ich nicht einfach direkt mit der RSA-Funktion verschlüsseln?

Rohes 'Lehrbuch'-RSA ist deterministisch und formbar, was Informationen preisgibt und die Manipulation von Chiffretexten ermöglicht. Eine sichere Verwendung erfordert randomisiertes Padding wie OAEP für die Verschlüsselung und PSS für Signaturen, weshalb Standards diese Schemata vorschreiben.