Warum sind Primzahlen in der Kryptographie wichtig?

191

Eines fällt mir als Nicht-Kryptograf immer auf: Warum ist es so wichtig, Primzahlen zu verwenden? Was macht sie so besonders in der Kryptographie?

Hat jemand eine einfache kurze Erklärung? (Ich bin mir bewusst, dass es viele Grundierungen gibt und dass Angewandte Kryptographie die Bibel ist, aber wie gesagt: Ich möchte meinen eigenen kryptografischen Algorithmus nicht implementieren, und das, was ich gefunden habe, hat mein Gehirn explodieren lassen - keine 10 Seiten mathematischer Formeln Bitte :))

Danke für alle Antworten. Ich habe das akzeptiert, das mir das eigentliche Konzept am klarsten gemacht hat.

Michael Stum
quelle
Einige Beobachtungen: 1. Die folgenden Personen erwähnen, dass "die Primfaktorisierung großer Zahlen lange dauert". Tatsächlich gilt das Gleiche für jede Faktorisierung. Wichtig ist, dass jede ganze Zahl! = 0 eine eindeutige Faktorisierung als Produkt von Primzahlen aufweist (einschließlich 1, die eine Zerlegung der Länge 0 aufweist).
TT_
1
2. Bitte überprüfen Sie meine Erklärung, warum Primzahlen für Hash-Funktionen wichtig sind: stackoverflow.com/questions/1145217/… Sie bezieht sich auf die Eigenschaft von Polynomen mit Koeffizienten, die zu einem Feld gehören (was wahrscheinlich keine kurze Erklärung ist).
TT_
2
Zu einfache kurze Erklärung → Lösen : a * b = 91. Nun lösen Sie : 13 * 7 = x. Die zweite Gleichung ist viel schneller zu lösen (für einen Menschen oder einen Computer).
Dem Pilafian

Antworten:

203

Grundlegendste und allgemeinste Erklärung: Bei der Kryptographie dreht sich alles um die Zahlentheorie , und alle ganzzahligen Zahlen (außer 0 und 1) bestehen aus Primzahlen, sodass Sie sich in der Zahlentheorie häufig mit Primzahlen beschäftigen.

Insbesondere hängen einige wichtige kryptografische Algorithmen wie RSA entscheidend von der Tatsache ab, dass die Primfaktorisierung großer Zahlen lange dauert. Grundsätzlich haben Sie einen "öffentlichen Schlüssel", der aus einem Produkt von zwei großen Primzahlen besteht, die zum Verschlüsseln einer Nachricht verwendet werden, und einen "geheimen Schlüssel", der aus diesen beiden Primzahlen besteht, die zum Entschlüsseln der Nachricht verwendet werden. Sie können den öffentlichen Schlüssel öffentlich machen, und jeder kann ihn zum Verschlüsseln von Nachrichten an Sie verwenden, aber nur Sie kennen die Hauptfaktoren und können die Nachrichten entschlüsseln. Alle anderen müssten die Zahl berücksichtigen, was angesichts des aktuellen Standes der Zahlentheorie zu lange dauert, um praktikabel zu sein.

Michael Borgwardt
quelle
7
Wie wir das Zeitalter der Quanten eingeben Berechnung scheint es Notiz angebracht , dass die Faktorisierung von Primzahlen einen Quantencomputer in Polynomialzeit usiong Shor-Algorithmus erreicht werden en.wikipedia.org/wiki/Shor%27s_algorithm Es ist wahrscheinlich , dass Computer existieren bereits dem Entschlüsselung der Verschlüsselung mit öffentlichem Schlüssel wie RSA
stujo
16
@stujo: Sie überschätzen den Zustand des Quantencomputers massiv. Es ist in der Tat sicher, dass kein solcher Computer existiert. Die größte Zahl, die mit Shors Algorithmus und den neuesten Forschungsanstrengungen in der Quantenhardware berücksichtigt wurde, ist 21. Das sind nicht 21 Bit, sondern die Zahl 21, Primfaktoren 3 und 7.
Michael Borgwardt
1
Ich bin mir nicht sicher, welche Daten aktuell sind. Es ist schwierig, Informationen über die neuesten Arbeiten zu erhalten. Ich glaube, das war 2012, dieser Artikel stammt aus dem Jahr 2014 ( m.phys.org/news/2014-11-largest-factored- quantum-device.html ) Haben wir öffentliche Daten von 2016 gesehen? Nicht auszuschließen, was klassifiziert werden könnte. Obwohl es Shors Algorithmus nicht ausführen kann, ist D-Wave jetzt über 1000 qbits
stujo
1
@stujo: Dieselben Prinzipien gelten, wenn wir alle Quantum-CPUs verwenden, da Primzahlen weiter wachsen können. Es geht darum, größere, für Quanten-CPUs unpraktische zu finden. Das Problem besteht, wenn einige reguläre CPUS zum Erstellen von Schlüsseln verwenden und andere Quantum-CPUs verwenden brechen diese. Die Leistung von Quanten-CPUs besteht meines Wissens darin, dass sie Q-Bits verwenden. Jedes Q-Bit kann 3 Werte haben. Die neue Technologie ist also Basis 3 und nicht Basis 2. Eine 64-Q-Bit-CPU hätte 3 ^ 64 Kombinationen in einem Wort. Ich weiß nicht, wie sich das auf die Leistung auswirkt.
Juanmf
5
@juanmf: Dein Verständnis von Quantencomputing ist völlig falsch. Es hat absolut nichts mit 3 Werten zu tun, das wäre absolut uninteressant. Die Details sind sehr komplex, aber der Effekt ist, dass einige Quantenalgorithmen Probleme mit einer geringeren Big-O-Komplexität lösen können als "normale" Algorithmen auf Nicht-Quantenhardware.
Michael Borgwardt
137

Einfach? Jep.

Wenn Sie zwei große Primzahlen multiplizieren, erhalten Sie eine große Nicht-Primzahl mit nur zwei (großen) Primfaktoren.

Das Faktorisieren dieser Zahl ist eine nicht triviale Operation, und diese Tatsache ist die Quelle vieler kryptografischer Algorithmen. Siehe Einwegfunktionen für weitere Informationen.

Nachtrag: Nur ein bisschen mehr Erklärung. Das Produkt der beiden Primzahlen kann als öffentlicher Schlüssel verwendet werden, während die Primzahlen selbst als privater Schlüssel verwendet werden. Alle Vorgänge an Daten, die nur rückgängig gemacht werden können, wenn einer der beiden Faktoren bekannt ist, sind für die Entschlüsselung nicht trivial.

user54650
quelle
2
Erwähnenswert ist auch, dass neben dem Faktorisierungsproblem auch viele moderne Kryptografien (oder stattdessen) auf dem Problem des diskreten Logarithmus beruhen. Beide sind "Einweg" -Funktionen: Es ist einfach, bekannte Eingaben zu nehmen und eine Antwort zu berechnen, aber es ist schwierig, eine Antwort zu nehmen und diese Eingaben zu berechnen.
Nezroy
4
Die Verknüpfung dieser Erklärung mit dem Begriff "Einwegfunktion" wäre hilfreich: en.wikipedia.org/wiki/One-way_function
Chris Conway
Aber wenn der öffentliche Schlüssel zum Verschlüsseln verwendet werden kann, warum kann er nicht zum Gegenteil verwendet werden?
Jayarjo
45

Hier ist ein sehr einfaches und allgemeines Beispiel.

Der RSA-Verschlüsselungsalgorithmus, der üblicherweise auf Websites für sicheren Handel verwendet wird, basiert auf der Tatsache, dass es einfach ist, zwei (sehr große) Primzahlen zu nehmen und zu multiplizieren, während es äußerst schwierig ist, das Gegenteil zu tun - was bedeutet: Nehmen Sie a sehr große Zahl, gegeben, dass es nur zwei Primfaktoren hat, und finden Sie sie.

Yuval Adam
quelle
30
Nur zu Ihrer Information, die Zahl, die Sie durch Multiplizieren von zwei Primzahlen erhalten, wird als Semi-Primzahl bezeichnet.
Matthew Brubaker
15

Es sind nicht so sehr die Primzahlen selbst wichtig, sondern die Algorithmen, die mit Primzahlen arbeiten. Insbesondere das Finden der Faktoren einer Zahl (eine beliebige Zahl).

Wie Sie wissen, hat jede Zahl mindestens zwei Faktoren. Primzahlen haben die einzigartige Eigenschaft, dass sie genau zwei Faktoren haben: 1 und sich selbst.

Der Grund, warum Factoring so wichtig ist, ist, dass Mathematiker und Informatiker nicht wissen, wie man eine Zahl faktorisiert, ohne einfach jede mögliche Kombination auszuprobieren. Versuchen Sie also zuerst, durch 2, dann durch 3, dann durch 4 usw. zu teilen. Wenn Sie versuchen, eine Primzahl zu faktorisieren - insbesondere eine sehr große -, müssen Sie (im Wesentlichen) jede mögliche Zahl zwischen 2 und dieser großen Primzahl versuchen. Selbst auf den schnellsten Computern wird es Jahre (sogar Jahrhunderte) dauern, bis die in der Kryptographie verwendeten Primzahlen berücksichtigt sind.

Es ist die Tatsache, dass wir nicht wissen, wie wir eine große Anzahl effizient faktorisieren können, die kryptografischen Algorithmen ihre Stärke verleiht. Wenn eines Tages jemand herausfindet, wie es geht, werden alle derzeit verwendeten kryptografischen Algorithmen veraltet sein. Dies bleibt ein offenes Forschungsgebiet.

Barry Brown
quelle
10
Sie müssen die Primzahlen nur bis zur Quadratwurzel der Zahl testen, die Sie faktorisieren möchten.
Matthew Brubaker
3
Ich weiß. Es war ein Detail, das ich im Namen der Einfachheit "übersehen" habe.
Barry Brown
@MatthewBrubaker Würde es Ihnen etwas ausmachen zu erklären, warum dies so ist? Ich verstehe nicht wirklich.
Kartik Chugh
4
@KartikChugh ヅ sagen nist nicht Prime & n = a * b. Wenn a > sqrt(n), bmuss kleiner sein und umgekehrt, sonst a * b > nselbst, was unseren ursprünglichen Anspruch negieren würde. Um nach Prime zu suchen, prüfen wir nur bis sqrt.
Abhinav Gauniyal
13

Weil niemand einen schnellen Algorithmus kennt, um eine ganze Zahl in ihre Primfaktoren zu zerlegen. Es ist jedoch sehr einfach zu überprüfen, ob sich eine Reihe von Primfaktoren mit einer bestimmten Ganzzahl multipliziert.

nes1983
quelle
1
Interessanterweise ist es bereits in kurzer Zeit möglich herauszufinden, ob eine Zahl eine Primzahl ist.
nes1983
Hier fehlt ein "wenn die Primfaktoren groß sind".
Ben Voigt
@ Ben: Es fehlt nicht. Das Problem ist im Allgemeinen schwer. Beachten Sie, dass Probleme, die im Allgemeinen schwierig sind, einfache Fälle haben können. In diesem Fall sind kleine Primzahlen keineswegs die einzigen einfachen Fälle.
nes1983
2
Niemand weiß "in der Öffentlichkeit". Es ist möglich, dass die Geheimdienste der verschiedenen Weltregierungen Techniken haben, die sie nicht teilen. Sie stellen eine große Anzahl von Mathematikabsolventen ein. Zum Beispiel förderte die NSA heimlich die Erzeugung zufälliger Primzahlen durch "Dual EC_DRBG", von dem sie wussten, dass es schwach war, als Teil eines Standard-Krypto-Schemas für den öffentlichen Gebrauch. bits.blogs.nytimes.com/2013/09/10/…
Don Bright
don: Die schneebedeckten Dokumente scheinen zu zeigen, dass dies nicht der Fall ist. Sie zeichnen ein ziemlich schlüssiges Bild, dass die NSA (im Großen und Ganzen kann es Ecken geben) verschlüsselte Daten nicht durch spezielle mathematische Magie entschlüsseln kann, die nur sie kennen. Schneier diskutierte das Thema ausführlich.
nes1983
12

Es gibt einige gute Ressourcen, um Krypto hochzufahren. Hier ist eine:

Von dieser Seite:

In dem am häufigsten verwendeten Kryptografiesystem mit öffentlichem Schlüssel, das 1977 von Ron Rivest, Adi Shamir und Len Adleman erfunden wurde, werden sowohl der öffentliche als auch der private Schlüssel nach einer relativ einfachen mathematischen Formel aus einem Paar großer Primzahlen abgeleitet. Theoretisch könnte es möglich sein, den privaten Schlüssel vom öffentlichen Schlüssel abzuleiten, indem man die Formel rückwärts arbeitet. Aber nur das Produkt der großen Primzahlen ist öffentlich, und es ist so schwierig, Zahlen dieser Größe in Primzahlen zu zerlegen, dass selbst die leistungsstärksten Supercomputer der Welt einen gewöhnlichen öffentlichen Schlüssel nicht brechen können.

Bruce Schneiers Buch Applied Cryptography ist ein weiteres. Ich kann dieses Buch nur empfehlen. Es macht Spaß zu lesen.

Brian Clapper
quelle
9

Um etwas konkreter darüber zu sein, wie RSA Eigenschaften von Primzahlen verwendet, hängt der RSA-Algorithmus entscheidend vom Euler-Theorem ab , das besagt, dass für relativ Primzahlen "a" und "N" a ^ e zu 1 Modulo N kongruent ist , wobei e ist die Totientenfunktion des Eulers von N.

Woher kommen Primzahlen? Um die Euler-Totientenfunktion von N effizient zu berechnen, muss die Primfaktorisierung von N bekannt sein. Im Fall des RSA-Algorithmus, bei dem N = pq für einige Primzahlen "p" und "q" ist, ist e = (p - 1) (q - 1) = N - p - q + 1. Ohne Kenntnis von p und q ist die Berechnung von e jedoch sehr schwierig.

Noch abstrakter verwenden viele krypotgrafische Protokolle verschiedene Falltürfunktionen, Funktionen , die einfach zu berechnen, aber schwer zu invertieren sind. Die Zahlentheorie ist eine reichhaltige Quelle für solche Falltürfunktionen (wie die Multiplikation großer Primzahlen), und Primzahlen sind für die Zahlentheorie von zentraler Bedeutung.

Sam Hasler
quelle
7

Ich würde das Buch A Mathematical Journey In Code vorschlagen . Das Buch hat ein schönes bodenständiges Gefühl, was überraschend ist, da es sich um Kryptographie handelt. Das Buch fasst Sarah Flanneries Reise vom Lernen von Rätseln als Kind zur Entwicklung des Cayley-Purser (CP) -Algorithmus im Alter von 16 Jahren zusammen. Es bietet eine erstaunlich detaillierte Erklärung der Einwegfunktionen, der Zahlentheorie und der Primzahlen und ihrer Beziehung zu ihnen Kryptographie.

Was dieses Buch noch spezifischer für Ihre Frage macht, ist, dass Sarah versucht hat, einen neuen Algorithmus für öffentliche Schlüssel mithilfe von Matrizen zu implementieren. Es war viel schneller als die Verwendung von Primzahlen, aber es wurde eine Lücke gefunden, die es ausnutzen konnte. Es stellte sich heraus, dass ihr Algorithmus besser als privater Verschlüsselungsmechanismus verwendet wurde. Das Buch ist ein großartiger Beweis für die Verwendung von Primzahlen zur Verschlüsselung, da es den Test der Zeit und die Herausforderungen sehr kluger Menschen bestanden hat.

Jason Rowe
quelle
6

Eine weitere Ressource für Sie. Sicherheit jetzt! In Episode 30 (~ 30 Minuten Podcast, Link zum Transkript) wird über Kryptografieprobleme gesprochen und erklärt, warum Primzahlen wichtig sind.

Bill die Eidechse
quelle
6

Ich bin kein Mathematiker oder Kryptiker, daher hier eine äußere Beobachtung in Laienbegriffen (keine ausgefallenen Gleichungen, sorry).

Dieses ganze Thema mit Erklärungen über gefüllt ist HOW Primzahlen in der Kryptographie verwendet wird, ist es schwer , jemand in diesem Thread auf einfache Art und Weise zu erklären , findet WARUM Primzahlen verwendet werden ... wahrscheinlich , weil jeder , dass das Wissen für selbstverständlich.

Nur wenn man das Problem von außen betrachtet, kann eine Reaktion wie: Wenn sie jedoch die Summen von zwei Primzahlen verwenden, warum nicht eine Liste aller möglichen Summen erstellen, die zwei Primzahlen erzeugen können?

Auf dieser Site gibt es eine Liste von 455.042.511 Primzahlen, wobei die höchsten Primzahlen 9.987.500.000 ( 10 Stellen) sind.

Die größte bekannte Primzahl (Stand Februar 2015) ist 2 hoch 257.885.161 - 1, was 17.425.170 Stellen entspricht.

Dies bedeutet, dass es keinen Sinn macht, eine Liste aller bekannten Primzahlen und noch weniger aller möglichen Summen zu führen. Es ist einfacher, eine Zahl zu nehmen und zu überprüfen, ob es sich um eine Primzahl handelt.

Das Berechnen großer Primzahlen an sich ist eine monumentale Aufgabe. Die umgekehrte Berechnung von zwei Primzahlen, die sowohl von Kryptographen als auch von Mathematikern miteinander multipliziert wurden, ist heute schwer genug .

Calmo
quelle
3
Nur Ihr letzter Absatz ist wirklich gültig. Das Argument der Summen kann auch für jede zusammengesetzte Zahl gesagt werden (es gibt einen großen Bereich [technisch unendlich groß], die Speicherung aller Summen ist unmöglich / dumm). Auch die Summe der Primzahlen ist in der Kryptographie nicht so relevant, wichtiger (normalerweise, wie im Fall von RSA) ist ihr Produkt. Mit umgekehrter Berechnung meinen Sie wahrscheinlich auch Factoring . Das wird wahrscheinlich helfen, was du dort meinst.
Initramfs
4

Kryptografische Algorithmen beruhen im Allgemeinen für ihre Sicherheit auf einem "schwierigen Problem". Die meisten modernen Algorithmen scheinen das Faktorisieren sehr großer Zahlen als schwieriges Problem zu verwenden. Wenn Sie zwei große Zahlen miteinander multiplizieren, ist die Berechnung ihrer Faktoren "schwierig" (dh zeitaufwändig). Wenn diese beiden Zahlen Primzahlen sind, gibt es nur eine Antwort, was es noch schwieriger macht und garantiert, dass wenn Sie die Antwort finden, es die richtige ist, nicht irgendeine andere Antwort, die zufällig das gleiche Ergebnis liefert.

gkrogers
quelle
4

Ich denke, was in der Kryptographie wichtig ist, sind nicht die Primzahlen selbst, aber es ist die Schwierigkeit des Problems der Primfaktorisierung

Angenommen, Sie haben eine sehr sehr große ganze Zahl, von der bekannt ist, dass sie aus zwei Primzahlen m und n besteht. Es ist nicht einfach, m und n zu finden. Ein Algorithmus wie RSA hängt von dieser Tatsache ab.

Übrigens gibt es ein veröffentlichtes Papier über Algorithmen, die dieses Problem der Primfaktorisierung in akzeptabler Zeit unter Verwendung eines Quantencomputers "lösen" können. Neuere Algorithmen in der Kryptographie stützen sich möglicherweise nicht mehr auf diese "Schwierigkeit" der Primfaktorisierung, wenn der Quantencomputer in die Stadt kommt :)

Gant
quelle
3

Weil Faktorisierungsalgorithmen mit jedem gefundenen Faktor erheblich schneller werden. Wenn Sie beide privaten Schlüssel als Primzahl festlegen, wird sichergestellt, dass der erste gefundene Faktor auch der letzte ist. Im Idealfall sind auch beide privaten Schlüssel nahezu gleichwertig, da nur die Stärke des schwächeren Schlüssels von Bedeutung ist.

Michael
quelle
Das sieht für mich etwas überflüssig aus. Ein Teil aus dem schwächeren Schlüsselteil, der zur Top-Antwort kommentiert werden könnte :)
Ulysse BN
-1

Primzahlen werden hauptsächlich in der Kryptographie verwendet, da sie viel Zeit in Anspruch nehmen, um festzustellen, ob eine bestimmte Zahl eine Primzahl ist oder nicht. Für den Hacker wird ein Algorithmus, der viel Zeit benötigt, um den Code zu brechen, für ihn unbrauchbar

Chengappa BS
quelle
7
Herauszufinden, ob eine Zahl eine Primzahl ist, ist billig und wir brauchen sie, um billig zu sein. Wie sonst würden wir wissen, dass wir Primzahlen als unsere Primfaktoren in RSA oder Primzahlen als Modul in Finite-Feld-Krypto gewählt haben? Was teuer ist, ist die Berücksichtigung einer großen zusammengesetzten Zahl in ihren großen Primfaktoren.
CodesInChaos