Deutsche knacken RSA-Verschlüsselung mit 576 Bit

Internet & Webdienste Moderne mathematische Verschlüsselungsverfahren beruhen auf der Schwierigkeit, große Zahlen in ihre Primfaktoren zu zerlegen. Denn was bei "21 = 7 mal 3" noch jeder Drittklässler problemlos schafft, wird bei genügend großen Zahlen fast unmöglich. ... mehr...

Diese Nachricht vollständig anzeigen.

Jetzt einen Kommentar schreiben
 
MEGAROFL. PGP-Author Phil Zimmermann hat doch in einem kleinen und mittlerweile wieder wegzensierten Statement doch selber zugegeben, dass er mal bei der NSA war und diese schön längst einen einfachen aber genialen Algorithmus zur Faktorisierung kennen.
 
Na klar, und das CIA ist an den Anschlägen auf das WTC schuld (oh, was für ein dummer Vergleich, es stimmt ja fast)
 
Ja, ja, wir Deutschen können was.... :-)
 
21 ist 3*7 .. dachte immer 17+4? u. @Rika - Ja genau und da ist noch niemand anderes draufgekommen. Nennt man Primfaktorzerlegung... extrem einfach! Schon klasse diese Typen bei der NSA was: Einfach aber genial :-) Und überhaupt die wiegen uns alle nur in Sicherheit, die können längst alles lesen was wir uns jeden Tag per PGP verschlüsselten Nachrichten schicken. Wir schicken ja auch schon gar nichts mehr ohne Verschlüsselung, soviel Privatleben muss auch sein finde ich. Die sollen auch mal ein einfaches und geniales Mittel errechnen um die Nahrungsmittel auf der Erde effektiv zu verteilen. Zerlegt mal 3003!
 
Einfach ist ein Algorithmus genau dann, wenn er nicht schwierig ist. Schwierig ist ein Algorithmus, wenn er mehr als polynomiale Laufzeit hat. Sie haben einen Algorithmus entwickelt, der mit sehr wenig Aufwand auch große Zahlen faktorisieren kann. Anundfürsich ist das sogar glaubhaft, schließlich haben wir nach knapp 200 Jahren vor einigen Monaten auch einen polynomialen Algorithmus für die Inzidenz von Primzahlen mit O(ln(n)^6) gefunden. PGP ist damit als definitiv unsicher zu betrachten. BTW, 3003 = 3*7*11*13. Es geht aber bei dem Faktorisierungsproblem bei RSA nur um Zahlen, die definitiv nur aus zwei sehr große Primfaktoren bestehen - und dieses Problem ist wesentlich schwieriger als 'ne herkömmliche Faktorisierung.
 
Antwort auf den Kommentar von oderwat. Naja ganz so schlimm ist es nicht, RSA ist schon noch sicher, denn der Aufwand jetzt den 1024er zu knacken ist ja exponentiell größer, deshalb ist das gar kein Vergleich, ist ja nicht so als müsste man jetzt nur doppelt soviel Power aufwenden um den 1024er zu knacken, deshalb halte ich es für schlichtweg unmöglich in den nächsten Jahren die 2048 zu knacken, so ne geilen Algorythmus hat niemand, auch die Mathematik hat Grenzen. Aber nen 1024er würde ich nicht mehr huntertprozentig Vertrauen, denn es könnte schon sein, dass jemand noch einen besseren Algorithmus hat, der es noch einfacher macht die Faktorisierung durchzuführen.
 
Antwort auf den Kommentar von oderwat: Wie sieht es eigentlich mit anderen Verfahren für Public-Key Verschlüsselung? Hat da jemand nen schönen Link für? Sowas wie: http://entropy.stop1984.com/de/mceliece.html
 
Herrje, willst du es denn nicht verstehen? Wenn es einen polynomialen Algorithmus gibt, dann ist der Aufwand auch nur polynomial größer. Wenn es ein O(ln(n)^3)-Algorithmus ist, dann braucht man für die doppelte Schlüssellänge nur 8 mal mehr Zeit. Wenn man pro 1024-Bit-Schlüssel vielleicht 1 Stunden braucht, dann braucht man für 2048 Bit nur 8 Stunden. Die Mathematik hat nur vermutet, dass überhaupt kein exponentieller Algorithmus existieren kann - aber das hat sie bei der Primzahl-Inzidenz auch behauptet, und letztendlich das Gegenteil festgestellt. (http://www.cse.iitk.ac.in/news/primality.html). Weiterhin wurde vermutet, dass ein starker Zusammenhang zwischen der Primzahlinzidenz und der Faktoriserung besteht, in dem Sinne, dass wenn Prinzahlinzidenz schwierig ist, dass dann auch Faktosieren schwerig ist - und ebenso umgekehrt, wenn Faktosieren leicht ist, dann auch Primzahlinzidenz. Die Feststellung, dass die Primzahlindizenz einfach ist, ist zwar kein Beweis, aber ein sehr starkes Indiz dafür, dass auch Faktorisieren leicht ist. Von daher ist Phil Zimmermann mit dieser Aussage sehr glaubwürdig.
 
DSS bzw. DHS als neuere Verfahren bei PGP basieren auch auf ein dem Faktorisierungsproblem äquivalenten Problem und sind laut Zimmermann ebensfalls leicht zu entschlüsseln. An alternativen Verfahren ist eigentlich nur Snefru 6 bekannt, was auf Permutationen basiert und als wirklich serh sicher betrachtet wird. Aber solange weder PGP noch SSL noch S/MIME dieses Verfahren nutzt, sind unsere Daten zumindest vor der NSa und einigen anderen Organisationen nicht sicher.
 
Antwort auf den Kommentar von oderwat. Rika das sind doch alles nur Vermutungen und Gerüchte, Theorien, aber es gibt doch keine Beweise dafür. Außerdem wer verschlüsselt denn mit RSA, kein Schwanz, RSA wird nur zum Signieren verwendet. Zum Verschlüsseln setzt man AES, BlowFish etc ein, also total uninterressant und für die sieht die Sache wieder ganz anders aus.
 
Antwort auf den Kommentar von oderwat @Rika ... ohje ... ich habe meine geheimen daten jetzt alle mal schnell ausgedruckt und verbrannt ... :-)
 
1. Das ist ja das Problem - solange die NSA nix rausrückt, kann auch keiner was beweisen. Und die Forscher müssen unnötig selber die Lösung des Problems suchen. Fakt ist, dass weder RSA noch PGP noch der Author von PGP vertrauenswürdig sind. 2. Aber die Schlüssel von den symmaterischen Verfahren müssen wiederum verschlüsselt werden, und zwar mit Public-Key-Verfahren - es sei denn, es stehe ein absolut sicherer Transportweg zur Verfügung, und das trifft auf's INet nicht zu. Es sei denn, man verwendet wiederum Public-Key-Verfahren... du erkennst das Problem? Der Schlüssel kann den Empfänger nie sicher erreichen , sondern kann abgefangen und selbst verwendet werden.
 
http://www.mathepower.com/primfaktor.php
 
ROFL. "Die Primfaktorenzerlegung von 8388607 ist:
8388607". Dabei ist 8388607 durch 47 teilbar...
 
Antwort auf den Kommentar von oderwat: Na da hat man wenigstens ne gute Ausrede wenn die Mathehausaufgaben nicht stimmen :-)
 
Die DEUTSCHEN sind die besten :)
 
Antwort auf den Kommentar von didudo0 Vorsicht, sonst kriegste ne Predigt.... :-)
 
Gassner's Law: Jemand, der gewisse Grundsätze und Prinzipien als "typisch deutsch!" bezeichnet, hat automatisch verloren. "Typisch deutsch" kommt nur von Argumentationslosen. Sie haben nichts mehr zu sagen.
 
Wer im Glashaus sitzt.....
 
Noschinski's Zusatz: Es sind meistens Deutsche, die von "typisch Deutsch" reden.
 
stereotypen erklären nunmal die welt am besten
 
@Rika,

respekt, mit wieviel wissen du hier auftrumpfst. Was machst du beruflich?
 
Ich wette der studiert Mathe oder sowas... boah eh, ihc versteh von seinen sachen nur bahnhof... aber was mit polynomen hab ich schonmal in mathe gehört...
 
Wahrscheinlich hätte ich auch Mathe studiert, wenn da die Berufsaussichten etwas besser wären... Wirtschaftsmathematik ist zwar hochbezahlt, aber stinklangweilig. Und wenn du von dem oben genannten nciht viel verstehtst, dann benutze Google und lies misc.comp.security.cryptography, solange bis du es verstehst.
 
Antwort auf den Kommentar von chaossos Ich vermute mal das er arbeitsloser Programmierer ist (so oft bei WF unterwegs). :-)
 
Als Student ist man fast zwangsläufig arbeitslos...
 
naja das war klar. warum so ein highlight? die haben sowas schonmal geschafft. nur nicht mit einem so großen schlüssel. ist doch klar dass das auch so weitergeht. ich denke mit der zeit wirds auch für AES schwer werden. Ich denke es wird noch dauern bis eine wirklich extrem gute und sichere methode zum verschlüsseln geht, die aber dennoch so einfach ist.
 
@Rika Primzahlerzeugung kann auf Faktorisierung reduziert werden. Falls tatsächlich ein Algorithmus mit polynomialer Laufzeit dafür gefunden wurde, wäre die gesammte allgemein benutzte Kryptographie (AES, Blowfish, etc) in Gefahr, da die sich alle aufeinander reduzieren lassen. Nicht polynomiale Laufzeit bedeutet aber trotzdem nicht automatisch schnell. Link zur Behauptung, dass solch ein Algorithmus gefunden wurde?
 
1. Kaum eine symmetrische Verschlüsselung wie AES oder Blowfish basiert auf Primzahlen, sondern auf eher auf S-Boxen, Feistel-Netzwerken, Permutationsgruppen, Codierungen etc. Es sind wirklich Public-Key-Verfahren betroffen, die als bislang sicher galten. Mit Ausnahme von Snefru 6. AES gilt als leicht fehlerhaft (und einem großen mathematischen Theorem zufolge ist es dann garantiert vollständig fehlerhaft), Blowfish-128 wurde bereits geknackt. 2. Wie ich schon sagte, das betreffende Posting in m.c.s.c sowie drei Webseiten mit dem Statement wurden kurzerhand wieder entfernt.
 
Richtig, das waren exakt die falschen Beispiele, symetrische Verschlüsselung ist natürlich relativ uninteresant. Entscheidend ist die Sicherheit von Public Key Verfahren. Wobei ein Posting das zurückgenommen wird etc. natürlich auch eine nette Art von PR sein könnte, die dazu führt, dass weniger verschlüsselt wird, da es ja anscheinend eh sinnlos ist. Es gab vor vielen Jahren mal einen "Bug" in einer allgemein verwendeten RSA Implementierung, da stand im Source statt != == , und die Anzahl der möglichen Kombinationen hat sich dadurch drastisch reduziert. Der Fehler wurde lange nicht gefunden, ist eben auch recht unwahrscheinlich dass sowas sofort entdeckt wird.
 
Die Verschlüsselung wurde schon vor fast 2 Monaten geknackt :)
Siehe http://mathworld.wolfram.com/news/2003-12-05/rsa/
 
Hier noch etwas zum Thema: http://kremlinencrypt.com/crypto/algorithms.html
Kommentar abgeben Netiquette beachten!

Video-Empfehlungen

WinFuture Mobil

WinFuture.mbo QR-Code Auch Unterwegs bestens informiert!
Nachrichten und Kommentare auf
dem Smartphone lesen.

Folgt uns auf Twitter

WinFuture bei Twitter

Interessante Artikel & Testberichte

WinFuture wird gehostet von Artfiles