2a. Kryptographische Basistechniken
Die Sicherheit des RSA-Verfahrens
Genaueres im Kapitel
Kryptoanalyse des
RSA-Verfahrens der Kryptologie-Vorlesung
a) Iterations-Angriff auf den Geheimtext
Iterieren der Verschlüsselung ergibt:
Er(c) = cer
Da die Exponenten mod f(n) reduziert
werden können, sich also in der endlichen multiplikativen Gruppe des
Restklassenrings Z/f(n)Z
bewegen, gibt es ein r mit
er º 1
(mod f(n)),
also Er(c) = c,
also Er-1(c) = m (!!)
Die Wahrscheinlichkeit, dass für einen gegebenen Geheimtext c
der Exponent r klein ist, ist extrem gering.
===> Das Problem kann vernachlässigt werden.
b) Faktorisierungs-Angriff auf den Schlüssel
Wer den Modul n = pq faktorisieren kann, kann den
geheimen Exponenten d aus dem öffentlichen e bestimmen.
Es ist kein besseres Verfahren bekannt; möglicherweise sind beide
Probleme äquivalent (im komplexitätstheoretischen Sinn, also die
Lösungen gleich aufwendig).
Entscheidend für die Sicherheit also:
Wie schnell kann man große Zahlen faktorisieren?
Wie schnell kann man faktorisieren?
- Es gibt »schnelle« Verfahren nur für spezielle Zahlen
(der Gestalt ab ± c mit »kleinem« a
und c).
- Diese Zahlen werden durch die Nebenbedingungen
für die RSA-Schlüsselerzeugung praktisch ausgeschlossen ...
- ... und fallen gegenüber den allgemeinen Verfahren für große
Zahlen praktisch nicht ins Gewicht.
- Die schnellsten allgemeinen Verfahren
- Zahlkörpersieb u. ä. (Silverman 1987, Pomerance 1988,
A. K. Lenstra/ H. W. Lenstra/ Manasse/ Pollard 1990),
- Elliptische-Kurven-Faktorisierung
(H. W. Lenstra 1987, Atkin/Morain 1993),
haben einen Zeitaufwand der Größenordnung
Ln =
![[Faktorisieren]](Faktoris.gif)
Daraus ergeben sich folgende Erfahrungswerte und
Schätzungen:
| Zahl | Dezimalstellen | Aufwand | Status |
|---|
| rsa120 (399 Bit) | 120 | 100 MIPS-Jahre |
(auf schnellem PC in 1/2 Woche machbar) |
| rsa140 (466 Bit) | 140 | 2000 MIPS-Jahre |
(te Riele, CWI, 1999) |
| 512-Bit-Modul | 154 | 8000 MIPS-Jahre |
(Muffet, CWI, 1999) |
| 640-Bit-Modul | 193 | 40000 MIPS-Jahre |
(Franke, Uni Bonn, 2005, aktueller Weltrekord) |
| 1024-Bit-Modul | 308 | 1011
MIPS-Jahre |
(ganz kurzfristige Sicherheitsgrenze) |
| 2048-Bit-Modul | 616 | 1015
MIPS-Jahre |
(mittelfristige Sicherheitsgrenze) |
... solange die Mathematiker keine wesentlich schnelleren
Faktorisierungsverfahren finden!
Schätzungen von Rivest (80er Jahre)
[Grenze in Dezimalstellen - im Bereich von 2048 Bit entspricht
die pessimistische Schätzung dem heutigen Stand]:
| Jahr | optimistisch | mittel | pessimistisch
|
|---|
| 1990 | 117 | 155 | 388
|
| 1995 | 122 | 163 | 421
|
| 2000 | 127 | 172 | 455
|
| 2005 | 132 | 181 | 490
|
| 2010 | 137 | 190 | 528
|
| 2015 | 142 | 199 | 567
|
| 2020 | 147 | 204 | 607
|
Vorsicht: Alle diese Schätzungen sind mit sehr
großer Unsicherheit behaftet.
Was kann ein PC?
| Sekunden/Jahr | 30 * 106 |
| 1 MIPS-Jahr | 30 * 1012 Instruktionen |
| 386-Architektur (32 Bit) | ca. 0.5 Instruktionen/Takt |
| 2-GHz-PC |
109 Instruktionen/Sekunde
= 103 MIPS = 1 GIPS |
| ... benötigt für 1 MIPS-Jahr |
30 * 103 Sekunden = 500 Minuten = 8:20 Stunden |
| ... für 100 MIPS-Jahre (400-Bit-Modul) |
3.5 Tage = 1/2 Woche |
| ... für 512-Bit-Modul |
40 Wochen |
Was kann ein Super-Computer?
- Cray-I (1978) entspricht ungefähr 50 MHz Pentium-III -
heute nicht mehr »super«.
- Aktuell bekannter schnellster Rechner: »BlueGene/L«
(IBM, Lawrence Livermore Laboratories): > 300 TFLOPS.
- Geplant bis 2011 in Japan: 10 PetaFlops = 10000 TFLOPs.
- 100-TFLOPS-Maschine:
100 * 1012 Gleitkomma-Operationen/Sekunde,
- massiv parallele Architektur,
- entspricht etwa dem 5000-fachen des schnellsten kommerziell
erhältlichen PC,
- und kann 1024-Bit-Moduln in wenigen Sekunden faktorisieren.
- Alternative: Viele vernetzte PCs.
Entwicklung der Faktorisierungsrekorde
[für »allgemeine Zahlen«, waagerechte Achse: Jahr, senkrechte Achse: Bits]
Neue Entwicklungen
- Shamirs »TWINKLE« (= The Weizmann Institute Key Locating Machine)
- Hardware-Umsetzung einer Idee von Lehmer aus den 30er-Jahren,
die das Faktorisieren um den Faktor 100 - 1000 beschleunigt
(ohne die Größenordnung zu ändern).
- Selecting
Cryptographic Key
Sizes (Arjen Lenstra, Eric Verheul); zu pessimistisch, da der
Speicherbedarf der Verfahren nicht berücksichtigt wurde.
- Circuits for
integer factorization: A proposal (Daniel J. Bernstein) -
verdreifacht (!) die Stellenzahl, die bei festem Aufwand für
das schnellste Faktorisierungsverfahren erreichbar ist.
Nach Bernsteins Vorschlag ist der Aufwand für das Zahlkörpersieb:
| Zeit | Ln1.19 + o(1) |
|---|
| Speicherpaltz | Ln0.79 + o(1) |
|---|
Die Abschätzung von Lenstra/Verheul sieht jetzt eher zu optimistisch
aus. 1024-Bit-Schlüssel sollten schnellstens aus dem Verkehr gezogen
werden! 2048-Bit-Schlüssel sind gerade noch für ein paar Jahre sicher.
Ein neuerer Artikel
- Arjen K. Lenstra: Unbelievable security. Matching AES security
using public key systems.
ASIACRYPT 2001, Springer LCNS 2248, 67 - 86
stellt Schlüssellängen gleicher Sicherheit für verschiedene symmetrische und
asymmetrische Verfahren nebeneinander. Danach entspricht die Sicherheit von AES
mit 128-Bit-Schlüssel zur Zeit etwa der Sicherheit von RSA mit 3200-Bit-Modul.
[Beides ist noch etwas redundant.]
Weitere Sicherheitsprobleme
- Die RSA-Falle: Entschlüsseln einer Nachricht durch versehentliches,
möglicherweise blindes
Signieren.
- Grund: Die Homomorphie-Eigenschaft des RSA.
- Verwendung kleiner Exponenten in manchen Szenarien kritisch.
- Gleicher Modul für mehrere Teilnehmer unsinnig.
- Diese Teilnehmer müssen sich uneingeschränkt trauen.
- Gleiche Nachrichten an zwei Teilnehmer können gebrochen werden.
- Side-Channel-Analysen
[siehe Chipkarten]:
- Timing- und Powerattacken
(Zeit- und Stromverbrauch beim binären Potenzalgorithmus).
- Differenzielle Fehleranalyse
(Chip wird unter »Stress« gesetzt und sein Verhalten analysiert).
Vorlesung Datenschutz und Datensicherheit,
Johannes-Gutenberg-Universität Mainz
Autor: Klaus Pommerening, 31. März 1999; letzte Änderung: 16. Juni 2007.
E-Mail an Pommerening »AT« imbei.uni-mainz.de.
![[Faktorisierungsrekorde]](FaktRek72.gif)