StartseiteMathlog

232-stellige Zahl faktorisiert

Von / 9. Januar 2010 / 9 Kommentare
Mehr

2,5 Jahre hat’s gedauert, hunderte Rechner waren beteiligt.

Einen neuen Rekord bei der Primzahlfaktorisierung meldet eine 13-köpfige Gruppe aus Lausanne, Tokio, Bonn, Nancy, Redmond und Amsterdam. Die Zahl RSA-768 wurde in 2,5-jähriger Arbeit in Primfaktoren zerlegt. Bisheriger Rekord, war eine 200-stellige Zahl, die Mai 2005 faktorisiert wurde.

Das mathematische Verfahren wird in diesem 22-seitigen Text beschrieben.

So gut wie alle Bezahl-Verfahren im Internet benutzen (ohne daß man dies als Nutzer überhaupt bemerken würde) die RSA-Verschlüsselung, die mit Produkten großer Primzahlen arbeitet.
Praktisch läuft das so, daß bei Verbindungsaufnahme der Kaufhaus-Rechner zwei große Primzahlen p,q nach einem Zufallsverfahren erzeugt, und das Produkt dieser beiden Zahlen pq an den Kunden-Rechner übermittelt. (Außerdem gibt es noch einen geheimen Schlüssel, der nur im Kaufhaus-Rechner gespeichert wird und einen öffentlichen Schlüssel, der über die Leitung an den Kunden-Rechner übertragen wird.) Das Produkt pq und der öffentliche Schlüssel (die beide über die evtl. unsicheren Leitungen übertragen worden sind), werden dann vom Rechner des Kunden zur Verschlüsselung der Daten verwendet. Zur Entschlüsselung reichen diese Informationen aber nicht aus, dazu braucht man den geheimen Schlüssel, der beim Kaufhaus-Rechner gespeichert ist und nicht über die Leitung übertragen wurde.
Der Punkt ist, daß nur das Produkt pq und der öffentliche Schlüssel, nicht aber der geheime Schlüssel, über die unsichere Leitung übertragen wird. Die Primzahlen p,q wurden im Kaufhaus-Rechner benutzt, um den geheimen Schlüssel zu berechnen, und anschließend ‘vernichtet’. Wer nur das Produkt pq über die unsichere Leitung abgehört hat, aber nicht p und q kennt, wird den geheimen Schlüssel nicht mit vernünftigem Aufwand berechnen können. Die Sicherheit des RSA-Verfahrens beruht also darauf, daß Hacker die verwendenten Zahlen nicht (mit vernünftigem Aufwand) in Primfaktoren p,q zerlegen können.

Trotz des neuen Faktorisierungs-Erfolges kann RSA aber weiter als sicher gelten. Kein Hacker wird Hunderte Rechner 2,5 Jahre rechnen lassen, nur um die Daten einer Kreditkarte abzugreifen 🙂

(Die NSA plant übrigens, in den nächsten 10 Jahren RSA durch Elliptische-Kurven-Kryptographie zu ersetzen. )

Stichworte: , , , ,
Mehr

Kommentare (9)

  1. #1 Dennis
    10. Januar 2010

    Im krassen Gegensatz dazu ist der neueste Rekord bei der Berechnung der Nachkommastellen von π auf einem einzigen ganz normalen Rechner entstanden:
    Pi Computation Record by Fabrice Bellard. Genaueres dazu steht in diesem Artikel; allerdings ist hier die Verifikation des Ergebnisses nicht ganz so einfach wie beim RSA-Rekord.

  2. #2 Odysseus
    10. Januar 2010

    Die Welt demonstriert geballtes Sachwissen… gnarf.

  3. #3 antiangst
    10. Januar 2010

    Wieso macht man so was eigentlich, wenn man das Verfahren kennt, kann man auch abschätzen wie lange so was dauert? Ob eine von von den vielen 232-stelligen Zahlen nun tatsächlich faktorisiert ist oder nicht, dürfte doch egal sein.

  4. #4 hanse
    11. Januar 2010

    Ich bin jetzt etwas verwirrt weil im Text von der “RSA-768 Zahl” die Rede ist. Wurde nicht genau ein 768 Bitiger RSA Schlüssel geknackt, also nur eine von vielen möglichen Zahlen?

    Die Aussage das kein Hacker diesen Aufwand betreiben würde halte ich imho auch für irreführend, schließlich können auch größere Organisationen, mit mehr Ressourcen, Interesse an verschlüsselten Daten haben (dann aber ehrer nicht Kreditkarten). Auch nicht vergessen darf man, dass Rechner immer schneller werden und in ein paar Jahren der Aufwand wesentlich geringer sein könnte, die Daten aber dennoch empfindlich sind.

  5. #5 Thilo Kuessner
    11. Januar 2010

    Ich bin jetzt etwas verwirrt weil im Text von der “RSA-768 Zahl” die Rede ist. Wurde nicht genau ein 768 Bitiger RSA Schlüssel geknackt, also nur eine von vielen möglichen Zahlen?

    Ja, es wurde eine spezielle Zahl faktorisiert. Natürlich nicht irgendeine, sondern eine, die vor 19 Jahren von der RSA-Firma als eine besonders schwer zu faktorisierende veröffentlicht worden war. (D.h. die RSA-Firma hatte zwei Primzahlen genommen, deren 232-stelliges Produkt veröffentlicht und dann die Preisaufgabe gestellt, diese Zahl zu faktorisieren. Es gibt natürlich andere 232-stellige Zahlen, die leichter zu faktorisieren sind.)

    Die RSA-Firma hatte damals (1991) eine Liste von Zahlen mit zwischen 100 und 617 Stellen veröffentlicht und Preisgelder für ihre Faktorisierung ausgelobt. (Die Frist für die Preisgelder ist aber 2007 ausgelaufen.) Es handelte sich um eine Liste von 54 Zahlen, die jetzt geknackte ist wohl die 15., die faktorisiert wurde. (Es gibt aber noch kleinere, die bisher nicht faktorisiert sind.)

    https://www.rsa.com/rsalabs/node.asp?id=2093 : “The RSA Challenge numbers are the kind we believe to be the hardest to factor; these numbers should be particularly challenging. These are the kind of numbers used in devising secure RSA cryptosystems.”

    Die Aussage das kein Hacker diesen Aufwand betreiben würde halte ich imho auch für irreführend, schließlich können auch größere Organisationen, mit mehr Ressourcen, Interesse an verschlüsselten Daten haben

    Es sind ja immer nur die jeweils aktuellen Schlüssel (für die Verschlüsselung der eigentlichen Daten), die mit RSA verschlüsselt werden. (Die Daten selbst werden dann mit AES verschlüsselt.) Der mit RSA verschlüsselte Schlüssel ändert sich für jede Transaktion. D.h. man müßte praktisch instantan RSA knacken können, weil man einen Tag später mit dem geknackten Schlüssel nichts mehr anfangen kann.

  6. #6 Odysseus
    11. Januar 2010

    @hanse: Genau, es wurde nur eine spezielle 768-Bit-Zahl expemplarisch faktorisiert. Das heißt, ich könnte weiterhin mit jeder anderen Zahl dieser Länge arbeiten, ohne dass ich damit rechnen müsste, dass jemand in den nächsten Monaten den Schlüssel knackt. Für die meisten Transaktionen werden zur Zeit 1024Bit-Zahlen verwendet, deren Faktorisierung nochmal etwa drei Größenordnungen länger dauert. Zur Entwicklung der Computergeschwindigkeit zitiere ich aus dem Paper:

    [I]t is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours or the one in [7]. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.

    RSA ist nicht plötzlich unsicher geworden, und ohne richtig große Großrechner (wie sie wohl nur die NSA hat) kriegst du nach wie vor keine Kreditkarte klein, geschweige denn noch stärker verschlüsselte Daten.

  7. #7 Odysseus
    11. Januar 2010

    War Thilo mal wieder schneller…

  8. #8 hanse
    11. Januar 2010

    Danke für die ausführliche Antwort. Wusste gar nicht das es da so ne Liste gibt.

    Allerdings wir RSA ja nicht nur bei Kreditkarten eingesetzt, sondern auch z.B. bei EMail Verschlüsselung. Dort wird der symmetrische Schlüssel mitgeliefert und damit kann dann der Rest der Nachricht entschlüsselt werden (zumindest macht OpenGPG das so ( https://www.ietf.org/rfc/rfc4880.txt unter 2.1).

  9. #9 Thilo Kuessner
    12. Januar 2010

    Dort wird der symmetrische Schlüssel mitgeliefert und damit kann dann der Rest der Nachricht entschlüsselt werden

    Zwar wird bei PGP der symmetrische Schlüssel mit-übertragen, aber nicht unverschlüsselt: er wurde vorher mit dem öffentlichen RSA-Schlüssel des Empfängers verschlüsselt. Ein Hacker hat also dasselbe Problem: er muß erst den geheimen RSA-Schlüssel des Empfängers kennen, bevor er den verschlüsselt übertragenen symmetrischen Schlüssel entschlüsseln kann.