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] [Đại học Harvard]

3
00:00:04,000 --> 00:00:07,000
[Đây là CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Chúng ta hãy nhìn vào RSA, một thuật toán được sử dụng rộng rãi cho việc mã hóa dữ liệu.

5
00:00:11,000 --> 00:00:16,000
Thuật toán mã hóa như Caesar và các thuật toán mật mã Vigenère không phải là rất an toàn.

6
00:00:16,000 --> 00:00:20,000
Với mật mã Caesar, một kẻ tấn công chỉ cần thử 25 phím khác nhau

7
00:00:20,000 --> 00:00:22,000
để có được đồng bằng văn bản của tin nhắn.

8
00:00:22,000 --> 00:00:25,000
Trong khi mật mã Vigenère là an toàn hơn so với thuật toán mã hóa Caesar

9
00:00:25,000 --> 00:00:28,000
vì không gian tìm kiếm lớn hơn cho các phím, một khi một kẻ tấn công

10
00:00:28,000 --> 00:00:30,000
biết chiều dài của khoá mật mã Vigenère,

11
00:00:30,000 --> 00:00:34,000
mà có thể được xác định thông qua việc phân tích các mẫu trong các văn bản được mã hóa,

12
00:00:34,000 --> 00:00:38,000
mật mã Vigenère là không phải là an toàn hơn nhiều hơn so với các thuật toán mã hóa Caesar.

13
00:00:38,000 --> 00:00:42,000
RSA, mặt khác, không phải là dễ bị tấn công như thế này.

14
00:00:42,000 --> 00:00:45,000
Caesar thuật toán mã hóa và mật mã Vigenère sử dụng cùng khóa

15
00:00:45,000 --> 00:00:47,000
cho cả hai mã hóa và giải mã tin nhắn.

16
00:00:47,000 --> 00:00:51,000
Điều này làm cho các thuật toán mật mã khóa đối xứng.

17
00:00:51,000 --> 00:00:54,000
Một vấn đề cơ bản với các thuật toán khóa đối xứng

18
00:00:54,000 --> 00:00:57,000
là họ dựa vào một trong những mã hóa và gửi tin nhắn

19
00:00:57,000 --> 00:00:59,000
và một trong những tiếp nhận và giải mã thông điệp

20
00:00:59,000 --> 00:01:03,000
đã đồng ý trả trước trên chính họ sẽ sử dụng cả hai.

21
00:01:03,000 --> 00:01:06,000
Nhưng chúng tôi có một chút của một vấn đề khởi động ở đây.

22
00:01:06,000 --> 00:01:10,000
Làm thế nào để 2 máy tính muốn giao tiếp thiết lập một khóa bí mật giữa chúng?

23
00:01:10,000 --> 00:01:16,000
Nếu khóa phải là bí mật, sau đó chúng ta cần một cách để mã hóa và giải mã khoá.

24
00:01:16,000 --> 00:01:18,000
Nếu tất cả những gì chúng ta có là mật mã khóa đối xứng

25
00:01:18,000 --> 00:01:21,000
sau đó chúng tôi đã chỉ cần trở lại cùng một vấn đề.

26
00:01:21,000 --> 00:01:25,000
RSA, mặt khác, sử dụng một cặp khóa,

27
00:01:25,000 --> 00:01:28,000
một cho việc mã hóa và một để giải mã.

28
00:01:28,000 --> 00:01:32,000
Một được gọi là khóa công khai, và các khác là các khóa riêng.

29
00:01:32,000 --> 00:01:34,000
Khóa công khai được sử dụng để mã hóa thông điệp.

30
00:01:34,000 --> 00:01:38,000
Như bạn có thể đoán theo tên của nó, chúng ta có thể chia sẻ khóa công khai của chúng tôi với

31
00:01:38,000 --> 00:01:43,000
bất cứ ai chúng tôi muốn mà không ảnh hưởng đến sự an toàn của một tin nhắn mã hóa.

32
00:01:43,000 --> 00:01:45,000
Tin nhắn mã hóa bằng cách sử dụng một khóa công khai

33
00:01:45,000 --> 00:01:49,000
chỉ có thể được giải mã với khóa riêng của nó tương ứng.

34
00:01:49,000 --> 00:01:53,000
Trong khi bạn có thể chia sẻ chìa khóa công cộng của bạn, bạn nên luôn luôn giữ bí mật khóa riêng của bạn.

61
00:01:55,000 --> 00:01:58,000
và chỉ có khóa riêng có thể được sử dụng để giải mã thông điệp

62
00:01:58,000 --> 00:02:02,000
nếu 2 người muốn gửi tin nhắn được mã hóa với RSA

63
00:02:02,000 --> 00:02:07,000
qua lại cả hai người dùng cần phải có cặp khóa công cộng và tư nhân của riêng mình.

64
00:02:07,000 --> 00:02:10,000
Thông điệp từ người sử dụng 1 người dùng 2

65
00:02:10,000 --> 00:02:15,000
chỉ sử dụng người dùng 2 cặp khóa, và tin nhắn từ người sử dụng 2 người sử dụng 1

66
00:02:15,000 --> 00:02:17,000
chỉ sử dụng cặp khóa người sử dụng 1.

67
00:02:17,000 --> 00:02:21,000
Thực tế là có 2 phím riêng biệt để mã hóa và giải mã tin nhắn

68
00:02:21,000 --> 00:02:24,000
làm cho RSA một thuật toán khoá bất đối xứng.

69
00:02:24,000 --> 00:02:28,000
Chúng ta không cần mã hóa khóa công khai để gửi đến một máy tính khác

70
00:02:28,000 --> 00:02:31,000
kể từ khi chính là công anyway.

71
00:02:31,000 --> 00:02:33,000
Điều này có nghĩa là RSA không có cùng một vấn đề khởi động

72
00:02:33,000 --> 00:02:36,000
như các thuật toán khóa đối xứng.

73
00:02:36,000 --> 00:02:39,000
Vì vậy, nếu tôi muốn gửi một tin nhắn bằng cách sử dụng mã hóa RSA

74
00:02:39,000 --> 00:02:42,000
Rob, tôi lần đầu tiên sẽ cần khóa công khai của Rob.

75
00:02:42,000 --> 00:02:47,000
Để tạo ra một cặp khóa, Rob cần phải chọn 2 số nguyên tố lớn.

76
00:02:47,000 --> 00:02:50,000
Những con số này sẽ được sử dụng trong cả khóa công cộng và tư nhân,

77
00:02:50,000 --> 00:02:54,000
nhưng khóa công khai sẽ chỉ sử dụng sản phẩm của 2 số này,

78
00:02:54,000 --> 00:02:56,000
không phải là bản thân các con số.

79
00:02:56,000 --> 00:02:59,000
Sau khi đã mã hóa tin nhắn bằng cách sử dụng khóa công khai của Rob

80
00:02:59,000 --> 00:03:01,000
Tôi có thể gửi tin nhắn tới Rob.

81
00:03:01,000 --> 00:03:05,000
Đối với máy tính, số bao thanh toán là một vấn đề khó khăn.

82
00:03:05,000 --> 00:03:09,000
Chìa khóa công cộng, hãy nhớ, sử dụng sản phẩm của 2 số nguyên tố.

83
00:03:09,000 --> 00:03:12,000
Sản phẩm này sau đó phải có chỉ có 2 yếu tố,

84
00:03:12,000 --> 00:03:16,000
xảy ra được những con số mà tạo nên các khóa riêng.

85
00:03:16,000 --> 00:03:20,000
Để tin giải mã, RSA sẽ sử dụng khóa riêng

86
00:03:20,000 --> 00:03:25,000
hoặc các con số nhân với nhau trong quá trình tạo khóa công khai.

87
00:03:25,000 --> 00:03:28,000
Bởi vì đó là tính toán yếu tố trong các số

88
00:03:28,000 --> 00:03:32,000
được sử dụng trong một khóa công khai vào 2 số điện thoại được sử dụng trong các khóa riêng

89
00:03:32,000 --> 00:03:36,000
nó sẽ là khó khăn cho kẻ tấn công để tìm ra khóa riêng

90
00:03:36,000 --> 00:03:39,000
đó sẽ là cần thiết để giải mã thông điệp.

91
00:03:39,000 --> 00:03:43,000
Bây giờ chúng ta hãy đi vào một số chi tiết mức độ thấp của RSA.

92
00:03:43,000 --> 00:03:46,000
Trước tiên hãy xem làm thế nào chúng ta có thể tạo ra một cặp khóa.

93
00:03:46,000 --> 00:03:49,000
Trước tiên, chúng tôi sẽ cần 2 số nguyên tố.

94
00:03:49,000 --> 00:03:52,000
Chúng tôi sẽ gọi những 2 số p và q.

95
00:03:52,000 --> 00:03:56,000
Để nhận p và q, trong thực tế, chúng tôi pseudorandomly sẽ tạo ra

96
00:03:56,000 --> 00:03:59,000
số lượng lớn và sau đó sử dụng một bài kiểm tra để xác định có hay không

97
00:03:59,000 --> 00:04:02,000
những con số có thể là số nguyên tố.

98
00:04:02,000 --> 00:04:05,000
Chúng ta có thể tiếp tục tạo ra các số ngẫu nhiên hơn và hơn nữa

99
00:04:05,000 --> 00:04:08,000
cho đến khi chúng tôi có 2 số nguyên tố mà chúng ta có thể sử dụng.

100
00:04:08,000 --> 00:04:15,000
Ở đây chúng ta hãy chọn p = 23 và q = 43.

101
00:04:15,000 --> 00:04:19,000
Hãy nhớ rằng, trong thực tế, p và q phải là con số lớn hơn nhiều.

102
00:04:19,000 --> 00:04:22,000
Theo như chúng tôi biết, lớn hơn các con số, các khó hơn là

103
00:04:22,000 --> 00:04:25,000
để crack một tin nhắn mã hóa.

104
00:04:25,000 --> 00:04:29,000
Nhưng nó cũng đắt hơn tin nhắn mã hóa và giải mã.

105
00:04:29,000 --> 00:04:33,000
Ngày nay nó thường được khuyên là p và q là ít nhất là 1024 bit,

106
00:04:33,000 --> 00:04:37,000
trong đó đặt mỗi số hơn 300 chữ số thập phân.

107
00:04:37,000 --> 00:04:40,000
Nhưng chúng tôi sẽ chọn những con số nhỏ cho ví dụ này.

108
00:04:40,000 --> 00:04:43,000
Bây giờ chúng ta sẽ nhân p và q với nhau để có được một số thứ 3,

109
00:04:43,000 --> 00:04:45,000
mà chúng ta sẽ gọi n.

110
00:04:45,000 --> 00:04:55,000
Trong trường hợp của chúng tôi, n = 23 * 43 = 989.

111
00:04:55,000 --> 00:04:58,000
Chúng tôi có n = 989.

112
00:04:58,000 --> 00:05:02,000
Tiếp theo chúng ta sẽ nhân p - 1 q - 1

113
00:05:02,000 --> 00:05:05,000
để có được một số thứ 4, mà chúng ta sẽ gọi m.

114
00:05:05,000 --> 00:05:15,000
Trong trường hợp của chúng tôi, m = 22 * ​​42 = 924.

115
00:05:15,000 --> 00:05:18,000
Chúng tôi có m = 924.

116
00:05:18,000 --> 00:05:22,000
Bây giờ chúng ta sẽ cần một e con số đó là tương đối nguyên tố m

117
00:05:22,000 --> 00:05:25,000
và ít hơn m.

118
00:05:25,000 --> 00:05:28,000
Hai số là nguyên tố hoặc nguyên tố cùng nhau

119
00:05:28,000 --> 00:05:33,000
nếu số nguyên duy nhất tích cực chia cả hai đều là 1.

120
00:05:33,000 --> 00:05:37,000
Nói cách khác, ước số chung lớn nhất của e và m

121
00:05:37,000 --> 00:05:39,000
phải là 1.

122
00:05:39,000 --> 00:05:44,000
Trong thực tế, nó phổ biến cho e là số nguyên tố 65.537

123
00:05:44,000 --> 00:05:48,000
miễn là con số này không xảy ra là một yếu tố của m.

124
00:05:48,000 --> 00:05:53,000
Cho các phím của chúng tôi, chúng tôi sẽ chọn e = 5

125
00:05:53,000 --> 00:05:57,000
vì 5 là tương đối nguyên tố 924.

126
00:05:57,000 --> 00:06:01,000
Cuối cùng, chúng tôi sẽ cần một số lượng nhiều hơn, chúng ta sẽ gọi d.

127
00:06:01,000 --> 00:06:11,000
D phải có một số giá trị đáp ứng các phương trình de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
M mod này có nghĩa chúng tôi sẽ sử dụng một cái gì đó được gọi là mô-đun số học.

129
00:06:17,000 --> 00:06:21,000
Trong số học modula, một khi một số lượng được cao hơn so với một số ràng buộc trên

130
00:06:21,000 --> 00:06:24,000
nó sẽ quấn lại xung quanh để 0.

131
00:06:24,000 --> 00:06:27,000
Đồng hồ A, ví dụ, sử dụng số học modula.

132
00:06:27,000 --> 00:06:31,000
Một phút sau 1:59, ví dụ, là 2:00,

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

134
00:06:33,000 --> 00:06:36,000
Kim phút đã bao bọc xung quanh là 0

135
00:06:36,000 --> 00:06:39,000
khi đạt đến một ràng buộc trên là 60.

136
00:06:39,000 --> 00:06:46,000
Vì vậy, chúng ta có thể nói 60 là tương đương với 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
và 125 là tương đương 65 là tương đương với 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Khóa công khai của chúng tôi sẽ là cặp e và n

139
00:07:02,000 --> 00:07:09,000
trong trường hợp này e là 5 và n là 989.

140
00:07:09,000 --> 00:07:15,000
Khóa riêng của chúng tôi sẽ là cặp d và n,

141
00:07:15,000 --> 00:07:22,000
mà trong trường hợp của chúng tôi là 185 và 989.

142
00:07:22,000 --> 00:07:25,000
Chú ý rằng các số nguyên tố ban đầu của chúng tôi p và q không xuất hiện

143
00:07:25,000 --> 00:07:29,000
bất cứ nơi nào trong các phím của chúng tôi tư nhân hoặc công cộng.

144
00:07:29,000 --> 00:07:33,000
Bây giờ chúng ta có cặp phím của chúng tôi, chúng ta hãy xem làm thế nào chúng ta có thể mã hóa

145
00:07:33,000 --> 00:07:36,000
và giải mã một tin nhắn.

146
00:07:36,000 --> 00:07:38,000
Tôi muốn gửi một thông điệp tới Rob,

147
00:07:38,000 --> 00:07:42,000
do đó, ông sẽ là một trong để tạo ra cặp khóa.

148
00:07:42,000 --> 00:07:46,000
Sau đó, tôi sẽ yêu cầu Rob khóa công khai của mình, mà tôi sẽ sử dụng

149
00:07:46,000 --> 00:07:48,000
để mã hóa một tin nhắn gửi cho anh ta.

150
00:07:48,000 --> 00:07:53,000
Hãy nhớ rằng, nó hoàn toàn okay cho Rob chia sẻ khóa công khai của mình với tôi.

151
00:07:53,000 --> 00:07:56,000
Nhưng nó sẽ không được chia sẻ khóa riêng của mình.

152
00:07:56,000 --> 00:08:00,000
Tôi không có bất kỳ ý tưởng khóa riêng của mình là gì.

153
00:08:00,000 --> 00:08:03,000
Chúng tôi có thể phá vỡ thông điệp m của chúng tôi lên thành nhiều mẩu

154
00:08:03,000 --> 00:08:07,000
nhỏ hơn n và sau đó mã hóa mỗi của những khối.

155
00:08:07,000 --> 00:08:12,000
Chúng tôi sẽ mã hóa CS50 chuỗi, mà chúng ta có thể chia thành 4 khối,

156
00:08:12,000 --> 00:08:14,000
một cho mỗi thư.

157
00:08:14,000 --> 00:08:17,000
Để mã hóa tin nhắn của tôi, tôi sẽ cần phải chuyển đổi nó thành

158
00:08:17,000 --> 00:08:20,000
một số loại đại diện số.

159
00:08:20,000 --> 00:08:25,000
Hãy nối các giá trị ASCII với các ký tự trong tin nhắn của tôi.

160
00:08:25,000 --> 00:08:28,000
Để mã hóa một thông điệp được đưa ra m

161
00:08:28,000 --> 00:08:37,000
Tôi sẽ cần phải tính toán c = m e (mod n).

162
00:08:37,000 --> 00:08:40,000
Nhưng m phải nhỏ hơn n,

163
00:08:40,000 --> 00:08:45,000
hoặc người nào khác được thông báo đầy đủ không thể được thể hiện modulo n.

164
00:08:45,000 --> 00:08:49,000
Chúng tôi có thể phá vỡ m thành nhiều mẩu, tất cả trong số đó là nhỏ hơn n,

165
00:08:49,000 --> 00:08:52,000
và mã hóa của những khối.

166
00:08:52,000 --> 00:09:03,000
Mã hóa mỗi của các khối, chúng tôi nhận được c1 = 67 đến 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Đối với đoạn thứ hai của chúng tôi, chúng tôi có 83 đến 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Đối với đoạn thứ ba của chúng tôi, chúng tôi có 53 đến 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
Và cuối cùng, cho đoạn cuối cùng của chúng tôi, chúng tôi có 48 đến 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Bây giờ chúng ta có thể gửi qua các giá trị này được mã hóa Rob.

175
00:09:54,000 --> 00:09:58,000
Ở đây bạn đi, Rob.

176
00:09:58,000 --> 00:10:01,000
Trong khi thông điệp của chúng tôi là trong chuyến bay, chúng ta hãy có cái nhìn khác

177
00:10:01,000 --> 00:10:07,000
như thế nào, chúng tôi đã nhận rằng giá trị so với d.

178
00:10:07,000 --> 00:10:17,000
D số của chúng tôi cần thiết để đáp ứng 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Điều này làm cho d nghịch đảo nhân của 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Với 2 số nguyên, a và b, thuật toán Euclide mở rộng

181
00:10:28,000 --> 00:10:33,000
có thể được sử dụng để tìm ước chung lớn nhất của 2 số nguyên.

182
00:10:33,000 --> 00:10:37,000
Nó cũng sẽ cho chúng ta 2 con số khác, x và y,

183
00:10:37,000 --> 00:10:47,000
đáp ứng các phương trình ax + by = UCLN của a và b.

184
00:10:47,000 --> 00:10:49,000
Làm thế nào để giúp chúng tôi?

185
00:10:49,000 --> 00:10:52,000
Vâng, cắm vào e = 5 cho một

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

187
00:10:56,000 --> 00:10:59,000
chúng ta đã biết rằng những con số này là nguyên tố cùng nhau.

188
00:10:59,000 --> 00:11:03,000
Ước số chung lớn nhất của họ là 1.

189
00:11:03,000 --> 00:11:09,000
Điều này cho chúng ta 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Nhưng nếu chúng ta chỉ quan tâm về tất cả mọi thứ modulo 924

192
00:11:22,000 --> 00:11:25,000
sau đó chúng ta có thể thả - 924y.

193
00:11:25,000 --> 00:11:27,000
Hãy nhớ lại đồng hồ.

194
00:11:27,000 --> 00:11:31,000
Nếu bàn tay phút là 1 và sau đó đúng 10 giờ vượt qua,

195
00:11:31,000 --> 00:11:35,000
chúng ta biết tay phút vẫn sẽ có trên 1.

196
00:11:35,000 --> 00:11:39,000
Ở đây chúng tôi bắt đầu từ 1 và sau đó quấn xung quanh thời gian chính xác y,

197
00:11:39,000 --> 00:11:41,000
vì vậy chúng tôi vẫn sẽ có tại 1.

198
00:11:41,000 --> 00:11:49,000
Chúng tôi có 5x = 1 (mod 924).

199
00:11:49,000 --> 00:11:55,000
Và đây x này cũng giống như d chúng tôi đang tìm kiếm trước khi,

200
00:11:55,000 --> 00:11:58,000
vì vậy nếu chúng ta sử dụng thuật toán Euclide mở rộng

201
00:11:58,000 --> 00:12:04,000
để có được số x, đó là số lượng, chúng ta nên sử dụng như là d của chúng tôi.

202
00:12:04,000 --> 00:12:07,000
Bây giờ hãy chạy thuật toán Euclide mở rộng cho một 5 =

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

204
00:12:11,000 --> 00:12:14,000
Chúng tôi sẽ sử dụng một phương pháp gọi là phương pháp bảng.

205
00:12:14,000 --> 00:12:21,000
Bảng của chúng tôi sẽ có 4 cột, x, y, d, và k.

206
00:12:21,000 --> 00:12:23,000
Bảng của chúng tôi bắt đầu với 2 hàng.

207
00:12:23,000 --> 00:12:28,000
Trong hàng đầu tiên, chúng tôi có 1, 0, sau đó giá trị của chúng tôi, mà là 5,

208
00:12:28,000 --> 00:12:37,000
và hàng thứ hai của chúng tôi là 0, 1, và giá trị của chúng tôi cho b, đó là 924.

209
00:12:37,000 --> 00:12:40,000
Giá trị của cột thứ 4, k, sẽ là kết quả

210
00:12:40,000 --> 00:12:45,000
phân chia giá trị của d trong hàng trên nó với giá trị của d

211
00:12:45,000 --> 00:12:49,000
trên cùng một hàng.

212
00:12:49,000 --> 00:12:56,000
Chúng tôi có 5 chia cho 924 là 0 với phần còn lại một số.

213
00:12:56,000 --> 00:12:59,000
Điều đó có nghĩa là chúng ta có k = 0.

214
00:12:59,000 --> 00:13:05,000
Bây giờ giá trị của tất cả các tế bào khác sẽ là giá trị của 2 dòng tế bào ở trên nó

215
00:13:05,000 --> 00:13:09,000
trừ đi giá trị của hàng trên nó lần k.

216
00:13:09,000 --> 00:13:11,000
Chúng ta hãy bắt đầu với d ở hàng ghế thứ 3.

217
00:13:11,000 --> 00:13:19,000
Chúng tôi có 5 - 924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Tiếp theo, chúng ta có 0 - 1 * 0 mà là 0

219
00:13:25,000 --> 00:13:30,000
và 1 - 0 * 0 mà là 1.

220
00:13:30,000 --> 00:13:33,000
Không quá xấu, vì vậy hãy chuyển sang hàng tiếp theo.

221
00:13:33,000 --> 00:13:36,000
Trước tiên, chúng ta cần giá trị của chúng tôi k.

222
00:13:36,000 --> 00:13:43,000
924 chia cho 5 = 184 với một số còn lại,

223
00:13:43,000 --> 00:13:46,000
do đó, giá trị của chúng tôi cho k là 184.

224
00:13:46,000 --> 00:13:54,000
Bây giờ 924 - 5 * 184 = 4.

225
00:13:54,000 --> 00:14:05,000
1 - 0 * 184 là 1 và 0 - 1 * 184 là -184.

226
00:14:05,000 --> 00:14:07,000
Được rồi, chúng ta hãy làm hàng tiếp theo.

227
00:14:07,000 --> 00:14:10,000
Giá trị của k sẽ là 1 vì

228
00:14:10,000 --> 00:14:15,000
5 chia cho 4 = 1 với một số phần còn lại.

229
00:14:15,000 --> 00:14:17,000
Hãy điền vào các cột khác.

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

233
00:14:33,000 --> 00:14:35,000
Hãy xem những gì giá trị tiếp theo của chúng tôi k.

234
00:14:35,000 --> 00:14:40,000
Vâng, có vẻ như chúng ta có 4 chia 1, mà là 4.

235
00:14:40,000 --> 00:14:43,000
Trong trường hợp này, nơi chúng tôi đang chia 1 k như vậy mà là bằng

236
00:14:43,000 --> 00:14:50,000
giá trị của d trong hàng trên có nghĩa rằng chúng tôi đang thực hiện với các thuật toán của chúng tôi.

237
00:14:50,000 --> 00:14:58,000
Chúng ta có thể thấy rằng chúng ta có x = 185 và y = -1 ở hàng cuối cùng.

238
00:14:58,000 --> 00:15:00,000
Bây giờ chúng ta hãy quay trở lại với mục tiêu ban đầu của chúng tôi.

239
00:15:00,000 --> 00:15:04,000
Chúng tôi cho rằng, giá trị của x là kết quả của chạy thuật toán này

240
00:15:04,000 --> 00:15:08,000
sẽ là nghịch đảo nhân (mod b).

241
00:15:08,000 --> 00:15:15,000
Điều đó có nghĩa rằng 185 là nghịch đảo nhân của 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
điều đó có nghĩa rằng chúng ta có một giá trị trong tổng số 185 d.

243
00:15:20,000 --> 00:15:23,000
Thực tế là d = 1 ở hàng cuối cùng

244
00:15:23,000 --> 00:15:26,000
xác minh điện tử mà nguyên tố cùng nhau m.

245
00:15:26,000 --> 00:15:30,000
Nếu nó không được 1 sau đó chúng tôi sẽ phải chọn một e mới.

246
00:15:30,000 --> 00:15:33,000
Bây giờ chúng ta hãy xem nếu Rob đã nhận được tin nhắn của tôi.

247
00:15:33,000 --> 00:15:35,000
Khi ai đó gửi cho tôi một tin nhắn mã hóa

248
00:15:35,000 --> 00:15:38,000
miễn là tôi đã giữ khoá riêng của tôi một bí mật

249
00:15:38,000 --> 00:15:41,000
Tôi là người duy nhất có thể giải mã thông điệp.

250
00:15:41,000 --> 00:15:46,000
Để giải mã một đoạn c tôi có thể tính toán các thông báo ban đầu

251
00:15:46,000 --> 00:15:53,000
bằng các chunk d điện (mod n).

252
00:15:53,000 --> 00:15:57,000
Hãy nhớ rằng d và n là các từ khóa riêng của tôi.

253
00:15:57,000 --> 00:16:01,000
Để có được một tin nhắn đầy đủ từ các khối của nó chúng ta giải mã từng đoạn

254
00:16:01,000 --> 00:16:04,000
và nối các kết quả.

255
00:16:04,000 --> 00:16:08,000
RSA chính xác như thế nào là an toàn?

256
00:16:08,000 --> 00:16:10,000
Sự thật là, chúng ta không biết.

257
00:16:10,000 --> 00:16:14,000
An ninh được dựa trên bao lâu nó sẽ có được một kẻ tấn công để crack một tin nhắn

258
00:16:14,000 --> 00:16:16,000
mã hóa với RSA.

259
00:16:16,000 --> 00:16:19,000
Hãy nhớ rằng một kẻ tấn công có thể truy cập vào khóa công khai của bạn,

260
00:16:19,000 --> 00:16:21,000
trong đó có cả e và n.

261
00:16:21,000 --> 00:16:26,000
Nếu kẻ tấn công quản lý yếu tố n thành 2 số nguyên tố, p và q,

262
00:16:26,000 --> 00:16:30,000
sau đó cô có thể tính toán d bằng cách sử dụng các thuật toán Euclide mở rộng.

263
00:16:30,000 --> 00:16:35,000
Điều này mang lại cho cô ấy khóa riêng, có thể được sử dụng để giải mã bất kỳ tin nhắn.

264
00:16:35,000 --> 00:16:38,000
Nhưng làm thế nào chúng ta có thể nhanh chóng yếu tố số nguyên?

265
00:16:38,000 --> 00:16:41,000
Một lần nữa, chúng ta không biết.

266
00:16:41,000 --> 00:16:43,000
Không ai đã tìm thấy một cách nhanh chóng làm việc đó,

267
00:16:43,000 --> 00:16:46,000
có nghĩa là cho đủ lớn n

268
00:16:46,000 --> 00:16:49,000
nó sẽ có một kẻ tấn công không thực tế dài

269
00:16:49,000 --> 00:16:51,000
yếu tố trong các số.

270
00:16:51,000 --> 00:16:54,000
Nếu ai đó đã tiết lộ một cách nhanh chóng các số nguyên bao thanh toán

271
00:16:54,000 --> 00:16:57,000
RSA sẽ bị phá vỡ.

272
00:16:57,000 --> 00:17:01,000
Nhưng thừa số nguyên ngay cả khi vốn chậm

273
00:17:01,000 --> 00:17:04,000
thuật toán RSA vẫn có thể có một số lỗ hổng trong nó

274
00:17:04,000 --> 00:17:07,000
cho phép dễ dàng để giải mã các thông điệp.

275
00:17:07,000 --> 00:17:10,000
Không ai đã tìm thấy và tiết lộ một lỗ hổng như vậy,

276
00:17:10,000 --> 00:17:12,000
nhưng điều đó không có nghĩa là không tồn tại.

277
00:17:12,000 --> 00:17:17,000
Về lý thuyết, một người nào đó có thể là có đọc tất cả các dữ liệu được mã hóa với RSA.

278
00:17:17,000 --> 00:17:19,000
Có một chút của một vấn đề riêng tư.

279
00:17:19,000 --> 00:17:23,000
Nếu Tommy mã hóa một số tin nhắn bằng cách sử dụng khóa công cộng của tôi

280
00:17:23,000 --> 00:17:26,000
và một kẻ tấn công mã hóa cùng một thông điệp bằng cách sử dụng khóa công cộng của tôi

281
00:17:26,000 --> 00:17:29,000
kẻ tấn công sẽ thấy 2 thông báo giống hệt nhau

282
00:17:29,000 --> 00:17:32,000
và do đó biết những gì Tommy mã hóa.

283
00:17:32,000 --> 00:17:36,000
Để ngăn chặn điều này, các thông điệp thường được đệm bằng các bit ngẫu nhiên

284
00:17:36,000 --> 00:17:39,000
trước khi được mã hóa để cùng một thông điệp mã hóa

285
00:17:39,000 --> 00:17:44,000
nhiều lần sẽ khác miễn là padding trên tin nhắn khác nhau.

286
00:17:44,000 --> 00:17:47,000
Nhưng hãy nhớ làm thế nào chúng ta phải chia tin nhắn vào khối

287
00:17:47,000 --> 00:17:50,000
để mỗi đoạn nhỏ hơn n?

288
00:17:50,000 --> 00:17:52,000
Padding các khối có nghĩa là chúng ta có thể có để phân chia những thứ lên

289
00:17:52,000 --> 00:17:57,000
thành khối nhiều hơn kể từ khi các chunk đệm phải nhỏ hơn n.

290
00:17:57,000 --> 00:18:01,000
Mã hóa và giải mã tương đối đắt tiền với RSA,

291
00:18:01,000 --> 00:18:05,000
và như vậy cần phải phá vỡ một tin nhắn vào khối có thể rất tốn kém.

292
00:18:05,000 --> 00:18:09,000
Nếu một khối lượng lớn dữ liệu cần phải được mã hóa và giải mã

293
00:18:09,000 --> 00:18:12,000
chúng ta có thể kết hợp những lợi ích của các thuật toán khóa đối xứng

294
00:18:12,000 --> 00:18:16,000
với những người của RSA để có được cả an ninh và hiệu quả.

295
00:18:16,000 --> 00:18:18,000
Mặc dù chúng tôi sẽ không đi vào nó ở đây,

296
00:18:18,000 --> 00:18:23,000
AES là một thuật toán khóa đối xứng như Vigenère và mật mã Caesar

297
00:18:23,000 --> 00:18:25,000
nhưng khó khăn hơn nhiều để crack.

298
00:18:25,000 --> 00:18:30,000
Tất nhiên, chúng tôi không thể sử dụng AES mà không thành lập một khóa chia sẻ bí mật

299
00:18:30,000 --> 00:18:34,000
giữa 2 hệ thống, và chúng tôi thấy vấn đề với trước.

300
00:18:34,000 --> 00:18:40,000
Nhưng bây giờ chúng tôi có thể sử dụng RSA để thiết lập phím chia sẻ bí mật giữa 2 hệ thống.

301
00:18:40,000 --> 00:18:43,000
Chúng tôi sẽ gọi máy tính gửi dữ liệu người gửi

302
00:18:43,000 --> 00:18:46,000
và máy tính nhận dữ liệu nhận.

303
00:18:46,000 --> 00:18:49,000
Nhận có một cặp khóa RSA và gửi

304
00:18:49,000 --> 00:18:51,000
khóa công khai cho người gửi.

305
00:18:51,000 --> 00:18:54,000
Người gửi tạo ra một chìa khóa AES,

306
00:18:54,000 --> 00:18:57,000
mã hóa nó với khóa công khai RSA của người nhận,

307
00:18:57,000 --> 00:19:00,000
và gửi chìa khóa AES cho người nhận.

308
00:19:00,000 --> 00:19:04,000
Người nhận giải mã thông điệp với khóa riêng của nó RSA.

309
00:19:04,000 --> 00:19:09,000
Cả người gửi và người nhận đều có một chìa khóa AES được chia sẻ giữa chúng.

310
00:19:09,000 --> 00:19:14,000
AES, là nhanh hơn nhiều mã hóa và giải mã hơn so với RSA,

311
00:19:14,000 --> 00:19:18,000
bây giờ có thể được sử dụng để mã hóa khối lượng lớn dữ liệu và gửi đến người nhận,

312
00:19:18,000 --> 00:19:21,000
giải mã có thể người sử dụng cùng khóa.

313
00:19:21,000 --> 00:19:26,000
AES, là nhanh hơn nhiều mã hóa và giải mã hơn so với RSA,

314
00:19:26,000 --> 00:19:30,000
bây giờ có thể được sử dụng để mã hóa khối lượng lớn dữ liệu và gửi đến người nhận,

315
00:19:30,000 --> 00:19:32,000
giải mã có thể người sử dụng cùng khóa.

316
00:19:32,000 --> 00:19:36,000
Chúng tôi chỉ cần RSA để chuyển khóa chia sẻ.

317
00:19:36,000 --> 00:19:40,000
Chúng tôi không còn cần phải sử dụng RSA ở tất cả.

318
00:19:40,000 --> 00:19:46,000
Dường như tôi đã nhận được tin nhắn.

319
00:19:46,000 --> 00:19:49,000
Nó không quan trọng nếu có ai đọc những gì trên chiếc máy bay giấy trước khi tôi bắt gặp nó

320
00:19:49,000 --> 00:19:55,000
bởi vì tôi là người duy nhất có khóa riêng.

321
00:19:55,000 --> 00:19:57,000
Hãy giải mã mỗi của các khối trong tin nhắn.

322
00:19:57,000 --> 00:20:07,000
The chunk đầu tiên, 658, chúng tôi nâng cao sức mạnh d, mà là 185,

323
00:20:07,000 --> 00:20:18,000
mod n, đó là 989, bằng 67,

324
00:20:18,000 --> 00:20:24,000
là chữ C trong ASCII.

325
00:20:24,000 --> 00:20:31,000
Bây giờ, vào đoạn thứ hai.

326
00:20:31,000 --> 00:20:35,000
Đoạn thứ hai có giá trị là 15,

327
00:20:35,000 --> 00:20:41,000
mà chúng tôi nâng cao sức mạnh 185,

328
00:20:41,000 --> 00:20:51,000
989 mod, và đây là bằng 83

329
00:20:51,000 --> 00:20:57,000
đó là chữ S trong ASCII.

330
00:20:57,000 --> 00:21:06,000
Bây giờ cho đoạn thứ ba, trong đó có giá trị 799, chúng tôi nâng cao đến 185,

331
00:21:06,000 --> 00:21:17,000
989 mod, và đây là bằng 53,

332
00:21:17,000 --> 00:21:24,000
đó là giá trị của nhân vật 5 trong ASCII.

333
00:21:24,000 --> 00:21:30,000
Bây giờ cho đoạn cuối cùng, trong đó có giá trị 975,

334
00:21:30,000 --> 00:21:41,000
chúng tôi nâng cao đến 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
và điều này là tương đương với 48, đó là giá trị của 0 ký tự trong ASCII.

336
00:21:51,000 --> 00:21:57,000
Tên tôi là Rob Bowden, và đây là CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA ở tất cả.

339
00:22:08,000 --> 00:22:14,000
RSA ở tất cả. [Cười]

340
00:22:14,000 --> 00:22:17,000
Tại tất cả.