Warum sind Primzahlen in der Kryptographie wichtig?

Question

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

Hat jemand ein einfach kurze Erklärung?(Mir ist bewusst, dass es viele Grundlagen gibt und dass Angewandte Kryptographie die Bibel ist, aber wie gesagt:Ich habe nicht vor, meinen eigenen kryptografischen Algorithmus zu implementieren, und das Zeug, das ich gefunden habe, hat mein Gehirn explodieren lassen – bitte keine 10 Seiten mit mathematischen Formeln :))

Danke für alle Antworten.Ich habe diejenige akzeptiert, die mir das eigentliche Konzept am klarsten verdeutlichte.

Answer 1

Die meisten grundlegend und allgemeine Erklärung: Kryptographie ist alles über Zahlentheorie und alle Integer-Zahlen ( außer 0 und 1) sind aus Primzahlen gemacht, so dass Sie mit Primzahlen viel in der zahlen~~POS=TRUNC beschäftigen.

Insbesondere einige wichtige Verschlüsselungsalgorithmen wie RSA hängen entscheidend von der Tatsache, dass Primfaktorzerlegung der großen Zahlen dauert eine lange Zeit. Grundsätzlich haben Sie einen „öffentlichen Schlüssel“, bestehend aus einem Produkt aus zwei großen Primzahlen verwendet, um eine Nachricht zu verschlüsseln, und einen „geheimen Schlüssel“, bestehend aus den beiden Primzahlen verwendet, um die Nachricht zu entschlüsseln. Sie können den öffentlichen Schlüssel öffentlich machen, und jeder kann es verwenden, um Nachrichten zu Sie verschlüsseln, sondern nur wissen, dass Sie die Primfaktoren und die Nachrichten entschlüsseln können. Jeder andere hätte die Zahl Faktor, der zu lange dauert, praktisch zu sein, den aktuellen Stand der Technik der Zahlentheorie gegeben.

Answer 2

Einfach? Yup.

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

die Zahl Factoring ist eine nicht-triviale Operation, und diese Tatsache ist die Quelle von vielen kryptographischen Algorithmen. Siehe Einwegfunktionen für weitere Informationen .

Nachtrag: Nur ein bisschen mehr Erklärung. Das Produkt der beiden Primzahlen kann als ein öffentlicher Schlüssel, während die Primzahlen sich als privater Schlüssel verwendet werden. Alle Angaben erfolgen Operation, die nur durch die Kenntnis einer der beiden Faktoren rückgängig gemacht werden wird nicht trivial zu entschlüsseln.

Answer 3

Hier ist ein sehr einfaches und allgemeines Beispiel.

Die RSA-Verschlüsselungsalgorithmus , die üblicherweise in sicheren Commerce-Websites verwendet wird, ist basierend auf der Tatsache, dass es einfach ist, zwei (sehr groß) Primzahlen zu nehmen und multiplizieren sie, während es extrem schwierig ist, das Gegenteil zu tun - das heißt: nehmen sie eine sehr große Zahl gegeben, das es nur zwei Primfaktoren hat, und findet sie.

Answer 4

Es ist nicht so sehr die Primzahlen selbst, die wichtig sind, aber die Algorithmen, die mit Primzahlen arbeiten. Insbesondere finden die Faktoren einer Zahl (eine beliebige Zahl).

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

Der Grund Factoring ist so wichtig ist Mathematiker und Informatiker nicht wissen, wie eine Reihe Faktor ohne einfach jede mögliche Kombination zu versuchen. Das heißt, zunächst versuchen, durch 2 dividiert, dann mit 3, dann mit 4, und so weiter. Wenn Sie versuchen, eine Primzahl Faktor - vor allem ein sehr groß - ich wird versuchen müssen (im Wesentlichen) jede mögliche Zahl zwischen 2 und dieser großen Primzahl. Auch auf dem schnellsten Computer, es wird Jahre dauern (sogar Jahrhunderte) die Arten von Primzahlen in der Kryptographie verwendet zu berücksichtigen.

Es ist die Tatsache, dass wir nicht wissen, wie effizient eine große Anzahl Faktor, die Verschlüsselungsalgorithmen ihre Stärke verleiht. Wenn eines Tages jemand herausfindet, wie es geht, alle Verschlüsselungsalgorithmen wir derzeit wird verwenden obsolet geworden. Dies bleibt ein offener Bereich der Forschung.

Answer 5

Weil niemand einen schnellen Algorithmus kennt eine ganze Zahl in ihre Primfaktoren zerlegt. Dennoch ist es sehr einfach, wenn ein Satz von Primfaktoren zu überprüfen, um eine bestimmten ganzen Zahl multiplizieren.

Answer 6

Es gibt einige gute Ressourcen für die Krypto-Hochlauf. Ist hier ein:

• http://research.microsoft.com/en-us/ Gruppen / crypto / firstcrypto.aspx

Von dieser Seite:

  

In dem am häufigsten verwendeten Public-Key   Kryptographiesystem, erfunden von Ron   Rivest, Adi Shamir und Len Adleman in   1977, sowohl die öffentlichen und dem privaten   Schlüssel werden von einem Paar großer abgeleiteten   Primzahlen gemäß a   relativ einfache mathematische   Formel. Theoretisch könnte es sein,   möglich, den privaten Schlüssel abzuleiten   aus dem öffentlichen Schlüssel von der Arbeits   Formel rückwärts. Aber nur die   Produkt der großen Primzahlen   Öffentlichkeit und Factoring von Zahlen,   Größe in Primzahlen so hart ist, dass selbst   die leistungsfähigsten Supercomputer   die Welt kann nicht einen gewöhnlichen brechen   Öffentliche Schlüssel.

Bruce Schneier Buch Applied Cryptography ist eine andere. Ich empfehle das Buch hoch; es ist viel Spaß beim Lesen.

Answer 7

Um ein wenig konkreter zu sein, wie RSA verwendet Eigenschaften von Primzahlen, hängt der RSA-Algorithmus kritisch auf Eulersche Theorem , die für relative Primzahlen "a" und "N", a ^ e kongruent zu 1 Modulo N, wobei E die Eulersche Phi-Funktion ist von N.

Wo Primzahlen kommen in das? Zur Berechnung effizient Im Fall des RSA-Algorithmus der Eulersche Phi-Funktion von N die Primfaktorzerlegung von N. erfordert zu wissen, wo N = pq für einige Primzahlen „p“ und „q“, dann e = (p - 1) (q - 1) = N - p -. q + 1. Aber ohne zu wissen, p und q, Berechnung von e ist sehr schwierig,

Weitere abstrakt, viele crypotgraphic Protokolle verwenden verschiedene Falltür Funktionen , Funktionen, die einfach zu berechnen sind, aber schwer zu invertieren. Zahlentheorie ist eine reiche Quelle für solche Falltür Funktionen (wie Multiplikation von großen Primzahlen) und Primzahlen sind absolut zentrale Bedeutung für die Zahlentheorie.

Answer 8

Ich würde das Buch empfehlen Eine mathematische Reise im Code.Das Buch wirkt angenehm bodenständig, was überraschend ist, da es sich um Kryptographie handelt.Das Buch fasst Sarah Flannerys Reise vom Rätsellernen als Kind bis zur Entwicklung des Cayley-Purser (CP)-Algorithmus im Alter von 16 Jahren zusammen.Es gibt eine erstaunlich detaillierte Erklärung von Einwegfunktionen, Zahlentheorie und Primzahlen und wie sie mit der Kryptographie zusammenhängen.

Was dieses Buch für Ihre Frage noch spezifischer macht, ist, dass Sarah versucht hat, mithilfe von Matrizen einen neuen Public-Key-Algorithmus 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 eingesetzt werden konnte.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.

Answer 9

Eine weitere Ressource für Sie. Security Now! Folge 30 (~ 30 Minuten Podcast Link zum Transkript) spricht über Kryptographie Fragen und erklärt, warum Primzahlen wichtig sind.

Answer 10

Ich bin kein Mathematiker oder cryptician, also hier eine Außen Beobachtung in juristischer Hinsicht (keine Phantasie Gleichungen, sorry).

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

Nur auf das Problem von außen sucht, kann eine Reaktion wie erzeugen; aber wenn sie die Summen zweier Primzahlen verwenden, warum nicht eine Liste aller möglichen Summen erstellen alle zwei Primzahlen erzeugen kann?

Auf dieser Website gibt es eine Liste von 455042511 Primzahlen, wo die höchste Primzahlen 9987500000 ( 10 Stellen).
Der größte bekannte Primzahl (Stand: Februar 2015) ist 2 auf die Kraft der 257.885.161 - 1 , die ist 17425170 Ziffern
Das bedeutet, dass es keinen Sinn. eine Liste aller bekannten Primzahlen zu halten und viel weniger alle möglichen Summen. Es ist einfacher, eine Nummer zu nehmen und prüfen, ob es eine Primzahl ist.

große Primzahlen in sich selbst zu berechnen ist eine gewaltige Aufgabe, so Reverse Berechnung zwei Primzahlen, die beide Kryptologen und Mathematiker miteinander multipliziert wurde sagen würde, ist hart genug .. . heute.

Answer 11

Krypto-Algorithmen beruhen im Allgemeinen für ihre Sicherheit ein „schwieriges Problem“ zu müssen. Die meisten modernen Algorithmen scheinen die Factoring mit sehr großen Zahlen als schwieriges Problem zu verwenden - wenn Sie zwei große Zahlen zusammen multiplizieren, deren Faktoren Berechnung ist „schwierig“ (das heißt zeitaufwendig). Wenn diese beiden Zahlen Primzahlen sind, dann gibt es nur eine Antwort, die es noch schwieriger macht, und garantiert auch, dass, wenn Sie die Antwort finden, es ist die richtige, nicht eine andere Antwort, die gerade geschieht, um das gleiche Ergebnis zu erhalten.

Answer 12

Ich denke, was in der Kryptographie wichtig sind, selbst nicht-Primzahlen, aber es ist die Schwierigkeiten von Primfaktorzerlegung Problem

Sie sehr, sehr große ganze Zahl Angenommen haben, die bekannt ist Produkt zweier Primzahlen m und n zu sein, ist es nicht leicht zu finden, was m und n. Algorithmus wie RSA ist abhängig von dieser Tatsache.

Übrigens gibt es eine veröffentlichten Papier auf Algorithmus, der kann „lösen "diese Primfaktorzerlegung Problem in akzeptabler Zeit mit Quantencomputern. So neuere Algorithmen in der Kryptographie vertrauen können nicht in dieser „Schwierigkeit“ der Primfaktorzerlegung mehr als Quantencomputer in der Stadt kommt:)

Answer 13

Da Faktorisierung Algorithmen erheblich beschleunigt mit jedem Faktor gefunden. sowohl private Schlüssel prime machen sorgt für den ersten Faktor wird auch die letzte sein gefunden. Idealerweise werden beide private Schlüssel auch nur die Kraft der schwächeren Schlüsselfragen seit fast den gleichen Wert sein.

Answer 14

Primzahlen sind vor allem in der Kryptographie verwendet, da es viel Zeit verbraucht bei der Bestimmung, ob eine bestimmte Zahl Primzahl ist oder nicht. Für die Hacker, wenn jeder Algorithmus viel Zeit in Anspruch nimmt, den Code zu brechen es für sie nutzlos wird