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] [Universiti Harvard]

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

4
00:00:07,000 --> 00:00:11,000
Mari kita lihat di RSA, algoritma yang digunakan secara meluas untuk menyulitkan data.

5
00:00:11,000 --> 00:00:16,000
Algoritma penyulitan seperti Caesar dan sifer Vigenère tidak sangat selamat.

6
00:00:16,000 --> 00:00:20,000
Dengan cipher Caesar, penyerang hanya perlu cuba 25 kunci yang berbeza

7
00:00:20,000 --> 00:00:22,000
untuk mendapatkan teks mesej.

8
00:00:22,000 --> 00:00:25,000
Walaupun cipher Vigenère adalah lebih selamat daripada cipher Caesar

9
00:00:25,000 --> 00:00:28,000
kerana ruang carian yang lebih besar untuk kunci, sekali penyerang

10
00:00:28,000 --> 00:00:30,000
tahu panjang kunci dalam cipher Vigenère,

11
00:00:30,000 --> 00:00:34,000
yang boleh ditentukan melalui analisis corak dalam teks disulitkan,

12
00:00:34,000 --> 00:00:38,000
cipher Vigenère tidak adalah yang lebih selamat daripada cipher Caesar.

13
00:00:38,000 --> 00:00:42,000
RSA, di sisi lain, tidak terdedah kepada serangan seperti ini.

14
00:00:42,000 --> 00:00:45,000
Cipher Caesar dan Vigenère cipher menggunakan kekunci yang sama

15
00:00:45,000 --> 00:00:47,000
kepada kedua-dua menyulitkan dan menyahsulit mesej.

16
00:00:47,000 --> 00:00:51,000
Harta tanah ini menjadikan ini sifer kunci algoritma simetri.

17
00:00:51,000 --> 00:00:54,000
Satu masalah asas simetri dengan algoritma utama

18
00:00:54,000 --> 00:00:57,000
adalah bahawa mereka bergantung pada satu menyulitkan dan menghantar mesej

19
00:00:57,000 --> 00:00:59,000
dan satu menerima dan decrypting mesej

20
00:00:59,000 --> 00:01:03,000
telah pun bersetuju terlebih dahulu pada kekunci yang kedua-dua mereka akan menggunakan.

21
00:01:03,000 --> 00:01:06,000
Tetapi kita mempunyai sedikit masalah permulaan di sini.

22
00:01:06,000 --> 00:01:10,000
Bagaimana 2 komputer yang mahu berkomunikasi menubuhkan kunci rahsia antara mereka?

23
00:01:10,000 --> 00:01:16,000
Jika kunci mesti menjadi rahsia, maka kita memerlukan satu cara untuk menyulitkan dan menyahsulit kekunci.

24
00:01:16,000 --> 00:01:18,000
Jika semua yang kita ada adalah kunci kriptografi simetri

25
00:01:18,000 --> 00:01:21,000
maka kita baru sahaja kembali kepada masalah yang sama.

26
00:01:21,000 --> 00:01:25,000
RSA, di sisi lain, menggunakan sepasang kunci,

27
00:01:25,000 --> 00:01:28,000
satu untuk penyulitan dan lain untuk penyahsulitan.

28
00:01:28,000 --> 00:01:32,000
Satu dipanggil kunci awam, dan lain-lain adalah kunci persendirian.

29
00:01:32,000 --> 00:01:34,000
Kunci awam yang digunakan untuk menyulitkan mesej.

30
00:01:34,000 --> 00:01:38,000
Seperti yang anda sangka dengan namanya, kita boleh berkongsi kunci awam kita dengan

31
00:01:38,000 --> 00:01:43,000
sesiapa sahaja yang kita mahu tanpa menjejaskan keselamatan mesej disulitkan.

32
00:01:43,000 --> 00:01:45,000
Mesej disulitkan menggunakan kekunci awam

33
00:01:45,000 --> 00:01:49,000
hanya boleh dibuka dengan kekunci yang sepadan swasta.

34
00:01:49,000 --> 00:01:53,000
Walaupun anda boleh berkongsi kunci awam anda, anda sentiasa perlu menyimpan rahsia peribadi anda yang utama.

61
00:01:55,000 --> 00:01:58,000
dan hanya kunci persendirian boleh digunakan untuk menyahsulit mesej

62
00:01:58,000 --> 00:02:02,000
jika 2 pengguna mahu untuk menghantar mesej disulitkan dengan RSA

63
00:02:02,000 --> 00:02:07,000
belakang dan sebagainya kedua-dua pengguna perlu untuk mempunyai pasangan mereka sendiri kunci awam dan swasta.

64
00:02:07,000 --> 00:02:10,000
Mesej dari 1 pengguna kepada 2 pengguna

65
00:02:10,000 --> 00:02:15,000
hanya menggunakan sepasang utama 2 pengguna, dan mesej daripada 2 pengguna 1 pengguna

66
00:02:15,000 --> 00:02:17,000
hanya menggunakan pasangan kunci pengguna 1.

67
00:02:17,000 --> 00:02:21,000
Hakikat bahawa terdapat 2 kunci berasingan untuk menyulitkan dan menyahsulit mesej

68
00:02:21,000 --> 00:02:24,000
membuat RSA algoritma simetri utama.

69
00:02:24,000 --> 00:02:28,000
Kita tidak perlu untuk menyulitkan kunci awam dalam usaha untuk hantar ke komputer lain

70
00:02:28,000 --> 00:02:31,000
sejak kunci awam anyway.

71
00:02:31,000 --> 00:02:33,000
Ini bermakna bahawa RSA tidak mempunyai masalah permulaan yang sama

72
00:02:33,000 --> 00:02:36,000
sebagai algoritma kekunci simetri.

73
00:02:36,000 --> 00:02:39,000
Jadi jika saya mahu menghantar mesej menggunakan penyulitan RSA

74
00:02:39,000 --> 00:02:42,000
untuk Rob, saya mula-mula akan memerlukan kunci awam Rob.

75
00:02:42,000 --> 00:02:47,000
Untuk menjana sepasang kunci, Rob perlu mengambil 2 nombor perdana yang besar.

76
00:02:47,000 --> 00:02:50,000
Nombor-nombor ini akan digunakan dalam kedua-dua kunci awam dan swasta,

77
00:02:50,000 --> 00:02:54,000
tetapi kunci awam hanya akan menggunakan produk ini 2 nombor,

78
00:02:54,000 --> 00:02:56,000
bukan nombor itu sendiri.

79
00:02:56,000 --> 00:02:59,000
Apabila saya telah disulitkan mesej menggunakan kunci awam Rob

80
00:02:59,000 --> 00:03:01,000
Saya boleh menghantar mesej kepada Rob.

81
00:03:01,000 --> 00:03:05,000
Untuk komputer, nombor pemfaktoran adalah masalah yang sukar.

82
00:03:05,000 --> 00:03:09,000
Kunci awam, ingat, menggunakan produk 2 nombor perdana.

83
00:03:09,000 --> 00:03:12,000
Produk ini kemudian mesti mempunyai hanya 2 faktor,

84
00:03:12,000 --> 00:03:16,000
yang berlaku menjadi nombor yang membentuk kunci persendirian.

85
00:03:16,000 --> 00:03:20,000
Dalam usaha untuk menyahsulit mesej, RSA akan menggunakan kunci persendirian

86
00:03:20,000 --> 00:03:25,000
atau nombor didarab bersama dalam proses mewujudkan kunci awam.

87
00:03:25,000 --> 00:03:28,000
Kerana ia adalah computationally sukar untuk faktor nombor

88
00:03:28,000 --> 00:03:32,000
digunakan dalam kunci awam kepada 2 nombor yang digunakan dalam kunci persendirian

89
00:03:32,000 --> 00:03:36,000
ia adalah sukar bagi penyerang untuk memikirkan kunci persendirian

90
00:03:36,000 --> 00:03:39,000
yang akan diperlukan untuk menyahsulit mesej.

91
00:03:39,000 --> 00:03:43,000
Sekarang mari kita pergi ke beberapa maklumat tahap yang lebih rendah RSA.

92
00:03:43,000 --> 00:03:46,000
Mari kita pertama kali melihat bagaimana kita boleh menjana sepasang kunci.

93
00:03:46,000 --> 00:03:49,000
Pertama, kita perlukan 2 nombor perdana.

94
00:03:49,000 --> 00:03:52,000
Kami akan memanggil-2 nombor p dan q.

95
00:03:52,000 --> 00:03:56,000
Dalam usaha untuk memilih p dan q, dalam amalan kita pseudorandomly akan menjana

96
00:03:56,000 --> 00:03:59,000
nombor besar dan kemudian menggunakan ujian untuk menentukan sama ada atau tidak

97
00:03:59,000 --> 00:04:02,000
nombor-nombor tersebut mungkin perdana.

98
00:04:02,000 --> 00:04:05,000
Kita boleh terus menjana nombor rawak berulang-ulang kali

99
00:04:05,000 --> 00:04:08,000
sehingga kita mempunyai 2 nombor perdana yang boleh kita gunakan.

100
00:04:08,000 --> 00:04:15,000
Di sini mari kita memilih p = 23 dan q = 43.

101
00:04:15,000 --> 00:04:19,000
Ingat, dalam amalan, p dan q harus nombor yang lebih besar.

102
00:04:19,000 --> 00:04:22,000
Setakat yang kita tahu, semakin besar nombor, semakin sukar ia adalah

103
00:04:22,000 --> 00:04:25,000
retak mesej disulitkan.

104
00:04:25,000 --> 00:04:29,000
Tetapi ia juga lebih mahal untuk menyulitkan dan menyahsulit mesej.

105
00:04:29,000 --> 00:04:33,000
Hari ini ia sering disyorkan bahawa p dan q adalah sekurang-kurangnya 1024 bit,

106
00:04:33,000 --> 00:04:37,000
yang meletakkan setiap nombor di lebih 300 digit desimal.

107
00:04:37,000 --> 00:04:40,000
Tetapi kita akan memilih nombor-nombor kecil untuk contoh ini.

108
00:04:40,000 --> 00:04:43,000
Sekarang kita akan membiak p dan q bersama-sama untuk mendapatkan beberapa ke-3,

109
00:04:43,000 --> 00:04:45,000
yang kita akan panggil n.

110
00:04:45,000 --> 00:04:55,000
Dalam kes kita, n = 23 * 43, yang = 989.

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

112
00:04:58,000 --> 00:05:02,000
Seterusnya kita akan membiak p - 1 dengan q - 1

113
00:05:02,000 --> 00:05:05,000
untuk mendapatkan nombor 4, yang kita akan memanggil m.

114
00:05:05,000 --> 00:05:15,000
Dalam kes kita, m = 22 * ​​42, yang = 924.

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

116
00:05:18,000 --> 00:05:22,000
Sekarang kita akan memerlukan e nombor yang agak perdana untuk m

117
00:05:22,000 --> 00:05:25,000
dan kurang daripada m.

118
00:05:25,000 --> 00:05:28,000
Dua nombor adalah agak perdana atau coprime

119
00:05:28,000 --> 00:05:33,000
jika integer hanya positif yang membahagikan kedua-dua mereka sama rata ialah 1.

120
00:05:33,000 --> 00:05:37,000
Dalam erti kata lain, terbesar pembahagi biasa e dan m

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

122
00:05:39,000 --> 00:05:44,000
Dalam amalan, ia adalah perkara biasa untuk e untuk menjadi nombor perdana 65537

123
00:05:44,000 --> 00:05:48,000
selagi bilangan ini tidak berlaku menjadi faktor m.

124
00:05:48,000 --> 00:05:53,000
Bagi kunci kami, kami akan memilih e = 5

125
00:05:53,000 --> 00:05:57,000
sejak 5 adalah agak perdana kepada 924.

126
00:05:57,000 --> 00:06:01,000
Akhirnya, kita akan memerlukan satu nombor yang lebih, yang kita akan panggil d.

127
00:06:01,000 --> 00:06:11,000
D mesti beberapa nilai yang memuaskan persamaan de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Ini m arena menandakan kita akan menggunakan sesuatu yang dinamakan aritmetik modular.

129
00:06:17,000 --> 00:06:21,000
Dalam aritmetik modular, sekali beberapa semakin tinggi daripada beberapa batasan atas

130
00:06:21,000 --> 00:06:24,000
ia akan mengakhiri balik sekitar kepada 0.

131
00:06:24,000 --> 00:06:27,000
Jam A, sebagai contoh, menggunakan aritmetik modular.

132
00:06:27,000 --> 00:06:31,000
Satu minit selepas 1:59, sebagai contoh, adalah 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Tangan minit telah dibalut di sekeliling kepada 0

135
00:06:36,000 --> 00:06:39,000
apabila mencapai terikat atas 60 tahun.

136
00:06:39,000 --> 00:06:46,000
Jadi, kita boleh mengatakan 60 adalah bersamaan dengan 0 (arena 60)

137
00:06:46,000 --> 00:06:57,000
dan 125 adalah bersamaan kepada 65 adalah bersamaan dengan 5 (arena 60).

138
00:06:57,000 --> 00:07:02,000
Kunci awam kami akan e sepasang dan n

139
00:07:02,000 --> 00:07:09,000
di mana dalam kes ini e adalah 5 dan n ialah 989.

140
00:07:09,000 --> 00:07:15,000
Kunci persendirian kami akan sepasang d dan n,

141
00:07:15,000 --> 00:07:22,000
yang dalam kes kami adalah 185 dan 989.

142
00:07:22,000 --> 00:07:25,000
Notis bahawa asal kita nombor perdana p dan q tidak muncul

143
00:07:25,000 --> 00:07:29,000
mana-mana sahaja dalam kunci kami swasta atau awam.

144
00:07:29,000 --> 00:07:33,000
Sekarang kita mempunyai pasangan kita kunci, mari kita melihat bagaimana kita boleh menyulitkan

145
00:07:33,000 --> 00:07:36,000
dan menyahsulit mesej.

146
00:07:36,000 --> 00:07:38,000
Saya mahu menghantar mesej kepada Rob,

147
00:07:38,000 --> 00:07:42,000
jadi dia akan menjadi satu untuk menjana pasangan kunci ini.

148
00:07:42,000 --> 00:07:46,000
Kemudian saya akan bertanya Rob untuk kunci awam, yang saya akan gunakan

149
00:07:46,000 --> 00:07:48,000
untuk menyulitkan mesej untuk menghantar kepadanya.

150
00:07:48,000 --> 00:07:53,000
Ingat, ia adalah benar-benar ok untuk Rob untuk berkongsi kunci awam dengan saya.

151
00:07:53,000 --> 00:07:56,000
Tetapi ia tidak akan menjadi okay untuk berkongsi kunci persendirian.

152
00:07:56,000 --> 00:08:00,000
Saya tidak mempunyai sebarang idea apa kunci persendirian beliau.

153
00:08:00,000 --> 00:08:03,000
Kita boleh memecahkan m mesej kami kepada ketulan beberapa

154
00:08:03,000 --> 00:08:07,000
semua yang lebih kecil daripada n dan kemudian menyulitkan setiap mereka ketulan.

155
00:08:07,000 --> 00:08:12,000
Kami akan menyulitkan CS50 tali, yang kita boleh memecahkan kepada 4 ketulan,

156
00:08:12,000 --> 00:08:14,000
salah satu surat.

157
00:08:14,000 --> 00:08:17,000
Dalam usaha untuk menyulitkan mesej saya, saya akan perlu untuk menukar ke

158
00:08:17,000 --> 00:08:20,000
beberapa jenis perwakilan angka.

159
00:08:20,000 --> 00:08:25,000
Mari kita menyatukan nilai ASCII dengan watak-watak dalam mesej saya.

160
00:08:25,000 --> 00:08:28,000
Dalam usaha untuk menyulitkan mesej m yang diberikan

161
00:08:28,000 --> 00:08:37,000
Saya akan perlu untuk mengira c = m e (arena n).

162
00:08:37,000 --> 00:08:40,000
Tetapi m mestilah lebih kecil daripada n,

163
00:08:40,000 --> 00:08:45,000
atau lain mesej penuh tidak boleh dinyatakan modulo n.

164
00:08:45,000 --> 00:08:49,000
Kita boleh memecahkan m kepada ketulan beberapa, semua yang lebih kecil daripada n,

165
00:08:49,000 --> 00:08:52,000
dan menyulitkan setiap mereka ketulan.

166
00:08:52,000 --> 00:09:03,000
Menyulitkan setiap ketulan ini, kita akan mendapat c1 = 67 5 (arena 989)

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

168
00:09:06,000 --> 00:09:15,000
Bagi sebahagian kedua kami, kami mempunyai 83 hingga 5 (arena 989)

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

170
00:09:18,000 --> 00:09:26,000
Bagi sebahagian ketiga kami, kami mempunyai 53 hingga 5 (arena 989)

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

172
00:09:30,000 --> 00:09:39,000
Dan akhirnya, untuk sebahagian terakhir kami, kami mempunyai 48 hingga 5 (arena 989)

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

174
00:09:43,000 --> 00:09:48,000
Sekarang kita boleh menghantar lebih nilai-nilai disulitkan kepada Rob.

175
00:09:54,000 --> 00:09:58,000
Di sini anda pergi, Rob.

176
00:09:58,000 --> 00:10:01,000
Walaupun mesej kami berada dalam penerbangan, mari kita lihat lain

177
00:10:01,000 --> 00:10:07,000
bagaimana kita mendapat bahawa nilai untuk d.

178
00:10:07,000 --> 00:10:17,000
D nombor kami yang diperlukan untuk memenuhi 5d = 1 (arena 924).

179
00:10:17,000 --> 00:10:24,000
Ini menjadikan d songsang pendaraban 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Memandangkan integer 2, a dan b, algoritma Euclid dilanjutkan

181
00:10:28,000 --> 00:10:33,000
boleh digunakan untuk mencari pembahagi terbesar sepunya bagi integer 2.

182
00:10:33,000 --> 00:10:37,000
Ia juga akan memberikan kita 2 nombor lain, x dan y,

183
00:10:37,000 --> 00:10:47,000
yang memuaskan persamaan kapak + oleh = pembahagi terbesar sepunya a dan b.

184
00:10:47,000 --> 00:10:49,000
Bagaimana ini membantu kita?

185
00:10:49,000 --> 00:10:52,000
Nah, memasang dalam e = 5 untuk

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

187
00:10:56,000 --> 00:10:59,000
kita sudah tahu bahawa nombor-nombor ini adalah coprime.

188
00:10:59,000 --> 00:11:03,000
Pembahagi terbesar sepunya mereka adalah 1.

189
00:11:03,000 --> 00:11:09,000
Ini memberikan kita 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Tetapi jika kita hanya mengambil berat tentang segala-galanya modulo 924

192
00:11:22,000 --> 00:11:25,000
maka kita boleh menggugurkan - 924y.

193
00:11:25,000 --> 00:11:27,000
Fikirkan kembali kepada jam.

194
00:11:27,000 --> 00:11:31,000
Jika tangan minit adalah pada 1 dan kemudian tepat 10 jam lulus,

195
00:11:31,000 --> 00:11:35,000
kita tahu tangan minit masih akan pada 1.

196
00:11:35,000 --> 00:11:39,000
Di sini kita bermula pada 1 dan kemudian membalut di sekitar masa yang tepat y,

197
00:11:39,000 --> 00:11:41,000
jadi kita masih akan berada di 1.

198
00:11:41,000 --> 00:11:49,000
Kami mempunyai 5x = 1 (arena 924).

199
00:11:49,000 --> 00:11:55,000
Dan di sini x ini adalah sama sebagai d kami cari sebelum,

200
00:11:55,000 --> 00:11:58,000
jadi jika kita menggunakan algoritma Euclid dilanjutkan

201
00:11:58,000 --> 00:12:04,000
untuk mendapatkan nombor x, itulah nombor kita harus menggunakan sebagai d kami.

202
00:12:04,000 --> 00:12:07,000
Sekarang mari kita menjalankan algoritma Euclid dilanjutkan untuk 5 =

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

204
00:12:11,000 --> 00:12:14,000
Kami akan menggunakan kaedah yang dipanggil kaedah jadual.

205
00:12:14,000 --> 00:12:21,000
Meja kami akan mempunyai 4 tiang, x, y, d, dan k.

206
00:12:21,000 --> 00:12:23,000
Meja kami bermula dengan 2 baris.

207
00:12:23,000 --> 00:12:28,000
Dalam baris pertama kami mempunyai 1, 0, maka nilai kita, iaitu 5,

208
00:12:28,000 --> 00:12:37,000
dan baris kedua kami adalah 0, 1, dan nilai kita untuk b, yang merupakan 924.

209
00:12:37,000 --> 00:12:40,000
Nilai lajur 4, k, akan menjadi keputusan

210
00:12:40,000 --> 00:12:45,000
membahagikan nilai d berturut-turut di atas dengan nilai d

211
00:12:45,000 --> 00:12:49,000
pada baris yang sama.

212
00:12:49,000 --> 00:12:56,000
Kami mempunyai 5 dibahagikan dengan 924 adalah 0 dengan baki beberapa.

213
00:12:56,000 --> 00:12:59,000
Ini bermakna kita mempunyai k = 0.

214
00:12:59,000 --> 00:13:05,000
Sekarang nilai setiap sel lain akan menjadi nilai 2 barisan sel atas

215
00:13:05,000 --> 00:13:09,000
tolak nilai berturut-turut di atas ia kali k.

216
00:13:09,000 --> 00:13:11,000
Mari kita mulakan dengan d berturut-turut 3.

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

218
00:13:19,000 --> 00:13:25,000
Seterusnya kita mempunyai 0 - 1 * 0 ialah 0

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

220
00:13:30,000 --> 00:13:33,000
Tidak terlalu buruk, jadi mari kita bergerak ke baris seterusnya.

221
00:13:33,000 --> 00:13:36,000
Mula-mula kita perlu nilai kami k.

222
00:13:36,000 --> 00:13:43,000
924 dibahagikan dengan 5 = 184 dengan bakinya beberapa,

223
00:13:43,000 --> 00:13:46,000
jadi nilai kami untuk k ialah 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Baiklah, mari kita buat baris seterusnya.

227
00:14:07,000 --> 00:14:10,000
Nilai kami k akan menjadi 1 kerana

228
00:14:10,000 --> 00:14:15,000
5 dibahagikan dengan 4 = 1 dengan baki beberapa.

229
00:14:15,000 --> 00:14:17,000
Mari mengisi di ruangan lain.

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

233
00:14:33,000 --> 00:14:35,000
Mari kita lihat apa nilai seterusnya kami k akan menjadi.

234
00:14:35,000 --> 00:14:40,000
Nah, ia kelihatan seperti kita mempunyai 4 dibahagikan dengan 1, yang 4.

235
00:14:40,000 --> 00:14:43,000
Dalam kes ini di mana kita sedang membahagikannya dengan 1 k yang sama dengan

236
00:14:43,000 --> 00:14:50,000
nilai d berturut-turut di atas bermakna bahawa kita sedang dilakukan dengan algoritma kami.

237
00:14:50,000 --> 00:14:58,000
Kita boleh lihat di sini bahawa kita mempunyai x = 185 dan y = -1 dalam baris terakhir.

238
00:14:58,000 --> 00:15:00,000
Mari kita kini kembali kepada matlamat asal kita.

239
00:15:00,000 --> 00:15:04,000
Kami berkata bahawa nilai x akibat daripada menjalankan algoritma ini

240
00:15:04,000 --> 00:15:08,000
akan menjadi songsang pendaraban (arena b).

241
00:15:08,000 --> 00:15:15,000
Ini bermakna bahawa 185 adalah songsang pendaraban of 5 (arena 924)

242
00:15:15,000 --> 00:15:20,000
yang bermaksud bahawa kita mempunyai nilai 185 untuk d.

243
00:15:20,000 --> 00:15:23,000
Hakikat bahawa d = 1 pada baris terakhir

244
00:15:23,000 --> 00:15:26,000
mengesahkan bahawa e coprime m.

245
00:15:26,000 --> 00:15:30,000
Jika ia tidak 1, maka kita akan mempunyai untuk memilih e baru.

246
00:15:30,000 --> 00:15:33,000
Sekarang mari kita lihat jika Rob telah menerima mesej saya.

247
00:15:33,000 --> 00:15:35,000
Apabila seseorang menghantar saya mesej disulitkan

248
00:15:35,000 --> 00:15:38,000
selagi saya telah disimpan kunci persendirian saya rahsia

249
00:15:38,000 --> 00:15:41,000
Saya satu-satunya yang boleh menyahsulit mesej.

250
00:15:41,000 --> 00:15:46,000
Untuk menyahsulit sebahagian c saya boleh mengira mesej asal

251
00:15:46,000 --> 00:15:53,000
adalah sama kepada sebahagian d kuasa (arena n).

252
00:15:53,000 --> 00:15:57,000
Ingatlah bahawa d dan n adalah dari kunci persendirian saya.

253
00:15:57,000 --> 00:16:01,000
Untuk mendapatkan mesej penuh daripada ketulan yang kita menyahsulit setiap ketulan

254
00:16:01,000 --> 00:16:04,000
dan menyatukan keputusan.

255
00:16:04,000 --> 00:16:08,000
Tepat bagaimana selamat adalah RSA?

256
00:16:08,000 --> 00:16:10,000
Sebenarnya, kita tidak tahu.

257
00:16:10,000 --> 00:16:14,000
Keselamatan berdasarkan berapa lama ia akan mengambil penyerang untuk memecahkan mesej

258
00:16:14,000 --> 00:16:16,000
disulitkan dengan RSA.

259
00:16:16,000 --> 00:16:19,000
Ingatlah bahawa penyerang mempunyai akses kepada kunci awam anda,

260
00:16:19,000 --> 00:16:21,000
yang mengandungi kedua-dua e dan n.

261
00:16:21,000 --> 00:16:26,000
Jika penyerang menguruskan faktor n ke nombor perdana 2, p dan q,

262
00:16:26,000 --> 00:16:30,000
maka dia boleh mengira d menggunakan algoritma Euclid dilanjutkan.

263
00:16:30,000 --> 00:16:35,000
Ini memberikan beliau kunci persendirian, yang boleh digunakan untuk menyahsulit mesej apa-apa.

264
00:16:35,000 --> 00:16:38,000
Tetapi berapa cepat kita boleh faktor integer?

265
00:16:38,000 --> 00:16:41,000
Sekali lagi, kita tidak tahu.

266
00:16:41,000 --> 00:16:43,000
Tiada siapa yang telah menemui cara yang cepat melakukannya,

267
00:16:43,000 --> 00:16:46,000
yang bermakna yang diberikan cukup besar n

268
00:16:46,000 --> 00:16:49,000
ia akan mengambil penyerang unrealistically lama

269
00:16:49,000 --> 00:16:51,000
faktor nombor.

270
00:16:51,000 --> 00:16:54,000
Jika seseorang mendedahkan cara yang cepat pemfaktoran integer

271
00:16:54,000 --> 00:16:57,000
RSA akan dipecahkan.

272
00:16:57,000 --> 00:17:01,000
Tetapi walaupun pemfaktoran integer memang perlahan

273
00:17:01,000 --> 00:17:04,000
algoritma RSA masih boleh mempunyai beberapa kecacatan di dalamnya

274
00:17:04,000 --> 00:17:07,000
yang membolehkan untuk penyahsulitan mudah mesej.

275
00:17:07,000 --> 00:17:10,000
Tiada siapa yang telah ditemui dan mendedahkan apa-apa kecacatan lagi,

276
00:17:10,000 --> 00:17:12,000
tetapi itu tidak bermakna seseorang itu tidak wujud.

277
00:17:12,000 --> 00:17:17,000
Secara teori, seseorang boleh menjadi di luar sana membaca semua data yang disulitkan dengan RSA.

278
00:17:17,000 --> 00:17:19,000
Ada lagi sedikit isu privasi.

279
00:17:19,000 --> 00:17:23,000
Jika Tommy menyulitkan beberapa mesej menggunakan kunci awam saya

280
00:17:23,000 --> 00:17:26,000
dan penyerang menyulitkan mesej yang sama menggunakan kunci awam saya

281
00:17:26,000 --> 00:17:29,000
penyerang akan melihat bahawa 2 mesej adalah sama

282
00:17:29,000 --> 00:17:32,000
dan dengan itu tahu apa yang Tommy disulitkan.

283
00:17:32,000 --> 00:17:36,000
Dalam usaha untuk mencegah ini, mesej biasanya berpad dengan cebisan rawak

284
00:17:36,000 --> 00:17:39,000
sebelum disulitkan supaya mesej yang sama disulitkan

285
00:17:39,000 --> 00:17:44,000
beberapa kali akan kelihatan berbeza selagi padding pada mesej adalah berbeza.

286
00:17:44,000 --> 00:17:47,000
Tetapi ingat bagaimana kita perlu berpecah mesej ke dalam ketulan

287
00:17:47,000 --> 00:17:50,000
supaya setiap ketulan adalah lebih kecil daripada n?

288
00:17:50,000 --> 00:17:52,000
Padding ketulan bermakna bahawa kita mungkin perlu berpecah perkara

289
00:17:52,000 --> 00:17:57,000
kepada ketulan yang lebih sejak sebahagian empuk mestilah lebih kecil daripada n.

290
00:17:57,000 --> 00:18:01,000
Penyulitan dan penyahsulitan agak mahal dengan RSA,

291
00:18:01,000 --> 00:18:05,000
dan sebagainya yang memerlukan untuk memecahkan mesej kepada ketulan yang banyak boleh menjadi sangat mahal.

292
00:18:05,000 --> 00:18:09,000
Jika jumlah data yang besar perlu disulitkan dan dibuka

293
00:18:09,000 --> 00:18:12,000
kita boleh menggabungkan faedah algoritma simetri utama

294
00:18:12,000 --> 00:18:16,000
dengan orang-orang RSA untuk mendapatkan kedua-dua keselamatan dan kecekapan.

295
00:18:16,000 --> 00:18:18,000
Walaupun kita tidak akan pergi ke sini,

296
00:18:18,000 --> 00:18:23,000
AES adalah algoritma simetri utama seperti Vigenère dan Caesar sifer

297
00:18:23,000 --> 00:18:25,000
tetapi lebih sukar untuk retak.

298
00:18:25,000 --> 00:18:30,000
Sudah tentu, kita tidak boleh menggunakan AES tanpa mewujudkan kunci rahsia yang dikongsi bersama

299
00:18:30,000 --> 00:18:34,000
antara 2 sistem, dan kita melihat masalah dengan itu sebelum ini.

300
00:18:34,000 --> 00:18:40,000
Tetapi kini kita boleh menggunakan RSA untuk mewujudkan kunci dikongsi rahsia antara 2 sistem.

301
00:18:40,000 --> 00:18:43,000
Kami akan memanggil komputer menghantar data pengirim

302
00:18:43,000 --> 00:18:46,000
dan komputer menerima data penerima.

303
00:18:46,000 --> 00:18:49,000
Penerima mempunyai pasangan kunci RSA dan menghantar

304
00:18:49,000 --> 00:18:51,000
kunci awam kepada penghantar.

305
00:18:51,000 --> 00:18:54,000
Penghantar menjana kunci AES,

306
00:18:54,000 --> 00:18:57,000
menyulitkan ia dengan kekunci RSA umum penerima,

307
00:18:57,000 --> 00:19:00,000
dan menghantar kunci AES kepada penerima.

308
00:19:00,000 --> 00:19:04,000
Penerima decrypts mesej dengan kunci RSA swasta.

309
00:19:04,000 --> 00:19:09,000
Kedua-dua penghantar dan penerima kini mempunyai kunci dikongsi AES antara mereka.

310
00:19:09,000 --> 00:19:14,000
AES, yang lebih cepat pada penyulitan dan penyahsulitan daripada RSA,

311
00:19:14,000 --> 00:19:18,000
kini boleh digunakan untuk menyulitkan jumlah data yang besar dan menghantar mereka kepada penerima,

312
00:19:18,000 --> 00:19:21,000
yang boleh menyahsulit menggunakan kunci yang sama.

313
00:19:21,000 --> 00:19:26,000
AES, yang lebih cepat pada penyulitan dan penyahsulitan daripada RSA,

314
00:19:26,000 --> 00:19:30,000
kini boleh digunakan untuk menyulitkan jumlah data yang besar dan menghantar mereka kepada penerima,

315
00:19:30,000 --> 00:19:32,000
yang boleh menyahsulit menggunakan kunci yang sama.

316
00:19:32,000 --> 00:19:36,000
Kami hanya memerlukan RSA untuk memindahkan kunci dikongsi.

317
00:19:36,000 --> 00:19:40,000
Kita tidak perlu lagi untuk menggunakan RSA pada semua.

318
00:19:40,000 --> 00:19:46,000
Ia kelihatan seperti saya telah mendapat mesej.

319
00:19:46,000 --> 00:19:49,000
Ia tidak kisah jika sesiapa membaca apa yang kapal terbang kertas sebelum saya ditangkap

320
00:19:49,000 --> 00:19:55,000
kerana saya satu-satunya dengan kunci persendirian.

321
00:19:55,000 --> 00:19:57,000
Mari kita menyahsulit setiap ketulan dalam mesej.

322
00:19:57,000 --> 00:20:07,000
Sebahagian pertama, 658, kami meningkatkan kuasa d, yang adalah 185,

323
00:20:07,000 --> 00:20:18,000
mod n, yang 989, adalah sama kepada 67,

324
00:20:18,000 --> 00:20:24,000
yang merupakan huruf C di ASCII.

325
00:20:24,000 --> 00:20:31,000
Sekarang, ke Sebahagian kedua.

326
00:20:31,000 --> 00:20:35,000
Sebahagian kedua mempunyai nilai 15,

327
00:20:35,000 --> 00:20:41,000
yang kita meningkatkan kuasa 185,

328
00:20:41,000 --> 00:20:51,000
arena 989, dan ini adalah sama kepada 83

329
00:20:51,000 --> 00:20:57,000
yang merupakan S surat dalam ASCII.

330
00:20:57,000 --> 00:21:06,000
Sekarang bagi sebahagian ketiga, yang mempunyai nilai 799, kita meningkatkan kepada 185,

331
00:21:06,000 --> 00:21:17,000
arena 989, dan ini adalah sama kepada 53,

332
00:21:17,000 --> 00:21:24,000
yang merupakan nilai watak 5 dalam ASCII.

333
00:21:24,000 --> 00:21:30,000
Sekarang untuk sebahagian terakhir, yang mempunyai nilai 975,

334
00:21:30,000 --> 00:21:41,000
kita meningkatkan kepada 185, 989 arena,

335
00:21:41,000 --> 00:21:51,000
dan ini adalah sama dengan 48, yang merupakan nilai 0 watak dalam ASCII.

336
00:21:51,000 --> 00:21:57,000
Nama saya adalah Rob Bowden, dan ini adalah CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA pada semua.

339
00:22:08,000 --> 00:22:14,000
RSA pada semua. [Ketawa]

340
00:22:14,000 --> 00:22:17,000
Pada semua.