it-swarm-eu.dev

Wie lässt sich die Zeit abschätzen, die zum Knacken der RSA-Verschlüsselung benötigt wird?

Wie lässt sich die Zeit abschätzen, die zum Knacken der RSA-Verschlüsselung benötigt wird? Ich meine die Zeit, die benötigt wird, um die Rsa-Verschlüsselung mit einer Schlüssellänge von 1024, 2048, 3072, 4096, 5120, 6144, 5120, 7168, 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360 und 16384 zu knacken.

67
Predator

Unter diese Site finden Sie eine Zusammenfassung der wichtigsten Stärkenschätzungen, die von verschiedenen Forschern und Organisationen verwendet werden.

Ihre "512-Bit in 12μs" ist völlig falsch. Mal sehen, woher es kommt. 1999 war das Jahr, in dem die erste allgemeine 512-Bit-Faktorisierung für eine von RSA (dem Unternehmen) veröffentlichte Herausforderung mit dem Namen RSA-155 durchgeführt wurde (da die Zahl aus 155 Dezimalstellen bestand - binär beträgt die Länge 512 Bit). Diese Faktorisierung dauerte 6 Monate. Bei der im selben Jahr organisierten Eurocrypt-Veranstaltung (im Mai; zu diesem Zeitpunkt hatte die 512-Bit-Faktorisierung begonnen, war aber noch nicht abgeschlossen), Adi Shamir , vom Weizmann Das Institut präsentierte ein theoretisches Gerät namens TWINKLE , das angeblich bei der Faktorisierung erheblich helfen kann. Es sollte aus einer großen Anzahl von Dioden bestehen, die bei sorgfältig ausgewählten Frequenzen in einer Art schwarzer Röhre blinken. Shamir brachte ein spezielles Gerät mit, das aus 10 Metern Entfernung wie eine Kaffeemaschine aussah. Er bat die Leute, das Licht auszuschalten, damit der Eurocrypt-Teilnehmer die roten Dioden four bestaunen könne, die in Umkehrungen von 2, 3, 5 und 7 Sekunden blinken. Oh! und Aah! Sie gingen, obwohl die eigentliche Maschine, würde sie gebaut werden, einige Millionen Dioden und Frequenzen in den 10 oder 100 gigahertz benötigen würde. Die Idee macht also Spaß (zumindest für Kryptologieforscher, von denen bekannt ist, dass sie einen seltsamen Sinn für Humor haben), ist aber noch nicht über den theoretischen Skizzenschritt hinausgegangen. Shamir ist ein großartiger Schausteller.

TWINKLE ist jedoch nur "Hilfe". Der bekannteste Faktorisierungsalgorithmus heißt General Number Field Sieve ; Die beiden nächsten Algorithmen sind das Quadratisches Sieb und das Elliptische Kurvenmethode . Eine 512-Bit-Nummer ist mit der heutigen Technologie außerhalb der Reichweite von QS und ECM und erst recht mit der Technologie von 1999. GNFS ist sehr komplex (mathematisch gesehen), zumal es eine sorgfältige Auswahl einiger kritischer Parameter erfordert ("Polynomauswahl"). Es muss also eine anfängliche Anstrengung von sehr intelligenten Gehirnen geben (bei großen Computern, aber Gehirne sind hier am wichtigsten). Danach besteht GNFS aus zwei Teilen, dem Sieb und dem linearen Reduktion . Das Sieb kann parallel über Hunderte oder Tausende von Maschinen hergestellt werden, die noch relativ groß sein müssen (im RAM), aber dies ist machbar. Die lineare Reduktion beinhaltet das Berechnen von Dingen mit einer Matrix, die zu groß ist, um in einen Computer zu passen (um mehrere Größenordnungen, und selbst wenn wir annehmen, dass der Computer Terabyte schnellen RAM hat). Es gibt Algorithmen, um die Matrix (die ziemlich spärlich ist) in einem komprimierten Format zu halten und trotzdem in der Lage zu sein, darauf zu rechnen, aber das ist schwierig. Bei der 512-Bit-Faktorisierung dauerte das Sieben etwa 80% der Gesamtzeit, bei größeren Zahlen ist die lineare Reduzierung jedoch der Engpass.

Bei TWINKLE geht es nur darum, den Siebteil zu beschleunigen. Es macht nichts gegen die lineare Reduktion. Mit anderen Worten, es beschleunigt den Teil, der einfach ist (relativ gesehen). Selbst eine TWINKLE-verstärkte Siebhälfte wäre nicht annähernd 12 μs. Stattdessen würde es eher helfen, einen viermonatigen Siebaufwand auf beispielsweise drei Wochen zu reduzieren. Was auf wissenschaftliche Weise gut ist, aber kein Rekordbrecher, zumal bei größeren Größen die lineare Reduktion dominiert. Die 12μs-Zahl scheint aus einer Verwechslung mit einem noch mythischeren Tier, dem Quantencomputer , zu stammen, das leicht große Zahlen berücksichtigen könnte, wenn eine Qualitätskontrolle mit 512 "Qubits" gebaut werden könnte. D-Wave hat kürzlich einen Quantencomputer mit 128 Qubits angekündigt, aber es stellte sich heraus, dass dies keine "echten" Qubits waren und für die Faktorisierung ungeeignet sind (sie können theoretisch immer noch einige effiziente Annäherungen bei Optimierungsproblemen durchführen, was großartig ist aber grundsätzlich nicht anwendbar auf Kryptographie, da kryptographische Algorithmen nicht annähernd zugänglich sind - sie sind so konzipiert, dass ein einzelnes falsches Bit das Ganze verschlüsselt). Die bisher beste "echte" Qualitätskontrolle scheint der Prototyp von IBM zu sein, der, soweit ich mich erinnere, 5 Qubits hat, wodurch festgestellt werden kann, dass 15 gleich 3 mal 5 ist.

Der aktuelle RSA-Faktorisierungsrekord bezieht sich auf eine 768-Bit-Ganzzahl , der im Dezember 2009 angekündigt wurde. Es dauerte vier Jahre und umfasste die klügsten Zahlentheoretiker, die derzeit auf der Erde leben, einschließlich Lenstra und Montgomery, die etwas Gott- haben. wie Status in diesen Kreisen. Ich habe kürzlich erfahren, dass die Auswahl der Parameter für eine 1024-Bit-Zahlenfaktorisierung begonnen hat (das ist der "kluge" Teil); Das Sieben ist technisch machbar (es ist teuer und erfordert jahrelange Rechenzeit in vielen Universitätsclustern), aber im Moment weiß niemand, wie der lineare Reduktionsteil für eine 1024-Bit-Ganzzahl ausgeführt wird. Erwarten Sie also keine baldige 1024-Bit-Unterbrechung.

Derzeit kann ein engagierter Amateur, der den veröffentlichten Code verwendet (z. B. Msieve ), eine 512-Bit-Faktorisierung erzielen, wenn er Zugriff auf leistungsstarke Computer hat (mehrere Dutzend große PCs und mindestens eine Uhr mit schnellem RAM) ) und ein paar Monate Freizeit; Im Grunde bedeutet "engagierter Amateur" "gelangweilter Informatikstudent an einer wohlhabenden Universität". Alles, was über 512 Bit hinausgeht, ist für einen Amateur unerreichbar.

Zusammenfassung: In Ihrem Code können Sie "praktisch unendlich" als Cracking-Zeit für alle Schlüssellängen zurückgeben. Ein typischer Benutzer wird einen 1024-Bit-RSA-Schlüssel nicht brechen, nicht jetzt und auch nicht in zehn Jahren. Es gibt ungefähr ein Dutzend Menschen auf der Erde, die mit jeder Glaubwürdigkeit behaupten können, dass es mit einer geringen Wahrscheinlichkeit, aber ungleich Null, denkbar ist, dass sie könnte in der Lage sein, a zu faktorisieren einzelne 1024-Bit-Ganzzahl zu einem nicht festgelegten Zeitpunkt vor dem Jahr 2020.

(Es ist jedoch äußerst einfach, eine Implementierung von RSA oder einer Anwendung, die RSA verwendet, so zu verpfuschen, dass die darin enthaltenen vertraulichen Daten wiederhergestellt werden können, ohne sich um den RSA-Schlüssel zu kümmern. Wenn Sie 1024-Bit-RSA-Schlüssel verwenden, Sie können sicher sein, dass Ihre Anwendung, wenn sie gehackt wird, nicht durch eine RSA-Schlüsselfaktorisierung erfolgt.)

90
Thomas Pornin

Kurze Antwort : Die einfachste Methode wäre die Verwendung des Primzahlsatz , aber beachten Sie, dass es sich um eine Annäherung handelt. Schätzen Sie, wie lange Sie brauchen würden, um jede dieser Primzahlen auszuprobieren. Zeit pro Primzahl * Die Anzahl der Primzahlen gibt die Gesamtzeit an. Dadurch erhalten Sie eine Schätzung für die Brute-Force-Suche.

Sie können auch die Laufzeitschätzung für das quadratisches Sieb oder das allgemeines Zahlenfeldsieb verwenden. Auf diese Weise erhalten Sie Schätzungen für Factoring-Algorithmen, die tatsächlich von Personen verwendet werden, die RSA-Zahlen brechen.

Langer Hintergrund :

Zeit der Zahlentheorie!

Schauen wir uns zunächst die Größe der Zahlen an, über die Sie sprechen. Bei 2 ^ 3 = 8, was 1000 in binär ist, können wir sehen, dass dies eine 4-Bit-Zahl ist, das Minimum, das möglich ist. 2 ^ 2 = 4 ist also eine 3-Bit-Zahl (100). Für ein gegebenes x ist der minimal mögliche Wert, um sicherzustellen, dass wir genug Bits haben, 2 ^ (x-1). 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328. Das ist die Größe der Zahl, die Sie mit hier zu tun haben, das heißt, die Größe von n werden berücksichtigt.

Die nächste große Frage ist dann, wie n aufgebaut ist. n=pq Wie Sie aus der Definition von RSA wissen, suchen Sie nach zwei Primzahlen als Faktoren für diese Zahl. Dann stellt sich die Frage, wie wir feststellen, dass eine Zahl eine Primzahl ist und ob wir sie zählen können.

Per Definition ist eine Zahl also nicht reduzierbar, wenn für eine beliebige Zahl x\gcd(p, x) = 1 mit Ausnahme von x=1. Das können wir jedoch verbessern. Sie sollten ziemlich schnell erkennen, dass es für jede Zahl entweder eine Primzahl ist oder nicht. Wenn es keine Primzahl ist, muss der gcd davon und mindestens eine Primzahl größer als 1 sein (andernfalls wäre es eine Primzahl). Wir schließen daraus, dass jede Nicht-Primzahl durch eine Menge von Primzahlen teilbar sein muss. Ein formaler mathematischer Beweis ist eigentlich kein so großer Sprung von hier.

Dies nennt man den Grundsatz der Arithemtik und vereinfacht die Sache leicht. Wenn wir also herausfinden, ob eine Zahl eine Primzahl ist, müssen wir nicht mehr jede Zahl ausprobieren, sondern nur die Zahlen, die wir bereits kennen, sind Primzahlen!

Dies ist eindeutig immer noch sehr langsam, also machen wir noch eine Beobachtung - da Faktoren paarweise auftreten, ist die niedrigere der beiden Zahlen höchstens die Quadratwurzel der Zahl. Wenn wir auf N (die Menge der natürlichen Zahlen) beschränkt sind, stellt dies eine Obergrenze für den größtmöglichen Wert dar, den wir überprüfen müssen. Für jede Zahl N müssen wir nun jede ganze Zahl von 2 bis sqrt (N) nach jeder Zahl durchsuchen, die wir in dieser Liste als Primzahl bestimmen. Wir können dann, wenn wir eine Primzahl finden, ableiten, ob sie N selbst berücksichtigt. Ich werde die Laufzeit nicht schätzen, weil ich zweifellos das Falsche sagen werde, aber es wird lange dauern.

Jetzt sehen Sie die Stärke von RSA. Wählen Sie eine sehr große Primzahl und Sie haben einen langen Weg vor sich. So wie es derzeit aussieht, müssen wir bei 2 beginnen, was eindeutig schrecklich ist.

Primalitätstest zielt darauf ab, dies mithilfe verschiedener Techniken zu verbessern. Die naive Methode ist die, die wir gerade besprochen haben. Ich denke, eine ausführliche Diskussion dieser Techniken ist wahrscheinlich besser für die Mathematik geeignet. Lassen Sie mich das zusammenfassen: Alle Laufzeiten sind Müll, und es wäre schrecklich, dies als Methode zum Zählen von Primzahlen zu verwenden.

Wir können also die Anzahl der Primzahlen nicht zuverlässig kleiner als eine Zahl zählen, ohne ewig zu dauern, da dies praktisch der ganzzahligen Faktorisierung entspricht. Was ist mit einer Funktion, die Primzahlen auf andere Weise zählt?

Geben Sie \pi(n) = \frac{n}{\log(n) - 1.08366} ein, einen Versuch des Primzahlsatz eine Annäherung an die Anzahl der Primzahlen. Es ist jedoch genau das; Das Ziel einer solchen Funktion ist es, die Anzahl der Primzahlen genau zu zählen, aber derzeit erhalten Sie lediglich eine Schätzung. Für Ihre Zwecke könnte dies als gut genug angesehen werden.

Es ist jedoch absolut immer noch eine Annäherung. Schauen Sie sich den Rest des Artikels an. Andere Schätzungen hängen unter anderem von der Riemann-Hypothese ab.

Ok, was ist mit ganzzahlige Faktorisierung ? Nun, die bisher zweitbeste Methode heißt Quadratisches Sieb und die beste heißt allgemeines Zahlenfeldsieb . Beide Methoden berühren einige ziemlich fortgeschrittene Mathematik; Angenommen, Sie meinen es ernst mit dem Faktorisieren von Primzahlen, würde ich mich darüber informieren. Sicherlich sollten Sie in der Lage sein, die Schätzungen für beide als Verbesserungen für die Verwendung des Primzahlsatzes zu verwenden, da Sie diese und keine Brute-Force-Suche verwenden möchten, wenn Sie große Primzahlen berücksichtigen möchten.

Aber ich möchte etwas über Quanten wissen?

OK Fair genug. Die Ganzzahlfaktorisierung auf einem Quantencomputer kann in lächerlich kurzer Zeit erfolgen, vorausgesetzt, wir können Shors Algorithmus implementieren. Ich sollte jedoch darauf hinweisen, dass dies einen Quantencomputer erfordert. Soweit mir bekannt ist, ist die Entwicklung von Quantencomputern der Größenordnung, die RSA knacken können, derzeit weit entfernt. Siehe Quantencomputer-Entwicklungen .

In jedem Fall wäre Shors Algorithmus exponentiell schneller. Auf der Seite finden Sie eine Schätzung für die Laufzeit, die Sie möglicherweise in Ihre Schätzungen aufnehmen möchten.

25
user2213

Eine andere Möglichkeit besteht darin, eine große Datenbank mit möglichen Schlüsseln zu erstellen und diese als Nachschlagetabelle zu verwenden. Anscheinend brauchen Sie nicht einmal ALLE Primzahlen, nur ein paar werden Sie durch einen großen Prozentsatz des Internetverkehrs bringen.

Quelle: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

0
Evgeny