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] [Harvardo universiteto]

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

4
00:00:07,000 --> 00:00:11,000
Paimkime RSA, plačiai naudojama duomenų šifravimo algoritmas atrodo.

5
00:00:11,000 --> 00:00:16,000
Šifravimo algoritmai, kaip Cezaris ir Vigenere šifrai yra nelabai saugi.

6
00:00:16,000 --> 00:00:20,000
Su Cezario šifras, užpuolikas tik reikia išbandyti 25 skirtingų kodų

7
00:00:20,000 --> 00:00:22,000
gauti Message paprastą tekstą.

8
00:00:22,000 --> 00:00:25,000
Nors Vigenere šifras yra saugesnis nei Cezario šifras

9
00:00:25,000 --> 00:00:28,000
dėl didesnių paieškos vietos raktams, kai užpuolikas

10
00:00:28,000 --> 00:00:30,000
žino į Vigenere šifravimo rakto ilgį,

11
00:00:30,000 --> 00:00:34,000
tai galima nustatyti per saugiame teksto analizės modelius,

12
00:00:34,000 --> 00:00:38,000
Vigenere šifras yra ne tai, kad daug saugesnis nei Cezario šifras.

13
00:00:38,000 --> 00:00:42,000
RSA, kita vertus, nėra pažeidžiama atakų, kaip šis.

14
00:00:42,000 --> 00:00:45,000
Cezario šifras ir Vigenere šifras naudoti tą patį klavišą

15
00:00:45,000 --> 00:00:47,000
užšifruoti ir iššifruoti pranešimų.

16
00:00:47,000 --> 00:00:51,000
Ši savybė leidžia šias šifrai simetriškai pagrindinius algoritmus.

17
00:00:51,000 --> 00:00:54,000
Pagrindinė problema, su simetrinių pagrindinių algoritmų

18
00:00:54,000 --> 00:00:57,000
yra tai, kad jie remiasi šifravimo ir siunčia pranešimą

19
00:00:57,000 --> 00:00:59,000
ir vienas, priėmimo ir iškodavimo pranešimą

20
00:00:59,000 --> 00:01:03,000
jau susitarė iš anksto, ant klavišo jie abu naudoti.

21
00:01:03,000 --> 00:01:06,000
Bet mes turime šiek tiek paleisties problemos čia.

22
00:01:06,000 --> 00:01:10,000
Kaip 2 kompiuteriai, kurie nori bendrauti nustatyti slaptą raktą tarp jų?

23
00:01:10,000 --> 00:01:16,000
Jei raktas turi būti paslaptis, tada mes turime būdą, užšifruoti ir iššifruoti raktą.

24
00:01:16,000 --> 00:01:18,000
Jei viskas, ką turime, yra simetriška rakto kriptografija

25
00:01:18,000 --> 00:01:21,000
tada mes tiesiog grįžti į tą pačią problemą.

26
00:01:21,000 --> 00:01:25,000
RSA, kita vertus, naudoja raktų porą,

27
00:01:25,000 --> 00:01:28,000
viena, kai šifravimui ir kito iššifravimo.

28
00:01:28,000 --> 00:01:32,000
Vienas yra vadinamas viešasis raktas, o kitas privatus raktas.

29
00:01:32,000 --> 00:01:34,000
Viešasis raktas naudojamas šifruoti laiškus.

30
00:01:34,000 --> 00:01:38,000
Kaip jūs galite atspėti jo pavadinimo, mes galime pasidalinti savo viešąjį raktą su

31
00:01:38,000 --> 00:01:43,000
kiekvienas norime nepakenkiant laiškas užšifruotas saugumą.

32
00:01:43,000 --> 00:01:45,000
Pranešimai šifruojami naudojant viešąjį raktą

33
00:01:45,000 --> 00:01:49,000
gali būti iššifruoti su savo atitinkamas privataus rakto.

34
00:01:49,000 --> 00:01:53,000
Nors galite pasidalinti savo viešą raktą, jūs visada turėtų išlaikyti savo asmeninio rakto paslaptis.

61
00:01:55,000 --> 00:01:58,000
ir tik privatus raktas gali būti naudojamas iššifruoti pranešimų

62
00:01:58,000 --> 00:02:02,000
jei norite siųsti pranešimus, saugiame su RSA 2 vartotojai

63
00:02:02,000 --> 00:02:07,000
pirmyn ir atgal, abu vartotojai turi turėti savo viešojo ir privataus raktų porą.

64
00:02:07,000 --> 00:02:10,000
Pranešimai user 1 2 Vartotojo

65
00:02:10,000 --> 00:02:15,000
naudoti tik Vartotojas 2 raktų porą ir pranešimus nuo 1 vartotojui 2 Vartotojo

66
00:02:15,000 --> 00:02:17,000
naudoti tik user 1 raktų porą.

67
00:02:17,000 --> 00:02:21,000
Faktas, kad yra 2 atskiri raktai, užšifruoti ir iššifruoti messages

68
00:02:21,000 --> 00:02:24,000
daro RSA asimetrinis rakto algoritmas.

69
00:02:24,000 --> 00:02:28,000
Mums nereikia šifruoti viešąjį raktą, kad būtų galima siųsti į kitą kompiuterį

70
00:02:28,000 --> 00:02:31,000
nes svarbiausia yra viešas vistiek.

71
00:02:31,000 --> 00:02:33,000
Tai reiškia, kad "RSA neturi tą patį paleisties problemą

72
00:02:33,000 --> 00:02:36,000
Simetrinių pagrindinių algoritmų.

73
00:02:36,000 --> 00:02:39,000
Taigi, jei aš noriu, kad siųsti žinutę naudojant RSA šifravimo

74
00:02:39,000 --> 00:02:42,000
apiplėšti, aš pirmiausia reikia Rob viešą raktą.

75
00:02:42,000 --> 00:02:47,000
Norėdami generuoti raktų porą, Rob reikia pasirinkti 2 dideli paprastų skaičių.

76
00:02:47,000 --> 00:02:50,000
Šie skaičiai bus naudojamas tiek viešojo ir privataus raktų,

77
00:02:50,000 --> 00:02:54,000
o viešasis raktas bus panaudoti tik 2 numeriai produktą,

78
00:02:54,000 --> 00:02:56,000
ne patys skaičiai.

79
00:02:56,000 --> 00:02:59,000
Kai aš užšifruoti pranešimą, naudojant Rob viešąjį raktą

80
00:02:59,000 --> 00:03:01,000
Galiu siųsti pranešimą Rob.

81
00:03:01,000 --> 00:03:05,000
Už kompiuterį, faktoringo numeriai yra sudėtingas uždavinys.

82
00:03:05,000 --> 00:03:09,000
Viešasis raktas, atminkite, 2 paprastais skaičiais produktą.

83
00:03:09,000 --> 00:03:12,000
Šis produktas turi turėti tik 2 veiksnius,

84
00:03:12,000 --> 00:03:16,000
, kurie atsitiktų būti skaičiai, kurie sudaro privatų raktą.

85
00:03:16,000 --> 00:03:20,000
Kad iššifruoti laiško, RSA naudoti šį privatų raktą

86
00:03:20,000 --> 00:03:25,000
arba skaičiai dauginama kartu kuriant viešąjį raktą.

87
00:03:25,000 --> 00:03:28,000
, Nes jis skaičiavimais sunku veiksnys numerį

88
00:03:28,000 --> 00:03:32,000
naudojamas viešojo rakto į 2 numerių, naudojamų privataus rakto

89
00:03:32,000 --> 00:03:36,000
sunku užpuolikas privatų raktą, išsiaiškinti,

90
00:03:36,000 --> 00:03:39,000
kad reikės iššifruoti laiško.

91
00:03:39,000 --> 00:03:43,000
Dabar eikime į kai žemesnio lygio informacijos apie RSA.

92
00:03:43,000 --> 00:03:46,000
Pirmiausia pažiūrėkime, kaip mes galime sukurti raktų porą.

93
00:03:46,000 --> 00:03:49,000
Pirma, mums reikia 2 paprastų skaičių.

94
00:03:49,000 --> 00:03:52,000
Mes paskambinsime šių 2 numeriai P ir Q.

95
00:03:52,000 --> 00:03:56,000
Siekiant gauti P ir Q, praktikoje mes pseudorandomly generuoti

96
00:03:56,000 --> 00:03:59,000
daug ir tada naudokite kriterijų, skirtą nustatyti, ar

97
00:03:59,000 --> 00:04:02,000
šie skaičiai yra turbūt svarbiausias.

98
00:04:02,000 --> 00:04:05,000
Mes galime išlaikyti generuoti atsitiktinius numerius vėl ir vėl

99
00:04:05,000 --> 00:04:08,000
kol mes turime 2 primes, kad mes galime naudoti.

100
00:04:08,000 --> 00:04:15,000
Čia leiskite pasirinkti p = 23 ir Q = 43.

101
00:04:15,000 --> 00:04:19,000
Atminkite, kad praktikoje, p ir q turi būti daug didesni skaičiai.

102
00:04:19,000 --> 00:04:22,000
Kiek mes žinome, tuo didesnis skaičių, tuo sunkiau

103
00:04:22,000 --> 00:04:25,000
nulaužti šifruotą pranešimą.

104
00:04:25,000 --> 00:04:29,000
Bet jis taip pat brangesnis užšifruoti ir iššifruoti pranešimų.

105
00:04:29,000 --> 00:04:33,000
Šiandien tai dažnai rekomenduojama, kad p ir q yra bent 1024 bitų,

106
00:04:33,000 --> 00:04:37,000
kuris nurodo kiekvieno numerio ne daugiau kaip 300 ženklų po kablelio.

107
00:04:37,000 --> 00:04:40,000
Bet mes pasirinkti šiuos mažus skaičius šiame pavyzdyje.

108
00:04:40,000 --> 00:04:43,000
Dabar mes daugintis P ir Q gauti 3rd numerį,

109
00:04:43,000 --> 00:04:45,000
kuriuos mes vadiname n.

110
00:04:45,000 --> 00:04:55,000
Mūsų atveju, n = 23 * 43 = 989.

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

112
00:04:58,000 --> 00:05:02,000
Kitas mes daugintis su q p - 1 - 1

113
00:05:02,000 --> 00:05:05,000
gauti 4. skaičių, kurį mes vadiname m.

114
00:05:05,000 --> 00:05:15,000
Mūsų atveju m = 22 * ​​42 = 924.

115
00:05:15,000 --> 00:05:18,000
Mes turime M = 924.

116
00:05:18,000 --> 00:05:22,000
Dabar mums reikia, kad yra gana pagrindinis numeris El m

117
00:05:22,000 --> 00:05:25,000
ir mažiau nei m.

118
00:05:25,000 --> 00:05:28,000
Du skaičiai yra gana pagrindinis arba tarpusavyje paprastųjų

119
00:05:28,000 --> 00:05:33,000
jei tik teigiamas sveikasis skaičius, kad dalybos juos abu tolygiai yra 1.

120
00:05:33,000 --> 00:05:37,000
Kitaip tariant, didžiausias bendras daliklis e ir m

121
00:05:37,000 --> 00:05:39,000
turi būti 1.

122
00:05:39,000 --> 00:05:44,000
Iš tikrųjų, tai dažnai e būti pirminis skaičius 65.537

123
00:05:44,000 --> 00:05:48,000
tol, kol tai neįvyks būti M faktorius.

124
00:05:48,000 --> 00:05:53,000
Mūsų raktus, mes pasiimti e = 5

125
00:05:53,000 --> 00:05:57,000
yra gana pagrindinis nuo 5 iki 924.

126
00:05:57,000 --> 00:06:01,000
Galiausiai, mes jums reikia dar vieną numerį, kurį mes vadiname d.

127
00:06:01,000 --> 00:06:11,000
D turi būti kai vertė, kuri atitinka lygtį = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Šis mod m reiškia, mes naudoti kažką vadinama modulinė aritmetinis.

129
00:06:17,000 --> 00:06:21,000
Modulinės aritmetinis, kai skaičius tampa didesnis, nei kai viršutinė riba

130
00:06:21,000 --> 00:06:24,000
jis bus užbaigtas apie 0.

131
00:06:24,000 --> 00:06:27,000
Laikrodis, pavyzdžiui, naudoja modulinę aritmetiką.

132
00:06:27,000 --> 00:06:31,000
Viena minutė po 1:59, pavyzdžiui, 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Minučių ranka apvynioti aplink 0

135
00:06:36,000 --> 00:06:39,000
sulaukę viršutinė riba 60.

136
00:06:39,000 --> 00:06:46,000
Taigi, mes galime pasakyti, 60 yra lygus 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
ir 125 yra lygiavertis 65 atitinka 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Mūsų viešasis raktas bus pora e ir n

139
00:07:02,000 --> 00:07:09,000
kur šiuo atveju e yra 5 ir n yra 989.

140
00:07:09,000 --> 00:07:15,000
Mūsų privatus raktas bus pora d ir n,

141
00:07:15,000 --> 00:07:22,000
kuri mūsų atveju yra 185 ir 989.

142
00:07:22,000 --> 00:07:25,000
Atkreipkite dėmesį, kad mūsų originalus paprastų p ir q neatrodo

143
00:07:25,000 --> 00:07:29,000
bet mūsų privačių ar viešųjų raktų.

144
00:07:29,000 --> 00:07:33,000
Dabar, mes turime savo raktų porą, galime pažvelgti kaip mes galime užšifruoti išvaizdą

145
00:07:33,000 --> 00:07:36,000
ir iššifruoti žinutę.

146
00:07:36,000 --> 00:07:38,000
Noriu siųsti žinutę Rob,

147
00:07:38,000 --> 00:07:42,000
, kad jis bus vienas generuojame šį raktų porą.

148
00:07:42,000 --> 00:07:46,000
Tada aš paklausti Rob savo viešąjį raktą, kurį aš naudoti

149
00:07:46,000 --> 00:07:48,000
užšifruoti žinutę siųsti jam.

150
00:07:48,000 --> 00:07:53,000
Atminkite, kad tai yra visiškai gerai, Rob pasidalinti savo viešąjį raktą su manimi.

151
00:07:53,000 --> 00:07:56,000
Bet tai nebūtų gerai pasidalinti savo privatų raktą.

152
00:07:56,000 --> 00:08:00,000
Aš neturiu jokio supratimo, ką jo privatus raktas yra.

153
00:08:00,000 --> 00:08:03,000
Mes galime sulaužyti mūsų žinia m į kelis gabaliukus

154
00:08:03,000 --> 00:08:07,000
visi mažesnis nei n ir tada užšifruoti kiekvienas iš šių gabaliukus.

155
00:08:07,000 --> 00:08:12,000
Mes užšifruoti eilutę CS50, kuriuos mes galime išeiti į 4 gabaliukus,

156
00:08:12,000 --> 00:08:14,000
vieną kiekvienai raidei.

157
00:08:14,000 --> 00:08:17,000
Tam, kad užkoduoti mano pranešimą, aš reikia ją konvertuoti į

158
00:08:17,000 --> 00:08:20,000
kažkoks Skaitinė atstovavimas.

159
00:08:20,000 --> 00:08:25,000
Leiskite Jungiant su savo pranešimo simbolių ASCII reikšmes.

160
00:08:25,000 --> 00:08:28,000
Tam, kad užkoduoti tam tikrą pranešimą m

161
00:08:28,000 --> 00:08:37,000
Man reikės apskaičiuoti C = M e (mod n).

162
00:08:37,000 --> 00:08:40,000
Bet m, turi būti mažesnės nei n,

163
00:08:40,000 --> 00:08:45,000
ar kitur visą pranešimas negali būti išreikštas pagal modulis n.

164
00:08:45,000 --> 00:08:49,000
Mes galime sulaužyti m iki į kelis gabaliukus, visi, kurie yra mažesni nei n

165
00:08:49,000 --> 00:08:52,000
ir šifruoti kiekvieną iš šių gabaliukus.

166
00:08:52,000 --> 00:09:03,000
Šifravimo kiekvieną iš šių gabaliukus, kurią mes gauname c1 5 67 = (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Mūsų antra riekė nuo 83 iki 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Mūsų trečiosios riekė nuo 53 iki 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
Ir, pagaliau, mūsų paskutinio riekė mes turime nuo 48 iki 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Dabar mes galime išsiųsti per šiuos saugiame vertybes Rob.

175
00:09:54,000 --> 00:09:58,000
Čia jūs einate, Rob.

176
00:09:58,000 --> 00:10:01,000
Nors mūsų žinia skrydžio metu, tegul kitą išvaizdą

177
00:10:01,000 --> 00:10:07,000
, kaip mes turime, kad D vertę.

178
00:10:07,000 --> 00:10:17,000
Mūsų numeris d reikia patenkinti 5D = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Tai daro d Multiplikacinis atvirkštinis 924 5 modulį.

180
00:10:24,000 --> 00:10:28,000
Atsižvelgiant į 2 sveikieji skaičiai a ir b pratęstas Euklido algoritmas

181
00:10:28,000 --> 00:10:33,000
gali būti naudojama ir siekiant rasti 2 sveikųjų skaičių didžiausias bendras daliklis.

182
00:10:33,000 --> 00:10:37,000
Jis taip pat suteiks mums 2 kiti numeriai, X ir Y,

183
00:10:37,000 --> 00:10:47,000
kurios atitinka lygtis ax + = didžiausias bendras daliklis A ir B.

184
00:10:47,000 --> 00:10:49,000
Kaip tai gali mums padėti?

185
00:10:49,000 --> 00:10:52,000
Na, kaiščiais e = 5

186
00:10:52,000 --> 00:10:56,000
m = 924 b

187
00:10:56,000 --> 00:10:59,000
mes jau žinome, kad šie skaičiai yra tarpusavyje paprastųjų.

188
00:10:59,000 --> 00:11:03,000
Jų didžiausias bendras daliklis yra 1.

189
00:11:03,000 --> 00:11:09,000
Tai suteikia mums 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Bet jei mes tik rūpintis apie viską modulį 924

192
00:11:22,000 --> 00:11:25,000
tada mes galime lašas - 924y.

193
00:11:25,000 --> 00:11:27,000
Pagalvokite atgal į laikrodį.

194
00:11:27,000 --> 00:11:31,000
Jei yra 1 minutę ranka ir tada lygiai 10 valandoms,

195
00:11:31,000 --> 00:11:35,000
mes žinome, minutę ranka vis dar bus ant 1.

196
00:11:35,000 --> 00:11:39,000
Čia mes pradedame 1 ir tada wrap aplink tiksliai y kartus,

197
00:11:39,000 --> 00:11:41,000
todėl mes vis dar gali būti "1".

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

199
00:11:49,000 --> 00:11:55,000
Čia x yra tas pats kaip mes ieškojome prieš d,

200
00:11:55,000 --> 00:11:58,000
todėl, jei mes naudojame pratęstas Euklido algoritmas

201
00:11:58,000 --> 00:12:04,000
gauti šią numeris X, tai numeris, kurį reikia naudoti, nes mūsų d.

202
00:12:04,000 --> 00:12:07,000
Dabar galime paleisti pratęstas Euklido algoritmas = 5

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

204
00:12:11,000 --> 00:12:14,000
Mes naudojame metodą, vadinamą lentelės metodas.

205
00:12:14,000 --> 00:12:21,000
Mūsų lentelė turės 4 stulpelius, x, y, d ir k.

206
00:12:21,000 --> 00:12:23,000
Mūsų stalas prasideda su 2 eilučių.

207
00:12:23,000 --> 00:12:28,000
Pirmoje eilutėje turime 1, 0, tada mūsų vertė, kuri yra 5,

208
00:12:28,000 --> 00:12:37,000
ir mūsų antra eilutė yra 0, 1, ir mūsų vertė b, kuris yra 924.

209
00:12:37,000 --> 00:12:40,000
4-ame stulpelyje, K, vertė bus rezultatas

210
00:12:40,000 --> 00:12:45,000
D reikšmę dalijant D reikšmę virš jo eilės

211
00:12:45,000 --> 00:12:49,000
toje pačioje eilutėje.

212
00:12:49,000 --> 00:12:56,000
Mes turime 5, padalytas iš 924 yra 0 su tam tikru likusios.

213
00:12:56,000 --> 00:12:59,000
Tai reiškia, kad turime k = 0.

214
00:12:59,000 --> 00:13:05,000
Dabar kiekvieno kito elemento reikšmė bus 2 ląstelių eilių virš jo vertė

215
00:13:05,000 --> 00:13:09,000
atėmus eilutėje virš datos k vertę.

216
00:13:09,000 --> 00:13:11,000
Pradėkime d 3 eilutėje.

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

218
00:13:19,000 --> 00:13:25,000
Toliau mes turite 0 - 1 * 0 yra 0

219
00:13:25,000 --> 00:13:30,000
ir 1 - 0 * 0 1.

220
00:13:30,000 --> 00:13:33,000
Nėra labai blogai, todėl galime pereiti į kitą eilutę.

221
00:13:33,000 --> 00:13:36,000
Pirmiausia mes turime mūsų vertę k.

222
00:13:36,000 --> 00:13:43,000
924, padalytas iš 5 = 184, su kai kuriais likusiam

223
00:13:43,000 --> 00:13:46,000
todėl mūsų k vertė yra 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Viskas gerai, darykime kitą eilutę.

227
00:14:07,000 --> 00:14:10,000
Mūsų Koeficiento k vertė bus 1, nes

228
00:14:10,000 --> 00:14:15,000
5, padalytas iš 4 = 1 su kai kurių likusių.

229
00:14:15,000 --> 00:14:17,000
Tegul užpildyti kitų stulpelių.

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
Ir 1-184 * 1 185.

233
00:14:33,000 --> 00:14:35,000
Pažiūrėkime, ką būtų mūsų kitas Koeficiento k vertė.

234
00:14:35,000 --> 00:14:40,000
Na, atrodo, kaip mes turime, 4, padalytas iš 1, kuris yra 4.

235
00:14:40,000 --> 00:14:43,000
Šiuo atveju, kai mes dalijama iš 1 toks, kad k yra lygus

236
00:14:43,000 --> 00:14:50,000
D vertė virš eilutės reiškia, kad mes su mūsų algoritmas.

237
00:14:50,000 --> 00:14:58,000
Mes galime pamatyti, kad mes turime x = 185 ir y = -1 paskutinę eilutę.

238
00:14:58,000 --> 00:15:00,000
Tegul dabar grįžti prie pradinio tikslo.

239
00:15:00,000 --> 00:15:04,000
Mes sakėme, kad x vertė, nes dėl paleisti šį algoritmą

240
00:15:04,000 --> 00:15:08,000
būtų Multiplikacinis atvirkštinis (mod b).

241
00:15:08,000 --> 00:15:15,000
Tai reiškia, kad 185 yra didinamasis atvirkštinis 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
, o tai reiškia, kad mes turime vertę 185 D.

243
00:15:20,000 --> 00:15:23,000
Tai, kad d = 1 paskutine eilute

244
00:15:23,000 --> 00:15:26,000
tikrina, kad e tarpusavyje paprastųjų iki m.

245
00:15:26,000 --> 00:15:30,000
Jei tai buvo ne 1, tada mes turėtume pasirinkti naują el.

246
00:15:30,000 --> 00:15:33,000
Dabar pažiūrėkime,, jei Rob gavo mano laišką.

247
00:15:33,000 --> 00:15:35,000
Kai kas nors atsiunčia man šifruotą pranešimą

248
00:15:35,000 --> 00:15:38,000
kaip ilgai, kaip aš išlaikė savo privatų raktą, paslaptį

249
00:15:38,000 --> 00:15:41,000
Aš esu vienintelis, kuris gali iššifruoti pranešimą.

250
00:15:41,000 --> 00:15:46,000
Iššifruoti riekė a galima apskaičiuoti pirminį pranešimą

251
00:15:46,000 --> 00:15:53,000
yra lygus gautu D galia (mod n).

252
00:15:53,000 --> 00:15:57,000
Atminkite, kad d ir n yra iš mano privataus rakto.

253
00:15:57,000 --> 00:16:01,000
Gauti visą pranešimą iš savo gabaliukus iššifruoti kiekviena riekė

254
00:16:01,000 --> 00:16:04,000
ir Jungiant rezultatus.

255
00:16:04,000 --> 00:16:08,000
Tiksliai, kaip saugi yra RSA?

256
00:16:08,000 --> 00:16:10,000
Tiesa yra tai, mes nežinome.

257
00:16:10,000 --> 00:16:14,000
Saugumas yra pagrįstas, kiek laiko užtruktų užpuolikas nulaužti pranešimą

258
00:16:14,000 --> 00:16:16,000
užšifruoti su RSA.

259
00:16:16,000 --> 00:16:19,000
Atminkite, kad užpuolikas turi priėjimą prie savo viešąjį raktą,

260
00:16:19,000 --> 00:16:21,000
kuri yra tiek E ir N.

261
00:16:21,000 --> 00:16:26,000
Jei užpuolikas sugeba į jo 2 primes, P ir Q faktorius N,

262
00:16:26,000 --> 00:16:30,000
tada ji galėtų apskaičiuoti ð naudodama pratęstas Euklido algoritmas.

263
00:16:30,000 --> 00:16:35,000
Tai suteikia jai privatų raktą, kuris gali būti naudojamas iššifruoti bet kokį pranešimą.

264
00:16:35,000 --> 00:16:38,000
Bet kaip greitai mes galime veiksnys sveikieji skaičiai?

265
00:16:38,000 --> 00:16:41,000
Vėlgi, mes nežinome.

266
00:16:41,000 --> 00:16:43,000
Niekas rado greitas būdas tai daryti,

267
00:16:43,000 --> 00:16:46,000
o tai reiškia, kad skiriamas pakankamai didelis, n

268
00:16:46,000 --> 00:16:49,000
ji imsis užpuolikas nerealiai ilgai

269
00:16:49,000 --> 00:16:51,000
veiksnys numerį.

270
00:16:51,000 --> 00:16:54,000
Jei kas nors paaiškėjo, greitas būdas faktoringo sveikaisiais skaičiais

271
00:16:54,000 --> 00:16:57,000
RSA bus sulaužyta.

272
00:16:57,000 --> 00:17:01,000
Bet net jei sveikasis skaičius Faktorizavimas iš esmės yra lėtas

273
00:17:01,000 --> 00:17:04,000
RSA algoritmas gali dar šiek tiek trūkumas jame

274
00:17:04,000 --> 00:17:07,000
kuri leidžia lengvai iššifravimas pranešimų.

275
00:17:07,000 --> 00:17:10,000
Niekas rado ir atskleidė tokį trūkumas dar

276
00:17:10,000 --> 00:17:12,000
bet tai nereiškia, kad jo nėra.

277
00:17:12,000 --> 00:17:17,000
Teoriškai, nors galėtų būti ten skaityti visus duomenis užšifruoti su RSA.

278
00:17:17,000 --> 00:17:19,000
Yra dar vienas šiek tiek privatumo klausimas.

279
00:17:19,000 --> 00:17:23,000
Jei Tomas užšifruoja tam tikrą pranešimą naudodami savo viešąjį raktą

280
00:17:23,000 --> 00:17:26,000
ir užpuolikas užšifruoja savo viešąjį raktą naudojant tą patį pranešimą

281
00:17:26,000 --> 00:17:29,000
užpuolikas bus matyti, kad 2 pranešimai yra vienodi

282
00:17:29,000 --> 00:17:32,000
ir taip žino, ką Tommy užšifruoti.

283
00:17:32,000 --> 00:17:36,000
Siekiant užkirsti kelią, pranešimai paprastai kamšalu su atsitiktinių bitų

284
00:17:36,000 --> 00:17:39,000
prieš užkoduojama taip, kad tas pats pranešimas šifruojamas

285
00:17:39,000 --> 00:17:44,000
kelis kartus tol, kol atrodys kitaip, kaip pranešimo išklojimui skiriasi.

286
00:17:44,000 --> 00:17:47,000
Bet prisiminti, kaip mes turime padalinti į gabaliukus pranešimus

287
00:17:47,000 --> 00:17:50,000
taip, kad kiekviena riekė yra mažesnis nei n?

288
00:17:50,000 --> 00:17:52,000
Prikimšti į gabaliukus reiškia, kad mes galime padalinti things up

289
00:17:52,000 --> 00:17:57,000
į dar daugiau gabaliukus, nes kamšalu riekė turi būti mažesnis nei n.

290
00:17:57,000 --> 00:18:01,000
Šifravimo ir dešifravimo yra gana brangus su RSA,

291
00:18:01,000 --> 00:18:05,000
ir todėl reikia lūžti pranešimą į daugelį gabaliukus, gali būti labai brangus.

292
00:18:05,000 --> 00:18:09,000
Jei didelės duomenų apimties turi būti šifruojamas ir iššifruoti

293
00:18:09,000 --> 00:18:12,000
mes galime sujungti simetrinių pagrindinių algoritmų privalumus

294
00:18:12,000 --> 00:18:16,000
su RSA gauti tiek saugumą ir efektyvumą.

295
00:18:16,000 --> 00:18:18,000
Nors mes ne eiti į jį,

296
00:18:18,000 --> 00:18:23,000
AES simetriškai rakto algoritmas kaip Vigenere ir Caesar šifrai

297
00:18:23,000 --> 00:18:25,000
bet daug sunkiau nulaužti.

298
00:18:25,000 --> 00:18:30,000
Žinoma, mes negalime naudoti AES be įtvirtinant bendrą slaptą raktą

299
00:18:30,000 --> 00:18:34,000
tarp 2 sistemų, ir mes matėme su šia problema anksčiau.

300
00:18:34,000 --> 00:18:40,000
Bet dabar mes galime naudoti RSA nustatyti bendrą slaptą raktą tarp 2 sistemų.

301
00:18:40,000 --> 00:18:43,000
Mes paskambinsime kompiuterį Siunčiant duomenis siuntėją

302
00:18:43,000 --> 00:18:46,000
ir kompiuteris duomenis gaunanti imtuvą.

303
00:18:46,000 --> 00:18:49,000
Imtuvas turi RSA raktų porą ir siunčia

304
00:18:49,000 --> 00:18:51,000
viešojo rakto gavėjui.

305
00:18:51,000 --> 00:18:54,000
Siuntėjas sukuria AES raktą,

306
00:18:54,000 --> 00:18:57,000
šifravimas su gavėjo RSA viešojo rakto,

307
00:18:57,000 --> 00:19:00,000
ir siunčia AES raktą į imtuvą.

308
00:19:00,000 --> 00:19:04,000
Imtuvas iššifruoja pranešimą su RSA raktas.

309
00:19:04,000 --> 00:19:09,000
Tiek siuntėjas, ir gavėjas dabar turi bendrą AES raktą tarp jų.

310
00:19:09,000 --> 00:19:14,000
AES, kuri yra daug greičiau šifravimui ir iššifravimui nei RSA,

311
00:19:14,000 --> 00:19:18,000
dabar gali būti naudojama užšifruoti didelius duomenų kiekius ir siųsti juos į imtuvą,

312
00:19:18,000 --> 00:19:21,000
kas gali iššifruoti naudojant tą patį raktą.

313
00:19:21,000 --> 00:19:26,000
AES, kuri yra daug greičiau šifravimui ir iššifravimui nei RSA,

314
00:19:26,000 --> 00:19:30,000
dabar gali būti naudojama užšifruoti didelius duomenų kiekius ir siųsti juos į imtuvą,

315
00:19:30,000 --> 00:19:32,000
kas gali iššifruoti naudojant tą patį raktą.

316
00:19:32,000 --> 00:19:36,000
Mes tiesiog reikia RSA perkelti rakto.

317
00:19:36,000 --> 00:19:40,000
Mums nebereikia naudoti RSA ne visi.

318
00:19:40,000 --> 00:19:46,000
Atrodo, kad aš gavo pranešimą.

319
00:19:46,000 --> 00:19:49,000
Nesvarbu, jei kas nors perskaityti, kas ant popieriaus lėktuvo, kol aš sugauti jį

320
00:19:49,000 --> 00:19:55,000
nes aš tik vienas su privataus rakto.

321
00:19:55,000 --> 00:19:57,000
Leiskite iššifruoti kiekvienas pranešimo gabaliukus.

322
00:19:57,000 --> 00:20:07,000
Pirmasis riekė, 658, mes keliame D galia, kuri yra 185,

323
00:20:07,000 --> 00:20:18,000
mod n, kuris yra 989, yra lygus 67,

324
00:20:18,000 --> 00:20:24,000
kuri yra įrašyta raidė C, ASCII.

325
00:20:24,000 --> 00:20:31,000
Dabar į antrąjį riekė.

326
00:20:31,000 --> 00:20:35,000
Antrasis riekė turi vertę 15,

327
00:20:35,000 --> 00:20:41,000
, kuriuos mes keliame 185. galios,

328
00:20:41,000 --> 00:20:51,000
mod 989, ir tai yra lygus 83

329
00:20:51,000 --> 00:20:57,000
kuris yra raidė S ASCII.

330
00:20:57,000 --> 00:21:06,000
Dabar trečią riekė, kuri turi vertę 799, mes keliame 185

331
00:21:06,000 --> 00:21:17,000
mod 989, ir tai yra lygus 53,

332
00:21:17,000 --> 00:21:24,000
kuris yra charakterio vertė ASCII 5.

333
00:21:24,000 --> 00:21:30,000
Dabar už paskutinį gabalą, kuriame yra reikšmė, 975,

334
00:21:30,000 --> 00:21:41,000
mes keliame iki 185, mod 989

335
00:21:41,000 --> 00:21:51,000
ir ji yra lygi 48, kuris vertė 0 ASCII simbolių.

336
00:21:51,000 --> 00:21:57,000
My name is Rob Bowden, ir tai yra CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA ne visi.

339
00:22:08,000 --> 00:22:14,000
RSA ne visi. [Juokas]

340
00:22:14,000 --> 00:22:17,000
Ne visiems.