Wie bestimmt die Fähigkeit, große Zahlen zu faktorisieren, die Sicherheit gängiger Verschlüsselungsalgorithmen?

Question

Wie hängt die Sicherheit des Verschlüsselungsalgorithmus von der Faktorisierung großer Zahlen ab?

Zum Beispiel habe ich in einigen Mathe-Programmierforen gelesen, dass man mit Hilfe des Quadratischen Siebs oder des allgemeinen Zahlenfeldsiebs eine 256-Bit-Zahl relativ einfach auf handelsüblicher Hardware faktorisieren kann.

Wie kann dies die Sicherheit von Algorithmen wie RSA, AES usw. beeinträchtigen? Kann man die Länge des Schlüssels ausreichend einteilen?

Gibt es jemanden, der sich mit Kryptographie und Verschlüsselungsalgorithmen auskennt, der ein wenig Licht darauf werfen könnte?

Answer 1

RSA, Der Kryptoalgorithmus, stützt sich auf Zahlentheorie, insbesondere die Multiplikation zweier großer Primzahlen und die Tatsache, dass dies schwierig zu bewerten ist, um zwischen öffentlichen und privaten Schlüsseln zu unterscheiden.

Hier ist eine Frage auf Yahoo Antworten, wo jemand einige Details gegeben hat: http://answers.yahoo.com/question/index?qid=20070125183948AALJ40l

es auf ein paar Fakten beruht:

• n=p.q leicht zu berechnen, aber schwer
• Fermats kleinen Satz zu umkehren : http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
• Verschiedene Ergebnisse der Zahlentheorie.

Es ist nicht schwierig, große Zahlen zu berücksichtigen, es handelt sich um zwei große Zahlen, deren einzige Faktoren selbst große Primzahlen sind, weil das Finden dieser Primzahlen schwierig ist.

Eine schnelle Suche durch meine Lesezeichen gibt mir das: the mathematical guts of rsa encryption wenn Sie daran interessiert sind, wie es funktioniert. Auch hier eine Erklärung - lies einfach meine num-Theorie-Noten noch einmal, um klar zu sein.

• n = p * q gibt Ihnen eine große Zahl gegeben p, q prime.
• Phi (n) = (p-1) (q-1). Dies ist eine Erweiterung von Fermat's kleinen Theorem Mehr darüber, warum wir das brauchen und warum es auf meinem Blog hier funktioniert: http://vennard.org.uk/weblog/2010/02/a-full-explanation-of-the-rsa-algorithm/
• Das bedeutet, wenn wir eine Zahl E coprime (keine gemeinsamen Primfaktoren) zu (p-1) wählen (q-1) können wir Es inverse mod phi (n) finden.

• Was wir tun, finden wir DE = 1 (p-1) (q-1) oder besser lösen wir mit dem größten gemeinsamen Teileralgorithmus, der erweiterten Version von euclid.

• Nun, wenn wir T^E (pq) nehmen, erhalten wir C. Wenn wir aber (T^E)^D (pq) nehmen, erhalten wir T wieder zurück.

AES ist nicht das gleiche - es ist keine Kryptographie mit öffentlichem Schlüssel. AES nimmt einen Schlüssel und verwendet diesen in beide Richtungen, Verschlüsselung und Entschlüsselung. Der Prozess ist im Grunde sehr schwer rückgängig zu machen, eher wie ein Hash, aber reversibel. Es beruht jedoch nicht darauf, große Zahlen in Primzahlen für seine Sicherheit einzumessen; es beruht vollständig auf der Stärke des Schlüssels und der Unfähigkeit, entweder den Schlüssel aus dem Algorithmus oder den Schlüssel, der bekannten Klartext und den Algorithmus gegeben ist, abzuleiten.

Wikipedia hat a good article on AES für hohe Ebene mit einem guten Link, der Ihnen zeigt, wie es funktioniert - siehe here und here. Ich mag besonders den letzteren Link.

Answer 2

AES ist viel anders, AES erstellt ein SPN, Substitution Permutation Network. Es erzeugt S-Boxen (Substitutionsboxen) basierend auf Polynomfunktionen, die zur Verschlüsselungszeit erzeugt werden. Es führt es durch 10-14 Runden der Byte-Ebene Substitution und Bit-Ebene Permutieren, die Bit-Länge des Schlüssels bestimmt die Anzahl der Runden und die Runden-Schlüssel.

RSA basiert auf Faktoren großer Primzahlen, die sehr rechenintensiv, aber relativ einfach zu verschlüsseln sind.

Answer 3

Wie hängt die Sicherheit eines Verschlüsselungsalgorithmus von der Faktorisierung großer Zahlen ab?

Die fehlende Phrase ist "public-key", wie in "Wie der öffentliche Schlüssel Sicherheit des Verschlüsselungsalgorithmus ist ..."

In der modernen Kryptographie gibt es zwei Hauptkategorien von Chiffren, symmetrisch (secret key) und öffentlicher Schlüssel (der ein öffentliches/privates Schlüsselpaar verwendet).

Innerhalb jeder Kategorie finden Sie die Schlüsselgrößen relativ nah. Für Public-Key-Systeme wie RSA und DH/DSA, die beide in der OpenPGP-E-Mail-Verschlüsselung verwendet werden, sind die gängigen Schlüsselgrößen heute (Anfang 2010) 1024 Bit und größer. Dies hat mit den mathematischen Anforderungen geeigneter Schlüssel zu tun, die zum Verschlüsseln und Entschlüsseln von Nachrichten verwendet werden. Für RSA, kurz gesagt, ist es viel einfacher, einen Faktor von zwei zufälligen großen Primzahlen zu erzeugen und Multiplikationen mit ihnen zu machen, verglichen mit dem Faktorisieren von sehr großen Zahlen, die keine kleinen Faktoren haben. Wie Sie entdeckt haben, ist das Factoring von sehr großen Zahlen das "Problem" oder der Ansatz, der zu Bruch RSA über rohe Kraft benötigt wird.

Diffie-Hellman/Digitaler Signaturalgorithmus (DH/DSA) basiert auf einem anderen mathematischen Problem, das diskrete Logarithmen berechnet.

Aufgrund der Eigenschaften der öffentlichen und privaten Schlüsselpaare ist der Suchraum auf Faktoren von großen Primzahlen beschränkt, was unglaublich spärlich wird, so dass es sinnvoller ist zu versuchen, Faktor zu sein jede sehr große Anzahl.

Während bei symmetrischen Chiffren wie AES, RC6, RC4, Twofish, DES und Triple-DES diese Algorithmen einen zufälligen Schlüssel einer bestimmten Bitlänge verwenden. Jede nicht-triviale (d. H. 0x000 ... 000 kann eine schlechte Schlüsselwahl sein) ist ein zufälliger Schlüssel geeignet. Wenn also bei diesen Systemen kein Angriff auf den Algorithmus selbst erfolgt, können Sie einfach Brute-Force durch den Schlüsselraum suchen (d. H. Alle 2^256 möglichen Schlüssel versuchen), um eine Nachricht ohne den geheimen Schlüssel zu entschlüsseln. Da jeder Schlüssel geeignet ist, beträgt die Dichte der Schlüssel 2^256.

Ich ignoriere Quantum Computing (theoretisch und praktisch), vor allem, weil a) kann ich keine solide Antwort geben, und b) es stellt einen großen Paradigmenwechsel, der viel angewandte Mathematik und Computerwissenschaften von Computer-Komplexität potenziell verwandelt auf seinem Kopf ist dieses Grundverständnis immer noch ein bewegliches Ziel. Oh, und die meisten meiner Feinde haben noch keinen Quantencomputer. :)

Ich hoffe, dass das den allgemeinen Unterschied zwischen den beiden Arten von Kryptosystemen, wie RSA und AES erklärt.

Sidebar: Cryptography ein reiches und komplexes Thema ist, wo die Grundlagen einfach genug sein können, zu verstehen und sogar eine naive („Lehrbuch“) Implementierung schreiben, die komplexen Feinheiten einer sicheren Implementierung macht es am besten für Programmierer Wer sind keine Kryptographieexperten, um Krypto-Systeme auf hohem Niveau zu verwenden, einschließlich der Verwendung bekannter Standardprotokolle, um Ihre Chancen zu verbessern, dass die Kryptographie eines Systems nicht der ausnutzbare Fehler in einem System ist.

Answer 4

RSA ist durch Factoring gebrochen. Tatsächlich sind RSA zwei Algorithmen, einer für (asymmetrische) Verschlüsselung und einer für digitale Signaturen; Beide benutzen das gleiche Primitiv. In RSA gibt es einen öffentlichen Wert (Modul, oft notiert n), der ein Produkt von zwei (oder mehr) verschiedenen Primfaktoren ist. Factoring n enthüllt den privaten Schlüssel. Faktorisieren wird schwieriger, wenn die Größe von n zunimmt. Der aktuelle Datensatz (Anfang dieses Jahres veröffentlicht) bezieht sich auf eine 768-Bit-Ganzzahl; Es dauerte vier Jahre, in denen viel Rechenarbeit und harte Arbeit von sehr schlauen Leuten geleistet wurden. Dieselben Leute geben offen zu, dass sie wenig Ahnung haben, wie sie den gleichen Stunt auf einer 1024-Bit-Integer versuchen könnten (es gibt einen Teil des bekanntesten Factorization-Algorithmus, der sehr viel schnellen RAM benötigt, und einen 1024-Bit Ganzzahl, die eine lächerlich große Maschine erfordern würde). Aktuelle Empfehlungen der Schlüssellänge für RSA sind 1024 Bits für kurzfristige, 2048 Bits für langfristige Sicherheit. Beachten Sie, dass der Rechenaufwand von RSA auch mit der Schlüsselgröße ansteigt, sodass wir keine wirklich großen Schlüssel ohne guten Grund verwenden wollen. Ein Basis-PC erzeugt etwa 1000 RSA-Signaturen pro Sekunde (und pro Kern) mit einem 1024-Bit-Schlüssel und acht Mal weniger mit einem 2048-Bit-Schlüssel. Das ist immer noch ziemlich gut.

Es gibt andere asymmetrische Verschlüsselungsalgorithmen und digitale Signaturalgorithmen. Etwas verwandt mit RSA ist der Rabin-Williams-Verschlüsselungsalgorithmus; Factoring bricht es auch. Dann gibt es Algorithmen, die auf dem diskreten Logarithmus basieren (in der multiplikativen Gruppe von Zahlen modulo eine große Primzahl): Diffie-Hellman (Schlüsselaustausch), DSA (Signatur), El Gamal (Verschlüsselung) ... für diese Algorithmen ist die Faktorisierung nicht direkt Bedrohung; aber sie beruhen auf den gleichen Teilen der Zahlentheorie, und der bekannteste Algorithmus für den diskreten Logarithmus ist dem bekanntesten Algorithmus für die Faktorisierung sehr ähnlich (und hat den gleichen Namen: GNFS - als Allgemeine Nummer Feldsieb). Es wird daher vermutet, dass ein Fortschritt in der Faktorisierung aus einem Fortschritt in der Zahlentheorie resultieren würde, der wahrscheinlich auch den diskreten Logarithmus beleuchten würde.

Die diskreten Logarithmusalgorithmen können auf andere Gruppen angewendet werden, wobei die bekanntesten elliptische Kurven sind. Elliptische Kurven werden nicht durch Faktorisierung beeinflusst. Wenn die Faktorisierung einfach wurde, was RSA abschürfte und indirekt DSA und Diffie-Hellman gefährdete, dann würden wir zu ECDH und ECDSA wechseln; Standards und Implementierungen existieren und werden bereitgestellt.

"Symmetrische Kryptographie", dh Hashfunktionen (MD5, SHA-256 ...), Authentifizierungscode (HMAC, CBC-MAC ...), symmetrische Verschlüsselung (AES, 3DES ...), Zufallsgenerierung (RC4 ...) und verwandte Aktivitäten sind von Faktorisierung völlig unabhängig. Für diese Algorithmen sind Schlüssel nur Bündel von Bits, ohne irgendeine spezielle Struktur; Es gibt nichts zu berücksichtigen.