1024 bit RSA
ist nicht mehr sicher!Ruediger Weis
cryptolabs Amsterdam
Weis c
�
c
�
c
�
2003 – p.1/23
Aktuelle ÜbersichtsartikelRuediger Weis & Andreas Bogk & Stefan Lucks
� ”1024 bit reichen wohl nicht mehr”,CCC Datenschleuder, 2003.
� ”Sicherheit von 1024 bit RSA Schlüsselngefährdet”,Datenschutz und Datesicherheit (DuD), 2003.
http://www.cryptolabs.org/rsa/
Weis c
�
c
�
c
�
2003 – p.2/23
Vor 4 JahrenCCCongress
� � � �
� Hauptspeicher � �
GB für� ��
-bit Modulus.
Weis c
�
c
�
c
�
2003 – p.3/23
RSARon Rivest, Adi Shamir, Leonard Adleman
� A method for obtaining digital signatures andpublic-key cryptosystems,
Communications of the ACM, 21(2),Februar 1978.
Weis c
�
c
�
c
�
2003 – p.4/23
23.01.2003Adi Shamir, Eran Tromer
� Primaly Draft
Weis c
�
c
�
c
�
2003 – p.5/23
Kostenabschätzungen
� 512 bit Keys: 10.000
�
Hardware10 min
� 1024 bit Keys: 10.000.000�
Hardware1 Jahr
in der Theorie
Weis c
�
c
�
c
�
2003 – p.6/23
Sieb-Algorithmen
� Siebungsschritt
� Gleichungssystem Schritt
Weis c
�
c
�
c
�
2003 – p.7/23
Komplexität GNFS
� � �� �
��� � � � � � � ln
� � � � ��� � � ln�
ln
� � � � � ��� �
Weis c
�
c
�
c
�
2003 – p.8/23
Siebungsschritt
� Zahlen suchen mit bestimmter Eigenschaft(Smoothness)
� Hochgradig parallelisierbar
Weis c
�
c
�
c
�
2003 – p.9/23
Mathmatische Details IEine Instanz eines "Sieb-Problems" besteht auseiner ganzen Zahl , einem Schwellwert T undPaaren
� ��� � ��� �
, wobei � � eine kleine Primzahl ist.Die Paare
� ��� � �� �
definieren ”Progressionen”
� � � � ! � mod ��� � �� "
Weis c
�
c
�
c
�
2003 – p.10/23
Mathmatische Details IIBeim "Sieb-Problem" geht es darum, möglichstviele Werte � zu finden, mit
�$# % & ')(
log
� ��� � *
Weis c
�
c
�
c
�
2003 – p.11/23
SpezialhardwareGrob vereinfacht kann man Geräte wie TWIRLals Spezialhardware auffassen, die dazu dient,die Summen
�$# % & '(log
� ��� �
mit Einsatz von möglichst wenig Chipfläche zuberechnen.
Weis c
�
c
�
c
�
2003 – p.12/23
Matrixreduktion
� Weis, R., CCC 1999: ’Home PC’
� Lenstra, Shamir, Tomlinson, Tromer,“Analysis of Bernstein’s Factorization Circuit”ASIACRYPT 2002
” the security of RSA relies exclusivelyon the hardness of the relation collectionstep of the number field sieve.”
Weis c
�
c
�
c
�
2003 – p.13/23
D.J. Bernstein
� Neuartigen Ansatz zur effizientenImplemenation der Matrix-Reduktion
� Neues Kostemass
� ’Lange Zahlen’
Weis c
�
c
�
c
�
2003 – p.14/23
Mathematische Trivialitäten
� Parallelisierbarkeit
� Wiedernutzbarkeit
Weis c
�
c
�
c
�
2003 – p.15/23
Parallelisierbarkeit
� Das Verfarhen ist nahezu beliebigparallelisierbar.
� Beispielsweise mit Hardware für 120Millionen Euro
1 Monat.
� Rest Übungsaufgabe
Weis c
�
c
�
c
�
2003 – p.16/23
Wiedernutzbarkeit
� Hardware kann für mehrere Schlüssel(nacheinander) verwendet werden.
Weis c
�
c
�
c
�
2003 – p.17/23
Weizmann Institute
� TWINKLE: Gallium-Arsenid-Technologie
� TWIRL: Silizum-Technologie
Weis c
�
c
�
c
�
2003 – p.18/23
Hardware Analyse TWINKLE
� Gallium-Arsenid-Technologie
� 512-Bit-Keys Wafer mit 30cm Durchmesser
Weis c
�
c
�
c
�
2003 – p.19/23
Hardware Analyse TWIRL
� Silizium-basierter VLSI-Technologie
� +
� �-, Strukturgrösse
� � .� � / / � pro Chip für� +� .
Bit Modulus
Weis c
�
c
�
c
�
2003 – p.20/23
TCG keys MUST be2048 bit RSA or greater
TCG1.2 (Part 1, P.12 f.)
� ”All Storage keys MUST be of strengthequivalent to a
� + .0
bit RSA key or greater.”
� ”The minimum RECOMENDED key size is� + .0
bits.”
Weis c
�
c
�
c
�
2003 – p.21/23
Cryptophone: 4096 bitDH 4096 bit (DLP basiert)
� Selbst auf aktuellen PDAs sind. + �1
bit PublicKey-Verfahren Verfahren machbar.
http://www.cryptophone.de/
”Produkt!”
Weis c
�
c
�
c
�
2003 – p.22/23
Acknowledgments
� Stefan Lucks, Andreas Bogk
� c cryptolabs Amsterdam 2003under the GNU Free Document License.
� Produced with Free Software underGNU/Linux.
Weis c
�
c
�
c
�
2003 – p.23/23