1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Vigenère Cipher]

2
00:00:02,000 --> 00:00:04,000
[Nate Hardison - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Esta é CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Conheça Alice.

5
00:00:09,000 --> 00:00:11,260
Alice tem uma queda por Bob.

6
00:00:11,260 --> 00:00:15,030
Felizmente para Alice, Bob também tem olhos para ela.

7
00:00:15,030 --> 00:00:17,700
Infelizmente para o seu romance,

8
00:00:17,700 --> 00:00:20,580
não só os pais de Alice desaprovam Bob,

9
00:00:20,580 --> 00:00:23,820
mas o melhor amigo de Alice, Evelyn, tem uma paixão secreta por Bob

10
00:00:23,820 --> 00:00:27,290
e egoisticamente quer mantê-los separados em todos os custos.

11
00:00:27,290 --> 00:00:31,280
Para enviar mensagens secretas para o outro que os pais de Alice não consegue entender,

12
00:00:31,280 --> 00:00:34,140
>> Alice e Bob foram usando uma cifra de César,

13
00:00:34,140 --> 00:00:37,410
que funciona através da transferência do alfabeto por um certo número de cartas

14
00:00:37,410 --> 00:00:39,800
como um modo para gerar um novo alfabeto.

15
00:00:39,800 --> 00:00:44,130
Cada letra do alfabeto original é então substituído por seu letra correspondente

16
00:00:44,130 --> 00:00:46,920
no novo alfabeto deslocado.

17
00:00:46,920 --> 00:00:50,240
Número favorito de Alice é 3, que Bob sabe,

18
00:00:50,240 --> 00:00:52,450
de modo que ela usa como sua chave 3.

19
00:00:52,450 --> 00:00:55,430
Quando ela muda o alfabeto Inglês por três letras,

20
00:00:55,430 --> 00:01:00,680
A torna-se D, B torna-se E, C torna-se F,

21
00:01:00,680 --> 00:01:02,670
e assim por diante.

22
00:01:02,670 --> 00:01:07,460
>> Quando chega ao fim do alfabeto - para as letras X, Y e Z -

23
00:01:07,460 --> 00:01:09,970
ela apenas envolve em torno de volta para o início do alfabeto

24
00:01:09,970 --> 00:01:14,850
e X substitutos com um Y, com B e Z com C.

25
00:01:14,850 --> 00:01:18,550
Assim, quando Alice vai para criptografar sua mensagem secreta a Bob,

26
00:01:18,550 --> 00:01:21,520
ou seja, "Encontre-me no parque no onze horas",

27
00:01:21,520 --> 00:01:23,790
ela só faz as substituições adequadas.

28
00:01:23,790 --> 00:01:30,900
M torna-se P, E torna-se H, e assim por diante até que ela não criptografada mensagem de texto simples

29
00:01:30,900 --> 00:01:34,350
é transformada em texto cifrado criptografado:

30
00:01:34,350 --> 00:01:37,280
"Phhw ph dw WKH sdun dw hohyhq dp"

31
00:01:37,280 --> 00:01:39,370
definitivamente não é o som mais romântico,

32
00:01:39,370 --> 00:01:41,650
mas Alice acreditam que ele vai fazer.

33
00:01:41,650 --> 00:01:45,140
>> Alice dá a mensagem de Evelyn para entregar a casa de Bob.

34
00:01:45,140 --> 00:01:50,030
Mas Evelyn vez leva-lo de volta para seu quarto e tenta decifrar o código.

35
00:01:50,030 --> 00:01:55,470
Uma das primeiras coisas Evelyn avisos é que a letra H ocorre sete vezes na mensagem,

36
00:01:55,470 --> 00:01:58,930
vezes mais do que qualquer outra letra.

37
00:01:58,930 --> 00:02:01,960
Sabendo que a letra E é a mais comum no idioma Inglês,

38
00:02:01,960 --> 00:02:05,390
ocorrendo cerca de 13% do tempo,

39
00:02:05,390 --> 00:02:09,910
Evelyn suposições que H tem sido substituídos por E, a fim de tornar a mensagem secreta

40
00:02:09,910 --> 00:02:14,030
e tenta usar uma chave de 3 a decifrá-lo.

41
00:02:14,030 --> 00:02:19,700
>> Dentro de minutos, Evelyn descobre planos de Alice e maldosamente chama os pais de Alice.

42
00:02:19,700 --> 00:02:22,700
Alice e Bob tinha tomado CS50, teriam conhecido deste

43
00:02:22,700 --> 00:02:25,750
freqüência de análise-ataque à cifra de César,

44
00:02:25,750 --> 00:02:28,310
que permite que ele seja quebrado rapidamente.

45
00:02:28,310 --> 00:02:32,590
Eles também poderiam ter sabido que a cifra é facilmente sujeitos a um ataque de força bruta,

46
00:02:32,590 --> 00:02:35,940
pelo qual Evelyn poderia ter tentado todos os possíveis 25 teclas,

47
00:02:35,940 --> 00:02:38,440
ou turnos do alfabeto Inglês,

48
00:02:38,440 --> 00:02:40,490
com o fim de decifrar a mensagem.

49
00:02:40,490 --> 00:02:43,710
Por 25 teclas e não 26?

50
00:02:43,710 --> 00:02:49,010
>> Bem, tente deslocar qualquer carta por 26 posições, e você vai ver o porquê.

51
00:02:49,010 --> 00:02:52,280
De qualquer forma, um ataque de força bruta teria levado Evelyn um pouco mais

52
00:02:52,280 --> 00:02:56,070
mas não o suficiente para impedi-la de frustrar os planos de Alice e Bob,

53
00:02:56,070 --> 00:02:58,660
especialmente se Evelyn tem a ajuda de um computador

54
00:02:58,660 --> 00:03:02,640
que poderia rasgar todos os 25 casos em um instante.

55
00:03:02,640 --> 00:03:06,170
Então, este problema também atormentado outros, que usaram a cifra de César,

56
00:03:06,170 --> 00:03:10,300
e, portanto, as pessoas começaram a experimentar com cifras de substituição mais complexas

57
00:03:10,300 --> 00:03:14,190
que o uso de valores de deslocamento múltiplas em vez de apenas um.

58
00:03:14,190 --> 00:03:18,080
Um dos mais conhecidos deles é chamado de cifra de Vigenère.

59
00:03:18,080 --> 00:03:19,980
Como podemos obter valores de deslocamento múltiplos?

60
00:03:19,980 --> 00:03:24,630
Bem, em vez de usar um número como a chave, usamos uma palavra para a chave.

61
00:03:24,630 --> 00:03:27,940
Vamos usar cada letra a chave para gerar um número,

62
00:03:27,940 --> 00:03:33,670
eo efeito é que nós vamos ter vários César cifra estilo chaves para o deslocamento de letras.

63
00:03:33,670 --> 00:03:36,620
>> Vamos ver como isso funciona, criptografando mensagem de Alice para Bob:

64
00:03:36,620 --> 00:03:39,010
Encontre-me no parque de onze horas

65
00:03:39,010 --> 00:03:42,610
Eu, pessoalmente, acho que o bacon é delicioso,

66
00:03:42,610 --> 00:03:44,480
então vamos usar isso como a chave.

67
00:03:44,480 --> 00:03:48,220
Se tomarmos a mensagem em seu criptografado, formato de texto simples,

68
00:03:48,220 --> 00:03:51,020
vemos que são 25 letras.

69
00:03:51,020 --> 00:03:55,020
Bacon tem apenas 5 letras, por isso precisamos repetir 5 vezes

70
00:03:55,020 --> 00:03:57,200
para fazê-lo coincidir com o comprimento do texto simples.

71
00:03:57,200 --> 00:03:59,880
>> Bacon Bacon Bacon Bacon Bacon.

72
00:03:59,880 --> 00:04:02,300
Como um breve aparte, se o número de letras no texto simples

73
00:04:02,300 --> 00:04:05,780
não dividir limpa pelo número de letras na chave,

74
00:04:05,780 --> 00:04:08,260
nós apenas terminar a repetição final da nossa chave cedo,

75
00:04:08,260 --> 00:04:11,800
usando apenas as letras que precisávamos para fazer tudo igualar-se.

76
00:04:11,800 --> 00:04:14,590
Agora vamos em encontrar os valores de deslocamento.

77
00:04:14,590 --> 00:04:19,100
>> Nós vamos fazer isso usando a posição de cada letra do nosso chave - bacon -

78
00:04:19,100 --> 00:04:21,560
no alfabeto de A a Z.

79
00:04:21,560 --> 00:04:26,060
Desde que nós somos cientistas da computação, nós gostamos de começar a contar do zero em vez de um,

80
00:04:26,060 --> 00:04:30,230
então vamos dizer que a posição da primeira letra de bacon - B -

81
00:04:30,230 --> 00:04:33,840
está na posição 1 no A com índice zero para alfabeto Z,

82
00:04:33,840 --> 00:04:38,300
não 2, e a posição de A é zero e não 1.

83
00:04:38,300 --> 00:04:42,450
Usando esse algoritmo, podemos encontrar os valores de deslocamento para cada letra.

84
00:04:42,450 --> 00:04:45,330
>> Para criptografar o texto simples e gerar texto cifrado,

85
00:04:45,330 --> 00:04:49,070
nós apenas deslocar cada letra do texto claro pela quantidade especificada,

86
00:04:49,070 --> 00:04:54,140
assim como fazemos com a cifra de César, envolvendo de Z a A volta se necessário.

87
00:04:54,140 --> 00:04:57,880
M fica deslocado por um lugar para se tornar N.

88
00:04:57,880 --> 00:05:02,350
O primeiro E não muda em tudo, mas mudamos o E segundo por 2 lugares para G

89
00:05:02,350 --> 00:05:06,200
e T por 14 lugares para H.

90
00:05:06,200 --> 00:05:08,610
Se trabalhar com o texto simples, vamos acabar com,

91
00:05:08,610 --> 00:05:12,580
"Negh zf av huf pcfx bt gzrwep onça"

92
00:05:12,580 --> 00:05:16,620
Novamente, não muito romântico-som, mas definitivamente enigmático.

93
00:05:16,620 --> 00:05:19,750
Se Alice e Bob tinha conhecimento Vigenère cifra,

94
00:05:19,750 --> 00:05:23,330
teriam sido salvo de olhares indiscretos Evelyn?

95
00:05:23,330 --> 00:05:24,870
O que você acha?

96
00:05:24,870 --> 00:05:27,450
Você gostaria de entrar em sua conta bancária, se o seu banco decidiu usar

97
00:05:27,450 --> 00:05:32,720
>> Vigenère cifra para criptografar sua comunicação usando a sua senha como a chave?

98
00:05:32,720 --> 00:05:34,810
Se eu fosse você, eu não faria.

99
00:05:34,810 --> 00:05:38,720
E enquanto Evelyn pode ser mantido ocupado o tempo suficiente para Alice e Bob têm sua reunir-se,

100
00:05:38,720 --> 00:05:41,600
não vale a pena para Alice e Bob chance.

101
00:05:41,600 --> 00:05:45,780
Vigenère cifra é relativamente fácil de quebrar se você sabe o tamanho da chave

102
00:05:45,780 --> 00:05:48,490
porque, então, você pode tratar o texto cifrado criptografado

103
00:05:48,490 --> 00:05:52,840
como o produto de algumas cifras Caesar entrelaçadas.

104
00:05:52,840 --> 00:05:55,950
>> Encontrar o comprimento da chave não é muito difícil, também.

105
00:05:55,950 --> 00:06:00,520
Se a mensagem de texto simples original é longo o suficiente para que algumas palavras ocorrem várias vezes,

106
00:06:00,520 --> 00:06:04,420
eventualmente, você vai ver a repetição surgindo na codificação de texto criptografado,

107
00:06:04,420 --> 00:06:10,010
como neste exemplo, onde você vê Moncy aparecem duas vezes.

108
00:06:10,010 --> 00:06:13,800
Além disso, você pode executar um ataque de força bruta contra a cifra.

109
00:06:13,800 --> 00:06:17,220
Isso faz demorar muito mais do que um ataque de força bruta contra a cifra de César,

110
00:06:17,220 --> 00:06:20,670
o que pode ser feito quase instantaneamente com um computador

111
00:06:20,670 --> 00:06:27,130
pois em vez de 25 casos para verificar que você tem 26 ⁿ - 1 possibilidades,

112
00:06:27,130 --> 00:06:29,580
onde n é o comprimento da chave desconhecida.

113
00:06:29,580 --> 00:06:34,040
>> Isto é porque cada letra da chave pode ser qualquer um dos 26 letras,

114
00:06:34,040 --> 00:06:38,280
A a Z, e uma pessoa inteligente poderiam tentar usar uma chave que não podem ser encontradas em um dicionário,

115
00:06:38,280 --> 00:06:44,280
o que significa que você teria que testar todas as combinações de letras estranhas, como ZXXXFF,

116
00:06:44,280 --> 00:06:47,690
e não apenas um par cem mil palavras no dicionário.

117
00:06:47,690 --> 00:06:53,200
A menos 1 entra na matemática porque você não iria querer usar uma chave com apenas um é,

118
00:06:53,200 --> 00:06:56,200
uma vez que com o nosso alfabeto com índice zero que lhe daria o mesmo efeito

119
00:06:56,200 --> 00:06:59,620
como a utilização de uma cifra de César com uma chave de zero.

120
00:06:59,620 --> 00:07:04,120
De qualquer forma, 26 ⁿ - 1 não ficar grande rapidamente,

121
00:07:04,120 --> 00:07:08,080
mas enquanto você definitivamente não gostaria de tentar quebrar uma cifra à mão desta forma,

122
00:07:08,080 --> 00:07:11,080
este é definitivamente factível com um computador.

123
00:07:11,080 --> 00:07:14,030
Felizmente para Alice e Bob, e para serviços bancários online,

124
00:07:14,030 --> 00:07:17,890
criptógrafos desenvolveram maneiras mais seguras para encriptar mensagens secretas

125
00:07:17,890 --> 00:07:19,690
de olhos curiosos.

126
00:07:19,690 --> 00:07:22,400
>> No entanto, isso é um assunto para outro momento.

127
00:07:22,400 --> 00:07:26,210
Meu nome é Nate Hardison. Este é CS50.