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
[Ito ay CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Natin tingnan sa RSA, ang isang malawak na ginamit na algorithm para sa pag-encrypt data.

5
00:00:11,000 --> 00:00:16,000
Encryption algorithm tulad ng Caesar at Vigenère ciphers ay hindi napaka-secure na.

6
00:00:16,000 --> 00:00:20,000
Sa Caesar cipher, ang isang pag-atake ay lamang kailangang subukan ng 25 iba't ibang mga susi

7
00:00:20,000 --> 00:00:22,000
upang makakuha ng plain text ang mensahe.

8
00:00:22,000 --> 00:00:25,000
Habang ang Vigenère cipher ay mas ligtas kaysa sa Caesar cipher

9
00:00:25,000 --> 00:00:28,000
dahil sa ang mas malaking espasyo ng paghahanap para sa key, sa sandaling isang nang-aatake

10
00:00:28,000 --> 00:00:30,000
alam ang haba ng susi sa isang Vigenère cipher,

11
00:00:30,000 --> 00:00:34,000
na maaaring tinutukoy sa pamamagitan ng isang pagtatasa ng mga pattern sa naka-encrypt na teksto,

12
00:00:34,000 --> 00:00:38,000
ang Vigenère cipher ay hindi na mas secure kaysa sa Caesar cipher.

13
00:00:38,000 --> 00:00:42,000
RSA, sa kabilang banda, ay hindi mahina sa pag-atake tulad nito.

14
00:00:42,000 --> 00:00:45,000
Ang Caesar cipher and Vigenère cipher gamitin ang parehong key

15
00:00:45,000 --> 00:00:47,000
sa parehong-encrypt at decrypt ng isang mensahe.

16
00:00:47,000 --> 00:00:51,000
Ang property na ito ay gumagawa ng mga ciphers simetriko key algorithm.

17
00:00:51,000 --> 00:00:54,000
Ang pangunahing problema sa symmetric key algorithm

18
00:00:54,000 --> 00:00:57,000
na umaasa sila sa encrypt at sa pagpapadala ng mensahe

19
00:00:57,000 --> 00:00:59,000
at isa pagtanggap at decrypting ang mensahe

20
00:00:59,000 --> 00:01:03,000
pa sumang-ayon agad sa key sila ay parehong gamitin.

21
00:01:03,000 --> 00:01:06,000
Ngunit kami ay isang bit ng isang startup problema dito.

22
00:01:06,000 --> 00:01:10,000
Paano 2 computer na nais na makipag-ugnay magtatag ng sikretong key sa pagitan ng mga ito?

23
00:01:10,000 --> 00:01:16,000
Kung dapat na lihim ang key, pagkatapos kailangan namin ng isang paraan upang i-encrypt at decrypt ang susi.

24
00:01:16,000 --> 00:01:18,000
Kung ang lahat ng mayroon kaming ay simetriko key cryptography

25
00:01:18,000 --> 00:01:21,000
pagkatapos lamang namin na bumalik sa parehong problema.

26
00:01:21,000 --> 00:01:25,000
RSA, sa kabilang banda, ay gumagamit ng isang pares ng mga susi,

27
00:01:25,000 --> 00:01:28,000
isa para sa encryption at isa pa para sa decryption.

28
00:01:28,000 --> 00:01:32,000
Isa ay tinatawag na ang pampublikong key, at ang iba pa ay ang pribadong key.

29
00:01:32,000 --> 00:01:34,000
Ng public key na ginamit upang i-encrypt ng mga mensahe.

30
00:01:34,000 --> 00:01:38,000
Tulad ng maaaring mong hulaan ng pangalan nito, maaari naming ibahagi ang aming pampublikong key sa

31
00:01:38,000 --> 00:01:43,000
sinuman na gusto namin walang pag-kompromiso sa seguridad ng isang naka-encrypt na mensahe.

32
00:01:43,000 --> 00:01:45,000
Mensahe-encrypt gamit ang isang pampublikong key

33
00:01:45,000 --> 00:01:49,000
maaari lamang decrypted na may kaukulang pribadong key.

34
00:01:49,000 --> 00:01:53,000
Habang maaari mong ibahagi ang iyong mga pampublikong key, dapat mong laging panatilihin ang iyong pribadong key lihim.

61
00:01:55,000 --> 00:01:58,000
at lamang ang pribadong key ay maaaring gamitin upang i-decrypt mensahe

62
00:01:58,000 --> 00:02:02,000
kung ang 2 mga gumagamit ay nais na magpadala ng mga mensahe na naka-encrypt na may RSA

63
00:02:02,000 --> 00:02:07,000
pabalik-balik sa kapwa mga gumagamit ay kailangang magkaroon ng kanilang sariling pampublikong at pribadong key na pares.

64
00:02:07,000 --> 00:02:10,000
Mensahe mula sa user 1 user 2

65
00:02:10,000 --> 00:02:15,000
lamang gamitin ang key user 2 pares, at mga mensahe mula sa user 2 user 1

66
00:02:15,000 --> 00:02:17,000
lamang gamitin ang key pares ng user 1 ng.

67
00:02:17,000 --> 00:02:21,000
Ang katotohanan na may 2 magkahiwalay na mga key upang i-encrypt at i-decrypt mensahe

68
00:02:21,000 --> 00:02:24,000
gumagawa ng RSA ng tabingi key algorithm.

69
00:02:24,000 --> 00:02:28,000
Hindi namin kailangan upang i-encrypt ang pampublikong key upang ipadala ito sa ibang computer

70
00:02:28,000 --> 00:02:31,000
dahil ang susi ay pampublikong pa rin.

71
00:02:31,000 --> 00:02:33,000
Nangangahulugan ito na ang RSA ay hindi ang parehong problema sa startup

72
00:02:33,000 --> 00:02:36,000
bilang simetriko key algorithm.

73
00:02:36,000 --> 00:02:39,000
Kaya kung gusto kong magpadala ng mensahe gamit ang RSA encryption

74
00:02:39,000 --> 00:02:42,000
Rob, ako munang public key ng Rob.

75
00:02:42,000 --> 00:02:47,000
Upang bumuo ng isang pares ng mga susi, Rob ay kailangang pumili ng 2 malaking prime numero.

76
00:02:47,000 --> 00:02:50,000
Ang mga numerong ito ay ginagamit sa parehong pampubliko at pribadong key,

77
00:02:50,000 --> 00:02:54,000
ngunit ang public key ay lamang gumamit ng mga produkto ng mga 2 numero,

78
00:02:54,000 --> 00:02:56,000
hindi ang mga numero mismo.

79
00:02:56,000 --> 00:02:59,000
Kapag ako-encrypt ang mensahe gamit ang pampublikong key ng Rob

80
00:02:59,000 --> 00:03:01,000
Maaari ko bang ipadala ang mensahe sa Rob.

81
00:03:01,000 --> 00:03:05,000
Para sa isang computer, factoring numero ay isang mahirap na problema.

82
00:03:05,000 --> 00:03:09,000
Ng public key, tandaan, ginamit ang produkto ng 2 prime numero.

83
00:03:09,000 --> 00:03:12,000
Ang produktong ito ay dapat magkaroon ng 2 kadahilanan lamang,

84
00:03:12,000 --> 00:03:16,000
kung saan mangyayari ang mga numero na bumubuo sa pribadong key.

85
00:03:16,000 --> 00:03:20,000
Upang i-decrypt ang mensahe, RSA ay gamitin ang pribadong key

86
00:03:20,000 --> 00:03:25,000
o ang mga numero multiply kasama sa proseso ng paglikha ng pampublikong key.

87
00:03:25,000 --> 00:03:28,000
Dahil ito computationally ang mahirap salik ang bilang

88
00:03:28,000 --> 00:03:32,000
ginagamit sa isang pampublikong key sa 2 numero na ginamit sa pribadong key

89
00:03:32,000 --> 00:03:36,000
ito ay mahirap para sa isang pag-atake upang malaman kung ang pribadong key

90
00:03:36,000 --> 00:03:39,000
na kinakailangan upang i-decrypt ang mensahe.

91
00:03:39,000 --> 00:03:43,000
Ngayon ipaalam sa pumunta sa ilang mga mas mababang mga detalye ng antas ng RSA.

92
00:03:43,000 --> 00:03:46,000
Sabihin unang makita kung paano namin maaaring bumuo ng isang pares ng mga susi.

93
00:03:46,000 --> 00:03:49,000
Una, kakailanganin naming ang mga 2 prime numero.

94
00:03:49,000 --> 00:03:52,000
Susubukan naming tawagan mga 2 numero p at q.

95
00:03:52,000 --> 00:03:56,000
Upang makuha p at q, sa kasanayan namin pseudorandomly bumuo ng

96
00:03:56,000 --> 00:03:59,000
malaking numero at pagkatapos ay gamitin ang isang pagsubok para sa pagtukoy kung o hindi

97
00:03:59,000 --> 00:04:02,000
mga numero ay marahil prime.

98
00:04:02,000 --> 00:04:05,000
Maaari naming patuloy na pagbuo ng mga random na numero nang paulit-ulit

99
00:04:05,000 --> 00:04:08,000
hanggang kami ay may 2 primes na maaari naming gamitin.

100
00:04:08,000 --> 00:04:15,000
Dito sabihin pick p = 23 at q = 43.

101
00:04:15,000 --> 00:04:19,000
Tandaan, sa kasanayan, p at q dapat mas malaking numero.

102
00:04:19,000 --> 00:04:22,000
Tulad ng alam namin, ang mas malaki ang mga numero, ang mas mahirap ito ay

103
00:04:22,000 --> 00:04:25,000
upang magpahaginit isang naka-encrypt na mensahe.

104
00:04:25,000 --> 00:04:29,000
Ngunit ito rin mas mahal na-encrypt at decrypt mensahe.

105
00:04:29,000 --> 00:04:33,000
Ngayon madalas na inirerekomenda na p at q ay hindi bababa sa 1024 bits,

106
00:04:33,000 --> 00:04:37,000
kung saan naglalagay ang bawat numero sa mahigit sa 300 decimal digit.

107
00:04:37,000 --> 00:04:40,000
Ngunit makikita namin kukunin ang mga maliit na mga numero para sa halimbawang ito.

108
00:04:40,000 --> 00:04:43,000
Ngayon makikita na namin multiply ang p at q nang magkasama upang makakuha ng isang 3rd numero,

109
00:04:43,000 --> 00:04:45,000
kung saan kami tatawag n.

110
00:04:45,000 --> 00:04:55,000
Sa aming kaso, n = 23 * 43, kung saan = 989.

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

112
00:04:58,000 --> 00:05:02,000
Susunod na namin makikita multiply p - 1 may q - 1

113
00:05:02,000 --> 00:05:05,000
upang makakuha ng ika-4 na numero, kung saan kami tatawag m.

114
00:05:05,000 --> 00:05:15,000
Sa aming kaso, m = 22 * ​​42, kung saan = 924.

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

116
00:05:18,000 --> 00:05:22,000
Ngayon, kailangan nating e isang numero na medyo prime sa m

117
00:05:22,000 --> 00:05:25,000
at mas mababa sa m.

118
00:05:25,000 --> 00:05:28,000
Dalawang numero ay relatibong prime o coprime

119
00:05:28,000 --> 00:05:33,000
kung lamang positibong integer na divides sa kanila ng parehong pantay-pantay ay 1.

120
00:05:33,000 --> 00:05:37,000
Sa ibang salita, ang pinakadakilang karaniwang panghati ng e at m

121
00:05:37,000 --> 00:05:39,000
dapat na 1.

122
00:05:39,000 --> 00:05:44,000
Sa pagsasagawa, ito ay karaniwan para sa e prime bilang 65,537

123
00:05:44,000 --> 00:05:48,000
hangga't ang bilang na ito ay hindi mangyayari sa isang kadahilanan ng m.

124
00:05:48,000 --> 00:05:53,000
Para sa aming mga susi, magpapadala kami pumili e = 5

125
00:05:53,000 --> 00:05:57,000
dahil 5 ay relatibong prime sa 924.

126
00:05:57,000 --> 00:06:01,000
Panghuli, kakailanganin naming isa pang numero, kung saan kami tatawag d.

127
00:06:01,000 --> 00:06:11,000
D dapat ilang halaga na natutugunan ang equation de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Mod m Sumisimbolo na ito gagamitin namin ang isang bagay na tinatawag na Modular aritmetika.

129
00:06:17,000 --> 00:06:21,000
Sa Modular aritmetika, sa sandaling ang numero ng ay nakakakuha ng mas mataas kaysa sa ilang itaas bound

130
00:06:21,000 --> 00:06:24,000
ito I-wrap ang pabalik sa paligid sa 0.

131
00:06:24,000 --> 00:06:27,000
Orasan A, halimbawa, gumagamit ng Modular aritmetika.

132
00:06:27,000 --> 00:06:31,000
Isang minuto pagkatapos 1:59, halimbawa, ay 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Ang kamay ng minuto ay balot sa paligid ng 0

135
00:06:36,000 --> 00:06:39,000
kapag maabot ang isang pang-itaas na nakatali ng 60.

136
00:06:39,000 --> 00:06:46,000
Kaya, maaari naming sabihin 60 ay katumbas ng 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
at 125 ay katumbas sa 65 ay katumbas sa 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Ang aming pampublikong key ay ang pares e at n

139
00:07:02,000 --> 00:07:09,000
kung saan sa kasong ito e ay 5 at n ay 989.

140
00:07:09,000 --> 00:07:15,000
Aming pribadong key ay ang pares d at n,

141
00:07:15,000 --> 00:07:22,000
kung alin sa aming kaso ay 185 at 989.

142
00:07:22,000 --> 00:07:25,000
Pansinin na ang aming mga orihinal na primes p at q hindi lilitaw

143
00:07:25,000 --> 00:07:29,000
kahit saan sa aming mga pribado o pampublikong key.

144
00:07:29,000 --> 00:07:33,000
Ngayon na namin ang aming pares ng key, sabihin kumuha ng isang pagtingin sa kung paano maaari naming i-encrypt ang

145
00:07:33,000 --> 00:07:36,000
at i-decrypt ng mensahe.

146
00:07:36,000 --> 00:07:38,000
Gusto kong magpadala ng mensahe sa Rob,

147
00:07:38,000 --> 00:07:42,000
kaya siya ay upang bumuo ng ang key na ito pares.

148
00:07:42,000 --> 00:07:46,000
Pagkatapos kong tanungin Rob para sa kanyang public key, na makikita ko bang gamitin ang

149
00:07:46,000 --> 00:07:48,000
upang i-encrypt ng isang mensahe upang ipadala sa kanya.

150
00:07:48,000 --> 00:07:53,000
Tandaan, lubos na okay para sa Rob upang ibahagi ang kanyang pampublikong key sa akin.

151
00:07:53,000 --> 00:07:56,000
Ngunit hindi ito ay okay upang ibahagi ang kanyang pribadong key.

152
00:07:56,000 --> 00:08:00,000
Wala akong anumang mga ideya kung ano ang kanyang pribadong key.

153
00:08:00,000 --> 00:08:03,000
Maaari naming masira ang aming mensahe m sa ilang chunks

154
00:08:03,000 --> 00:08:07,000
lahat ng mga mas maliit kaysa sa n at pagkatapos ay i-encrypt ang bawat isa sa mga chunks.

155
00:08:07,000 --> 00:08:12,000
Susubukan naming i-encrypt ang CS50 ang string, na kung saan maaari naming masira up sa 4 chunks,

156
00:08:12,000 --> 00:08:14,000
isa sa bawat titik.

157
00:08:14,000 --> 00:08:17,000
Upang i-encrypt ang aking mensahe, kailangan ko upang i-convert ito sa

158
00:08:17,000 --> 00:08:20,000
ang ilang mga uri ng numeric na representasyon.

159
00:08:20,000 --> 00:08:25,000
Natin pagdugtungin ang mga ASCII na halaga sa ang mga character sa aking mensahe.

160
00:08:25,000 --> 00:08:28,000
Upang i-encrypt ang isang ibinigay na mensahe m

161
00:08:28,000 --> 00:08:37,000
Kailangan ko upang makalkula ang c = m sa e (mod n).

162
00:08:37,000 --> 00:08:40,000
Ngunit m dapat mas maliit kaysa sa n,

163
00:08:40,000 --> 00:08:45,000
kung ang buong mensahe ay hindi maaaring ipinahayag modulo n.

164
00:08:45,000 --> 00:08:49,000
Namin masira m sa ilang mga chunks, lahat ng mga ito ay mas maliit kaysa sa n,

165
00:08:49,000 --> 00:08:52,000
at i-encrypt ang bawat isa sa mga chunks.

166
00:08:52,000 --> 00:09:03,000
Encrypt ang bawat isa sa mga chunks, makuha namin C1 = 67 sa 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Para sa aming ikalawang tipak mayroon kaming 83 sa 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Para sa aming third tipak mayroon kaming 53 sa 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
At sa wakas, para sa aming huling tipak mayroon kaming 48 sa 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Ngayon ay maaari kaming magpadala sa paglipas ng mga naka-encrypt na halaga sa Rob.

175
00:09:54,000 --> 00:09:58,000
Narito pumunta ka, Rob.

176
00:09:58,000 --> 00:10:01,000
Habang ang aming mensahe sa flight, sabihin tumagal ng isa pang hitsura

177
00:10:01,000 --> 00:10:07,000
sa kung paano namin nakuha na halaga para sa d.

178
00:10:07,000 --> 00:10:17,000
Aming numero d kailangan upang masiyahan ang 5a = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Ginagawa d ang multiplicative kabaligtaran ng 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Given 2 integer, at b, pinalawig na Euclidean algorithm

181
00:10:28,000 --> 00:10:33,000
ay maaaring magamit upang mahanap ang pinakadakilang karaniwang panghati ng mga 2 integer.

182
00:10:33,000 --> 00:10:37,000
Mayroon din bigyan kami ng 2 iba pang mga numero, x at y,

183
00:10:37,000 --> 00:10:47,000
na masiyahan ang equation palakol + = ang pinakadakilang karaniwang panghati ng isang at b.

184
00:10:47,000 --> 00:10:49,000
Paano ito makakatulong sa amin?

185
00:10:49,000 --> 00:10:52,000
Well, i-plug sa e = 5 para sa isang

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

187
00:10:56,000 --> 00:10:59,000
na namin alam na ang mga bilang na ito ay coprime.

188
00:10:59,000 --> 00:11:03,000
Kanilang mga pinakadakilang karaniwang panghati ay 1.

189
00:11:03,000 --> 00:11:09,000
Ito ay nagbibigay sa amin 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Ngunit kung lamang namin pakialam tungkol sa lahat ng modulo 924

192
00:11:22,000 --> 00:11:25,000
pagkatapos ay maaari naming ilagay ang - 924y.

193
00:11:25,000 --> 00:11:27,000
Isipin pabalik sa orasan.

194
00:11:27,000 --> 00:11:31,000
Kung ang kamay ng minuto sa 1 at ang eksaktong 10 oras pumasa,

195
00:11:31,000 --> 00:11:35,000
alam namin ang kamay ng minuto ay pa rin sa 1.

196
00:11:35,000 --> 00:11:39,000
Narito namin magsimula sa 1 at pagkatapos ay I-wrap sa paligid eksaktong y beses,

197
00:11:39,000 --> 00:11:41,000
kaya pa rin namin sa 1.

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

199
00:11:49,000 --> 00:11:55,000
At dito x na ito ay ang parehong bilang d na namin ang hinahanap para sa bago,

200
00:11:55,000 --> 00:11:58,000
kaya kung ginagamit namin ang pinalawig na Euclidean algorithm

201
00:11:58,000 --> 00:12:04,000
upang makuha ang numero ng x, na ang bilang dapat naming gamitin ang aming d.

202
00:12:04,000 --> 00:12:07,000
Ngayon sabihin magpatakbo ng pinalawig na Euclidean algorithm para sa isang = 5

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

204
00:12:11,000 --> 00:12:14,000
Gagamitin namin ang isang pamamaraan na tinatawag talahanayan ng paraan ng.

205
00:12:14,000 --> 00:12:21,000
Aming talahanayan ay 4 haligi, x, y, d, at k.

206
00:12:21,000 --> 00:12:23,000
Aming talahanayan nagsisimula off na may 2 mga hilera.

207
00:12:23,000 --> 00:12:28,000
Sa unang hilera ay may kami ng 1, 0, pagkatapos ay ang aming halaga ng isang, na kung saan ay 5,

208
00:12:28,000 --> 00:12:37,000
at ang aming pangalawang hilera ay 0, 1, at ang aming halaga para sa b, na 924.

209
00:12:37,000 --> 00:12:40,000
Ang halaga ng ika-4 na haligi, k, ay ang resulta

210
00:12:40,000 --> 00:12:45,000
ng paghahati ang halaga ng d sa hilera itaas nito na may halaga ng d

211
00:12:45,000 --> 00:12:49,000
sa parehong hilera.

212
00:12:49,000 --> 00:12:56,000
Mayroon kaming 5 na hinati sa pamamagitan ng 924 ay 0 na may ilang natitira.

213
00:12:56,000 --> 00:12:59,000
Iyon ay nangangahulugang mayroon kaming k = 0.

214
00:12:59,000 --> 00:13:05,000
Ngayon ang halaga ng bawat iba pang mga cell ay ang halaga ng cell 2 mga hilera sa itaas nito

215
00:13:05,000 --> 00:13:09,000
minus ang halaga ng hilera itaas nito beses k.

216
00:13:09,000 --> 00:13:11,000
Natin magsimula sa d sa 3rd hilera.

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

218
00:13:19,000 --> 00:13:25,000
Susunod na kami ay may 0 - 1 * 0 na 0

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

220
00:13:30,000 --> 00:13:33,000
Hindi masyadong masamang, kaya sabihin ilipat sa sa susunod na hilera.

221
00:13:33,000 --> 00:13:36,000
Una kailangan namin ang aming halaga ng k.

222
00:13:36,000 --> 00:13:43,000
924 na hinati sa pamamagitan ng 5 = 184 na may ilang natitira,

223
00:13:43,000 --> 00:13:46,000
kaya ang aming halaga para sa k ay 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Lahat ng karapatan, sabihin sa susunod na hilera.

227
00:14:07,000 --> 00:14:10,000
Ang aming halaga ng k ay 1 dahil

228
00:14:10,000 --> 00:14:15,000
5 na hinati sa pamamagitan ng 4 = 1 may ilang natitira.

229
00:14:15,000 --> 00:14:17,000
Punan natin sa iba pang mga hanay.

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

233
00:14:33,000 --> 00:14:35,000
Natin makita kung ano ang aming susunod na halaga ng k ay.

234
00:14:35,000 --> 00:14:40,000
Well, mukhang mayroon kaming 4 na hinati sa pamamagitan ng 1, na kung saan ay 4.

235
00:14:40,000 --> 00:14:43,000
Sa kasong ito na kung saan kami ay paghahati ng 1 tulad k na katumbas ng

236
00:14:43,000 --> 00:14:50,000
ang halaga ng d sa itaas hilera ay nangangahulugan na tapos na kami sa aming algorithm.

237
00:14:50,000 --> 00:14:58,000
Maaari naming makita dito mayroon kaming x = 185 at y = -1 sa huling hilera.

238
00:14:58,000 --> 00:15:00,000
Natin ngayon bumalik sa aming orihinal na layunin.

239
00:15:00,000 --> 00:15:04,000
Sinabi namin na ang halaga ng x bilang resulta ng patakbuhin ito algorithm

240
00:15:04,000 --> 00:15:08,000
ay ang multiplicative kabaligtaran ng isang (mod b).

241
00:15:08,000 --> 00:15:15,000
Iyon ay nangangahulugan na ang 185 ang multiplicative kabaligtaran ng 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
na nangangahulugan na kami ay may isang halaga ng 185 para d.

243
00:15:20,000 --> 00:15:23,000
Ang katotohanan na ang d = 1 sa huling hilera

244
00:15:23,000 --> 00:15:26,000
verify e na coprime sa m.

245
00:15:26,000 --> 00:15:30,000
Kung ito ay hindi 1 pagkatapos ay namin upang pumili ng isang bagong e.

246
00:15:30,000 --> 00:15:33,000
Ngayon ipaalam sa makita kung Rob ay natanggap ang aking mensahe.

247
00:15:33,000 --> 00:15:35,000
Kapag may nagpadala sa akin ng isang naka-encrypt na mensahe

248
00:15:35,000 --> 00:15:38,000
hangga't ko ang iningatan ang aking pribadong key lihim ng

249
00:15:38,000 --> 00:15:41,000
Ako ang isa lamang na maaari i-decrypt ang mensahe.

250
00:15:41,000 --> 00:15:46,000
Upang i-decrypt isang tipak c ko makalkula ang orihinal na mensahe

251
00:15:46,000 --> 00:15:53,000
ay katumbas sa tipak sa d kapangyarihan (mod n).

252
00:15:53,000 --> 00:15:57,000
Tandaan na d at n mula sa aking pribadong key.

253
00:15:57,000 --> 00:16:01,000
Upang makakuha ng buong mensahe mula sa chunks namin i-decrypt ang bawat tipak

254
00:16:01,000 --> 00:16:04,000
at pagdugtungin ang mga resulta.

255
00:16:04,000 --> 00:16:08,000
Eksakto kung paano ka tiwasay ang RSA?

256
00:16:08,000 --> 00:16:10,000
Ang katotohanan ay, hindi namin alam.

257
00:16:10,000 --> 00:16:14,000
Security ay batay sa kung gaano katagal ito ay magdudulot ng isang nang-aatake sa magpahaginit ng mensahe

258
00:16:14,000 --> 00:16:16,000
-encrypt na may RSA.

259
00:16:16,000 --> 00:16:19,000
Tandaan na ang isang pag-atake ay may access sa iyong mga pampublikong key,

260
00:16:19,000 --> 00:16:21,000
na naglalaman ng parehong e at n.

261
00:16:21,000 --> 00:16:26,000
Kung ang umaatake ang namamahala sa salik n sa nito 2 primes, p at q,

262
00:16:26,000 --> 00:16:30,000
maaaring siya kalkulahin d gamit ang pinalawig na Euclidean algorithm.

263
00:16:30,000 --> 00:16:35,000
Ito ay nagbibigay sa kanya ang pribadong key, na maaaring magamit upang i-decrypt ang mensahe anumang.

264
00:16:35,000 --> 00:16:38,000
Ngunit kung gaano kabilis namin salik ng mga integer?

265
00:16:38,000 --> 00:16:41,000
Muli, hindi namin alam.

266
00:16:41,000 --> 00:16:43,000
Walang natagpuan ang isang mabilis na paraan ng paggawa nito,

267
00:16:43,000 --> 00:16:46,000
na nangangahulugan na ang naibigay na malaki sapat n

268
00:16:46,000 --> 00:16:49,000
tumagal ang isang attacker unrealistically mahaba

269
00:16:49,000 --> 00:16:51,000
salik ang bilang.

270
00:16:51,000 --> 00:16:54,000
Kung may isang taong nagsiwalat isang mabilis na paraan ng integer factoring

271
00:16:54,000 --> 00:16:57,000
RSA ay nasira.

272
00:16:57,000 --> 00:17:01,000
Ngunit kahit na integer paktorisasyon ay likas na mabagal

273
00:17:01,000 --> 00:17:04,000
ang RSA algorithm ay maaaring pa rin magkaroon ng ilang mga depekto sa

274
00:17:04,000 --> 00:17:07,000
na nagbibigay-daan para sa madaling decryption ng mga mensahe.

275
00:17:07,000 --> 00:17:10,000
Walang sinuman ay natagpuan at ipinahayag tulad kapintasan,

276
00:17:10,000 --> 00:17:12,000
ngunit na ay hindi nangangahulugan na hindi isa ay umiiral.

277
00:17:12,000 --> 00:17:17,000
Sa teorya, ang isang tao ay maaaring ang doon pagbabasa ng lahat ng data na na-encrypt na may RSA.

278
00:17:17,000 --> 00:17:19,000
May isa pang bit ng isang isyu sa privacy.

279
00:17:19,000 --> 00:17:23,000
Kung Tommy ine-encrypt ng ilang mensahe gamit ang aking pampublikong key

280
00:17:23,000 --> 00:17:26,000
at isang pag-atake ine-encrypt ng ang parehong mensahe na gamit ang aking pampublikong key

281
00:17:26,000 --> 00:17:29,000
umaatake ay makita na ang 2 mensahe ay magkapareho

282
00:17:29,000 --> 00:17:32,000
at sa gayon ay malaman kung ano Tommy-encrypt.

283
00:17:32,000 --> 00:17:36,000
Upang maiwasan ito, ang mga mensahe ay karaniwang may palaman sa random bits

284
00:17:36,000 --> 00:17:39,000
bago ine-encrypt sa gayon ay ang parehong mensahe na-encrypt

285
00:17:39,000 --> 00:17:44,000
nang maraming beses ang magiging hitsura ng iba't ibang hangga't ang padding sa mensahe ay naiiba.

286
00:17:44,000 --> 00:17:47,000
Ngunit tandaan kung paano mayroon kaming upang hatiin ang mga mensahe sa mga chunks

287
00:17:47,000 --> 00:17:50,000
sa gayon na ang bawat tipak ay mas maliit kaysa sa n?

288
00:17:50,000 --> 00:17:52,000
Padding ang chunks ay nangangahulugan na maaari naming upang hatiin ang mga bagay up

289
00:17:52,000 --> 00:17:57,000
sa higit pang mga chunks dahil may palaman tipak ay dapat na mas maliit kaysa sa n.

290
00:17:57,000 --> 00:18:01,000
Encryption at decryption medyo mahal sa RSA,

291
00:18:01,000 --> 00:18:05,000
at sa gayon ay nangangailangan masira ng mensahe sa maraming mga chunks ay maaaring masyadong mahal.

292
00:18:05,000 --> 00:18:09,000
Kung ang isang malaking dami ng data kailangang naka-encrypt at decrypted

293
00:18:09,000 --> 00:18:12,000
maaari naming pagsamahin ang mga benepisyo ng simetriko key algorithm

294
00:18:12,000 --> 00:18:16,000
sa mga RSA upang makakuha ng parehong seguridad at kahusayan.

295
00:18:16,000 --> 00:18:18,000
Bagaman hindi namin ay pumunta sa dito,

296
00:18:18,000 --> 00:18:23,000
AES ay symmetric key algorithm tulad ng Vigenère at Caesar ciphers

297
00:18:23,000 --> 00:18:25,000
ngunit mas mahirap sa magpahaginit.

298
00:18:25,000 --> 00:18:30,000
Siyempre, hindi namin maaaring gamitin ang AES walang pagtaguyod ng isang nakabahaging sikretong key

299
00:18:30,000 --> 00:18:34,000
sa pagitan ng 2 system, at nakita namin ang problema sa na bago.

300
00:18:34,000 --> 00:18:40,000
Ngunit ngayon na maaari naming gamitin RSA magtatag sa nakabahaging sikretong key sa pagitan ng 2 system.

301
00:18:40,000 --> 00:18:43,000
Susubukan naming tawagan ang computer sa pagpapadala ng data sa nagpadala

302
00:18:43,000 --> 00:18:46,000
at computer pagtanggap ng data ang receiver.

303
00:18:46,000 --> 00:18:49,000
Receiver ay isang RSA key pares at ipapadala

304
00:18:49,000 --> 00:18:51,000
ang pampublikong key sa nagpadala.

305
00:18:51,000 --> 00:18:54,000
Ang nagpadala ay bumubuo ng isang AES key,

306
00:18:54,000 --> 00:18:57,000
ine-encrypt ito sa RSA public key ang receiver,

307
00:18:57,000 --> 00:19:00,000
at ipapadala ang AES key sa receiver.

308
00:19:00,000 --> 00:19:04,000
Receiver ang decrypts ang mensahe na may RSA pribadong key.

309
00:19:04,000 --> 00:19:09,000
Parehong sa nagpadala at ang receiver ngayon ay may isang shared key AES sa pagitan ng mga ito.

310
00:19:09,000 --> 00:19:14,000
AES, na mas mabilis sa encryption at decryption kaysa RSA,

311
00:19:14,000 --> 00:19:18,000
ay maaari na ngayong gamitin upang i-encrypt ang malaking volume ng data at ipadala ang mga ito sa receiver,

312
00:19:18,000 --> 00:19:21,000
na maaaring i-decrypt gamit ang parehong key.

313
00:19:21,000 --> 00:19:26,000
AES, na mas mabilis sa encryption at decryption kaysa RSA,

314
00:19:26,000 --> 00:19:30,000
ay maaari na ngayong gamitin upang i-encrypt ang malaking volume ng data at ipadala ang mga ito sa receiver,

315
00:19:30,000 --> 00:19:32,000
na maaaring i-decrypt gamit ang parehong key.

316
00:19:32,000 --> 00:19:36,000
Kailangan lang namin RSA upang ilipat ang ibinahagi key.

317
00:19:36,000 --> 00:19:40,000
Hindi na namin kailangang gumamit ng RSA sa lahat.

318
00:19:40,000 --> 00:19:46,000
Mukhang Mayroon akong isang mensahe.

319
00:19:46,000 --> 00:19:49,000
Hindi mahalaga kung sinuman basahin kung ano ang sa eroplano papel bago nahuli ko ito

320
00:19:49,000 --> 00:19:55,000
dahil ako ang isa lamang na ang pribadong key.

321
00:19:55,000 --> 00:19:57,000
Natin i-decrypt ang bawat isa ng ang mga chunks sa mensahe.

322
00:19:57,000 --> 00:20:07,000
Ang unang tigkal, 658, itataas namin sa d kapangyarihan, na kung saan ay 185,

323
00:20:07,000 --> 00:20:18,000
mod n, kung saan ay 989, ay katumbas ng 67,

324
00:20:18,000 --> 00:20:24,000
na ang sulat C sa ASCII.

325
00:20:24,000 --> 00:20:31,000
Ngayon, papunta sa pangalawang tipak.

326
00:20:31,000 --> 00:20:35,000
Ang pangalawang tipak ay halaga 15,

327
00:20:35,000 --> 00:20:41,000
na aming itataas sa 185 kapangyarihan,

328
00:20:41,000 --> 00:20:51,000
mod 989, at ito ay katumbas ng 83

329
00:20:51,000 --> 00:20:57,000
na ang letrang S sa ASCII.

330
00:20:57,000 --> 00:21:06,000
Ngayon para sa ikatlong tigkal, na may halaga 799, itataas namin sa 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, at ito ay katumbas ng 53,

332
00:21:17,000 --> 00:21:24,000
na ang halaga ng character 5 sa ASCII.

333
00:21:24,000 --> 00:21:30,000
Ngayon para sa huling tipak, na may halaga 975,

334
00:21:30,000 --> 00:21:41,000
itataas namin sa 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
at ito ay katumbas ng 48, na kung saan ay ang halaga ng character 0 sa ASCII.

336
00:21:51,000 --> 00:21:57,000
Ang pangalan ko ay Rob Bowden, at ito ay CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA sa lahat.

339
00:22:08,000 --> 00:22:14,000
RSA sa lahat. [Tawa]

340
00:22:14,000 --> 00:22:17,000
Sa lahat.