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

2
00:00:02,000 --> 00:00:04,000
[Robs Bowden] [Tomijs MacWilliam] [Hārvarda]

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

4
00:00:07,000 --> 00:00:11,000
Pieņemsim to apskatīt RSA, plaši izmanto algoritmu datu šifrēšanai.

5
00:00:11,000 --> 00:00:16,000
Šifrēšanas algoritmi, piemēram, Cēzara un Vigenère cipariem nav ļoti droša.

6
00:00:16,000 --> 00:00:20,000
Ar Cēzara šifra, uzbrucējs tikai vajag izmēģināt 25 dažādas atslēgas

7
00:00:20,000 --> 00:00:22,000
lai saņemtu ziņu s teksta.

8
00:00:22,000 --> 00:00:25,000
Kamēr Vigenère šifra ir drošāka nekā Cēzara šifra

9
00:00:25,000 --> 00:00:28,000
jo lielāku meklēšanas telpu atslēgām, kad uzbrucējs

10
00:00:28,000 --> 00:00:30,000
zina atslēgas garums ir Vigenère izrēķināt,

11
00:00:30,000 --> 00:00:34,000
ko var noteikt, izmantojot analīzi modeļus šifrētā tekstā,

12
00:00:34,000 --> 00:00:38,000
the Vigenère šifra nav tik daudz drošāka nekā Cēzara šifra.

13
00:00:38,000 --> 00:00:42,000
RSA, no otras puses, nav neaizsargāti pret uzbrukumiem kā šis.

14
00:00:42,000 --> 00:00:45,000
Caesar šifra un Vigenère šifra izmantot to pašu atslēgu

15
00:00:45,000 --> 00:00:47,000
gan šifrēt un atšifrēt ziņojumu.

16
00:00:47,000 --> 00:00:51,000
Šī īpašība padara šos šifriem simetriskas galvenās algoritmus.

17
00:00:51,000 --> 00:00:54,000
Pamatproblēma ar simetrisko galvenajiem algoritmiem

18
00:00:54,000 --> 00:00:57,000
ir tas, ka viņi paļaujas uz vienu šifrējot un nosūtot īsziņu

19
00:00:57,000 --> 00:00:59,000
un viens saņemšanu un atšifrēšanas ziņu

20
00:00:59,000 --> 00:01:03,000
līdz jau ir vienojušās sākumā uz taustiņa viņi abi izmanto.

21
00:01:03,000 --> 00:01:06,000
Bet mums ir mazliet starta problēmu šeit.

22
00:01:06,000 --> 00:01:10,000
Kā 2 datori, kas vēlas sazināties izveidot slepenu atslēgu starp viņiem?

23
00:01:10,000 --> 00:01:16,000
Ja atslēga ir slepena, tad mums ir nepieciešams veids, lai šifrētu un atšifrētu taustiņu.

24
00:01:16,000 --> 00:01:18,000
Ja viss, kas mums ir simetriska atslēgas kriptogrāfijas

25
00:01:18,000 --> 00:01:21,000
tad mēs esam tikai nāk atpakaļ uz to pašu problēmu.

26
00:01:21,000 --> 00:01:25,000
RSA, no otras puses, izmanto atslēgu pāri,

27
00:01:25,000 --> 00:01:28,000
viens šifrēšanai un citu par atšifrēšanu.

28
00:01:28,000 --> 00:01:32,000
Viena sauc publisko atslēgu, un otrs ir privātā atslēga.

29
00:01:32,000 --> 00:01:34,000
Publiskā atslēga tiek izmantota, lai šifrētu ziņojumus.

30
00:01:34,000 --> 00:01:38,000
Kā jūs varētu uzminēt tās nosaukums, mēs varam dalīties mūsu publisko atslēgu ar

31
00:01:38,000 --> 00:01:43,000
kāds mēs vēlamies neapdraudot drošību šifrētu ziņu.

32
00:01:43,000 --> 00:01:45,000
Ziņas šifrēta, izmantojot publisko atslēgu

33
00:01:45,000 --> 00:01:49,000
var atšifrēt tikai ar atbilstošo privāto atslēgu.

34
00:01:49,000 --> 00:01:53,000
Kamēr jūs varat dalīties ar jūsu publisko atslēgu, jums vajadzētu vienmēr saglabāt savu privāto atslēgu noslēpumu.

61
00:01:55,000 --> 00:01:58,000
un tikai privātā atslēga var izmantot, lai atšifrēt ziņojumus

62
00:01:58,000 --> 00:02:02,000
ja 2 lietotāji vēlas, lai nosūtītu ziņojumus šifrēti ar RSA

63
00:02:02,000 --> 00:02:07,000
un atpakaļ abi lietotāji ir vajadzīga sava valsts un privāto atslēgu pāri.

64
00:02:07,000 --> 00:02:10,000
Ziņojumi no 1 lietotājs uz 2 lietotājam

65
00:02:10,000 --> 00:02:15,000
izmantot tikai User 2 atslēgu pāri, un ziņas no 2 lietotājs līdz 1 lietotājam

66
00:02:15,000 --> 00:02:17,000
izmantot tikai User 1 atslēgu pāri.

67
00:02:17,000 --> 00:02:21,000
Fakts, ka tur ir 2 atsevišķas atslēgas šifrēt un atšifrēt ziņojumus

68
00:02:21,000 --> 00:02:24,000
padara RSA asimetrisko atslēgu algoritms.

69
00:02:24,000 --> 00:02:28,000
Mums nav nepieciešams, lai šifrētu publisko atslēgu, lai to nosūtītu uz citu datoru

70
00:02:28,000 --> 00:02:31,000
jo galvenais ir publiski vienalga.

71
00:02:31,000 --> 00:02:33,000
Tas nozīmē, ka DĀR nav tāda pati starta problēma

72
00:02:33,000 --> 00:02:36,000
kā simetriskās galvenajiem algoritmiem.

73
00:02:36,000 --> 00:02:39,000
Tātad, ja es gribu, lai nosūtītu īsziņu, izmantojot RSA šifrēšanu

74
00:02:39,000 --> 00:02:42,000
aplaupīt, es vispirms aplaupīt publisko atslēgu.

75
00:02:42,000 --> 00:02:47,000
Lai radītu atslēgu pāri, Robs nepieciešams uzņemt 2 lielas prime skaitu.

76
00:02:47,000 --> 00:02:50,000
Šie numuri tiks izmantoti gan valsts un privātās atslēgas,

77
00:02:50,000 --> 00:02:54,000
bet publiskā atslēga būs tikai izmantot produktu no šiem 2 numuriem,

78
00:02:54,000 --> 00:02:56,000
nav skaitļi paši.

79
00:02:56,000 --> 00:02:59,000
Kad esmu šifrēts ziņojumu, izmantojot aplaupīt publisko atslēgu

80
00:02:59,000 --> 00:03:01,000
Es varu nosūtīt ziņu uz Rob.

81
00:03:01,000 --> 00:03:05,000
Par datoru, faktorings skaitļi ir grūti problēma.

82
00:03:05,000 --> 00:03:09,000
Publiskā atslēga, atcerieties, ko izmanto produktu par 2 galvenajiem numuriem.

83
00:03:09,000 --> 00:03:12,000
Šis produkts ir, tad ir tikai 2 faktori,

84
00:03:12,000 --> 00:03:16,000
kas gadās būt skaitļi, kas veido privāto atslēgu.

85
00:03:16,000 --> 00:03:20,000
Lai atšifrēt ziņu, RSA izmantos šo privāto atslēgu

86
00:03:20,000 --> 00:03:25,000
vai skaitļus reizina kopā veidojot publisko atslēgu.

87
00:03:25,000 --> 00:03:28,000
Jo tas ir skaitļošanas grūti faktors numuru

88
00:03:28,000 --> 00:03:32,000
izmanto publisko atslēgu no 2 numuriem, kas izmantoti privāto atslēgu

89
00:03:32,000 --> 00:03:36,000
tas ir grūti uzbrucējs izrēķināt privāto atslēgu

90
00:03:36,000 --> 00:03:39,000
kas būs nepieciešami, lai atšifrētu ziņojumu.

91
00:03:39,000 --> 00:03:43,000
Tagad pieņemsim iedziļināties dažos zemāka līmeņa detaļas RSA.

92
00:03:43,000 --> 00:03:46,000
Pieņemsim vispirms redzēt, kā mēs varam radīt atslēgu pāri.

93
00:03:46,000 --> 00:03:49,000
Pirmkārt, mēs nepieciešams 2 prime skaitu.

94
00:03:49,000 --> 00:03:52,000
Mēs saucam šie 2 skaitļi p un q.

95
00:03:52,000 --> 00:03:56,000
Lai izvēlētos p un q, praksē mēs pseudorandomly radīt

96
00:03:56,000 --> 00:03:59,000
liels skaits un tad izmanto kritēriju, lai noteiktu, vai nav

97
00:03:59,000 --> 00:04:02,000
šie skaitļi, iespējams, ir galvenais.

98
00:04:02,000 --> 00:04:05,000
Mēs varam saglabāt radītu nejaušības numurus atkal un atkal

99
00:04:05,000 --> 00:04:08,000
līdz mums ir 2 PRIMES ka mēs varam izmantot.

100
00:04:08,000 --> 00:04:15,000
Lūk pieņemsim uzņemt p = 23 un q = 43.

101
00:04:15,000 --> 00:04:19,000
Atceros, praksē, p un q būtu daudz lielāki skaitļi.

102
00:04:19,000 --> 00:04:22,000
Ciktāl mēs zinām, jo ​​lielāki skaitļiem, jo ​​grūtāk ir

103
00:04:22,000 --> 00:04:25,000
kreka šifrētu ziņojumu.

104
00:04:25,000 --> 00:04:29,000
Bet tas ir arī dārgāka, lai šifrētu un atšifrētu ziņojumus.

105
00:04:29,000 --> 00:04:33,000
Šodien tā ir bieži ieteicams p un q ir vismaz 1024 biti,

106
00:04:33,000 --> 00:04:37,000
kas liek katru numuru pie vairāk nekā 300 Decimālciparus.

107
00:04:37,000 --> 00:04:40,000
Bet mēs pick šos mazos numurus šim piemēram.

108
00:04:40,000 --> 00:04:43,000
Tagad mēs reizināt p un q kopā, lai iegūtu 3rd numuru,

109
00:04:43,000 --> 00:04:45,000
ko mēs saucam n.

110
00:04:45,000 --> 00:04:55,000
Mūsu gadījumā, n = 23 * 43, kas = 989.

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

112
00:04:58,000 --> 00:05:02,000
Nākamais mēs reizināt P - 1 ar Q - 1

113
00:05:02,000 --> 00:05:05,000
lai iegūtu 4. numuru, ko mēs saucam m.

114
00:05:05,000 --> 00:05:15,000
Mūsu gadījumā, m = 22 * ​​42, kas = 924.

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

116
00:05:18,000 --> 00:05:22,000
Tagad mums būs nepieciešams cipara e, kas ir salīdzinoši prime līdz m

117
00:05:22,000 --> 00:05:25,000
un mazāk nekā m.

118
00:05:25,000 --> 00:05:28,000
Divi skaitļi ir salīdzinoši prime vai coprime

119
00:05:28,000 --> 00:05:33,000
ja vienīgais pozitīvais skaitlis, kas dala tos gan vienmērīgi ir 1.

120
00:05:33,000 --> 00:05:37,000
Citiem vārdiem sakot, lielāko kopējo dalītājs e un m

121
00:05:37,000 --> 00:05:39,000
jābūt 1.

122
00:05:39,000 --> 00:05:44,000
Praksē tas ir parasts e būt pirmskaitlis 65.537

123
00:05:44,000 --> 00:05:48,000
kamēr šis numurs nav gadās būt faktors m.

124
00:05:48,000 --> 00:05:53,000
Mūsu atslēgas, mēs pick e = 5

125
00:05:53,000 --> 00:05:57,000
jo 5 ir salīdzinoši prime un 924.

126
00:05:57,000 --> 00:06:01,000
Visbeidzot, mums būs nepieciešams vēl viens numurs, ko mēs saucam d.

127
00:06:01,000 --> 00:06:11,000
A jābūt dažas vērtības, kas apmierina vienādojumu de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Šī mod m nozīmē mēs izmantot kaut ko sauc moduļu aritmētika.

129
00:06:17,000 --> 00:06:21,000
Moduļu aritmētisko, kad vairāki kļūst lielāks nekā daži augšējo robežu

130
00:06:21,000 --> 00:06:24,000
tas wrap atpakaļ ap 0.

131
00:06:24,000 --> 00:06:27,000
Pulksteni, piemēram, izmanto modulāro aritmētika.

132
00:06:27,000 --> 00:06:31,000
Vienu minūti pēc 01:59, piemēram, ir 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Minūti rokas ir aptīt ar 0

135
00:06:36,000 --> 00:06:39,000
sasniedzot augšējo robežu 60.

136
00:06:39,000 --> 00:06:46,000
Tātad, mēs varam teikt, 60 ir līdzvērtīga 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
un 125 ir līdzvērtīga 65 gadiem ir līdzvērtīgs 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Mūsu sabiedrība atslēga būs pāris e un n

139
00:07:02,000 --> 00:07:09,000
kur šajā gadījumā e ir 5 un n ir 989.

140
00:07:09,000 --> 00:07:15,000
Mūsu privātā atslēga būs pāris d un n,

141
00:07:15,000 --> 00:07:22,000
kas mūsu gadījumā ir 185 un 989.

142
00:07:22,000 --> 00:07:25,000
Ievērojiet, ka mūsu sākotnējais PRIMES p un q neparādās

143
00:07:25,000 --> 00:07:29,000
jebkur mūsu privāto vai publisko atslēgu.

144
00:07:29,000 --> 00:07:33,000
Tagad, kad mums ir mūsu atslēgu pāri, pieņemsim to apskatīt, kā mēs varam šifrēt

145
00:07:33,000 --> 00:07:36,000
un atšifrēt ziņu.

146
00:07:36,000 --> 00:07:38,000
Es gribu, lai nosūtītu ziņu uz Rob,

147
00:07:38,000 --> 00:07:42,000
tāpēc viņš būs viens, lai radītu šo atslēgu pāri.

148
00:07:42,000 --> 00:07:46,000
Tad es ņemšu uzdot Rob viņa publisko atslēgu, ko es ņemšu izmantot

149
00:07:46,000 --> 00:07:48,000
lai šifrētu ziņu, lai nosūtītu viņam.

150
00:07:48,000 --> 00:07:53,000
Atcerieties, tas ir pilnīgi labi, lai Robs dalīties savā publisko atslēgu ar mani.

151
00:07:53,000 --> 00:07:56,000
Bet tas nebūtu labi, lai dalītos savu privāto atslēgu.

152
00:07:56,000 --> 00:08:00,000
Man nav nekādu ideju, ko viņa privāto atslēgu.

153
00:08:00,000 --> 00:08:03,000
Mēs varam salauzt mūsu ziņu m pa vairākiem gabalos

154
00:08:03,000 --> 00:08:07,000
viss mazāks nekā n un tad šifrēt katru no šiem gabalos.

155
00:08:07,000 --> 00:08:12,000
Mēs šifrētu virkni CS50, ko mēs varam izjaukt uz 4 gabalos,

156
00:08:12,000 --> 00:08:14,000
vienu uz vēstuli.

157
00:08:14,000 --> 00:08:17,000
Lai šifrētu savu vēstījumu, man būs nepieciešams, lai pārvērstu to par

158
00:08:17,000 --> 00:08:20,000
sava veida ciparu pārstāvību.

159
00:08:20,000 --> 00:08:25,000
Pieņemsim saķēdēt ASCII vērtības ar manā ziņojumā rakstzīmes.

160
00:08:25,000 --> 00:08:28,000
Lai šifrētu doto ziņu m

161
00:08:28,000 --> 00:08:37,000
Man būs nepieciešams, lai aprēķinātu c = m uz e (mod n).

162
00:08:37,000 --> 00:08:40,000
Bet m ir mazāks nekā n,

163
00:08:40,000 --> 00:08:45,000
vai arī pilnu ziņu nevar izteikti MODULO n.

164
00:08:45,000 --> 00:08:49,000
Mēs varam lauzt m pa vairākiem gabalos, no kuriem visi ir mazāki nekā n,

165
00:08:49,000 --> 00:08:52,000
un šifrēt katru no šiem gabalos.

166
00:08:52,000 --> 00:09:03,000
Šifrējot katra no šīm gabalos, mēs C1 = 67-5 taustiņu (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Par mūsu otrā rieciens mums ir 83 līdz 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Par mūsu trešajā rieciens mums ir 53 līdz 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
Un visbeidzot, mūsu pēdējo gabalu mums ir 48 līdz 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Tagad mēs varam nosūtīt pa šīs šifrētu vērtības Rob.

175
00:09:54,000 --> 00:09:58,000
Šeit jums iet, Rob.

176
00:09:58,000 --> 00:10:01,000
Kamēr mūsu vēstījums ir lidojuma, pieņemsim citu izskatu

177
00:10:01,000 --> 00:10:07,000
pie kā mēs saņēmām ka vērtību d.

178
00:10:07,000 --> 00:10:17,000
Mūsu numurs d lai apmierinātu 5D = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Tas padara d multiplikatīvo apgriezto gada 5 moduļa 924.

180
00:10:24,000 --> 00:10:28,000
Ievadīts 2 veseli skaitļi, un b, pagarinātā Eiklida algoritms

181
00:10:28,000 --> 00:10:33,000
var izmantot, lai atrastu vislielāko kopējo dalītājs šiem 2 integers.

182
00:10:33,000 --> 00:10:37,000
Tas arī dos mums 2 citiem numuriem, X un Y

183
00:10:37,000 --> 00:10:47,000
kas atbilst vienādojums ax + by = vislielāko kopējo dalītājs a un b.

184
00:10:47,000 --> 00:10:49,000
Kā tas mums palīdzēt?

185
00:10:49,000 --> 00:10:52,000
Nu, tapām e = 5

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

187
00:10:56,000 --> 00:10:59,000
Mēs jau zinām, ka šie skaitļi ir coprime.

188
00:10:59,000 --> 00:11:03,000
Viņu lielākais kopīgais dalītājs ir 1.

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

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

191
00:11:17,000 --> 00:11:22,000
Bet, ja mēs tikai rūpējamies par visu moduļa 924

192
00:11:22,000 --> 00:11:25,000
tad mēs varam nomest - 924y.

193
00:11:25,000 --> 00:11:27,000
Think atpakaļ uz pulksteni.

194
00:11:27,000 --> 00:11:31,000
Ja minūti rokas ir par 1 gadu un tad tieši 10 stundas caurlaide,

195
00:11:31,000 --> 00:11:35,000
mēs zinām minūšu rādītājs joprojām būs uz 1.

196
00:11:35,000 --> 00:11:39,000
Šeit mēs sākam pēc 1 un tad wrap ap tieši y reizes,

197
00:11:39,000 --> 00:11:41,000
tāpēc mēs joprojām būs 1.

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

199
00:11:49,000 --> 00:11:55,000
Un šeit tas x ir tāds pats kā D Mēs meklējām pirms,

200
00:11:55,000 --> 00:11:58,000
tāpēc, ja mēs izmantot paplašināto Eiklida algoritms

201
00:11:58,000 --> 00:12:04,000
lai iegūtu šo numurs X, tas ir skaitlis mums vajadzētu izmantot kā mūsu d.

202
00:12:04,000 --> 00:12:07,000
Tagad palaist pagarināts Eiklida algoritms a = 5

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

204
00:12:11,000 --> 00:12:14,000
Mēs izmantot metodi sauc tabulu metode.

205
00:12:14,000 --> 00:12:21,000
Mūsu galda būs 4 kolonnas, x, y, d un k.

206
00:12:21,000 --> 00:12:23,000
Mūsu galda sākas ar 2 rindās.

207
00:12:23,000 --> 00:12:28,000
Pirmajā rindā mums ir 1, 0, tad mūsu vērtība, kas ir par 5,

208
00:12:28,000 --> 00:12:37,000
un mūsu otrais rindā ir 0, 1, un mūsu cenas B, kas ir 924.

209
00:12:37,000 --> 00:12:40,000
Par gada 4 kolonnas, k, vērtība būs rezultāts

210
00:12:40,000 --> 00:12:45,000
gada dalot D vērtību rindā virs tā ar vērtību D

211
00:12:45,000 --> 00:12:49,000
vienā rindā.

212
00:12:49,000 --> 00:12:56,000
Mums ir 5 dalīts ar 924 ir 0 ar dažiem atlikušo.

213
00:12:56,000 --> 00:12:59,000
Tas nozīmē, ka mums ir k = 0.

214
00:12:59,000 --> 00:13:05,000
Tagad par katru citu šūnu vērtība būs vērtība šūnu 2 rindās virs tā

215
00:13:05,000 --> 00:13:09,000
atņem rindas virs tā reizes k.

216
00:13:09,000 --> 00:13:11,000
Sāksim ar D gada 3 kārtas.

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

218
00:13:19,000 --> 00:13:25,000
Nākamais mums ir 0-1 * 0, kas ir 0

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

220
00:13:30,000 --> 00:13:33,000
Ne pārāk slikti, tāpēc pieņemsim pāriet uz nākamo rindu.

221
00:13:33,000 --> 00:13:36,000
Vispirms mums ir nepieciešams mūsu vērtību k.

222
00:13:36,000 --> 00:13:43,000
924 dalīts ar 5 = 184 ar dažiem atlikušo,

223
00:13:43,000 --> 00:13:46,000
tāpēc mūsu vērtība k ir 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Labi, pieņemsim do nākamo rindu.

227
00:14:07,000 --> 00:14:10,000
Mūsu k vērtība būs 1, jo

228
00:14:10,000 --> 00:14:15,000
5 dalīts ar 4 = 1 ar dažiem atlikušo.

229
00:14:15,000 --> 00:14:17,000
Pieņemsim aizpildīt citām kolonnām.

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

233
00:14:33,000 --> 00:14:35,000
Paskatīsimies, kāda ir mūsu nākamais k vērtība būtu.

234
00:14:35,000 --> 00:14:40,000
Nu, izskatās, ka mums ir 4 dala secīgi ar 1, kas ir par 4.

235
00:14:40,000 --> 00:14:43,000
Šajā gadījumā, ja mēs dalot ar 1, ka k ir vienāds ar

236
00:14:43,000 --> 00:14:50,000
gada D lielums iepriekš rindā nozīmē, ka mēs esam darīts ar mūsu algoritmu.

237
00:14:50,000 --> 00:14:58,000
Mēs varam redzēt šeit, ka mums ir x = 185 un y = -1 pēdējā rindā.

238
00:14:58,000 --> 00:15:00,000
Pieņemsim tagad nāk atpakaļ uz mūsu sākotnējo mērķi.

239
00:15:00,000 --> 00:15:04,000
Mēs teicām, ka vērtība x rezultātā darboties šo algoritmu

240
00:15:04,000 --> 00:15:08,000
būtu multiplikatīvo inversiju (mod b).

241
00:15:08,000 --> 00:15:15,000
Tas nozīmē, ka 185 ir multiplikatīvo apgriezto gada 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
kas nozīmē, ka mums ir vērtība 185 d.

243
00:15:20,000 --> 00:15:23,000
Fakts, ka d = 1 pēdējā rindā

244
00:15:23,000 --> 00:15:26,000
pārliecinās, ka e tika coprime m.

245
00:15:26,000 --> 00:15:30,000
Ja tas būtu nevis 1, tad mēs būtu izvēlēties jaunu e.

246
00:15:30,000 --> 00:15:33,000
Tagad pieņemsim redzēt, ja Robs ir saņēmusi manu vēstījumu.

247
00:15:33,000 --> 00:15:35,000
Kad kāds sūta man šifrētu ziņojumu

248
00:15:35,000 --> 00:15:38,000
kamēr es esmu tur manu privāto atslēgu noslēpumu

249
00:15:38,000 --> 00:15:41,000
Es esmu vienīgais, kas var atšifrēt ziņojumu.

250
00:15:41,000 --> 00:15:46,000
Lai atšifrētu gabaliņa c es varētu aprēķināt sākotnējo ziņojumu

251
00:15:46,000 --> 00:15:53,000
ir vienāds ar rieciens uz D jaudu (mod n).

252
00:15:53,000 --> 00:15:57,000
Atcerieties, ka d un n ir no manas privātās atslēgas.

253
00:15:57,000 --> 00:16:01,000
Lai iegūtu pilnu ziņu no tās gabalos mēs atšifrēt katru rieciens

254
00:16:01,000 --> 00:16:04,000
un saķēdēt rezultātus.

255
00:16:04,000 --> 00:16:08,000
Kā tieši drošs ir RSA?

256
00:16:08,000 --> 00:16:10,000
Patiesība ir, mēs nezinām.

257
00:16:10,000 --> 00:16:14,000
Drošība ir balstīta uz to, cik ilgi tas veic uzbrucējs kreka ziņu

258
00:16:14,000 --> 00:16:16,000
šifrēti ar RSA.

259
00:16:16,000 --> 00:16:19,000
Atcerieties, ka uzbrucējs var piekļūt jūsu publisko atslēgu,

260
00:16:19,000 --> 00:16:21,000
kas satur gan E un N.

261
00:16:21,000 --> 00:16:26,000
Ja uzbrucējs izdodas faktors n savos 2 PRIMES, P un Q,

262
00:16:26,000 --> 00:16:30,000
tad viņa varēja aprēķināt D, izmantojot paplašināto Eiklida algoritms.

263
00:16:30,000 --> 00:16:35,000
Tas dod viņai privāto atslēgu, ko var izmantot, lai atšifrētu jebkuru ziņu.

264
00:16:35,000 --> 00:16:38,000
Bet cik ātri mēs varam faktors integers?

265
00:16:38,000 --> 00:16:41,000
Atkal, mēs nezinām.

266
00:16:41,000 --> 00:16:43,000
Neviens nav atrasts ātrs veids, kā darīt to,

267
00:16:43,000 --> 00:16:46,000
kas nozīmē, ka, ņemot vērā pietiekami liels n

268
00:16:46,000 --> 00:16:49,000
tas būtu nepieciešams uzbrucēju nereāli ilgi

269
00:16:49,000 --> 00:16:51,000
faktors numuru.

270
00:16:51,000 --> 00:16:54,000
Ja kāds atklāja ātru veidu faktoringa integers

271
00:16:54,000 --> 00:16:57,000
RSA būtu sadalīti.

272
00:16:57,000 --> 00:17:01,000
Bet, pat ja skaitlim factorization būtības ir lēns

273
00:17:01,000 --> 00:17:04,000
RSA algoritms varētu vēl kādu plaisāt tajā

274
00:17:04,000 --> 00:17:07,000
, kas ļauj viegli atšifrēšanu ziņojumus.

275
00:17:07,000 --> 00:17:10,000
Neviens nav atrasts, un atklāja šādu plaisāt vēl,

276
00:17:10,000 --> 00:17:12,000
bet tas nenozīmē, ka tāda nav.

277
00:17:12,000 --> 00:17:17,000
Teorētiski, kāds varētu būt tur izlasot visu datu šifrēti ar RSA.

278
00:17:17,000 --> 00:17:19,000
Ir vēl viens privātuma jautājumu mazliet.

279
00:17:19,000 --> 00:17:23,000
Ja Tomijs šifrē kādu ziņu, izmantojot manu publisko atslēgu

280
00:17:23,000 --> 00:17:26,000
un uzbrucējs šifrē to pašu ziņu, izmantojot manu publisko atslēgu

281
00:17:26,000 --> 00:17:29,000
uzbrucējs redzēs, ka 2 ziņojumi ir identiski

282
00:17:29,000 --> 00:17:32,000
un tādējādi zina, ko Tomijs šifrēts.

283
00:17:32,000 --> 00:17:36,000
Lai to novērstu, ziņojumi parasti polsterētām ar izlases bitiem

284
00:17:36,000 --> 00:17:39,000
pirms šifrēta, ka tas pats vēstījums šifrēts

285
00:17:39,000 --> 00:17:44,000
vairākas reizes izskatīsies dažādas, kamēr uz ziņu polsterējums ir atšķirīgs.

286
00:17:44,000 --> 00:17:47,000
Bet atceros, kā mums ir sadalīt ziņas gabalos

287
00:17:47,000 --> 00:17:50,000
lai katrs gabals ir mazāks nekā n?

288
00:17:50,000 --> 00:17:52,000
Polsterējums gabalus nozīmē, ka mēs varētu būt sadalīt lietas uz augšu

289
00:17:52,000 --> 00:17:57,000
vērā pat vairāk gabalos kopš polsterētām rieciens jābūt mazākām nekā n.

290
00:17:57,000 --> 00:18:01,000
Šifrēšanu un atšifrēšanu ir salīdzinoši dārgi ar RSA,

291
00:18:01,000 --> 00:18:05,000
un tāpēc nepieciešams, lai izjauktu up ziņu daudzās gabalos, var būt ļoti dārgi.

292
00:18:05,000 --> 00:18:09,000
Ja liela apjoma datu jābūt šifrēta un atšifrēt

293
00:18:09,000 --> 00:18:12,000
mēs varam apvienot ieguvumus no simetriskas galveno algoritmu

294
00:18:12,000 --> 00:18:16,000
ar tiem RSA saņemt gan drošību un efektivitāti.

295
00:18:16,000 --> 00:18:18,000
Lai gan mēs ne iedziļināties to šeit,

296
00:18:18,000 --> 00:18:23,000
AES ir simetriska atslēgas algoritms piemēram Vigenère un Cēzara šifrēšana

297
00:18:23,000 --> 00:18:25,000
bet daudz grūtāk kreka.

298
00:18:25,000 --> 00:18:30,000
Protams, mēs nevaram izmantot AES nenosakot vienotu slepeno atslēgu

299
00:18:30,000 --> 00:18:34,000
starp 2 sistēmās, un mēs redzējām problēmu ar to pirms tam.

300
00:18:34,000 --> 00:18:40,000
Bet tagad mēs varam izmantot DĀR, lai izveidotu kopīgu slepenu atslēgu starp 2 sistēmās.

301
00:18:40,000 --> 00:18:43,000
Mēs saucam datoru datu nosūtīšanas sūtītājam

302
00:18:43,000 --> 00:18:46,000
un dators, kas saņem datus uztvērēju.

303
00:18:46,000 --> 00:18:49,000
Uztvērējs ir RSA atslēgu pāri un nosūta

304
00:18:49,000 --> 00:18:51,000
publiskā atslēga sūtītājam.

305
00:18:51,000 --> 00:18:54,000
Sūtītājs ģenerē AES atslēgu,

306
00:18:54,000 --> 00:18:57,000
šifrē to ar saņēmēja RSA publisko atslēgu,

307
00:18:57,000 --> 00:19:00,000
un nosūta AES atslēgu uz uztvērēju.

308
00:19:00,000 --> 00:19:04,000
Uztvērējs atšifrē ziņojumu ar savu RSA privāto atslēgu.

309
00:19:04,000 --> 00:19:09,000
Gan sūtītājs un saņēmējs tagad ir kopīga AES atslēgu starp tiem.

310
00:19:09,000 --> 00:19:14,000
AES, kas ir daudz ātrāks par šifrēšanu un atšifrēšanu nekā RSA,

311
00:19:14,000 --> 00:19:18,000
tagad var izmantot, lai šifrētu lielus datu apjomus un nosūtīt tos uz uztvērēju,

312
00:19:18,000 --> 00:19:21,000
kurš var atšifrēt, izmantojot to pašu atslēgu.

313
00:19:21,000 --> 00:19:26,000
AES, kas ir daudz ātrāks par šifrēšanu un atšifrēšanu nekā RSA,

314
00:19:26,000 --> 00:19:30,000
tagad var izmantot, lai šifrētu lielus datu apjomus un nosūtīt tos uz uztvērēju,

315
00:19:30,000 --> 00:19:32,000
kurš var atšifrēt, izmantojot to pašu atslēgu.

316
00:19:32,000 --> 00:19:36,000
Mēs vienkārši nepieciešams RSA nodot koplietojamo taustiņu.

317
00:19:36,000 --> 00:19:40,000
Mums vairs nav nepieciešams izmantot DĀR vispār.

318
00:19:40,000 --> 00:19:46,000
Izskatās, man ziņu.

319
00:19:46,000 --> 00:19:49,000
Tas nav svarīgi, ja kāds lasītu, kas ir uz papīra lidmašīnas pirms es nozvejotas to

320
00:19:49,000 --> 00:19:55,000
jo es esmu tikai viens ar privāto atslēgu.

321
00:19:55,000 --> 00:19:57,000
Pieņemsim atšifrēt katru no ziņojuma daļām.

322
00:19:57,000 --> 00:20:07,000
Pirmais rieciens, 658, mēs paceļam uz D jaudu, kas ir 185,

323
00:20:07,000 --> 00:20:18,000
MOD N, kas ir 989, ir vienāda ar 67,

324
00:20:18,000 --> 00:20:24,000
kas ir vēstule C ASCII.

325
00:20:24,000 --> 00:20:31,000
Tagad, uz otro gabalu.

326
00:20:31,000 --> 00:20:35,000
Otrais gabals ir vērtība 15,

327
00:20:35,000 --> 00:20:41,000
kas mēs paceļam uz 185. varas,

328
00:20:41,000 --> 00:20:51,000
MOD 989, un tas ir vienāds ar 83

329
00:20:51,000 --> 00:20:57,000
kas ir burts S ASCII.

330
00:20:57,000 --> 00:21:06,000
Tagad jau trešo rieciens, kura vērtība 799, mēs paaugstināt līdz 185,

331
00:21:06,000 --> 00:21:17,000
MOD 989, un tas ir vienāds ar 53,

332
00:21:17,000 --> 00:21:24,000
kas ir rakstura 5 ASCII vērtību.

333
00:21:24,000 --> 00:21:30,000
Tagad par pēdējo gabalu, kas ir vērtība 975,

334
00:21:30,000 --> 00:21:41,000
Mēs paaugstināt līdz 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
un tas ir vienāds ar 48, kas ir vērtība rakstzīmju 0 ASCII.

336
00:21:51,000 --> 00:21:57,000
Mans vārds ir Rob Bowden, un tas ir CS50.

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

338
00:22:06,000 --> 00:22:08,000
DĀR vispār.

339
00:22:08,000 --> 00:22:14,000
DĀR vispār. [Smiekli]

340
00:22:14,000 --> 00:22:17,000
Vispār.