[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Dies ist CS50.] [CS50.TV]
Werfen wir einen Blick auf RSA, ein weit verbreiteter Algorithmus zur Verschlüsselung von Daten.
Verschlüsselungsalgorithmen wie Caesar und Vigenère Chiffren sind nicht sehr sicher.
Mit der Caesar-Chiffre, ein Angreifer braucht nur zu 25 verschiedene Tasten ausprobieren
zu der Nachricht Klartext zu bekommen.
Während die Vigenère Chiffre ist sicherer als die Caesar-Chiffre
aufgrund des größeren Suchraum für Schlüssel, sobald ein Angreifer
kennt die Länge des Schlüssels in einem Vigenère Chiffre,
Es kann über eine Analyse von Mustern in dem verschlüsselten Text bestimmt werden,
Die Vigenère Chiffre ist nicht so, dass viel sicherer als die Caesar-Chiffre.
RSA, auf der anderen Seite ist nicht anfällig für Angriffe wie diese.
Die Cäsar-Chiffre und Vigenère Chiffre verwenden den gleichen Schlüssel
zum Verschlüsseln und Entschlüsseln einer Nachricht.
Diese Eigenschaft macht diese Chiffren symmetrischen Schlüssel Algorithmen.
Ein grundsätzliches Problem mit dem symmetrischen Schlüssel-Algorithmen
ist, dass sie auf der einen Verschlüsseln und Senden der Nachricht angewiesen
und das ein Empfangen und Entschlüsseln der Nachricht
bereits vereinbart im Voraus auf die Taste beide verwenden.
Aber wir haben ein bisschen von einem Startup Problem hier.
Wie 2 Computern, die miteinander kommunizieren wollen, Schaffung eines geheimen Schlüssels zwischen ihnen?
Wenn der Schlüssel muss geheim sein, dann müssen wir einen Weg zum Verschlüsseln und Entschlüsseln Sie die Taste.
Wenn alles, was wir haben, ist Kryptografie mit symmetrischen Schlüsseln
dann haben wir einfach wieder zu dem gleichen Problem kommen.
RSA, auf der anderen Seite, wird ein Paar von Schlüsseln,
eines für die Verschlüsselung und ein anderes für die Entschlüsselung.
Einer wird als der öffentliche Schlüssel und der andere ist der private Schlüssel.
Der öffentliche Schlüssel wird verwendet, um Nachrichten zu verschlüsseln.
Wie sein Name vermuten lässt, können wir unseren öffentlichen Schlüssel mit Aktien
alle wollen, ohne die Sicherheit einer verschlüsselten Nachricht.
Nachrichten verschlüsselt mittels eines öffentlichen Schlüssels
nur mit den entsprechenden privaten Schlüssel entschlüsselt werden.
Während Sie Ihren öffentlichen Schlüssel austauschen können, sollten Sie immer Ihren privaten Schlüssel geheim.
und nur der private Schlüssel kann zum Entschlüsseln von Nachrichten verwendet werden
wenn 2 Mitglieder möchten Nachrichten verschlüsselt mit RSA
hin und her, beide Benutzer müssen ihre eigenen öffentlichen und einen privaten Schlüssel haben.
Nachrichten von Benutzer 1 bis Benutzer 2
nur Benutzer 2 die Schlüsselpaar und Nachrichten von Benutzer 2 Benutzer 1
nur Benutzer 1 Schlüsselpaar.
Die Tatsache, dass es zwei separate Schlüssel zum Verschlüsseln und Entschlüsseln von Nachrichten
macht RSA einen asymmetrischen Schlüssel-Algorithmus.
Wir brauchen nicht um den öffentlichen Schlüssel zu verschlüsseln, um es an einen anderen Computer senden
da der Schlüssel ist öffentlich sowieso.
Dies bedeutet, dass RSA nicht die gleichen Startproblems
wie die symmetrischen Schlüssel Algorithmen.
Also, wenn ich will, um eine Nachricht mit RSA-Verschlüsselung senden
zu Rob, ich muss zuerst Rob öffentlichen Schlüssel.
Um ein Schlüsselpaar zu generieren, muss Rob zu 2 große Primzahlen zu pflücken.
Diese Zahlen werden in den öffentlichen und privaten Schlüsseln verwendet werden,
aber der öffentliche Schlüssel wird nur das Produkt dieser zwei Zahlen,
nicht die Zahlen selbst.
Einmal habe ich die Nachricht mit Rob öffentlichen Schlüssel verschlüsselt
Ich kann die Nachricht an Rob senden.
Für einen Computer ist Factoring Zahlen ein schwieriges Problem.
Der öffentliche Schlüssel, erinnern, verwendet das Produkt von 2 Primzahlen.
Dieses Produkt muss dann nur 2 Faktoren,
welche passieren, um die Zahlen, die den privaten Schlüssel sein.
Um die Nachricht zu entschlüsseln, wird RSA verwendet diesen privaten Schlüssel
oder die Zahlen miteinander multipliziert in dem Prozess der Schaffung des öffentlichen Schlüssels.
Weil es rechnerisch schwierig, die Zahl zu faktorisieren
eingesetzt in einem öffentlichen Schlüssel in der 2 Nummern im privaten Schlüssel verwendet
es ist schwierig für einen Angreifer, um herauszufinden, den privaten Schlüssel
die erforderlich sein, um die Nachricht entschlüsseln.
Lassen Sie uns nun in einigen niedrigeren Details RSA gehen.
Lassen Sie uns zunächst sehen, wie wir ein Schlüsselpaar generieren.
Erstens brauchen wir 2 Primzahlen.
Wir rufen diese 2 Zahlen p und q.
Um p und q, in der Praxis holen wir würden pseudozufällig generiert
großer Zahl und dann mit einem Test zur Bestimmung, ob
Diese Zahlen sind wahrscheinlich Primzahl.
Wir halten Erzeugen von Zufallszahlen wieder und wieder
bis wir 2 Primzahlen, die wir verwenden können.
Hier lassen Sie uns da p = 23 und q = 43.
Erinnern Sie sich, sollte in der Praxis p und q Zahlen viel größer sein.
Soweit wir wissen, desto größer die Zahl, desto schwieriger ist es
um eine verschlüsselte Nachricht zu knacken.
Aber es ist auch teurer zu verschlüsseln und Entschlüsseln von Nachrichten.
Heute ist es oft empfohlen, dass p und q mindestens 1024 Bit sind,
das bringt jede Zahl auf über 300 Dezimalstellen.
Aber wir werden diese kleinen Zahlen für dieses Beispiel nehmen.
Jetzt werden wir p und q zusammen multiplizieren, um eine dritte Zahl zu erhalten,
die wir nennen n.
In unserem Fall, n = 23 * 43, die 989 =.
Wir haben n = 989.
1 mit q - - Next wir p multiplizieren 1
eine vierte Zahl, die wir m werde erhalten.
In unserem Fall m = 22 * ​​42, die 924 =.
Wir haben m = 924.
Jetzt werden wir brauchen eine Zahl e, die teilerfremd zu m ist
und weniger als m.
Zwei Zahlen sind teilerfremd oder coprime
wenn das einzige positive ganze Zahl, die sie trennt beide gleichmäßig 1 ist.
Mit anderen Worten, der größte gemeinsame Teiler von e und m
muss 1 sein.
In der Praxis ist es üblich, dass e die Primzahl 65537 sein
Solange diese Zahl nicht zufällig ein Faktor m betragen.
Für unsere Schlüssel, wir holen e = 5
seit 5 teilerfremd zu 924.
Schließlich brauchen wir eine weitere Zahl, die wir d werde.
D muss einen gewissen Wert, der die Gleichung erfüllt sein, de = 1 (mod m).
Dieser Mod m bedeutet wir etwas namens modulare Arithmetik verwenden.
In modularer Arithmetik, erhält einmal eine Zahl größer als irgendeiner Obergrenze
es wird wickeln zurück um auf 0 gesetzt.
Eine Uhr, beispielsweise verwendet modulare Arithmetik.
Eine Minute nach 1:59, ist beispielsweise 2:00,
nicht 1:60.
Der Minutenzeiger hat rund um 0 gewickelt
bei Erreichen einer oberen von 60 gebunden.
So können wir sagen, 60 ist äquivalent zu 0 (mod 60)
und 125 ist äquivalent zu 65 entspricht 5 (mod 60).
Unsere öffentliche Schlüssel wird das Paar e und n
wobei in diesem Falle ist e 5 ist und n 989.
Unsere privaten Schlüssel wird das Paar d und n,
was in unserem Fall 185 und 989.
Beachten Sie, dass unsere ursprünglichen Primzahlen p und q nicht angezeigt
überall in unserem privaten oder öffentlichen Schlüsseln.
Nun haben wir unsere Schlüsselpaar haben, lassen Sie uns einen Blick darauf, wie können wir verschlüsseln
und Entschlüsseln einer Nachricht.
Ich möchte eine Nachricht an Rob senden,
so wird er derjenige sein, dieses Schlüsselpaar generieren.
Dann werde ich Rob für seinen öffentlichen Schlüssel, die ich verwende fragen
eine Nachricht an ihn senden zu verschlüsseln.
Denken Sie daran, es ist völlig okay für Rob seinen öffentlichen Schlüssel mit mir zu teilen.
Aber wäre es nicht in Ordnung, seinen privaten Schlüssel teilen.
Ich habe keine Ahnung, was seinen privaten Schlüssel ist.
Wir brechen kann unsere Botschaft m in mehrere Stücke
alle kleiner als n und dann Verschlüsseln jedes dieser Stücke.
Wir verschlüsseln die Zeichenfolge CS50, das wir brechen kann in 4 Stücke,
ein pro Buchstabe.
Um meine Nachricht zu verschlüsseln, brauche ich, um es in konvertieren
eine Art numerische Darstellung.
Lassen Sie verketten Sie die ASCII-Werte mit den Charakteren in meiner Nachricht.
Um Verschlüsseln einer bestimmten Nachricht m
Ich muss c = m zum e (mod n) zu berechnen.
Aber m muss kleiner sein als n,
oder aber die vollständige Meldung kann nicht modulo n ausgedrückt werden.
Wir können brechen m in mehrere Stücke, von denen alle kleiner als n sind,
und verschlüsseln jedes dieser Stücke.
Verschlüsseln jedes dieser Stücke, erhalten wir c1 = 67 mit dem 5 (mod 989)
die = 658.
Für unser zweites Stück haben wir 83 an der 5 (mod 989)
die = 15.
Für unsere dritte Stück haben wir 53 an den 5 (mod 989)
die = 799.
Und schließlich, für unsere letzte Stück haben wir 48 an den 5 (mod 989)
worin = 975.
Jetzt können wir senden über diese verschlüsselte Werte Rob.
Here you go, Rob.
Während unsere Botschaft ist auf der Flucht, lassen Sie uns einen Blick
, wie wir diesen Wert für d.
Unsere Zahl d benötigten bis 5d = 1 (mod 924) erfüllen.
Dies macht d das multiplikative Inverse von 5 modulo 924.
Angesichts 2 ganze Zahlen sind, a und b, die erweiterten euklidischen Algorithmus
können verwendet werden, um den größten gemeinsamen Teiler dieser ganzen Zahlen 2 finden.
Es wird uns auch andere Zahlen 2, x und y,
dass die Gleichung ax + by = der größte gemeinsame Teiler von a und b.
Wie hilft uns das?
Nun, Einstecken e = 5 für eine
und m = 924 für b
Wir wissen bereits, dass diese Zahlen teilerfremd sind.
Ihr größter gemeinsamer Teiler 1 ist.
Dies gibt uns 5x + 924y = 1
oder 5x = 1 - 924y.
Aber wenn wir nur über alles modulo 924 Pflege
dann können wir fallen lassen - 924y.
Denken Sie zurück an die Uhr.
Wenn der Minutenzeiger auf 1 und dann genau 10 Stunden vergehen,
Wir wissen, dass der Minutenzeiger wird immer noch auf der 1 sein.
Hier haben wir bei 1 beginnen und dann wickeln um genau y Zeiten
so dass wir immer noch auf 1 sein.
Wir haben 5x = 1 (mod 924).
Und hier dies x ist die gleiche wie die d wir vor uns waren,
so dass, wenn wir den erweiterten euklidischen Algorithmus
diese Zahl x zu bekommen, das ist die Zahl, die wir als unsere d verwenden sollten.
Jetzt lasst uns laufen erweiterten Euklidischen Algorithmus für a = 5
und b = 924.
Wir verwenden eine Methode namens der Tisch-Methode.
Unsere Tabelle wird 4 Spalten, x, y, d und k.
Unser Tisch beginnt mit 2 Reihen.
In der ersten Reihe haben wir 1, 0, dann ist unser Wert von a, die 5 beträgt,
und unsere zweite Reihe 0, 1, und unser Wert für b ist die 924.
Der Wert der vierten Spalte, k, wird das Ergebnis
des Teilens des Wertes von d in der Zeile darüber mit dem Wert von d
in der gleichen Zeile.
Wir haben 5 von 924 geteilt 0 mit einigen Rest aus.
Das heißt, wir haben k = 0 ist.
Jetzt ist der Wert von jeder anderen Zelle wird der Wert der Zelle 2 Zeilen darüber befinden
minus dem Wert der Zeile darüber mal k.
Beginnen wir mit d in der dritten Reihe.
Wir haben 5 bis 924 * 0 = 5.
Weiter haben wir 0 - 1 * 0, 0 ist
und 1 - 0 * 0 welches gleich 1 ist.
Nicht schlecht, also lasst uns auf die nächste Zeile zu springen.
Zunächst müssen wir unseren Wert von k.
924 um 5 = 184 mit einer gewissen Rest teilbar,
so dass unser Wert für k 184.
Jetzt 924 bis 5 * 184 = 4.
1 - 0 * 184 1 und 0 - 1 * 184 -184.
Alles klar, lasst uns die nächste Zeile.
Unser Wert von k wird 1 sein, weil
5 durch 4 = 1 mit etwas Rest aufgeteilt.
Lassen Sie uns in den anderen Spalten zu füllen.
5 bis 4 * 1 = 1.
0-1 * 1 = -1.
Und 1 - 184 * 1 185.
Mal sehen, was unser nächster Wert von k wäre.
Nun, es sieht aus wie haben wir 4 von 1, die 4 unterteilt.
In diesem Fall, in dem wir durch ein Aufteilen sind, so daß k gleich
der Wert von d in der obigen Zeile bedeutet, dass wir mit unserem Algorithmus fertig.
Wir können hier sehen, dass wir x = 185 und y = -1 haben in der letzten Zeile.
Lassen Sie uns nun zurück zu unserem ursprünglichen Ziel.
Wir haben gesagt, dass der Wert von x als Ergebnis dieses Algorithmus läuft
würde die multiplikative Inverse einer (mod b).
Das bedeutet, dass 185 die multiplikative Inverse von 5 (mod 924) ist
was bedeutet, dass wir einen Wert von 185 für d haben.
Die Tatsache, dass d = 1 in der letzten Reihe
stellt sicher, dass e wurde m teilerfremd.
Wenn es nicht 1, dann müssten wir eine neue E pflücken.
Nun wollen wir sehen, ob Rob meine Nachricht erhalten hat.
Wenn jemand schickt mir eine verschlüsselte Nachricht
Solange ich hielt meine private Schlüssel geheim
Ich bin der einzige, der die Nachricht entschlüsseln kann.
So entschlüsseln Sie ein Stück c I berechnen kann die ursprüngliche Nachricht
gleich der Chunk bis d Leistung (mod n).
Beachten Sie, dass d und n aus meinem privaten Schlüssel sind.
Um eine vollständige Nachricht aus seiner Stücke bekommen wir entschlüsseln jeder Chunk
und verketten Sie die Ergebnisse.
Genau wie sicher ist RSA?
Die Wahrheit ist, wir wissen es nicht.
Sicherheit ist, wie lange es dauern würde einen Angreifer zu ergreifen, um eine Nachricht zu knacken Basis
verschlüsselt mit RSA.
Beachten Sie, dass ein Angreifer Zugriff auf Ihre öffentlichen Schlüssel hat,
die enthält sowohl e und n.
Wenn der Angreifer gelingt, n in seine zwei Primzahlen p und q faktorisieren,
dann konnte sie ermitteln d mit Hilfe des erweiterten Euklidischen Algorithmus.
Dies gibt ihr den privaten Schlüssel, der zum Entschlüsseln verwendet werden kann jede Nachricht.
Aber wie schnell können wir Faktor Zahlen?
Auch wissen wir nicht.
Niemand hat einen schnellen Weg, es zu tun gefunden,
was bedeutet, dass angesichts groß genug n
wäre es einem Angreifer unrealistisch lange dauern
um die Anzahl faktorisieren.
Wenn jemand zeigte eine schnelle Wege des Factoring Zahlen
RSA würde gebrochen werden.
Aber selbst wenn Integer-Faktorisierung ist von Natur aus langsam
der RSA-Algorithmus könnte noch einige Fehler in ihm
das ermöglicht die einfache Entschlüsselung von Nachrichten.
Niemand gefunden hat und eine solche Schwachstelle zeigte noch
aber das bedeutet nicht, dass man nicht existiert.
In der Theorie könnte jemand da draußen liest alle Daten mit RSA verschlüsselt.
Es gibt einen anderen bisschen Privatsphäre vor.
Wenn Tommy verschlüsselt eine Botschaft mit meinem öffentlichen Schlüssel
und ein Angreifer verschlüsselt die gleiche Botschaft mit meinem öffentlichen Schlüssel
der Angreifer wird sehen, dass die 2-Nachrichten identisch sind
und somit wissen, was Tommy verschlüsselt.
Um dies zu verhindern, werden Nachrichten typischerweise mit Zufallsbits aufgefüllt
bevor sie verschlüsselt, so dass die gleiche Nachricht verschlüsselt
mehrfach aussehen wird so lange anders als die Polster an der Nachricht ist anders.
Aber denken Sie daran, wie wir die Nachrichten in Stücke aufgeteilt haben
so daß jeder Chunk kleiner als n?
Auffüllen der Brocken bedeutet, dass wir vielleicht die Dinge aufgeteilt
in noch mehr Brocken da die gepolsterte chunk muss kleiner sein als n.
Verschlüsselung und Entschlüsselung sind relativ teuer mit RSA,
und so braucht zu brechen eine Nachricht in viele Stücke können sehr kostspielig sein.
Wenn eine große Datenmenge muss verschlüsselt und entschlüsselt
Wir kombinieren die Vorteile der symmetrischen Schlüssel-Algorithmen
mit denen von RSA, um sowohl die Sicherheit und Effizienz.
Obwohl wir nicht in sie hier gehen,
AES ist ein symmetrischer Schlüssel-Algorithmus wie der Vigenère und Caesar Chiffren
aber viel schwerer zu knacken.
Natürlich können wir nicht verwenden AES ohne eine gemeinsamen geheimen Schlüssel
zwischen den 2 Systemen, und wir sahen das Problem mit, dass vor.
Aber jetzt können wir RSA an, den gemeinsamen geheimen Schlüssel zwischen den 2 Systemen zu etablieren.
Wir rufen Sie den Computer das Senden der Daten des Absenders
und der Computer die Daten empfängt, den Empfänger.
Der Receiver verfügt über ein RSA-Schlüsselpaar und sendet
der öffentliche Schlüssel an den Absender.
Der Absender erzeugt einen AES-Schlüssel,
verschlüsselt sie mit der Receiver-öffentlichen RSA-Schlüssel,
und sendet die AES-Schlüssel an den Empfänger.
Der Empfänger entschlüsselt die Nachricht mit seinem privaten RSA-Schlüssel.
Sowohl der Sender als auch der Empfänger haben nun eine gemeinsame AES-Schlüssel zwischen ihnen.
AES, die viel schneller Ver-und Entschlüsselung als RSA ist,
kann nun verwendet werden, um die großen Datenmengen verschlüsseln und senden sie an den Empfänger,
wer kann entschlüsseln mit dem gleichen Schlüssel.
AES, die viel schneller Ver-und Entschlüsselung als RSA ist,
kann nun verwendet werden, um die großen Datenmengen verschlüsseln und senden sie an den Empfänger,
wer kann entschlüsseln mit dem gleichen Schlüssel.
Wir brauchten nur RSA, um die gemeinsamen Schlüssel übertragen.
Wir müssen nicht mehr RSA zu benutzen.
Es sieht aus wie ich eine Nachricht habe.
Es spielt keine Rolle, ob jemand lesen, was auf dem Papier Flugzeug, bevor ich es erwischt
weil ich der einzige mit dem privaten Schlüssel bin.
Lassen Entschlüsseln jedes der Stücke in der Nachricht.
Das erste Stück, 658, erhöhen wir die d Macht, die 185 ist,
mod n, die 989 ist, ist gleich 67,
das ist der Buchstabe C in ASCII.
Nun, auf dem zweiten Block kommt.
Das zweite Stück hat den Wert 15,
die wir an den 185. potenzieren,
mod 989, und diese ist gleich 83
das ist der Buchstabe S in ASCII.
Nun zum dritten Brocken, die den Wert 799 hat, haben wir auf 185 zu erhöhen,
mod 989, und dies ist gleich 53,
das ist der Wert des Zeichens 5 in ASCII.
Nun zum letzten Stück hat, welcher Wert 975,
erheben wir bis 185, mod 989,
und dies ist gleich 48, die Wert des Zeichens 0 in ASCII ist.
Mein Name ist Rob Bowden, und dies ist CS50.
[CS50.TV]
RSA überhaupt.
RSA überhaupt. [Gelächter]
Überhaupt.