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
[Esta é CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Vamos dar uma olhada na RSA, um algoritmo utilizado para encriptar dados.

5
00:00:11,000 --> 00:00:16,000
Algoritmos de criptografia como César e cifras de Vigenère não são muito seguras.

6
00:00:16,000 --> 00:00:20,000
Com a cifra de César, o atacante só precisa tentar 25 chaves diferentes

7
00:00:20,000 --> 00:00:22,000
para obter texto simples da mensagem.

8
00:00:22,000 --> 00:00:25,000
Embora a cifra de Vigenère é mais seguro do que a cifra de César

9
00:00:25,000 --> 00:00:28,000
por causa do maior espaço de busca de chaves, uma vez que um atacante

10
00:00:28,000 --> 00:00:30,000
conhece o comprimento da chave de cifra de Vigenère,

11
00:00:30,000 --> 00:00:34,000
que pode ser determinada através de uma análise dos padrões de texto codificado,

12
00:00:34,000 --> 00:00:38,000
a cifra de Vigenère que não é muito mais seguro do que a cifra de César.

13
00:00:38,000 --> 00:00:42,000
RSA, por outro lado, não é vulnerável a ataques como este.

14
00:00:42,000 --> 00:00:45,000
A cifra de César e Vigenère cifra de usar a mesma chave

15
00:00:45,000 --> 00:00:47,000
para criptografar e descriptografar uma mensagem.

16
00:00:47,000 --> 00:00:51,000
Esta propriedade faz com que essas cifras de algoritmos de chaves simétricas.

17
00:00:51,000 --> 00:00:54,000
Um problema fundamental com algoritmos de chaves simétricas

18
00:00:54,000 --> 00:00:57,000
é que eles contam com a criptografar e enviar a mensagem

19
00:00:57,000 --> 00:00:59,000
e o de recepção e descodificação da mensagem

20
00:00:59,000 --> 00:01:03,000
para já concordaram adiantado na chave ambos irão usar.

21
00:01:03,000 --> 00:01:06,000
Mas nós temos um pouco de um problema de inicialização aqui.

22
00:01:06,000 --> 00:01:10,000
Como dois computadores que querem se comunicar estabelecer uma chave secreta entre eles?

23
00:01:10,000 --> 00:01:16,000
Se a chave deve ser secreta, então precisamos de uma maneira de criptografar e descriptografar a chave.

24
00:01:16,000 --> 00:01:18,000
Se tudo o que temos é a criptografia de chave simétrica

25
00:01:18,000 --> 00:01:21,000
então acabamos de voltar para o mesmo problema.

26
00:01:21,000 --> 00:01:25,000
RSA, por outro lado, utiliza um par de chaves,

27
00:01:25,000 --> 00:01:28,000
um para criptografia e outro para a descodificação.

28
00:01:28,000 --> 00:01:32,000
Uma é chamada a chave pública, e a outra é a chave privada.

29
00:01:32,000 --> 00:01:34,000
A chave pública é usada para criptografar mensagens.

30
00:01:34,000 --> 00:01:38,000
Como você pode imaginar pelo nome, podemos partilhar a nossa chave pública com

31
00:01:38,000 --> 00:01:43,000
qualquer pessoa que quiser, sem comprometer a segurança de uma mensagem criptografada.

32
00:01:43,000 --> 00:01:45,000
Mensagens criptografadas com uma chave pública

33
00:01:45,000 --> 00:01:49,000
só pode ser decifrada com a sua chave privada correspondente.

34
00:01:49,000 --> 00:01:53,000
Enquanto você pode compartilhar sua chave pública, você deve sempre manter o seu segredo da chave privada.

61
00:01:55,000 --> 00:01:58,000
e apenas a chave privada pode ser utilizada para decifrar as mensagens

62
00:01:58,000 --> 00:02:02,000
se dois usuários querem enviar mensagens criptografadas com RSA

63
00:02:02,000 --> 00:02:07,000
frente e para trás ambos os usuários precisam ter seu par de chaves pública e privada própria chave.

64
00:02:07,000 --> 00:02:10,000
Mensagens de usuário para um usuário 2

65
00:02:10,000 --> 00:02:15,000
usar apenas um par de chaves 2 usuário e mensagens de usuário para usuário 2 1

66
00:02:15,000 --> 00:02:17,000
usar apenas um par de chaves de usuário do.

67
00:02:17,000 --> 00:02:21,000
O fato de que há duas chaves separadas para criptografar e descriptografar as mensagens

68
00:02:21,000 --> 00:02:24,000
RSA faz um algoritmo de chave assimétrica.

69
00:02:24,000 --> 00:02:28,000
Nós não precisamos para criptografar a chave pública, a fim de enviá-lo para outro computador

70
00:02:28,000 --> 00:02:31,000
vez que a chave é pública qualquer maneira.

71
00:02:31,000 --> 00:02:33,000
Isto significa que o RSA não têm o mesmo problema de inicialização

72
00:02:33,000 --> 00:02:36,000
como os algoritmos de chave simétrica.

73
00:02:36,000 --> 00:02:39,000
Então, se eu quero enviar uma mensagem usando a criptografia RSA

74
00:02:39,000 --> 00:02:42,000
para Rob, eu vou primeiro precisa de chave pública de Rob.

75
00:02:42,000 --> 00:02:47,000
Para gerar um par de chaves, Rob precisa escolher dois números primos grandes.

76
00:02:47,000 --> 00:02:50,000
Esses números serão usados ​​em ambas as chaves, público e privado,

77
00:02:50,000 --> 00:02:54,000
mas a chave pública só vai usar o produto desses dois números,

78
00:02:54,000 --> 00:02:56,000
não os próprios números.

79
00:02:56,000 --> 00:02:59,000
Uma vez que eu tenho a mensagem criptografada usando a chave pública de Rob

80
00:02:59,000 --> 00:03:01,000
Posso enviar a mensagem para Rob.

81
00:03:01,000 --> 00:03:05,000
Para um computador, fatorar números é um problema difícil.

82
00:03:05,000 --> 00:03:09,000
A chave pública, lembre-se, usou o produto de dois números primos.

83
00:03:09,000 --> 00:03:12,000
Este produto deve então ter apenas dois elementos,

84
00:03:12,000 --> 00:03:16,000
que acontecem ser os números que compõem a chave privada.

85
00:03:16,000 --> 00:03:20,000
A fim de decifrar a mensagem, a RSA vai usar esta chave privada

86
00:03:20,000 --> 00:03:25,000
ou os números multiplicados em conjunto no processo de criação da chave pública.

87
00:03:25,000 --> 00:03:28,000
Porque é computacionalmente difícil fatorar o número

88
00:03:28,000 --> 00:03:32,000
utilizado em uma chave pública para os dois números utilizados na chave privada

89
00:03:32,000 --> 00:03:36,000
É difícil para um invasor descobrir a chave privada

90
00:03:36,000 --> 00:03:39,000
que será necessária para desencriptar a mensagem.

91
00:03:39,000 --> 00:03:43,000
Agora vamos entrar em alguns detalhes de nível mais baixo da RSA.

92
00:03:43,000 --> 00:03:46,000
Vamos primeiro ver como podemos gerar um par de chaves.

93
00:03:46,000 --> 00:03:49,000
Primeiro, vamos precisar de dois números primos.

94
00:03:49,000 --> 00:03:52,000
Vamos chamar esses dois números pe q.

95
00:03:52,000 --> 00:03:56,000
A fim de escolher p e q, na prática, seria pseudorandomly gerar

96
00:03:56,000 --> 00:03:59,000
grandes números e, em seguida, usar um teste para determinar se ou não

97
00:03:59,000 --> 00:04:02,000
esses números são provavelmente primo.

98
00:04:02,000 --> 00:04:05,000
Podemos manter a geração de números aleatórios e outra vez

99
00:04:05,000 --> 00:04:08,000
até que tenhamos dois primos que podemos usar.

100
00:04:08,000 --> 00:04:15,000
Aqui vamos escolher p = 23 e q = 43.

101
00:04:15,000 --> 00:04:19,000
Lembra-te, na prática, p e q devem ser números muito maiores.

102
00:04:19,000 --> 00:04:22,000
Tanto quanto sabemos, o maior dos números, o que é mais difícil

103
00:04:22,000 --> 00:04:25,000
para quebrar uma mensagem criptografada.

104
00:04:25,000 --> 00:04:29,000
Mas também é mais caro para criptografar e descriptografar mensagens.

105
00:04:29,000 --> 00:04:33,000
Hoje é frequentemente recomendado que p e q são pelo menos 1024 bits,

106
00:04:33,000 --> 00:04:37,000
o que coloca cada número em mais de 300 dígitos decimais.

107
00:04:37,000 --> 00:04:40,000
Mas vamos pegar esses números pequenos para este exemplo.

108
00:04:40,000 --> 00:04:43,000
Agora vamos multiplicar p e q juntos para obter um número de 3,

109
00:04:43,000 --> 00:04:45,000
que chamaremos de n.

110
00:04:45,000 --> 00:04:55,000
No nosso caso, n = 23 * 43, que é = 989.

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

112
00:04:58,000 --> 00:05:02,000
Em seguida, vamos multiplicar p - 1 com q - 1

113
00:05:02,000 --> 00:05:05,000
para obter um número 4, que chamaremos de m.

114
00:05:05,000 --> 00:05:15,000
No nosso caso, m = 22 * ​​42, que é = 924.

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

116
00:05:18,000 --> 00:05:22,000
Agora vamos precisar de um número e que é relativamente privilegiada para m

117
00:05:22,000 --> 00:05:25,000
e menos do que m.

118
00:05:25,000 --> 00:05:28,000
Dois números são relativamente primos ou primos entre si

119
00:05:28,000 --> 00:05:33,000
se o inteiro positivo apenas que divide os dois uniformemente é 1.

120
00:05:33,000 --> 00:05:37,000
Em outras palavras, o maior divisor comum de e e m

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

122
00:05:39,000 --> 00:05:44,000
Na prática, é comum e ser o número primo 65537

123
00:05:44,000 --> 00:05:48,000
enquanto este número não acontecer de ser um fator de m.

124
00:05:48,000 --> 00:05:53,000
Para os nossos chaves, nós vamos buscá-e = 5

125
00:05:53,000 --> 00:05:57,000
desde 5 é relativamente privilegiada para 924.

126
00:05:57,000 --> 00:06:01,000
Finalmente, vamos precisar de mais um número, que chamaremos de d.

127
00:06:01,000 --> 00:06:11,000
D tem de ser um valor que satisfaz a equação de = 1 (mod m).

128
00:06:11,000 --> 00:06:17,000
Este mod m significa que vamos usar algo chamado aritmética modular.

129
00:06:17,000 --> 00:06:21,000
Na aritmética modular, uma vez que um número maior do que recebe algum limite superior

130
00:06:21,000 --> 00:06:24,000
ele voltará para 0.

131
00:06:24,000 --> 00:06:27,000
Um relógio, por exemplo, usa aritmética modular.

132
00:06:27,000 --> 00:06:31,000
Um minuto após a 1:59, por exemplo, é de 2:00,

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

134
00:06:33,000 --> 00:06:36,000
O ponteiro dos minutos tem enrolado a 0

135
00:06:36,000 --> 00:06:39,000
ao atingir um limite superior de 60 anos.

136
00:06:39,000 --> 00:06:46,000
Então, podemos dizer que 60 é equivalente a 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
e 125 é equivalente a 65 é igual a 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Nossa chave pública será o e par e n

139
00:07:02,000 --> 00:07:09,000
onde, neste caso, e é 5 e n ​​é 989.

140
00:07:09,000 --> 00:07:15,000
Nossa chave privada será o par d e n,

141
00:07:15,000 --> 00:07:22,000
que no nosso caso é de 185 e 989.

142
00:07:22,000 --> 00:07:25,000
Observe que nossa original primos p e q não aparecem

143
00:07:25,000 --> 00:07:29,000
em qualquer lugar em nossas chaves privadas ou públicas.

144
00:07:29,000 --> 00:07:33,000
Agora que temos o nosso par de chaves, vamos dar uma olhada em como podemos criptografar

145
00:07:33,000 --> 00:07:36,000
e decifrar uma mensagem.

146
00:07:36,000 --> 00:07:38,000
Eu quero enviar uma mensagem para Rob,

147
00:07:38,000 --> 00:07:42,000
então ele vai ser o único a gerar esse par de chaves.

148
00:07:42,000 --> 00:07:46,000
Então eu vou pedir para Rob sua chave pública, que eu vou usar

149
00:07:46,000 --> 00:07:48,000
para criptografar uma mensagem para enviar para ele.

150
00:07:48,000 --> 00:07:53,000
Lembre-se, é totalmente bem para Rob para compartilhar sua chave pública comigo.

151
00:07:53,000 --> 00:07:56,000
Mas não seria bom para compartilhar sua chave privada.

152
00:07:56,000 --> 00:08:00,000
Eu não tenho nenhuma idéia do que a sua chave privada é.

153
00:08:00,000 --> 00:08:03,000
Nós podemos quebrar nossa mensagem m-se ​​em vários pedaços

154
00:08:03,000 --> 00:08:07,000
todos menores que n e, em seguida, criptografar cada um desses blocos.

155
00:08:07,000 --> 00:08:12,000
Vamos criptografar o CS50 string, que pode dividir-se em quatro pedaços,

156
00:08:12,000 --> 00:08:14,000
uma por letra.

157
00:08:14,000 --> 00:08:17,000
Para criptografar a minha mensagem, eu vou ter de convertê-lo em

158
00:08:17,000 --> 00:08:20,000
algum tipo de representação numérica.

159
00:08:20,000 --> 00:08:25,000
Vamos concatenar os valores ASCII com os personagens de minha mensagem.

160
00:08:25,000 --> 00:08:28,000
Para criptografar uma mensagem m dado

161
00:08:28,000 --> 00:08:37,000
Vou precisar para calcular c = m para o e (mod n).

162
00:08:37,000 --> 00:08:40,000
Mas m deve ser menor do que n,

163
00:08:40,000 --> 00:08:45,000
ou então a mensagem completa não pode ser expressa módulo n.

164
00:08:45,000 --> 00:08:49,000
Podemos dividir m acima em vários pedaços, todas as quais são menores do que n,

165
00:08:49,000 --> 00:08:52,000
e codificar cada uma destas porções.

166
00:08:52,000 --> 00:09:03,000
Criptografando cada um desses pedaços, temos c1 = 67 para o 5 (mod 989)

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

168
00:09:06,000 --> 00:09:15,000
Para o nosso pedaço segundo temos 83 a 5 (mod 989)

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

170
00:09:18,000 --> 00:09:26,000
Para o nosso pedaço terceiro temos 53 para o 5 (mod 989)

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

172
00:09:30,000 --> 00:09:39,000
E, finalmente, para o nosso último pedaço temos 48 para o 5 (mod 989)

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

174
00:09:43,000 --> 00:09:48,000
Agora podemos enviar mais estes valores criptografados para Rob.

175
00:09:54,000 --> 00:09:58,000
Aqui está, Rob.

176
00:09:58,000 --> 00:10:01,000
Enquanto a nossa mensagem está em vôo, vamos ter um outro olhar

177
00:10:01,000 --> 00:10:07,000
como chegamos esse valor para d.

178
00:10:07,000 --> 00:10:17,000
Nosso número d necessário para satisfazer 5D = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
Isso faz com que o d inverso multiplicativo modulo de 5 924.

180
00:10:24,000 --> 00:10:28,000
Dado dois inteiros, A e B, o algoritmo estendido de Euclides

181
00:10:28,000 --> 00:10:33,000
pode ser usada para encontrar o maior divisor comum destes dois números inteiros.

182
00:10:33,000 --> 00:10:37,000
Ele também irá dar-nos dois outros números, X e Y,

183
00:10:37,000 --> 00:10:47,000
que satisfazem a equação ax + by = máximo divisor comum de a e b.

184
00:10:47,000 --> 00:10:49,000
Como isso pode nos ajudar?

185
00:10:49,000 --> 00:10:52,000
Bem, ligar e = 5 para um

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

187
00:10:56,000 --> 00:10:59,000
já sabemos que estes números são primos entre si.

188
00:10:59,000 --> 00:11:03,000
Seu maior divisor comum é 1.

189
00:11:03,000 --> 00:11:09,000
Isso nos dá 5x + 924y = 1

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

191
00:11:17,000 --> 00:11:22,000
Mas, se só se preocupam com tudo o modulo 924

192
00:11:22,000 --> 00:11:25,000
então podemos deixar cair o - 924y.

193
00:11:25,000 --> 00:11:27,000
Pense novamente para o relógio.

194
00:11:27,000 --> 00:11:31,000
Se o ponteiro dos minutos é em 1 e, em seguida, exatamente 10 horas passam,

195
00:11:31,000 --> 00:11:35,000
sabemos que o ponteiro dos minutos vai ainda estar na 1.

196
00:11:35,000 --> 00:11:39,000
Aqui nós começam em 1 e, em seguida, envolver em torno de vezes exatamente y,

197
00:11:39,000 --> 00:11:41,000
por isso ainda vai ser em 1.

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

199
00:11:49,000 --> 00:11:55,000
E aqui esta x é o mesmo que o d estávamos procurando antes,

200
00:11:55,000 --> 00:11:58,000
assim, se usar o algoritmo estendido de Euclides

201
00:11:58,000 --> 00:12:04,000
para obter este número x, que é o número que deve usar como nosso d.

202
00:12:04,000 --> 00:12:07,000
Agora vamos executar o algoritmo estendido de Euclides para a = 5

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

204
00:12:11,000 --> 00:12:14,000
Vamos usar um método chamado de método de tabela.

205
00:12:14,000 --> 00:12:21,000
Nossa mesa terá 4 colunas, x, y, d, e k.

206
00:12:21,000 --> 00:12:23,000
Nossa mesa começa com duas linhas.

207
00:12:23,000 --> 00:12:28,000
Na primeira linha temos 1, 0, então o nosso valor de um, o que é 5,

208
00:12:28,000 --> 00:12:37,000
e nossa segunda linha é 0, 1, e o nosso valor para b, que é 924.

209
00:12:37,000 --> 00:12:40,000
O valor da coluna 4, k, será o resultado

210
00:12:40,000 --> 00:12:45,000
de dividir o valor de d na linha acima com o valor de d

211
00:12:45,000 --> 00:12:49,000
na mesma linha.

212
00:12:49,000 --> 00:12:56,000
Temos 5 dividido por 924 é 0, com algum remanescente.

213
00:12:56,000 --> 00:12:59,000
Isso significa que temos k = 0.

214
00:12:59,000 --> 00:13:05,000
Agora, o valor de todas as outras células, será o valor da célula de 2 linhas acima dela

215
00:13:05,000 --> 00:13:09,000
menos o valor da linha acima k vezes.

216
00:13:09,000 --> 00:13:11,000
Vamos começar com d na linha 3.

217
00:13:11,000 --> 00:13:19,000
Nós temos 5-924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Em seguida, temos 0-1 * 0 que é 0

219
00:13:25,000 --> 00:13:30,000
e 1-0 * 0 que é 1.

220
00:13:30,000 --> 00:13:33,000
Não é tão ruim, então vamos passar para a próxima linha.

221
00:13:33,000 --> 00:13:36,000
Primeiro precisamos de nosso valor de k.

222
00:13:36,000 --> 00:13:43,000
924 dividido por 5 = 184 com algum remanescente,

223
00:13:43,000 --> 00:13:46,000
então o nosso valor para k é 184.

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

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

226
00:14:05,000 --> 00:14:07,000
Tudo bem, vamos fazer a próxima linha.

227
00:14:07,000 --> 00:14:10,000
Nosso valor de k será 1 porque

228
00:14:10,000 --> 00:14:15,000
5 dividido por 4 = 1 com algum remanescente.

229
00:14:15,000 --> 00:14:17,000
Vamos preencher as outras colunas.

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

233
00:14:33,000 --> 00:14:35,000
Vamos ver o que o nosso próximo valor de k seria.

234
00:14:35,000 --> 00:14:40,000
Bem, parece que temos 4 dividido por 1, que é 4.

235
00:14:40,000 --> 00:14:43,000
Neste caso em que estamos a dividir por 1 k tal que é igual à

236
00:14:43,000 --> 00:14:50,000
o valor de d na linha acima significa que estamos a fazer com o nosso algoritmo.

237
00:14:50,000 --> 00:14:58,000
Podemos ver aqui que temos x = 185 e y = -1 na última fila.

238
00:14:58,000 --> 00:15:00,000
Vamos agora voltar ao nosso objetivo original.

239
00:15:00,000 --> 00:15:04,000
Dissemos que o valor de x, como resultado da execução deste algoritmo

240
00:15:04,000 --> 00:15:08,000
seria o inverso multiplicativo de um (mod b).

241
00:15:08,000 --> 00:15:15,000
Isso significa que 185 é o inverso multiplicativo de 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
o que significa que tem um valor de 185 para d.

243
00:15:20,000 --> 00:15:23,000
O fato de que d = 1 na última linha

244
00:15:23,000 --> 00:15:26,000
verifica se e foi para coprime m.

245
00:15:26,000 --> 00:15:30,000
Se não fosse um então teríamos que escolher um e novo.

246
00:15:30,000 --> 00:15:33,000
Agora vamos ver se Rob recebeu minha mensagem.

247
00:15:33,000 --> 00:15:35,000
Quando alguém me envia uma mensagem criptografada

248
00:15:35,000 --> 00:15:38,000
enquanto eu mantive a minha chave privada em segredo

249
00:15:38,000 --> 00:15:41,000
Eu sou a única pessoa que pode decifrar a mensagem.

250
00:15:41,000 --> 00:15:46,000
Para descriptografar um pedaço c eu posso calcular a mensagem original

251
00:15:46,000 --> 00:15:53,000
é igual ao bloco de potência d (mod n).

252
00:15:53,000 --> 00:15:57,000
Lembre-se que d e n são de minha chave privada.

253
00:15:57,000 --> 00:16:01,000
Para se ter uma mensagem cheia de seus pedaços que decifrar cada pedaço

254
00:16:01,000 --> 00:16:04,000
e concatenar os resultados.

255
00:16:04,000 --> 00:16:08,000
Exatamente o quão seguro é o RSA?

256
00:16:08,000 --> 00:16:10,000
A verdade é que nós não sabemos.

257
00:16:10,000 --> 00:16:14,000
A segurança é baseada em quanto tempo levaria um atacante para quebrar uma mensagem

258
00:16:14,000 --> 00:16:16,000
criptografada com RSA.

259
00:16:16,000 --> 00:16:19,000
Lembre-se que um atacante tem acesso a sua chave pública,

260
00:16:19,000 --> 00:16:21,000
a qual contém o e e n.

261
00:16:21,000 --> 00:16:26,000
Se o atacante consegue fator N em seus dois primos, P e Q,

262
00:16:26,000 --> 00:16:30,000
então ela poderia calcular d usando o algoritmo estendido de Euclides.

263
00:16:30,000 --> 00:16:35,000
Isto dá-lhe a chave privada, a qual pode ser usada para descodificar qualquer mensagem.

264
00:16:35,000 --> 00:16:38,000
Mas a rapidez com que podemos fatorar números inteiros?

265
00:16:38,000 --> 00:16:41,000
Mais uma vez, nós não sabemos.

266
00:16:41,000 --> 00:16:43,000
Ninguém encontrou uma maneira rápida de fazê-lo,

267
00:16:43,000 --> 00:16:46,000
o que significa que, dada suficientemente grande n

268
00:16:46,000 --> 00:16:49,000
levaria um atacante irrealisticamente longo

269
00:16:49,000 --> 00:16:51,000
fator para o número.

270
00:16:51,000 --> 00:16:54,000
Se alguém revelou uma maneira rápida de inteiros de factoring

271
00:16:54,000 --> 00:16:57,000
RSA seria quebrado.

272
00:16:57,000 --> 00:17:01,000
Mas mesmo se factorização inteira é lenta

273
00:17:01,000 --> 00:17:04,000
o algoritmo RSA ainda pode ter alguma falha nela

274
00:17:04,000 --> 00:17:07,000
que permite a fácil descodificação de mensagens.

275
00:17:07,000 --> 00:17:10,000
Ninguém descobriu e revelou tal falha, no entanto,

276
00:17:10,000 --> 00:17:12,000
mas isso não significa que um não existe.

277
00:17:12,000 --> 00:17:17,000
Em teoria, alguém poderia estar lá fora, lendo todos os dados criptografados com RSA.

278
00:17:17,000 --> 00:17:19,000
Há mais um pouco de uma questão de privacidade.

279
00:17:19,000 --> 00:17:23,000
Se Tommy criptografa alguma mensagem usando a minha chave pública

280
00:17:23,000 --> 00:17:26,000
e um atacante criptografa a mesma mensagem utilizando a chave pública

281
00:17:26,000 --> 00:17:29,000
o atacante vai ver que as duas mensagens são idênticas

282
00:17:29,000 --> 00:17:32,000
e, portanto, sabe o que Tommy criptografados.

283
00:17:32,000 --> 00:17:36,000
A fim de evitar isto, as mensagens são normalmente preenchidos com bits aleatórios

284
00:17:36,000 --> 00:17:39,000
antes de ser codificado de modo a que a mesma mensagem criptografada

285
00:17:39,000 --> 00:17:44,000
várias vezes será diferente, desde que a impregnação em que a mensagem é diferente.

286
00:17:44,000 --> 00:17:47,000
Mas lembre-se assim que temos de dividir as mensagens em pedaços

287
00:17:47,000 --> 00:17:50,000
de modo que cada bloco é menor do que n?

288
00:17:50,000 --> 00:17:52,000
Preenchimento dos pedaços significa que poderemos ter que dividir as coisas

289
00:17:52,000 --> 00:17:57,000
em pedaços ainda mais desde o pedaço acolchoado deve ser menor do que n.

290
00:17:57,000 --> 00:18:01,000
Criptografia e descriptografia são relativamente caros com RSA,

291
00:18:01,000 --> 00:18:05,000
e assim a necessidade de acabar com uma mensagem em pedaços muitos pode ser muito caro.

292
00:18:05,000 --> 00:18:09,000
Se um grande volume de dados precisa ser criptografados e descriptografados

293
00:18:09,000 --> 00:18:12,000
nós podemos combinar os benefícios de algoritmos de chaves simétricas

294
00:18:12,000 --> 00:18:16,000
com os da RSA para obter a segurança e eficiência.

295
00:18:16,000 --> 00:18:18,000
Embora não entrarei aqui,

296
00:18:18,000 --> 00:18:23,000
AES é um algoritmo de chave simétrica, como o Vigenère e cifras de César

297
00:18:23,000 --> 00:18:25,000
mas muito mais difícil de decifrar.

298
00:18:25,000 --> 00:18:30,000
Claro, não podemos usar AES sem estabelecer uma chave secreta compartilhada

299
00:18:30,000 --> 00:18:34,000
entre os dois sistemas, e vimos o problema com isso antes.

300
00:18:34,000 --> 00:18:40,000
Mas agora podemos usar RSA para estabelecer a chave secreta compartilhada entre os dois sistemas.

301
00:18:40,000 --> 00:18:43,000
Vamos chamar o computador que envia os dados do remetente

302
00:18:43,000 --> 00:18:46,000
e o computador recebe os dados do receptor.

303
00:18:46,000 --> 00:18:49,000
O receptor tem um par de chaves RSA e envia

304
00:18:49,000 --> 00:18:51,000
a chave pública do remetente.

305
00:18:51,000 --> 00:18:54,000
O remetente gera uma chave AES,

306
00:18:54,000 --> 00:18:57,000
criptografa com a chave RSA do receptor pública,

307
00:18:57,000 --> 00:19:00,000
e envia a chave AES para o receptor.

308
00:19:00,000 --> 00:19:04,000
O receptor decifra a mensagem com sua chave privada RSA.

309
00:19:04,000 --> 00:19:09,000
Tanto o remetente quanto o receptor têm agora uma chave AES compartilhado entre eles.

310
00:19:09,000 --> 00:19:14,000
AES, que é muito mais rápida a codificação e descodificação de RSA,

311
00:19:14,000 --> 00:19:18,000
agora pode ser usado para criptografar os grandes volumes de dados e enviá-los para o receptor,

312
00:19:18,000 --> 00:19:21,000
que podem descriptografar usando a mesma chave.

313
00:19:21,000 --> 00:19:26,000
AES, que é muito mais rápida a codificação e descodificação de RSA,

314
00:19:26,000 --> 00:19:30,000
agora pode ser usado para criptografar os grandes volumes de dados e enviá-los para o receptor,

315
00:19:30,000 --> 00:19:32,000
que podem descriptografar usando a mesma chave.

316
00:19:32,000 --> 00:19:36,000
Nós só precisávamos RSA para transferir a chave compartilhada.

317
00:19:36,000 --> 00:19:40,000
Nós não precisamos mais usar RSA em tudo.

318
00:19:40,000 --> 00:19:46,000
Parece que eu tenho uma mensagem.

319
00:19:46,000 --> 00:19:49,000
Não importa se alguém ler o que está no avião de papel antes que eu peguei

320
00:19:49,000 --> 00:19:55,000
porque eu sou o único com a chave privada.

321
00:19:55,000 --> 00:19:57,000
Vamos decifrar cada um dos pedaços na mensagem.

322
00:19:57,000 --> 00:20:07,000
O primeiro pedaço, 658, que aumenta para o poder d, que é de 185,

323
00:20:07,000 --> 00:20:18,000
mod n, que é 989, é igual a 67,

324
00:20:18,000 --> 00:20:24,000
que é a letra C em ASCII.

325
00:20:24,000 --> 00:20:31,000
Agora, para o segundo pedaço.

326
00:20:31,000 --> 00:20:35,000
O pedaço segundo tem valor 15,

327
00:20:35,000 --> 00:20:41,000
que levantamos ao poder 185,

328
00:20:41,000 --> 00:20:51,000
mod 989, e esta é igual a 83

329
00:20:51,000 --> 00:20:57,000
que é a letra S em ASCII.

330
00:20:57,000 --> 00:21:06,000
Agora, para o terceiro bloco, que tem valor 799, elevamos a 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, e esta é igual a 53,

332
00:21:17,000 --> 00:21:24,000
que é o valor do carácter 5 em ASCII.

333
00:21:24,000 --> 00:21:30,000
Agora, para o último pedaço, que tem valor 975,

334
00:21:30,000 --> 00:21:41,000
elevamos a 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
e esta é igual a 48, o qual é o valor de 0 a personagem em ASCII.

336
00:21:51,000 --> 00:21:57,000
Meu nome é Rob Bowden, e este é o CS50.

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

338
00:22:06,000 --> 00:22:08,000
RSA em tudo.

339
00:22:08,000 --> 00:22:14,000
RSA em tudo. [Risos]

340
00:22:14,000 --> 00:22:17,000
De todo.