Undolog.com

Zunächst einmal, wie im Beitrag erwähnt Verschlüsselung System RSA ist ein Public-Key-Verschlüsselung und nutzt die Eigenschaften von Primzahlen. Darüber hinaus ist das arithmetische Mittel verwendet (in den Berechnungen) nicht das gewöhnliche, sondern die sogenannte endliche oder artirmetica modular. Lassen Sie rechts ab dieser Schritt für Schritt bei der Umsetzung der RSA-Verschlüsselung vor.

Das arithmetische Mittel über, wie der Name schon sagt, ist Reihen von Zahlen endlich. Ein anschauliches Beispiel dafür, dass damit alles klar wird, ist der Computer zu beobachten. Nehmen Sie eine klassische Uhr mit den Händen, dass wir alle gewohnt sind. Es ist ein endliches System wie die Stunden auf dem Zifferblatt 12 dargestellt sind. The Lancet, in der Tat wird jeder Runde wieder - früher oder später - die gleiche Position. So kommt es, dass 3 +12 = 3 in unserem Computer zu beobachten. Genauer gesagt, nehmen Sie die arithmetischen Operationen der Addition und Multiplikation Ort über die gleiche Weise dell'aritmentica gewöhnlichen, außer, dass das Endergebnis Sie für das Modul (oft bezeichnet mod und in allen Programmiersprachen , C, Javascript oder PHP ist das Symbol%). Im Fall von unserer 12-Stunden-Takt, in der Tat ist die Addition nur 3 +12 = 15 mod 12, welche in 3 führen wird - optisch wie wir es gewohnt sind.
In der Praxis - in Bezug auf die Uhr - wir tun nur das, obwohl nicht bewusst. Der Betrieb des Moduls 12, zu verstehen, zu entsprechen, eine Reihe von 12 teilen und nehmen den Rest der Division:

ZB 15 mod 12 = 15/12 = (Rest 15-12) = 3
ZB 24 mod 12 = 24/12 = (Rest 0) = 0
ZB 26 mod 12 = 26/12 = (Rest 14-12) = 2

Die Anzahl der Stunden auf qudrante kann eine beliebige Zahl, 12, 24, 5, 128, werden ...
Allerdings wurde festgestellt, dass die Wahl eine Primzahl, da die Anzahl der Stunden, wir eine leistungsstarke Funktion hatte. Vor allem, wenn man eine Primzahl wählen wir nie eine Null-Ergebnis. Darüber hinaus eine beliebige Anzahl von einem Quadranten durch eine große Primzahl als erste Zahl gewählt gebildet gibt immer die Anzahl der Stunden angegeben. Wenn wir zum Beispiel eine Uhr nehmen mit 5 Stunden auf dem Zifferblatt und wir bringen wir zum Beispiel 2 ⁵ 2 wieder die Startnummer:

2 ⁵ = 32 mod 5 = 2

Welche übersetzt in:

x ^p = x (mod p)

Pierre de Fermat , der Mathematiker, der Kenntnis von diesem Verhalten wurde, bemerkte er, dass der Zeiger auf ein sich wiederholendes Muster zu ziehen schien. In der Praxis, in unserem Fall, nach fünf Schritten den Zeiger wieder in die Ausgangsposition.

Mit einer solchen Uhr zu 13 Stunden (bis zu 3 ^{13 versuchen)} erhalten wir:

3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3

Im Gegensatz zu unserem ersten Hand wird nicht auf alle möglichen Zahlen zu stoppen, aber der Trend scheint zu repetitiv und, in diesem Fall, wird die Hand zurück zu Schritt 3 nach 3 hat selbst 13 Mal multipliziert worden!

In 1736, Leonhard Euler konnte, um diese Funktion zu erweitern, sowie eine Erklärung zu geben. Er zeigte, dass bei einer vollen Stunde auf dem Zifferblatt mit N, wobei N = p * q das Produkt zweier Primzahlen p und q, beginnen die Leistung, um sich nach wiederholen würde (p -1) * (q -1) +1 Schritte.

Diese Funktion ist die Basis der RSA-Verschlüsselung. Es war klar, dass diese zyklischen Muster könnte - in der Tat - zu verschwinden und dann magisch bringen Informationen ans Licht. Wir sehen, dass N das Produkt zweier Primzahlen p und q ist, wird dieser Kunstgriff der Lage sein, zu veröffentlichen und zu pflegen N p und q geheim.

In der Praxis wird daher, woran Sie sich erinnern wird, um eine Karte Trick zu machen. Stellen wir uns einen Haufen aus einer großen Anzahl von Karten, so groß, dass wir müssten mindestens hundert Ziffern zu schreiben hat. Der Code wollen wir verschlüsseln, ist eine dieser Karten, nachdem er an der Spitze des Decks ist es gemischt, um zu verlieren - scheinbar - die Position unseres Papiers (die Botschaft). Mit der Uhr Arithmetik, in der Praxis ist es sehr einfach, um loszuwerden, das Papier, aber es ist nicht so einfach wieder zu erscheinen, wenn Sie die genaue Anzahl der Züge auf dem Deck in einer Weise wieder herzustellen Papier hergestellt werden wissen, oben drauf.
Wir haben dann vollständiges Beispiel, so können Sie sehen, alle Formeln benötigt, um diese Art von Magie zu erschaffen.
In unserem Beispiel verwenden wir kleine Zahlen, nur um den Mechanismus zu verstehen und sich vorstellen, dass unsere Kreditkartennummer an eine Website senden

SCHRITT 1

Die Website vermittelt - unsere Browsern - die erste öffentliche Schlüssel, wie N = p * q berechnet (die Website wird eifersüchtig, wenn die Zahlen p und q, nur das Produkt der Öffentlichkeit zugänglich gemacht), stellt es die Anzahl der Stunden verwendet On Our Watch. Bedenken Sie, dass in Wirklichkeit die Zahl p und q mindestens 60 Ziffern! Wir verwenden Zahlen mehr Menschen:

N = p * q = 5 * 11 = 55

Fünfundfünfzig ist unser öffentlicher Schlüssel, dank der Sicherheit des Codes kann die Website leicht und gleichmäßig auf alle seine Kunden verteilt werden. Obwohl es öffentlich gemacht wurde die Zahl N, die Primfaktoren p und q, dass komponieren geheim sind, werden sie dekodiert die Zahl unserer Kreditkarte!

SCHRITT 2

An diesem Punkt, und Sie erhalten eine zweite Nummer, angerufene Nummer Codierung. Diese Zahl ist die gleiche für alle öffentlichen und auch, wie N. Durch unsere Browser können wir kodieren die Zahl unserer Kreditkarte C, in der Praxis shuffle dem Deck, und stellt die Anzahl der shuffle das Deck:

C ^E (Form N)

Und die Zahl ist in der Regel klein und wird von der Formel, die wir trafen uns, wenn wir auf eine Uhr mit einer Anzahl von Stunden, bestehend aus einer Primzahl, gab es eine Sequenz, die später wiederholt wurde (p -1) sah berechnet * ( q -1) +1 Schritten (für Details hier klicken )!
Zuerst berechnen Sie eine Zahl b:

b = (p -1) * (q -1) = (5-1) * (11-1) = (4) * (10) = 40

Und sollte die Zahl eine Primzahl, die keine Trennwände mit b, ggT (E, b) = 1 sein
Zur Vereinfachung wollen wir versucht - esistone verschiedene Techniken für diese:

Wenn E = 2, dann ggT (2, 40) = 2 ist nicht gut
Wenn E = 3, dann gcd (3, 40) = 1 ist gut

An dieser Stelle können wir verschlüsseln unsere Anzahl von Kreditkarten C. Wenn C ist 32 und hat zum Beispiel:

Mod N ^und C = 32 ³ mod 55 = 43 C = _cf

Cool, ist 43 unsere Kreditkartennummer verschlüsselt! Wir schicken Sie es!

SCHRITT 3

Die Website erhält unsere Kreditkarten-Nummer C _cf verschlüsselt, oder 43. An diesem Punkt setzt die folgende Eigenschaft :

_Vgl. C = C ^d mod N

Die Zahl d ist der Kehrwert des arithmetischen und endliche Anzahl von Ordnung b, unsere Uhr Arithmetik. Dies ist der Einfachheit halber so, dass berechnete d * e mod b = 1
Going to verführen Sie feststellen, dass:

Für d = 1 zu 1 sein * 3 mod 40 = 3 mod 40 = 3 - nicht gut
Für d = 2 und 2 * 3 = 6 MOD 40 mod 40 = 6 - keine gute
Für d = 3 und 3 * 3 = 9 MOD 40 mod 40 = 9 - nicht gut
....
Für d = 27 ist ein 27 * 3 = 81 MOD 40 mod 40 = 1 - gefunden!

Nun ist die Website in der Lage, das Spiel mischen, um so wieder auf unserer Kreditkarten-Nummer:

_Vgl. C = C ^d mod N = 43 ²⁷ mod 55 = 32

In Zusammenfassung

Wenn Sie mit zufällig gewählten Zahlen experimentieren möchten klicken Sie hier .
Außerdem ist, wie erläutert auf dem gleichen Gelände des RSA:

Angenommen, Alice möchte eine Nachricht m an Bob senden. Alice den Geheimtext c durch potenzieren Erstellt c = ^m e mod n, und wo und n Bobs öffentlichen Schlüssel. Sie schickt c an Bob. So entschlüsseln, potenziert Bob auch: m = c ^d mod n, und d, und die Beziehung zwischen Gewährleistet das richtig Bob erholt m. Da nur Bob weiß, d, kann nur Bob entschlüsselt diese Nachricht.

Hacker und Security

Unsere Kreditkartennummer, verschlüsselt, reist sie auf das Netzwerk und alle Hacker könnte es zu lesen. Was ist ein Hacker zu unserem Code zu knacken brauchen, ist eine Zahl, die mit sich selbst multipliziert und manchmal der Computer Stunden N Uhr, gibt die Anzahl der verschlüsselten Kreditkartendaten _(vgl. C = C ^e mod n). Zusätzlich zu einem normalen Computer das Ergebnis der Multiplikation einer Reihe von zunehmend autmenta, die nicht auf einem Computer geschieht, um zu sehen, wo der Ausgangspunkt der Sicht verloren geht sehr schnell, da die Größe des Ergebnisses nichts mit der Position zu tun haben von wo aus Sie gestartet. Darüber hinaus in realen Fällen, die Zahl N mehr als hundert Figuren hat, gibt es mehr Stunden auf dem Zifferblatt des Computers, um Atome im Universum beobachten. Es ist nur durch die Anzahl der Entschlüsselung der Website kann die Anzahl der Kreditkarte holen, aber diese Zahl d ist der erzielbare nur, wenn Sie p und q. wissen Trotz der großen Zahl N = p * q ist öffentlich, der Schwierigkeit der Factoring-N macht es praktisch unmöglich, den Code zu knacken.

Doch niemand hat jemals bewiesen, dass es ein mathematischer Algorithmus, um sehr große Zahlen werden schnell mithilfe eines Computers gebrochen werden kann. Wenn dies geschehen wäre die Wirtschaft der entwickelten Welt in kürzester Zeit ruinieren.

Bibliographie

• Colin Bruce, Schrödingers Rabbits - qunatistica Physik und parallele Universen , Raffaello Cortina Editore
• Marcus Du Sautoy, Die Musik der Primzahlen. Die Riemann-Hypothese, das größte Geheimnis der Mathematik , BUR
• Simon Singh, Fermats letzter Satz. Das Abenteuer der ein Genie, ein mathematisches Problem und der Mann, der gelöst hat , Rizzoli
• Liceo Foscarini - Venedig http://www.liceofoscarini.it/studenti/crittografia/
• RSA: http://www.rsasecurity.com/