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
[To jest CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Rzućmy okiem na RSA, powszechnie stosowany algorytm szyfrowania danych.

5
00:00:11,000 --> 00:00:16,000
Algorytmy szyfrujące jak Cezar i szyfrów Vigenère nie są bardzo bezpieczne.

6
00:00:16,000 --> 00:00:20,000
Z szyfru Cezara, atakujący musi tylko spróbować 25 różnych kluczy

7
00:00:20,000 --> 00:00:22,000
na otrzymanie wiadomości na zwykły tekst.

8
00:00:22,000 --> 00:00:25,000
Podczas szyfrowania Vigenère jest bardziej bezpieczny niż szyfr Cezara

9
00:00:25,000 --> 00:00:28,000
z powodu większej przestrzeni szukać kluczy, raz napastnik

10
00:00:28,000 --> 00:00:30,000
wie długości klucza w szyfr Vigenère

11
00:00:30,000 --> 00:00:34,000
co można stwierdzić poprzez analizę wzorców w zaszyfrowanym tekście,

12
00:00:34,000 --> 00:00:38,000
Szyfr Vigenère nie jest dużo bardziej bezpieczny niż Cezara szyfru.

13
00:00:38,000 --> 00:00:42,000
RSA, z drugiej strony, nie jest wrażliwe na takie ataki.

14
00:00:42,000 --> 00:00:45,000
Caesar szyfr i Vigenère szyfr używać tego samego klucza

15
00:00:45,000 --> 00:00:47,000
zarówno do szyfrowania i deszyfrowania wiadomości.

16
00:00:47,000 --> 00:00:51,000
Ta właściwość sprawia, że ​​te szyfrów symetrycznych algorytmów kluczowych.

17
00:00:51,000 --> 00:00:54,000
Podstawowym problemem algorytmów symetrycznych kluczowych

18
00:00:54,000 --> 00:00:57,000
jest to, że opierają się one na jednej szyfrowania i wysyłania wiadomości

19
00:00:57,000 --> 00:00:59,000
i jeden odbiór i odszyfrowywania wiadomości

20
00:00:59,000 --> 00:01:03,000
aby uzgodniły już Upfront klawisza spowoduje oboje używają.

21
00:01:03,000 --> 00:01:06,000
Ale mamy trochę problem z uruchamianiem się tutaj.

22
00:01:06,000 --> 00:01:10,000
Jak 2 komputery, które chcą komunikować ustalenia tajnego klucza pomiędzy nimi?

23
00:01:10,000 --> 00:01:16,000
Jeśli klucz musi być tajne, to musimy znaleźć sposób na szyfrowanie i deszyfrowanie klucza.

24
00:01:16,000 --> 00:01:18,000
Jeśli wszystko, co mamy jest symetryczny klucz kryptograficzny

25
00:01:18,000 --> 00:01:21,000
wtedy właśnie wrócić do tego samego problemu.

26
00:01:21,000 --> 00:01:25,000
RSA, z drugiej strony, wykorzystuje parę kluczy,

27
00:01:25,000 --> 00:01:28,000
jeden do szyfrowania, a drugi do deszyfrowania.

28
00:01:28,000 --> 00:01:32,000
Jeden z nich to klucz publiczny, a drugi klucz prywatny.

29
00:01:32,000 --> 00:01:34,000
Klucz publiczny jest używany do szyfrowania wiadomości.

30
00:01:34,000 --> 00:01:38,000
Jak można się domyślić z nazwy, możemy dzielić się z klucza publicznego

31
00:01:38,000 --> 00:01:43,000
ktoś chcemy bez narażania bezpieczeństwa zaszyfrowanej wiadomości.

32
00:01:43,000 --> 00:01:45,000
Wiadomości zaszyfrowane przy użyciu klucza publicznego

33
00:01:45,000 --> 00:01:49,000
mogą być odszyfrowane tylko z odpowiadającym mu kluczem prywatnym.

34
00:01:49,000 --> 00:01:53,000
Chociaż można udostępnić swój klucz publiczny, należy zawsze zachować w tajemnicy klucza prywatnego.

61
00:01:55,000 --> 00:01:58,000
i tylko klucz prywatny może być użyty do deszyfrowania komunikatów

62
00:01:58,000 --> 00:02:02,000
jeśli 2 użytkownicy chcą wysyłać wiadomości szyfrowane RSA

63
00:02:02,000 --> 00:02:07,000
iz powrotem, obaj użytkownicy muszą mieć własne publicznego i prywatnego pary kluczy.

64
00:02:07,000 --> 00:02:10,000
Wiadomości od użytkownika do użytkownika 2 1

65
00:02:10,000 --> 00:02:15,000
używać tylko 2 pary kluczy użytkownika, oraz wiadomości od użytkownika do użytkownika 1 2

66
00:02:15,000 --> 00:02:17,000
używać tylko parę kluczy użytkownika 1 jest.

67
00:02:17,000 --> 00:02:21,000
Fakt, że są 2 oddzielne klucze do szyfrowania i deszyfrowania wiadomości

68
00:02:21,000 --> 00:02:24,000
sprawia RSA klucz asymetrycznego algorytmu.

69
00:02:24,000 --> 00:02:28,000
Nie potrzebujemy do szyfrowania klucza publicznego w celu wysłania go do innego komputera

70
00:02:28,000 --> 00:02:31,000
ponieważ klucz publiczny i tak.

71
00:02:31,000 --> 00:02:33,000
Oznacza to, że nie posiada RSA tego samego problemu uruchamiania

72
00:02:33,000 --> 00:02:36,000
jak algorytmów symetrycznych kluczy.

73
00:02:36,000 --> 00:02:39,000
Więc jeśli chcesz wysłać wiadomość, używając szyfrowania RSA

74
00:02:39,000 --> 00:02:42,000
okraść, ja najpierw klucza publicznego Roba.

75
00:02:42,000 --> 00:02:47,000
Aby wygenerować parę kluczy, Rob musi wybrać 2 dużych liczb pierwszych.

76
00:02:47,000 --> 00:02:50,000
Numery te będą wykorzystywane w obu kluczy publicznych i prywatnych,

77
00:02:50,000 --> 00:02:54,000
ale klucz publiczny będzie jedynie korzystać z produktu z tych 2 liczb

78
00:02:54,000 --> 00:02:56,000
nie same numery.

79
00:02:56,000 --> 00:02:59,000
Kiedy już zaszyfrowane wiadomości, używając klucza publicznego Roba

80
00:02:59,000 --> 00:03:01,000
Mogę wysłać wiadomość do Rob.

81
00:03:01,000 --> 00:03:05,000
W przypadku komputera, numery faktoringowych jest trudnym problemem.

82
00:03:05,000 --> 00:03:09,000
Klucza publicznego, pamiętaj, używany produkt z 2 liczb pierwszych.

83
00:03:09,000 --> 00:03:12,000
Ten produkt musi mieć tylko 2 czynniki,

84
00:03:12,000 --> 00:03:16,000
które stało się numery, które tworzą klucz prywatny.

85
00:03:16,000 --> 00:03:20,000
W celu odszyfrowania wiadomości, RSA użyje tego klucza prywatnego

86
00:03:20,000 --> 00:03:25,000
lub numery mnożone w procesie tworzenia klucza publicznego.

87
00:03:25,000 --> 00:03:28,000
Bo to jest obliczeniowo trudne uwzględniać liczbę

88
00:03:28,000 --> 00:03:32,000
używane klucza publicznego do wartości podanych w 2 klucza prywatnego

89
00:03:32,000 --> 00:03:36,000
trudno jest atakująca dowiedzieć klucz prywatny

90
00:03:36,000 --> 00:03:39,000
będzie konieczne odszyfrować komunikat.

91
00:03:39,000 --> 00:03:43,000
Teraz chodźmy do niektórych niższych szczegółów szczebla RSA.

92
00:03:43,000 --> 00:03:46,000
Niech najpierw zobaczyć, jak można wygenerować parę kluczy.

93
00:03:46,000 --> 00:03:49,000
Po pierwsze, musimy 2 liczb pierwszych.

94
00:03:49,000 --> 00:03:52,000
Nazwijmy te 2 liczby p i q.

95
00:03:52,000 --> 00:03:56,000
W celu odebrania P i Q, w praktyce będziemy pseudorandomly generować

96
00:03:56,000 --> 00:03:59,000
duża liczba, a następnie użyć test dla stwierdzenia, czy

97
00:03:59,000 --> 00:04:02,000
te numery są chyba pierwsze.

98
00:04:02,000 --> 00:04:05,000
Możemy informować generowania liczb losowych w kółko

99
00:04:05,000 --> 00:04:08,000
dopóki mamy 2 liczby pierwsze, które możemy wykorzystać.

100
00:04:08,000 --> 00:04:15,000
Tutaj niech odebrać p = 23 i Q = 43.

101
00:04:15,000 --> 00:04:19,000
Należy pamiętać, że w praktyce i p powinny być większe numery.

102
00:04:19,000 --> 00:04:22,000
O ile nam wiadomo, większe liczby, tym trudniej jest

103
00:04:22,000 --> 00:04:25,000
złamać zaszyfrowaną wiadomość.

104
00:04:25,000 --> 00:04:29,000
Ale jest to także droższe do szyfrowania i deszyfrowania wiadomości.

105
00:04:29,000 --> 00:04:33,000
Dziś często jest zalecane piq są co najmniej 1024 bitów,

106
00:04:33,000 --> 00:04:37,000
co stawia każdy numer na ponad 300 miejsc po przecinku.

107
00:04:37,000 --> 00:04:40,000
Ale będziemy wybierać te małe liczby, dla przykładu.

108
00:04:40,000 --> 00:04:43,000
Teraz mnożymy p oraz q, aby otrzymać 3rd numer,

109
00:04:43,000 --> 00:04:45,000
które będziemy nazywać n.

110
00:04:45,000 --> 00:04:55,000
W naszym przypadku n = 23 * 43 = 989 co.

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

112
00:04:58,000 --> 00:05:02,000
Dalej będziemy mnożyć p - 1 gdzie q - 1

113
00:05:02,000 --> 00:05:05,000
uzyskania 4-sze numer, który my nazywamy M.

114
00:05:05,000 --> 00:05:15,000
W naszym przypadku, m = 22 * ​​42 = 924 co.

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

116
00:05:18,000 --> 00:05:22,000
Teraz potrzebujemy liczba e, która jest względnie pierwsze z m

117
00:05:22,000 --> 00:05:25,000
m, a mniej niż.

118
00:05:25,000 --> 00:05:28,000
Dwie liczby są względnie pierwsze lub względnie pierwsze

119
00:05:28,000 --> 00:05:33,000
jeśli tylko dodatnia, że ​​dzieli ich zarówno równomiernie jest 1.

120
00:05:33,000 --> 00:05:37,000
Innymi słowy, największy wspólny dzielnik E i M

121
00:05:37,000 --> 00:05:39,000
musi być 1.

122
00:05:39,000 --> 00:05:44,000
W praktyce często zdarza się, e jest liczbą 65537

123
00:05:44,000 --> 00:05:48,000
dopóki ta liczba nie stało się czynnikiem m.

124
00:05:48,000 --> 00:05:53,000
Dla naszych kluczy, będziemy pick e = 5

125
00:05:53,000 --> 00:05:57,000
od 5 jest względnie pierwsze z 924.

126
00:05:57,000 --> 00:06:01,000
Wreszcie, musimy jeszcze jeden numer, który my nazywamy d.

127
00:06:01,000 --> 00:06:11,000
D musi być jakaś wartość, która spełnia równanie de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Ten mod m oznacza użyjemy coś zwane modułowe arytmetyki.

129
00:06:17,000 --> 00:06:21,000
W arytmetyce modularnej, raz liczba jest wyższa niż niektóre górne

130
00:06:21,000 --> 00:06:24,000
będzie zawijać powraca do 0.

131
00:06:24,000 --> 00:06:27,000
Zegara, na przykład, stosuje modułową arytmetycznych.

132
00:06:27,000 --> 00:06:31,000
Minutę po 01:59, na przykład, jest 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Minut ręka owinięta do 0

135
00:06:36,000 --> 00:06:39,000
po osiągnięciu górnej granicy 60.

136
00:06:39,000 --> 00:06:46,000
Więc można powiedzieć, 60 odpowiada 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
i 125 do 65 odpowiada odpowiada 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Nasz klucz publiczny będzie para i n e

139
00:07:02,000 --> 00:07:09,000
w tym przypadku, gdy jest 5 i e n 989.

140
00:07:09,000 --> 00:07:15,000
Nasz klucz prywatny będzie parę D, N,

141
00:07:15,000 --> 00:07:22,000
co w naszym przypadku jest 185 i 989.

142
00:07:22,000 --> 00:07:25,000
Zauważ, że nasze oryginalne liczby pierwsze p i q nie pojawiają

143
00:07:25,000 --> 00:07:29,000
wszędzie w naszych kluczy prywatnych lub publicznych.

144
00:07:29,000 --> 00:07:33,000
Teraz, gdy mamy parę kluczy, rzućmy okiem na to, jak możemy szyfrować

145
00:07:33,000 --> 00:07:36,000
i deszyfrowania wiadomości.

146
00:07:36,000 --> 00:07:38,000
Chcę wysłać wiadomość do Roba,

147
00:07:38,000 --> 00:07:42,000
tak, że będzie jeden do wygenerowania tego pary kluczy.

148
00:07:42,000 --> 00:07:46,000
Potem pytam Rob jego kluczem publicznym, który będziesz używać

149
00:07:46,000 --> 00:07:48,000
zaszyfrować wiadomość, aby wysłać do niego.

150
00:07:48,000 --> 00:07:53,000
Pamiętaj, że jest to całkowicie w porządku dla Rob do akcji jego klucz publiczny, ze mną.

151
00:07:53,000 --> 00:07:56,000
Ale to nie byłoby w porządku do akcji swojego klucza prywatnego.

152
00:07:56,000 --> 00:08:00,000
Nie mam pojęcia, co jego klucz prywatny jest.

153
00:08:00,000 --> 00:08:03,000
Możemy przełamać naszą m wiadomość na kilka kawałków

154
00:08:03,000 --> 00:08:07,000
wszystkie mniejsze niż N, a następnie każdy z tych szyfrowania kawałki.

155
00:08:07,000 --> 00:08:12,000
Będziemy zaszyfrować CS50 sznurka, którym możemy przerwać na 4 kawałki,

156
00:08:12,000 --> 00:08:14,000
jeden na liście.

157
00:08:14,000 --> 00:08:17,000
Aby zaszyfrować moją wiadomość, będę potrzebował do przekształcenia

158
00:08:17,000 --> 00:08:20,000
jakaś numerycznej reprezentacji.

159
00:08:20,000 --> 00:08:25,000
Miejmy złączyć wartości ASCII z bohaterów mojej wiadomości.

160
00:08:25,000 --> 00:08:28,000
Aby zaszyfrować daną wiadomość m

161
00:08:28,000 --> 00:08:37,000
Będę potrzebował do obliczenia C = M na e (mod n).

162
00:08:37,000 --> 00:08:40,000
M, ale może być mniejsza niż N,

163
00:08:40,000 --> 00:08:45,000
albo pełna wiadomość nie może zostać wyrażona modulo n.

164
00:08:45,000 --> 00:08:49,000
M można przerwać na kilka fragmentów, z których wszystkie są mniejsze niż N,

165
00:08:49,000 --> 00:08:52,000
i szyfrowania każdego z tych kawałków.

166
00:08:52,000 --> 00:09:03,000
Szyfrowanie każdy z tych kawałków, mamy c1 = 67 do 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Na naszym drugim fragmencie mamy 83 do 5 (mod 989)

169
00:09:15,000 --> 00:09:18,000
= 15, który.

170
00:09:18,000 --> 00:09:26,000
Na naszym trzecim fragmencie mamy 53 do 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
I wreszcie, na nasz ostatni kawałek mamy 48 do 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Teraz możemy wysłać na te zakodowane wartości Rob.

175
00:09:54,000 --> 00:09:58,000
Proszę, Rob.

176
00:09:58,000 --> 00:10:01,000
Podczas gdy nasz komunikat jest w locie, weźmy inny wygląd

177
00:10:01,000 --> 00:10:07,000
w jaki sposób mam to wartość dla d.

178
00:10:07,000 --> 00:10:17,000
Nasz numer d potrzebne do zaspokojenia 5D = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
To sprawia, że ​​d multiplicative odwrotność 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Podane 2 liczby całkowite, i B, rozszerzony algorytm Euklidesa

181
00:10:28,000 --> 00:10:33,000
można znaleźć największy wspólny dzielnik tych 2 liczb.

182
00:10:33,000 --> 00:10:37,000
Będzie on również dać nam 2 inne numery, X i Y,

183
00:10:37,000 --> 00:10:47,000
które spełniają równanie ax + by = największego wspólnego dzielnika A i B.

184
00:10:47,000 --> 00:10:49,000
Jak to nam pomoże?

185
00:10:49,000 --> 00:10:52,000
Cóż, podłączając e = 5 dla

186
00:10:52,000 --> 00:10:56,000
i M = 924 b dla

187
00:10:56,000 --> 00:10:59,000
już wiemy, że te liczby są względnie pierwsze.

188
00:10:59,000 --> 00:11:03,000
Ich największy wspólny dzielnik jest 1.

189
00:11:03,000 --> 00:11:09,000
To daje nam 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Ale jeśli tylko o wszystko modulo 924

192
00:11:22,000 --> 00:11:25,000
wtedy możemy upuścić - 924y.

193
00:11:25,000 --> 00:11:27,000
Pomyśl o zegarze.

194
00:11:27,000 --> 00:11:31,000
Jeśli minut ręka jest na 1, a następnie dokładnie 10 godziny mijają,

195
00:11:31,000 --> 00:11:35,000
wiemy minut ręka nadal będzie na 1.

196
00:11:35,000 --> 00:11:39,000
Tu zaczynają się od 1, a następnie owinąć wokół dokładnie y razy,

197
00:11:39,000 --> 00:11:41,000
więc będziemy nadal w 1.

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

199
00:11:49,000 --> 00:11:55,000
I tu w x jest taka sama, jak D szukaliśmy wcześniej

200
00:11:55,000 --> 00:11:58,000
więc jeśli używamy rozszerzonego algorytmu Euklidesa

201
00:11:58,000 --> 00:12:04,000
otrzymaj liczby x, to liczba powinniśmy używać jako naszego d.

202
00:12:04,000 --> 00:12:07,000
Teraz uruchom rozszerzony algorytm Euklidesa dla a = 5

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

204
00:12:11,000 --> 00:12:14,000
Użyjemy metodę zwaną metodą tabeli.

205
00:12:14,000 --> 00:12:21,000
Nasza tabela będzie miała 4 kolumny, x, y, d, k.

206
00:12:21,000 --> 00:12:23,000
Nasza tabela zaczyna się z 2 wierszy.

207
00:12:23,000 --> 00:12:28,000
W pierwszym wierszu mamy 1, 0, wówczas nasza wartość, która jest 5,

208
00:12:28,000 --> 00:12:37,000
i drugi rząd nasz oznacza 0, 1, a dla naszych B, która jest 924.

209
00:12:37,000 --> 00:12:40,000
Wartość 4. k kolumnie, będzie wynikiem

210
00:12:40,000 --> 00:12:45,000
podziału wartości D w wierszu nad nim z wartości d

211
00:12:45,000 --> 00:12:49,000
w tym samym rzędzie.

212
00:12:49,000 --> 00:12:56,000
Mamy 5 podzielić przez 924 wynosi 0 z pewnym reszty.

213
00:12:56,000 --> 00:12:59,000
To oznacza, że ​​mamy k = 0.

214
00:12:59,000 --> 00:13:05,000
Teraz wartość każdej innej komórce będzie wartość komórki 2 rzędach nad nim

215
00:13:05,000 --> 00:13:09,000
minus wartość wiersza ponad nim k razy.

216
00:13:09,000 --> 00:13:11,000
Zacznijmy d w 3 rzędzie.

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

218
00:13:19,000 --> 00:13:25,000
Następnie mamy 0 - 1 * 0, który jest 0

219
00:13:25,000 --> 00:13:30,000
i 1 - 0 * 0, który jest 1.

220
00:13:30,000 --> 00:13:33,000
Nie jest tak źle, więc przejdźmy do następnego wiersza.

221
00:13:33,000 --> 00:13:36,000
Najpierw musimy naszą wartość k.

222
00:13:36,000 --> 00:13:43,000
924 podzielone przez 5 = 184 z jakimś pozostałym

223
00:13:43,000 --> 00:13:46,000
więc nasz stosunek k jest 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Dobra, zróbmy następny wiersz.

227
00:14:07,000 --> 00:14:10,000
Nasza wartość k będzie 1, bo

228
00:14:10,000 --> 00:14:15,000
5 podzielić przez 4 = 1 z niektórych pozostały.

229
00:14:15,000 --> 00:14:17,000
Miejmy wypełnienie innych kolumn.

230
00:14:17,000 --> 00:14:21,000
5 - 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
I 1 - 184 185 * 1 jest.

233
00:14:33,000 --> 00:14:35,000
Zobaczmy, co nasz następny Wartość k będzie.

234
00:14:35,000 --> 00:14:40,000
Cóż, wygląda na to, że mamy 4 podzielone przez 1, czyli 4.

235
00:14:40,000 --> 00:14:43,000
W tym przypadku, gdy mamy do podziału przez 1, że k równe jest

236
00:14:43,000 --> 00:14:50,000
wartość D w powyższym wierszu oznacza, że ​​skończyliśmy z naszego algorytmu.

237
00:14:50,000 --> 00:14:58,000
Widzimy tutaj, że mamy x = 185, y = -1 w ostatnim rzędzie.

238
00:14:58,000 --> 00:15:00,000
Zróbmy teraz wrócić do naszego pierwotnego celu.

239
00:15:00,000 --> 00:15:04,000
Stwierdziliśmy, że wartość x w wyniku prowadzenia tego algorytmu

240
00:15:04,000 --> 00:15:08,000
będzie w mnożnikowy (odwrotność mod b).

241
00:15:08,000 --> 00:15:15,000
Oznacza to, że 185 z 5 odwrotna mnożnikowy (mod 924)

242
00:15:15,000 --> 00:15:20,000
co oznacza, że ​​mają wartość 185 do D.

243
00:15:20,000 --> 00:15:23,000
Fakt, że d = 1 w ostatnim wierszu

244
00:15:23,000 --> 00:15:26,000
sprawdza, e był względnie pierwsze m.

245
00:15:26,000 --> 00:15:30,000
Gdyby nie 1, a następnie będziemy musieli wybrać nowy e.

246
00:15:30,000 --> 00:15:33,000
Teraz zobaczymy, czy Rob otrzymał mojej wiadomości.

247
00:15:33,000 --> 00:15:35,000
Gdy ktoś wyśle ​​do mnie zaszyfrowaną wiadomość

248
00:15:35,000 --> 00:15:38,000
tak długo, jak ja trzymałem klucz prywatny sekret

249
00:15:38,000 --> 00:15:41,000
Jestem jedynym, który może odszyfrować wiadomość.

250
00:15:41,000 --> 00:15:46,000
Aby odszyfrować kawałek c można obliczyć oryginalną wiadomość

251
00:15:46,000 --> 00:15:53,000
jest równa części do potęgi d (mod n).

252
00:15:53,000 --> 00:15:57,000
Pamiętaj, że d i n są z mojego klucza prywatnego.

253
00:15:57,000 --> 00:16:01,000
Aby uzyskać pełną wiadomość od jego kawałki możemy odszyfrować każda porcja

254
00:16:01,000 --> 00:16:04,000
i łączyć wyniki.

255
00:16:04,000 --> 00:16:08,000
Dokładnie tak, jak bezpieczny jest RSA?

256
00:16:08,000 --> 00:16:10,000
Prawda jest taka, że ​​nie wiemy.

257
00:16:10,000 --> 00:16:14,000
Bezpieczeństwo opiera się na jak długo potrwa atakującemu złamać wiadomość

258
00:16:14,000 --> 00:16:16,000
szyfrowane RSA.

259
00:16:16,000 --> 00:16:19,000
Pamiętaj, że atakujący ma dostęp do klucza publicznego,

260
00:16:19,000 --> 00:16:21,000
który zawiera zarówno e i n.

261
00:16:21,000 --> 00:16:26,000
Jeśli atakujący zdoła czynnik N do swoich 2 liczb pierwszych, P i Q,

262
00:16:26,000 --> 00:16:30,000
następnie mogła obliczyć D Korzystanie rozszerzony algorytm Euklidesa.

263
00:16:30,000 --> 00:16:35,000
To daje jej klucz prywatny, który może być użyty do odszyfrowania każda wiadomość.

264
00:16:35,000 --> 00:16:38,000
Ale jak szybko możemy uwzględniać liczby całkowite?

265
00:16:38,000 --> 00:16:41,000
Ponownie, nie wiem.

266
00:16:41,000 --> 00:16:43,000
Nikt nie znalazł szybki sposób to robić,

267
00:16:43,000 --> 00:16:46,000
co oznacza, że ​​z uwagi na tyle duża N

268
00:16:46,000 --> 00:16:49,000
zajęłoby atakującemu nierealistycznie długi

269
00:16:49,000 --> 00:16:51,000
do czynnika numer.

270
00:16:51,000 --> 00:16:54,000
Jeśli ktoś ujawnił szybki sposób liczb faktoringowych

271
00:16:54,000 --> 00:16:57,000
RSA będzie złamane.

272
00:16:57,000 --> 00:17:01,000
Ale nawet jeśli na czynniki z natury powolne całkowitą

273
00:17:01,000 --> 00:17:04,000
algorytm RSA może jeszcze trochę w nim błąd

274
00:17:04,000 --> 00:17:07,000
, że pozwala na łatwe deszyfrowania komunikatów.

275
00:17:07,000 --> 00:17:10,000
Nikt nie znalazł i ujawnił taką wadę jeszcze,

276
00:17:10,000 --> 00:17:12,000
ale to nie znaczy, nie istnieje.

277
00:17:12,000 --> 00:17:17,000
W teorii, ktoś może być tam czytanie wszystkich danych zaszyfrowanych przy RSA.

278
00:17:17,000 --> 00:17:19,000
Jest jeszcze trochę kwestii prywatności.

279
00:17:19,000 --> 00:17:23,000
Jeśli Tommy szyfruje jakąś wiadomość używając mojego klucza publicznego

280
00:17:23,000 --> 00:17:26,000
i napastnik szyfruje sam komunikat używając mojego klucza publicznego

281
00:17:26,000 --> 00:17:29,000
napastnik będzie wiedział, że 2 komunikaty są identyczne

282
00:17:29,000 --> 00:17:32,000
a więc wiem, co Tommy zaszyfrowane.

283
00:17:32,000 --> 00:17:36,000
W celu zapobieżenia temu, komunikaty są zwykle wypełniane przypadkowych bitów

284
00:17:36,000 --> 00:17:39,000
zanim zostały zaszyfrowane tak, że sama wiadomość zaszyfrowana

285
00:17:39,000 --> 00:17:44,000
Wielokrotne wygląda inaczej ile dopełnienie w komunikacie jest inny.

286
00:17:44,000 --> 00:17:47,000
Ale pamiętam, jak mamy podzielić wiadomości na kawałki

287
00:17:47,000 --> 00:17:50,000
, tak że każdy kawałek jest mniejsza niż N?

288
00:17:50,000 --> 00:17:52,000
Wypychanie na kawałki oznacza, że ​​możemy mieć do podziału rzeczy

289
00:17:52,000 --> 00:17:57,000
do jeszcze większej liczby kawałków od wyściełane kawałek musi być mniejsza niż n.

290
00:17:57,000 --> 00:18:01,000
Szyfrowanie i deszyfrowanie są stosunkowo drogie z RSA,

291
00:18:01,000 --> 00:18:05,000
więc potrzeby rozbijania wiadomość do wielu kawałków może być bardzo kosztowne.

292
00:18:05,000 --> 00:18:09,000
Jeśli duża ilość danych musi być zaszyfrowane i odszyfrowane

293
00:18:09,000 --> 00:18:12,000
możemy połączyć zalety kluczowych algorytmów symetrycznych

294
00:18:12,000 --> 00:18:16,000
z tymi z RSA, aby bezpieczeństwo i skuteczność.

295
00:18:16,000 --> 00:18:18,000
Mimo, że nie będziemy się tym tutaj,

296
00:18:18,000 --> 00:18:23,000
AES jest klucz symetryczny algorytm jak Vigenère i szyfry Cezara

297
00:18:23,000 --> 00:18:25,000
ale znacznie trudniejsze do złamania.

298
00:18:25,000 --> 00:18:30,000
Oczywiście, nie możemy użyć AES bez ustanowienia wspólnego klucza tajnego

299
00:18:30,000 --> 00:18:34,000
między 2 systemów, i widzieliśmy problemu z tym wcześniej.

300
00:18:34,000 --> 00:18:40,000
Ale teraz możemy użyć RSA w celu ustalenia wspólnego tajnego klucza pomiędzy 2 systemami.

301
00:18:40,000 --> 00:18:43,000
Zadzwonimy do komputera przesyłającego dane nadawcy

302
00:18:43,000 --> 00:18:46,000
a komputer odbiera dane do odbiornika.

303
00:18:46,000 --> 00:18:49,000
Odbiornik posiada parę kluczy RSA i wysyła

304
00:18:49,000 --> 00:18:51,000
klucza publicznego nadawcy.

305
00:18:51,000 --> 00:18:54,000
Nadawca generuje klucz AES,

306
00:18:54,000 --> 00:18:57,000
szyfruje go z odbiornika RSA klucz publiczny,

307
00:18:57,000 --> 00:19:00,000
klucz i wysyła do odbiornika AES.

308
00:19:00,000 --> 00:19:04,000
Odbiornik dekoduje komunikat z jego klucz prywatny RSA.

309
00:19:04,000 --> 00:19:09,000
Zarówno nadawca, jak i odbiorca mają teraz wspólnego klucza AES między nimi.

310
00:19:09,000 --> 00:19:14,000
AES, który jest znacznie szybciej niż szyfrowania i deszyfrowania RSA,

311
00:19:14,000 --> 00:19:18,000
mogą być teraz używane do szyfrowania dużych ilości danych i wysyłanie ich do odbiornika,

312
00:19:18,000 --> 00:19:21,000
kto może odszyfrować przy użyciu tego samego klucza.

313
00:19:21,000 --> 00:19:26,000
AES, który jest znacznie szybciej niż szyfrowania i deszyfrowania RSA,

314
00:19:26,000 --> 00:19:30,000
mogą być teraz używane do szyfrowania dużych ilości danych i wysyłanie ich do odbiornika,

315
00:19:30,000 --> 00:19:32,000
kto może odszyfrować przy użyciu tego samego klucza.

316
00:19:32,000 --> 00:19:36,000
Potrzebowaliśmy jedynie RSA przenieść klucz udostępniany.

317
00:19:36,000 --> 00:19:40,000
Nie musimy już używać RSA wcale.

318
00:19:40,000 --> 00:19:46,000
Wygląda na to, mam wiadomość.

319
00:19:46,000 --> 00:19:49,000
To nie ma znaczenia, czy ktoś odczytać, co jest na papierze, zanim samolot złapał

320
00:19:49,000 --> 00:19:55,000
bo ja jestem tylko jednym z kluczem prywatnym.

321
00:19:55,000 --> 00:19:57,000
Załóżmy, deszyfrowanie każdego z kawałków w komunikacie.

322
00:19:57,000 --> 00:20:07,000
Pierwszy kawałek, 658, wznosimy się do d mocy, co jest 185,

323
00:20:07,000 --> 00:20:18,000
mod n, która jest 989, jest równa 67,

324
00:20:18,000 --> 00:20:24,000
co jest litera C w ASCII.

325
00:20:24,000 --> 00:20:31,000
Teraz, na drugim kawałku.

326
00:20:31,000 --> 00:20:35,000
Drugi fragment ma wartość 15,

327
00:20:35,000 --> 00:20:41,000
które wędrują na 185-sze władzy,

328
00:20:41,000 --> 00:20:51,000
mod 989, i wynosi ona 83

329
00:20:51,000 --> 00:20:57,000
która jest literą S w ASCII.

330
00:20:57,000 --> 00:21:06,000
Teraz w trzecim fragmencie, który ma wartość 799, to podnieść do 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, i wynosi ona 53,

332
00:21:17,000 --> 00:21:24,000
która to wartość w postaci 5 ASCII.

333
00:21:24,000 --> 00:21:30,000
Teraz do ostatniego kawałka, który ma wartość 975,

334
00:21:30,000 --> 00:21:41,000
możemy podnieść do 185, 989, mod

335
00:21:41,000 --> 00:21:51,000
i to jest równe 48, co jest wartość 0 znaków w kodzie ASCII.

336
00:21:51,000 --> 00:21:57,000
Nazywam się Rob Bowden, a to CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA w ogóle.

339
00:22:08,000 --> 00:22:14,000
RSA w ogóle. [Śmiech]

340
00:22:14,000 --> 00:22:17,000
W ogóle.