Abo
  • IT-Karriere:

MIT: Kryptopuzzle 15 Jahre zu früh gelöst

Ein 1999 von RSA-Miterfinder Ron Rivest erstelltes Kryptopuzzle, bei dem man eine langwierige Berechnung durchführen sollte, ist gelöst - viel früher als erwartet.

Artikel veröffentlicht am ,
Er war 15 Jahre früher dran als erwartet: Der Belgier Bernard Fabrot hat das Kryptopuzzle LCS35 gelöst.
Er war 15 Jahre früher dran als erwartet: Der Belgier Bernard Fabrot hat das Kryptopuzzle LCS35 gelöst. (Bild: MIT)

Der Programmierer Bernard Fabrot hat ein Puzzle gelöst, das 1999 vom Kryptografen Ron Rivest am MIT erdacht wurde. Beim sogenannten LCS35-Puzzle ging es darum, eine große Anzahl von Quadrierungen hintereinander durchzuführen. Rivest hatte geschätzt, dass es bis 2034 dauern würde, bis Computer schnell genug sind, damit jemand eine Lösung bereitstellen könnte. Rivest hatte sich somit deutlich verschätzt.

Stellenmarkt
  1. Etribes Connect GmbH, Hamburg
  2. Stadt Bochum, Bochum

Wie genau Fabrot das Rätsel gelöst hat, ist noch unklar, aber aus der Meldung des MIT geht hervor, dass er dabei wohl C-Code mit der GMP-Bibliothek verwendete. GMP ist eine Standardbibliothek für mathematische Operationen und freie Software. Fabrot hatte laut einem Artikel von Wired seit 2015 einen Computer an dem Rätsel rechnen lassen.

Anderes Team hätte Lösung im Mai gehabt

Pech gehabt hatte eine Gruppe namens Cryptohage, die fast zur gleichen Zeit ebenfalls versucht hatte, das Rätsel zu lösen, und hierfür optimierte FPGAs verwenden wollte. Das Cryptohage-Team ging davon aus, dass es mit Hilfe der Spezialhardware bis Mai in der Lage sein würde, das Rätsel zu lösen. Das Team wurde von Fabrot knapp überholt.

Das Konzept des Rätsels ist vergleichsweise einfach: Es galt, die Zahl 2 viele Male zu quadrieren, insgesamt etwa 80 Billionen mal. Nach jedem Schritt soll das Ergebnis zudem durch einen Modulus reduziert werden.

Rivest ging davon aus, dass es keine sinnvolle Möglichkeit gebe, diese Berechnung zu parallelisieren. Zwar könne innerhalb des Quadrierungs-Algorithmus` parallel gerechnet werden, aber jede Quadrierung für sich müsste einzeln durchgeführt werden. Damit sollte verhindert werden, dass jemand mit besonders vielen parallel arbeitenden Rechnern das Rätsel löst. Das Rätsel ist damit ein Beispiel für eine sogenannte verifizierbare Verzögerungsfunktion (Verifiable Delay Function, VDF).

Mit Primfaktoren lässt sich das Rätsel schneller lösen

Eine weitere Besonderheit: Der Modulus ist eine zusammengesetzte Zahl aus zwei Primfaktoren. Wer die Primfaktoren kennt, kann die Lösung mit einem speziellen Algorithmus schneller berechnen. Doch die kennen zunächst nur die Ersteller des Rätsels. Die Hintergründe sind in einem 1996 veröffentlichten Paper erläutert.

Die Modulus-Zahl ist 2.048 Bit groß. Statt die vielen Quadrierungen durchzuführen, könnte diese Zahl auch faktorisiert werden, doch das ist noch schwerer. Hier gibt es auch eine Verbindung zum von Rivest mitentwickelten Verschlüsselungsalgorithmus RSA: Wäre man in der Lage, diese Zahl zu faktorisieren, wäre auch RSA angreifbar. Doch Rivest gab demjenigen, der das Rätsel löst, eine Möglichkeit, die Primfaktoren zu erfahren. Er verschlüsselte eine kurze Nachricht mit dem Ergebnis des Rätsels und teilte diese ebenfalls mit.

Als Teil des Rätsels wurden 1999 einige Gegenstände aus der IT-Geschichte in eine Zeitschatulle verpackt. Diese sollte entweder 2034 oder zum Zeitpunkt der Lösung des Rätsels geöffnet werden und enthält Objekte, die von IT-Größen wie Bill Gates und Tim Berners-Lee beigesteuert wurden. Die Zeitschatulle soll am 15. Mai geöffnet werden. Dann will Fabrot auch Details über seinen Lösungsweg verraten.



Anzeige
Hardware-Angebote
  1. 177,90€ + Versand (Bestpreis!)
  2. (reduzierte Überstände, Restposten & Co.)
  3. (u. a. Ryzen 5-2600X für 184,90€ oder Sapphire Radeon RX 570 Pulse für 149,00€)

slemme 03. Mai 2019 / Themenstart

Ist das MIT nicht eine private Institution? Bekommen die dann überhaupt öffentliche Gelder?

0110101111010001 03. Mai 2019 / Themenstart

wieso bist du dann noch hier?

lahmbi5678 02. Mai 2019 / Themenstart

Ich habe es gestern abend nochmal durchdacht, leider machten mir die Potenzgesetze einen...

Mingfu 01. Mai 2019 / Themenstart

Preskriptum: Leser fordert mehr Clickbait. ;-) 15 Jahre zu früh stimmt eigentlich gar...

franzropen 01. Mai 2019 / Themenstart

Ich schätze er meint durchaus zwei o to loose = lösen => looser = Löser ;)

Kommentieren


Folgen Sie uns
       


Parrot Anafi Thermal angesehen

Die Anafi Thermal kann dank Wärmebildsensor Temperaturdaten von -10 bis 400° Celsius messen.

Parrot Anafi Thermal angesehen Video aufrufen
Bundestagsanhörung: Beim NetzDG drohen erste Bußgelder
Bundestagsanhörung
Beim NetzDG drohen erste Bußgelder

Aufgrund des Netzwerkdurchsetzungsgesetzes laufen mittlerweile über 70 Verfahren gegen Betreiber sozialer Netzwerke. Das erklärte der zuständige Behördenchef bei einer Anhörung im Bundestag. Die Regeln gegen Hass und Hetze auf Facebook & Co. entzweien nach wie vor die Expertenwelt.
Ein Bericht von Justus Staufburg

  1. NetzDG Grüne halten Löschberichte für "trügerisch unspektakulär"
  2. NetzDG Justizministerium sieht Gesetz gegen Hass im Netz als Erfolg
  3. Virtuelles Hausrecht Facebook muss beim Löschen Meinungsfreiheit beachten

Mobile-Games-Auslese: Games-Kunstwerke für die Hosentasche
Mobile-Games-Auslese
Games-Kunstwerke für die Hosentasche

Cultist Simulator, Photographs, Dungeon Warfare 2 und mehr: Diesen Monat lockt eine besonders hochkarätige Auswahl an kniffligen, gruseligen und komplexen Games an die mobilen Spielgeräte.
Von Rainer Sigl

  1. Spielebranche Auch buntes Spieleblut ist in China künftig verboten
  2. Remake Agent XIII kämpft wieder um seine Identität
  3. Workers & Resources im Test Vorwärts immer, rückwärts nimmer

Oneplus 7 Pro im Hands on: Neue Konkurrenz für die Smartphone-Oberklasse
Oneplus 7 Pro im Hands on
Neue Konkurrenz für die Smartphone-Oberklasse

Parallel zum Oneplus 7 hat das chinesische Unternehmen Oneplus auch das besser ausgestattete Oneplus 7 Pro vorgestellt. Das Smartphone ist mit seiner Kamera mit drei Objektiven für alle Fotosituationen gewappnet und hat eine ausfahrbare Frontkamera - das hat aber seinen Preis.
Ein Hands on von Ingo Pakalski

  1. Oneplus 7 Der Nachfolger des Oneplus 6t kostet 560 Euro
  2. Android 9 Oneplus startet Pie-Beta für Oneplus 3 und 3T
  3. MWC 2019 Oneplus will Prototyp eines 5G-Smartphones zeigen

    •  /