1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [RSA]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden] [Tommy MacWilliam] [Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Dies ist CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Werfen wir einen Blick auf RSA, ein weit verbreiteter Algorithmus zur Verschlüsselung von Daten.

5
00:00:11,000 --> 00:00:16,000
Verschlüsselungsalgorithmen wie Caesar und Vigenère Chiffren sind nicht sehr sicher.

6
00:00:16,000 --> 00:00:20,000
Mit der Caesar-Chiffre, ein Angreifer braucht nur zu 25 verschiedene Tasten ausprobieren

7
00:00:20,000 --> 00:00:22,000
zu der Nachricht Klartext zu bekommen.

8
00:00:22,000 --> 00:00:25,000
Während die Vigenère Chiffre ist sicherer als die Caesar-Chiffre

9
00:00:25,000 --> 00:00:28,000
aufgrund des größeren Suchraum für Schlüssel, sobald ein Angreifer

10
00:00:28,000 --> 00:00:30,000
kennt die Länge des Schlüssels in einem Vigenère Chiffre,

11
00:00:30,000 --> 00:00:34,000
Es kann über eine Analyse von Mustern in dem verschlüsselten Text bestimmt werden,

12
00:00:34,000 --> 00:00:38,000
Die Vigenère Chiffre ist nicht so, dass viel sicherer als die Caesar-Chiffre.

13
00:00:38,000 --> 00:00:42,000
RSA, auf der anderen Seite ist nicht anfällig für Angriffe wie diese.

14
00:00:42,000 --> 00:00:45,000
Die Cäsar-Chiffre und Vigenère Chiffre verwenden den gleichen Schlüssel

15
00:00:45,000 --> 00:00:47,000
zum Verschlüsseln und Entschlüsseln einer Nachricht.

16
00:00:47,000 --> 00:00:51,000
Diese Eigenschaft macht diese Chiffren symmetrischen Schlüssel Algorithmen.

17
00:00:51,000 --> 00:00:54,000
Ein grundsätzliches Problem mit dem symmetrischen Schlüssel-Algorithmen

18
00:00:54,000 --> 00:00:57,000
ist, dass sie auf der einen Verschlüsseln und Senden der Nachricht angewiesen

19
00:00:57,000 --> 00:00:59,000
und das ein Empfangen und Entschlüsseln der Nachricht

20
00:00:59,000 --> 00:01:03,000
bereits vereinbart im Voraus auf die Taste beide verwenden.

21
00:01:03,000 --> 00:01:06,000
Aber wir haben ein bisschen von einem Startup Problem hier.

22
00:01:06,000 --> 00:01:10,000
Wie 2 Computern, die miteinander kommunizieren wollen, Schaffung eines geheimen Schlüssels zwischen ihnen?

23
00:01:10,000 --> 00:01:16,000
Wenn der Schlüssel muss geheim sein, dann müssen wir einen Weg zum Verschlüsseln und Entschlüsseln Sie die Taste.

24
00:01:16,000 --> 00:01:18,000
Wenn alles, was wir haben, ist Kryptografie mit symmetrischen Schlüsseln

25
00:01:18,000 --> 00:01:21,000
dann haben wir einfach wieder zu dem gleichen Problem kommen.

26
00:01:21,000 --> 00:01:25,000
RSA, auf der anderen Seite, wird ein Paar von Schlüsseln,

27
00:01:25,000 --> 00:01:28,000
eines für die Verschlüsselung und ein anderes für die Entschlüsselung.

28
00:01:28,000 --> 00:01:32,000
Einer wird als der öffentliche Schlüssel und der andere ist der private Schlüssel.

29
00:01:32,000 --> 00:01:34,000
Der öffentliche Schlüssel wird verwendet, um Nachrichten zu verschlüsseln.

30
00:01:34,000 --> 00:01:38,000
Wie sein Name vermuten lässt, können wir unseren öffentlichen Schlüssel mit Aktien

31
00:01:38,000 --> 00:01:43,000
alle wollen, ohne die Sicherheit einer verschlüsselten Nachricht.

32
00:01:43,000 --> 00:01:45,000
Nachrichten verschlüsselt mittels eines öffentlichen Schlüssels

33
00:01:45,000 --> 00:01:49,000
nur mit den entsprechenden privaten Schlüssel entschlüsselt werden.

34
00:01:49,000 --> 00:01:53,000
Während Sie Ihren öffentlichen Schlüssel austauschen können, sollten Sie immer Ihren privaten Schlüssel geheim.

61
00:01:55,000 --> 00:01:58,000
und nur der private Schlüssel kann zum Entschlüsseln von Nachrichten verwendet werden

62
00:01:58,000 --> 00:02:02,000
wenn 2 Mitglieder möchten Nachrichten verschlüsselt mit RSA

63
00:02:02,000 --> 00:02:07,000
hin und her, beide Benutzer müssen ihre eigenen öffentlichen und einen privaten Schlüssel haben.

64
00:02:07,000 --> 00:02:10,000
Nachrichten von Benutzer 1 bis Benutzer 2

65
00:02:10,000 --> 00:02:15,000
nur Benutzer 2 die Schlüsselpaar und Nachrichten von Benutzer 2 Benutzer 1

66
00:02:15,000 --> 00:02:17,000
nur Benutzer 1 Schlüsselpaar.

67
00:02:17,000 --> 00:02:21,000
Die Tatsache, dass es zwei separate Schlüssel zum Verschlüsseln und Entschlüsseln von Nachrichten

68
00:02:21,000 --> 00:02:24,000
macht RSA einen asymmetrischen Schlüssel-Algorithmus.

69
00:02:24,000 --> 00:02:28,000
Wir brauchen nicht um den öffentlichen Schlüssel zu verschlüsseln, um es an einen anderen Computer senden

70
00:02:28,000 --> 00:02:31,000
da der Schlüssel ist öffentlich sowieso.

71
00:02:31,000 --> 00:02:33,000
Dies bedeutet, dass RSA nicht die gleichen Startproblems

72
00:02:33,000 --> 00:02:36,000
wie die symmetrischen Schlüssel Algorithmen.

73
00:02:36,000 --> 00:02:39,000
Also, wenn ich will, um eine Nachricht mit RSA-Verschlüsselung senden

74
00:02:39,000 --> 00:02:42,000
zu Rob, ich muss zuerst Rob öffentlichen Schlüssel.

75
00:02:42,000 --> 00:02:47,000
Um ein Schlüsselpaar zu generieren, muss Rob zu 2 große Primzahlen zu pflücken.

76
00:02:47,000 --> 00:02:50,000
Diese Zahlen werden in den öffentlichen und privaten Schlüsseln verwendet werden,

77
00:02:50,000 --> 00:02:54,000
aber der öffentliche Schlüssel wird nur das Produkt dieser zwei Zahlen,

78
00:02:54,000 --> 00:02:56,000
nicht die Zahlen selbst.

79
00:02:56,000 --> 00:02:59,000
Einmal habe ich die Nachricht mit Rob öffentlichen Schlüssel verschlüsselt

80
00:02:59,000 --> 00:03:01,000
Ich kann die Nachricht an Rob senden.

81
00:03:01,000 --> 00:03:05,000
Für einen Computer ist Factoring Zahlen ein schwieriges Problem.

82
00:03:05,000 --> 00:03:09,000
Der öffentliche Schlüssel, erinnern, verwendet das Produkt von 2 Primzahlen.

83
00:03:09,000 --> 00:03:12,000
Dieses Produkt muss dann nur 2 Faktoren,

84
00:03:12,000 --> 00:03:16,000
welche passieren, um die Zahlen, die den privaten Schlüssel sein.

85
00:03:16,000 --> 00:03:20,000
Um die Nachricht zu entschlüsseln, wird RSA verwendet diesen privaten Schlüssel

86
00:03:20,000 --> 00:03:25,000
oder die Zahlen miteinander multipliziert in dem Prozess der Schaffung des öffentlichen Schlüssels.

87
00:03:25,000 --> 00:03:28,000
Weil es rechnerisch schwierig, die Zahl zu faktorisieren

88
00:03:28,000 --> 00:03:32,000
eingesetzt in einem öffentlichen Schlüssel in der 2 Nummern im privaten Schlüssel verwendet

89
00:03:32,000 --> 00:03:36,000
es ist schwierig für einen Angreifer, um herauszufinden, den privaten Schlüssel

90
00:03:36,000 --> 00:03:39,000
die erforderlich sein, um die Nachricht entschlüsseln.

91
00:03:39,000 --> 00:03:43,000
Lassen Sie uns nun in einigen niedrigeren Details RSA gehen.

92
00:03:43,000 --> 00:03:46,000
Lassen Sie uns zunächst sehen, wie wir ein Schlüsselpaar generieren.

93
00:03:46,000 --> 00:03:49,000
Erstens brauchen wir 2 Primzahlen.

94
00:03:49,000 --> 00:03:52,000
Wir rufen diese 2 Zahlen p und q.

95
00:03:52,000 --> 00:03:56,000
Um p und q, in der Praxis holen wir würden pseudozufällig generiert

96
00:03:56,000 --> 00:03:59,000
großer Zahl und dann mit einem Test zur Bestimmung, ob

97
00:03:59,000 --> 00:04:02,000
Diese Zahlen sind wahrscheinlich Primzahl.

98
00:04:02,000 --> 00:04:05,000
Wir halten Erzeugen von Zufallszahlen wieder und wieder

99
00:04:05,000 --> 00:04:08,000
bis wir 2 Primzahlen, die wir verwenden können.

100
00:04:08,000 --> 00:04:15,000
Hier lassen Sie uns da p = 23 und q = 43.

101
00:04:15,000 --> 00:04:19,000
Erinnern Sie sich, sollte in der Praxis p und q Zahlen viel größer sein.

102
00:04:19,000 --> 00:04:22,000
Soweit wir wissen, desto größer die Zahl, desto schwieriger ist es

103
00:04:22,000 --> 00:04:25,000
um eine verschlüsselte Nachricht zu knacken.

104
00:04:25,000 --> 00:04:29,000
Aber es ist auch teurer zu verschlüsseln und Entschlüsseln von Nachrichten.

105
00:04:29,000 --> 00:04:33,000
Heute ist es oft empfohlen, dass p und q mindestens 1024 Bit sind,

106
00:04:33,000 --> 00:04:37,000
das bringt jede Zahl auf über 300 Dezimalstellen.

107
00:04:37,000 --> 00:04:40,000
Aber wir werden diese kleinen Zahlen für dieses Beispiel nehmen.

108
00:04:40,000 --> 00:04:43,000
Jetzt werden wir p und q zusammen multiplizieren, um eine dritte Zahl zu erhalten,

109
00:04:43,000 --> 00:04:45,000
die wir nennen n.

110
00:04:45,000 --> 00:04:55,000
In unserem Fall, n = 23 * 43, die 989 =.

111
00:04:55,000 --> 00:04:58,000
Wir haben n = 989.

112
00:04:58,000 --> 00:05:02,000
1 mit q - - Next wir p multiplizieren 1

113
00:05:02,000 --> 00:05:05,000
eine vierte Zahl, die wir m werde erhalten.

114
00:05:05,000 --> 00:05:15,000
In unserem Fall m = 22 * ​​42, die 924 =.

115
00:05:15,000 --> 00:05:18,000
Wir haben m = 924.

116
00:05:18,000 --> 00:05:22,000
Jetzt werden wir brauchen eine Zahl e, die teilerfremd zu m ist

117
00:05:22,000 --> 00:05:25,000
und weniger als m.

118
00:05:25,000 --> 00:05:28,000
Zwei Zahlen sind teilerfremd oder coprime

119
00:05:28,000 --> 00:05:33,000
wenn das einzige positive ganze Zahl, die sie trennt beide gleichmäßig 1 ist.

120
00:05:33,000 --> 00:05:37,000
Mit anderen Worten, der größte gemeinsame Teiler von e und m

121
00:05:37,000 --> 00:05:39,000
muss 1 sein.

122
00:05:39,000 --> 00:05:44,000
In der Praxis ist es üblich, dass e die Primzahl 65537 sein

123
00:05:44,000 --> 00:05:48,000
Solange diese Zahl nicht zufällig ein Faktor m betragen.

124
00:05:48,000 --> 00:05:53,000
Für unsere Schlüssel, wir holen e = 5

125
00:05:53,000 --> 00:05:57,000
seit 5 teilerfremd zu 924.

126
00:05:57,000 --> 00:06:01,000
Schließlich brauchen wir eine weitere Zahl, die wir d werde.

127
00:06:01,000 --> 00:06:11,000
D muss einen gewissen Wert, der die Gleichung erfüllt sein, de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Dieser Mod m bedeutet wir etwas namens modulare Arithmetik verwenden.

129
00:06:17,000 --> 00:06:21,000
In modularer Arithmetik, erhält einmal eine Zahl größer als irgendeiner Obergrenze

130
00:06:21,000 --> 00:06:24,000
es wird wickeln zurück um auf 0 gesetzt.

131
00:06:24,000 --> 00:06:27,000
Eine Uhr, beispielsweise verwendet modulare Arithmetik.

132
00:06:27,000 --> 00:06:31,000
Eine Minute nach 1:59, ist beispielsweise 2:00,

133
00:06:31,000 --> 00:06:33,000
nicht 1:60.

134
00:06:33,000 --> 00:06:36,000
Der Minutenzeiger hat rund um 0 gewickelt

135
00:06:36,000 --> 00:06:39,000
bei Erreichen einer oberen von 60 gebunden.

136
00:06:39,000 --> 00:06:46,000
So können wir sagen, 60 ist äquivalent zu 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
und 125 ist äquivalent zu 65 entspricht 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Unsere öffentliche Schlüssel wird das Paar e und n

139
00:07:02,000 --> 00:07:09,000
wobei in diesem Falle ist e 5 ist und n 989.

140
00:07:09,000 --> 00:07:15,000
Unsere privaten Schlüssel wird das Paar d und n,

141
00:07:15,000 --> 00:07:22,000
was in unserem Fall 185 und 989.

142
00:07:22,000 --> 00:07:25,000
Beachten Sie, dass unsere ursprünglichen Primzahlen p und q nicht angezeigt

143
00:07:25,000 --> 00:07:29,000
überall in unserem privaten oder öffentlichen Schlüsseln.

144
00:07:29,000 --> 00:07:33,000
Nun haben wir unsere Schlüsselpaar haben, lassen Sie uns einen Blick darauf, wie können wir verschlüsseln

145
00:07:33,000 --> 00:07:36,000
und Entschlüsseln einer Nachricht.

146
00:07:36,000 --> 00:07:38,000
Ich möchte eine Nachricht an Rob senden,

147
00:07:38,000 --> 00:07:42,000
so wird er derjenige sein, dieses Schlüsselpaar generieren.

148
00:07:42,000 --> 00:07:46,000
Dann werde ich Rob für seinen öffentlichen Schlüssel, die ich verwende fragen

149
00:07:46,000 --> 00:07:48,000
eine Nachricht an ihn senden zu verschlüsseln.

150
00:07:48,000 --> 00:07:53,000
Denken Sie daran, es ist völlig okay für Rob seinen öffentlichen Schlüssel mit mir zu teilen.

151
00:07:53,000 --> 00:07:56,000
Aber wäre es nicht in Ordnung, seinen privaten Schlüssel teilen.

152
00:07:56,000 --> 00:08:00,000
Ich habe keine Ahnung, was seinen privaten Schlüssel ist.

153
00:08:00,000 --> 00:08:03,000
Wir brechen kann unsere Botschaft m in mehrere Stücke

154
00:08:03,000 --> 00:08:07,000
alle kleiner als n und dann Verschlüsseln jedes dieser Stücke.

155
00:08:07,000 --> 00:08:12,000
Wir verschlüsseln die Zeichenfolge CS50, das wir brechen kann in 4 Stücke,

156
00:08:12,000 --> 00:08:14,000
ein pro Buchstabe.

157
00:08:14,000 --> 00:08:17,000
Um meine Nachricht zu verschlüsseln, brauche ich, um es in konvertieren

158
00:08:17,000 --> 00:08:20,000
eine Art numerische Darstellung.

159
00:08:20,000 --> 00:08:25,000
Lassen Sie verketten Sie die ASCII-Werte mit den Charakteren in meiner Nachricht.

160
00:08:25,000 --> 00:08:28,000
Um Verschlüsseln einer bestimmten Nachricht m

161
00:08:28,000 --> 00:08:37,000
Ich muss c = m zum e (mod n) zu berechnen.

162
00:08:37,000 --> 00:08:40,000
Aber m muss kleiner sein als n,

163
00:08:40,000 --> 00:08:45,000
oder aber die vollständige Meldung kann nicht modulo n ausgedrückt werden.

164
00:08:45,000 --> 00:08:49,000
Wir können brechen m in mehrere Stücke, von denen alle kleiner als n sind,

165
00:08:49,000 --> 00:08:52,000
und verschlüsseln jedes dieser Stücke.

166
00:08:52,000 --> 00:09:03,000
Verschlüsseln jedes dieser Stücke, erhalten wir c1 = 67 mit dem 5 (mod 989)

167
00:09:03,000 --> 00:09:06,000
die = 658.

168
00:09:06,000 --> 00:09:15,000
Für unser zweites Stück haben wir 83 an der 5 (mod 989)

169
00:09:15,000 --> 00:09:18,000
die = 15.

170
00:09:18,000 --> 00:09:26,000
Für unsere dritte Stück haben wir 53 an den 5 (mod 989)

171
00:09:26,000 --> 00:09:30,000
die = 799.

172
00:09:30,000 --> 00:09:39,000
Und schließlich, für unsere letzte Stück haben wir 48 an den 5 (mod 989)

173
00:09:39,000 --> 00:09:43,000
worin = 975.

174
00:09:43,000 --> 00:09:48,000
Jetzt können wir senden über diese verschlüsselte Werte Rob.

175
00:09:54,000 --> 00:09:58,000
Here you go, Rob.

176
00:09:58,000 --> 00:10:01,000
Während unsere Botschaft ist auf der Flucht, lassen Sie uns einen Blick

177
00:10:01,000 --> 00:10:07,000
, wie wir diesen Wert für d.

178
00:10:07,000 --> 00:10:17,000
Unsere Zahl d benötigten bis 5d = 1 (mod 924) erfüllen.

179
00:10:17,000 --> 00:10:24,000
Dies macht d das multiplikative Inverse von 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Angesichts 2 ganze Zahlen sind, a und b, die erweiterten euklidischen Algorithmus

181
00:10:28,000 --> 00:10:33,000
können verwendet werden, um den größten gemeinsamen Teiler dieser ganzen Zahlen 2 finden.

182
00:10:33,000 --> 00:10:37,000
Es wird uns auch andere Zahlen 2, x und y,

183
00:10:37,000 --> 00:10:47,000
dass die Gleichung ax + by = der größte gemeinsame Teiler von a und b.

184
00:10:47,000 --> 00:10:49,000
Wie hilft uns das?

185
00:10:49,000 --> 00:10:52,000
Nun, Einstecken e = 5 für eine

186
00:10:52,000 --> 00:10:56,000
und m = 924 für b

187
00:10:56,000 --> 00:10:59,000
Wir wissen bereits, dass diese Zahlen teilerfremd sind.

188
00:10:59,000 --> 00:11:03,000
Ihr größter gemeinsamer Teiler 1 ist.

189
00:11:03,000 --> 00:11:09,000
Dies gibt uns 5x + 924y = 1

190
00:11:09,000 --> 00:11:17,000
oder 5x = 1 - 924y.

191
00:11:17,000 --> 00:11:22,000
Aber wenn wir nur über alles modulo 924 Pflege

192
00:11:22,000 --> 00:11:25,000
dann können wir fallen lassen - 924y.

193
00:11:25,000 --> 00:11:27,000
Denken Sie zurück an die Uhr.

194
00:11:27,000 --> 00:11:31,000
Wenn der Minutenzeiger auf 1 und dann genau 10 Stunden vergehen,

195
00:11:31,000 --> 00:11:35,000
Wir wissen, dass der Minutenzeiger wird immer noch auf der 1 sein.

196
00:11:35,000 --> 00:11:39,000
Hier haben wir bei 1 beginnen und dann wickeln um genau y Zeiten

197
00:11:39,000 --> 00:11:41,000
so dass wir immer noch auf 1 sein.

198
00:11:41,000 --> 00:11:49,000
Wir haben 5x = 1 (mod 924).

199
00:11:49,000 --> 00:11:55,000
Und hier dies x ist die gleiche wie die d wir vor uns waren,

200
00:11:55,000 --> 00:11:58,000
so dass, wenn wir den erweiterten euklidischen Algorithmus

201
00:11:58,000 --> 00:12:04,000
diese Zahl x zu bekommen, das ist die Zahl, die wir als unsere d verwenden sollten.

202
00:12:04,000 --> 00:12:07,000
Jetzt lasst uns laufen erweiterten Euklidischen Algorithmus für a = 5

203
00:12:07,000 --> 00:12:11,000
und b = 924.

204
00:12:11,000 --> 00:12:14,000
Wir verwenden eine Methode namens der Tisch-Methode.

205
00:12:14,000 --> 00:12:21,000
Unsere Tabelle wird 4 Spalten, x, y, d und k.

206
00:12:21,000 --> 00:12:23,000
Unser Tisch beginnt mit 2 Reihen.

207
00:12:23,000 --> 00:12:28,000
In der ersten Reihe haben wir 1, 0, dann ist unser Wert von a, die 5 beträgt,

208
00:12:28,000 --> 00:12:37,000
und unsere zweite Reihe 0, 1, und unser Wert für b ist die 924.

209
00:12:37,000 --> 00:12:40,000
Der Wert der vierten Spalte, k, wird das Ergebnis

210
00:12:40,000 --> 00:12:45,000
des Teilens des Wertes von d in der Zeile darüber mit dem Wert von d

211
00:12:45,000 --> 00:12:49,000
in der gleichen Zeile.

212
00:12:49,000 --> 00:12:56,000
Wir haben 5 von 924 geteilt 0 mit einigen Rest aus.

213
00:12:56,000 --> 00:12:59,000
Das heißt, wir haben k = 0 ist.

214
00:12:59,000 --> 00:13:05,000
Jetzt ist der Wert von jeder anderen Zelle wird der Wert der Zelle 2 Zeilen darüber befinden

215
00:13:05,000 --> 00:13:09,000
minus dem Wert der Zeile darüber mal k.

216
00:13:09,000 --> 00:13:11,000
Beginnen wir mit d in der dritten Reihe.

217
00:13:11,000 --> 00:13:19,000
Wir haben 5 bis 924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Weiter haben wir 0 - 1 * 0, 0 ist

219
00:13:25,000 --> 00:13:30,000
und 1 - 0 * 0 welches gleich 1 ist.

220
00:13:30,000 --> 00:13:33,000
Nicht schlecht, also lasst uns auf die nächste Zeile zu springen.

221
00:13:33,000 --> 00:13:36,000
Zunächst müssen wir unseren Wert von k.

222
00:13:36,000 --> 00:13:43,000
924 um 5 = 184 mit einer gewissen Rest teilbar,

223
00:13:43,000 --> 00:13:46,000
so dass unser Wert für k 184.

224
00:13:46,000 --> 00:13:54,000
Jetzt 924 bis 5 * 184 = 4.

225
00:13:54,000 --> 00:14:05,000
1 - 0 * 184 1 und 0 - 1 * 184 -184.

226
00:14:05,000 --> 00:14:07,000
Alles klar, lasst uns die nächste Zeile.

227
00:14:07,000 --> 00:14:10,000
Unser Wert von k wird 1 sein, weil

228
00:14:10,000 --> 00:14:15,000
5 durch 4 = 1 mit etwas Rest aufgeteilt.

229
00:14:15,000 --> 00:14:17,000
Lassen Sie uns in den anderen Spalten zu füllen.

230
00:14:17,000 --> 00:14:21,000
5 bis 4 * 1 = 1.

231
00:14:21,000 --> 00:14:25,000
0-1 * 1 = -1.

232
00:14:25,000 --> 00:14:33,000
Und 1 - 184 * 1 185.

233
00:14:33,000 --> 00:14:35,000
Mal sehen, was unser nächster Wert von k wäre.

234
00:14:35,000 --> 00:14:40,000
Nun, es sieht aus wie haben wir 4 von 1, die 4 unterteilt.

235
00:14:40,000 --> 00:14:43,000
In diesem Fall, in dem wir durch ein Aufteilen sind, so daß k gleich

236
00:14:43,000 --> 00:14:50,000
der Wert von d in der obigen Zeile bedeutet, dass wir mit unserem Algorithmus fertig.

237
00:14:50,000 --> 00:14:58,000
Wir können hier sehen, dass wir x = 185 und y = -1 haben in der letzten Zeile.

238
00:14:58,000 --> 00:15:00,000
Lassen Sie uns nun zurück zu unserem ursprünglichen Ziel.

239
00:15:00,000 --> 00:15:04,000
Wir haben gesagt, dass der Wert von x als Ergebnis dieses Algorithmus läuft

240
00:15:04,000 --> 00:15:08,000
würde die multiplikative Inverse einer (mod b).

241
00:15:08,000 --> 00:15:15,000
Das bedeutet, dass 185 die multiplikative Inverse von 5 (mod 924) ist

242
00:15:15,000 --> 00:15:20,000
was bedeutet, dass wir einen Wert von 185 für d haben.

243
00:15:20,000 --> 00:15:23,000
Die Tatsache, dass d = 1 in der letzten Reihe

244
00:15:23,000 --> 00:15:26,000
stellt sicher, dass e wurde m teilerfremd.

245
00:15:26,000 --> 00:15:30,000
Wenn es nicht 1, dann müssten wir eine neue E pflücken.

246
00:15:30,000 --> 00:15:33,000
Nun wollen wir sehen, ob Rob meine Nachricht erhalten hat.

247
00:15:33,000 --> 00:15:35,000
Wenn jemand schickt mir eine verschlüsselte Nachricht

248
00:15:35,000 --> 00:15:38,000
Solange ich hielt meine private Schlüssel geheim

249
00:15:38,000 --> 00:15:41,000
Ich bin der einzige, der die Nachricht entschlüsseln kann.

250
00:15:41,000 --> 00:15:46,000
So entschlüsseln Sie ein Stück c I berechnen kann die ursprüngliche Nachricht

251
00:15:46,000 --> 00:15:53,000
gleich der Chunk bis d Leistung (mod n).

252
00:15:53,000 --> 00:15:57,000
Beachten Sie, dass d und n aus meinem privaten Schlüssel sind.

253
00:15:57,000 --> 00:16:01,000
Um eine vollständige Nachricht aus seiner Stücke bekommen wir entschlüsseln jeder Chunk

254
00:16:01,000 --> 00:16:04,000
und verketten Sie die Ergebnisse.

255
00:16:04,000 --> 00:16:08,000
Genau wie sicher ist RSA?

256
00:16:08,000 --> 00:16:10,000
Die Wahrheit ist, wir wissen es nicht.

257
00:16:10,000 --> 00:16:14,000
Sicherheit ist, wie lange es dauern würde einen Angreifer zu ergreifen, um eine Nachricht zu knacken Basis

258
00:16:14,000 --> 00:16:16,000
verschlüsselt mit RSA.

259
00:16:16,000 --> 00:16:19,000
Beachten Sie, dass ein Angreifer Zugriff auf Ihre öffentlichen Schlüssel hat,

260
00:16:19,000 --> 00:16:21,000
die enthält sowohl e und n.

261
00:16:21,000 --> 00:16:26,000
Wenn der Angreifer gelingt, n in seine zwei Primzahlen p und q faktorisieren,

262
00:16:26,000 --> 00:16:30,000
dann konnte sie ermitteln d mit Hilfe des erweiterten Euklidischen Algorithmus.

263
00:16:30,000 --> 00:16:35,000
Dies gibt ihr den privaten Schlüssel, der zum Entschlüsseln verwendet werden kann jede Nachricht.

264
00:16:35,000 --> 00:16:38,000
Aber wie schnell können wir Faktor Zahlen?

265
00:16:38,000 --> 00:16:41,000
Auch wissen wir nicht.

266
00:16:41,000 --> 00:16:43,000
Niemand hat einen schnellen Weg, es zu tun gefunden,

267
00:16:43,000 --> 00:16:46,000
was bedeutet, dass angesichts groß genug n

268
00:16:46,000 --> 00:16:49,000
wäre es einem Angreifer unrealistisch lange dauern

269
00:16:49,000 --> 00:16:51,000
um die Anzahl faktorisieren.

270
00:16:51,000 --> 00:16:54,000
Wenn jemand zeigte eine schnelle Wege des Factoring Zahlen

271
00:16:54,000 --> 00:16:57,000
RSA würde gebrochen werden.

272
00:16:57,000 --> 00:17:01,000
Aber selbst wenn Integer-Faktorisierung ist von Natur aus langsam

273
00:17:01,000 --> 00:17:04,000
der RSA-Algorithmus könnte noch einige Fehler in ihm

274
00:17:04,000 --> 00:17:07,000
das ermöglicht die einfache Entschlüsselung von Nachrichten.

275
00:17:07,000 --> 00:17:10,000
Niemand gefunden hat und eine solche Schwachstelle zeigte noch

276
00:17:10,000 --> 00:17:12,000
aber das bedeutet nicht, dass man nicht existiert.

277
00:17:12,000 --> 00:17:17,000
In der Theorie könnte jemand da draußen liest alle Daten mit RSA verschlüsselt.

278
00:17:17,000 --> 00:17:19,000
Es gibt einen anderen bisschen Privatsphäre vor.

279
00:17:19,000 --> 00:17:23,000
Wenn Tommy verschlüsselt eine Botschaft mit meinem öffentlichen Schlüssel

280
00:17:23,000 --> 00:17:26,000
und ein Angreifer verschlüsselt die gleiche Botschaft mit meinem öffentlichen Schlüssel

281
00:17:26,000 --> 00:17:29,000
der Angreifer wird sehen, dass die 2-Nachrichten identisch sind

282
00:17:29,000 --> 00:17:32,000
und somit wissen, was Tommy verschlüsselt.

283
00:17:32,000 --> 00:17:36,000
Um dies zu verhindern, werden Nachrichten typischerweise mit Zufallsbits aufgefüllt

284
00:17:36,000 --> 00:17:39,000
bevor sie verschlüsselt, so dass die gleiche Nachricht verschlüsselt

285
00:17:39,000 --> 00:17:44,000
mehrfach aussehen wird so lange anders als die Polster an der Nachricht ist anders.

286
00:17:44,000 --> 00:17:47,000
Aber denken Sie daran, wie wir die Nachrichten in Stücke aufgeteilt haben

287
00:17:47,000 --> 00:17:50,000
so daß jeder Chunk kleiner als n?

288
00:17:50,000 --> 00:17:52,000
Auffüllen der Brocken bedeutet, dass wir vielleicht die Dinge aufgeteilt

289
00:17:52,000 --> 00:17:57,000
in noch mehr Brocken da die gepolsterte chunk muss kleiner sein als n.

290
00:17:57,000 --> 00:18:01,000
Verschlüsselung und Entschlüsselung sind relativ teuer mit RSA,

291
00:18:01,000 --> 00:18:05,000
und so braucht zu brechen eine Nachricht in viele Stücke können sehr kostspielig sein.

292
00:18:05,000 --> 00:18:09,000
Wenn eine große Datenmenge muss verschlüsselt und entschlüsselt

293
00:18:09,000 --> 00:18:12,000
Wir kombinieren die Vorteile der symmetrischen Schlüssel-Algorithmen

294
00:18:12,000 --> 00:18:16,000
mit denen von RSA, um sowohl die Sicherheit und Effizienz.

295
00:18:16,000 --> 00:18:18,000
Obwohl wir nicht in sie hier gehen,

296
00:18:18,000 --> 00:18:23,000
AES ist ein symmetrischer Schlüssel-Algorithmus wie der Vigenère und Caesar Chiffren

297
00:18:23,000 --> 00:18:25,000
aber viel schwerer zu knacken.

298
00:18:25,000 --> 00:18:30,000
Natürlich können wir nicht verwenden AES ohne eine gemeinsamen geheimen Schlüssel

299
00:18:30,000 --> 00:18:34,000
zwischen den 2 Systemen, und wir sahen das Problem mit, dass vor.

300
00:18:34,000 --> 00:18:40,000
Aber jetzt können wir RSA an, den gemeinsamen geheimen Schlüssel zwischen den 2 Systemen zu etablieren.

301
00:18:40,000 --> 00:18:43,000
Wir rufen Sie den Computer das Senden der Daten des Absenders

302
00:18:43,000 --> 00:18:46,000
und der Computer die Daten empfängt, den Empfänger.

303
00:18:46,000 --> 00:18:49,000
Der Receiver verfügt über ein RSA-Schlüsselpaar und sendet

304
00:18:49,000 --> 00:18:51,000
der öffentliche Schlüssel an den Absender.

305
00:18:51,000 --> 00:18:54,000
Der Absender erzeugt einen AES-Schlüssel,

306
00:18:54,000 --> 00:18:57,000
verschlüsselt sie mit der Receiver-öffentlichen RSA-Schlüssel,

307
00:18:57,000 --> 00:19:00,000
und sendet die AES-Schlüssel an den Empfänger.

308
00:19:00,000 --> 00:19:04,000
Der Empfänger entschlüsselt die Nachricht mit seinem privaten RSA-Schlüssel.

309
00:19:04,000 --> 00:19:09,000
Sowohl der Sender als auch der Empfänger haben nun eine gemeinsame AES-Schlüssel zwischen ihnen.

310
00:19:09,000 --> 00:19:14,000
AES, die viel schneller Ver-und Entschlüsselung als RSA ist,

311
00:19:14,000 --> 00:19:18,000
kann nun verwendet werden, um die großen Datenmengen verschlüsseln und senden sie an den Empfänger,

312
00:19:18,000 --> 00:19:21,000
wer kann entschlüsseln mit dem gleichen Schlüssel.

313
00:19:21,000 --> 00:19:26,000
AES, die viel schneller Ver-und Entschlüsselung als RSA ist,

314
00:19:26,000 --> 00:19:30,000
kann nun verwendet werden, um die großen Datenmengen verschlüsseln und senden sie an den Empfänger,

315
00:19:30,000 --> 00:19:32,000
wer kann entschlüsseln mit dem gleichen Schlüssel.

316
00:19:32,000 --> 00:19:36,000
Wir brauchten nur RSA, um die gemeinsamen Schlüssel übertragen.

317
00:19:36,000 --> 00:19:40,000
Wir müssen nicht mehr RSA zu benutzen.

318
00:19:40,000 --> 00:19:46,000
Es sieht aus wie ich eine Nachricht habe.

319
00:19:46,000 --> 00:19:49,000
Es spielt keine Rolle, ob jemand lesen, was auf dem Papier Flugzeug, bevor ich es erwischt

320
00:19:49,000 --> 00:19:55,000
weil ich der einzige mit dem privaten Schlüssel bin.

321
00:19:55,000 --> 00:19:57,000
Lassen Entschlüsseln jedes der Stücke in der Nachricht.

322
00:19:57,000 --> 00:20:07,000
Das erste Stück, 658, erhöhen wir die d Macht, die 185 ist,

323
00:20:07,000 --> 00:20:18,000
mod n, die 989 ist, ist gleich 67,

324
00:20:18,000 --> 00:20:24,000
das ist der Buchstabe C in ASCII.

325
00:20:24,000 --> 00:20:31,000
Nun, auf dem zweiten Block kommt.

326
00:20:31,000 --> 00:20:35,000
Das zweite Stück hat den Wert 15,

327
00:20:35,000 --> 00:20:41,000
die wir an den 185. potenzieren,

328
00:20:41,000 --> 00:20:51,000
mod 989, und diese ist gleich 83

329
00:20:51,000 --> 00:20:57,000
das ist der Buchstabe S in ASCII.

330
00:20:57,000 --> 00:21:06,000
Nun zum dritten Brocken, die den Wert 799 hat, haben wir auf 185 zu erhöhen,

331
00:21:06,000 --> 00:21:17,000
mod 989, und dies ist gleich 53,

332
00:21:17,000 --> 00:21:24,000
das ist der Wert des Zeichens 5 in ASCII.

333
00:21:24,000 --> 00:21:30,000
Nun zum letzten Stück hat, welcher Wert 975,

334
00:21:30,000 --> 00:21:41,000
erheben wir bis 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
und dies ist gleich 48, die Wert des Zeichens 0 in ASCII ist.

336
00:21:51,000 --> 00:21:57,000
Mein Name ist Rob Bowden, und dies ist CS50.

337
00:21:57,000 --> 00:22:00,000
[CS50.TV]

338
00:22:06,000 --> 00:22:08,000
RSA überhaupt.

339
00:22:08,000 --> 00:22:14,000
RSA überhaupt. [Gelächter]

340
00:22:14,000 --> 00:22:17,000
Überhaupt.