[Powered by Google Translate] [Vigenère Cipher]
[Nate Hardison - Harvard University]
[Esta é CS50. - CS50.TV]
Conheça Alice.
Alice tem uma queda por Bob.
Felizmente para Alice, Bob também tem olhos para ela.
Infelizmente para o seu romance,
não só os pais de Alice desaprovam Bob,
mas o melhor amigo de Alice, Evelyn, tem uma paixão secreta por Bob
e egoisticamente quer mantê-los separados em todos os custos.
Para enviar mensagens secretas para o outro que os pais de Alice não consegue entender,
>> Alice e Bob foram usando uma cifra de César,
que funciona através da transferência do alfabeto por um certo número de cartas
como um modo para gerar um novo alfabeto.
Cada letra do alfabeto original é então substituído por seu letra correspondente
no novo alfabeto deslocado.
Número favorito de Alice é 3, que Bob sabe,
de modo que ela usa como sua chave 3.
Quando ela muda o alfabeto Inglês por três letras,
A torna-se D, B torna-se E, C torna-se F,
e assim por diante.
>> Quando chega ao fim do alfabeto - para as letras X, Y e Z -
ela apenas envolve em torno de volta para o início do alfabeto
e X substitutos com um Y, com B e Z com C.
Assim, quando Alice vai para criptografar sua mensagem secreta a Bob,
ou seja, "Encontre-me no parque no onze horas",
ela só faz as substituições adequadas.
M torna-se P, E torna-se H, e assim por diante até que ela não criptografada mensagem de texto simples
é transformada em texto cifrado criptografado:
"Phhw ph dw WKH sdun dw hohyhq dp"
definitivamente não é o som mais romântico,
mas Alice acreditam que ele vai fazer.
>> Alice dá a mensagem de Evelyn para entregar a casa de Bob.
Mas Evelyn vez leva-lo de volta para seu quarto e tenta decifrar o código.
Uma das primeiras coisas Evelyn avisos é que a letra H ocorre sete vezes na mensagem,
vezes mais do que qualquer outra letra.
Sabendo que a letra E é a mais comum no idioma Inglês,
ocorrendo cerca de 13% do tempo,
Evelyn suposições que H tem sido substituídos por E, a fim de tornar a mensagem secreta
e tenta usar uma chave de 3 a decifrá-lo.
>> Dentro de minutos, Evelyn descobre planos de Alice e maldosamente chama os pais de Alice.
Alice e Bob tinha tomado CS50, teriam conhecido deste
freqüência de análise-ataque à cifra de César,
que permite que ele seja quebrado rapidamente.
Eles também poderiam ter sabido que a cifra é facilmente sujeitos a um ataque de força bruta,
pelo qual Evelyn poderia ter tentado todos os possíveis 25 teclas,
ou turnos do alfabeto Inglês,
com o fim de decifrar a mensagem.
Por 25 teclas e não 26?
>> Bem, tente deslocar qualquer carta por 26 posições, e você vai ver o porquê.
De qualquer forma, um ataque de força bruta teria levado Evelyn um pouco mais
mas não o suficiente para impedi-la de frustrar os planos de Alice e Bob,
especialmente se Evelyn tem a ajuda de um computador
que poderia rasgar todos os 25 casos em um instante.
Então, este problema também atormentado outros, que usaram a cifra de César,
e, portanto, as pessoas começaram a experimentar com cifras de substituição mais complexas
que o uso de valores de deslocamento múltiplas em vez de apenas um.
Um dos mais conhecidos deles é chamado de cifra de Vigenère.
Como podemos obter valores de deslocamento múltiplos?
Bem, em vez de usar um número como a chave, usamos uma palavra para a chave.
Vamos usar cada letra a chave para gerar um número,
eo efeito é que nós vamos ter vários César cifra estilo chaves para o deslocamento de letras.
>> Vamos ver como isso funciona, criptografando mensagem de Alice para Bob:
Encontre-me no parque de onze horas
Eu, pessoalmente, acho que o bacon é delicioso,
então vamos usar isso como a chave.
Se tomarmos a mensagem em seu criptografado, formato de texto simples,
vemos que são 25 letras.
Bacon tem apenas 5 letras, por isso precisamos repetir 5 vezes
para fazê-lo coincidir com o comprimento do texto simples.
>> Bacon Bacon Bacon Bacon Bacon.
Como um breve aparte, se o número de letras no texto simples
não dividir limpa pelo número de letras na chave,
nós apenas terminar a repetição final da nossa chave cedo,
usando apenas as letras que precisávamos para fazer tudo igualar-se.
Agora vamos em encontrar os valores de deslocamento.
>> Nós vamos fazer isso usando a posição de cada letra do nosso chave - bacon -
no alfabeto de A a Z.
Desde que nós somos cientistas da computação, nós gostamos de começar a contar do zero em vez de um,
então vamos dizer que a posição da primeira letra de bacon - B -
está na posição 1 no A com índice zero para alfabeto Z,
não 2, e a posição de A é zero e não 1.
Usando esse algoritmo, podemos encontrar os valores de deslocamento para cada letra.
>> Para criptografar o texto simples e gerar texto cifrado,
nós apenas deslocar cada letra do texto claro pela quantidade especificada,
assim como fazemos com a cifra de César, envolvendo de Z a A volta se necessário.
M fica deslocado por um lugar para se tornar N.
O primeiro E não muda em tudo, mas mudamos o E segundo por 2 lugares para G
e T por 14 lugares para H.
Se trabalhar com o texto simples, vamos acabar com,
"Negh zf av huf pcfx bt gzrwep onça"
Novamente, não muito romântico-som, mas definitivamente enigmático.
Se Alice e Bob tinha conhecimento Vigenère cifra,
teriam sido salvo de olhares indiscretos Evelyn?
O que você acha?
Você gostaria de entrar em sua conta bancária, se o seu banco decidiu usar
>> Vigenère cifra para criptografar sua comunicação usando a sua senha como a chave?
Se eu fosse você, eu não faria.
E enquanto Evelyn pode ser mantido ocupado o tempo suficiente para Alice e Bob têm sua reunir-se,
não vale a pena para Alice e Bob chance.
Vigenère cifra é relativamente fácil de quebrar se você sabe o tamanho da chave
porque, então, você pode tratar o texto cifrado criptografado
como o produto de algumas cifras Caesar entrelaçadas.
>> Encontrar o comprimento da chave não é muito difícil, também.
Se a mensagem de texto simples original é longo o suficiente para que algumas palavras ocorrem várias vezes,
eventualmente, você vai ver a repetição surgindo na codificação de texto criptografado,
como neste exemplo, onde você vê Moncy aparecem duas vezes.
Além disso, você pode executar um ataque de força bruta contra a cifra.
Isso faz demorar muito mais do que um ataque de força bruta contra a cifra de César,
o que pode ser feito quase instantaneamente com um computador
pois em vez de 25 casos para verificar que você tem 26 ⁿ - 1 possibilidades,
onde n é o comprimento da chave desconhecida.
>> Isto é porque cada letra da chave pode ser qualquer um dos 26 letras,
A a Z, e uma pessoa inteligente poderiam tentar usar uma chave que não podem ser encontradas em um dicionário,
o que significa que você teria que testar todas as combinações de letras estranhas, como ZXXXFF,
e não apenas um par cem mil palavras no dicionário.
A menos 1 entra na matemática porque você não iria querer usar uma chave com apenas um é,
uma vez que com o nosso alfabeto com índice zero que lhe daria o mesmo efeito
como a utilização de uma cifra de César com uma chave de zero.
De qualquer forma, 26 ⁿ - 1 não ficar grande rapidamente,
mas enquanto você definitivamente não gostaria de tentar quebrar uma cifra à mão desta forma,
este é definitivamente factível com um computador.
Felizmente para Alice e Bob, e para serviços bancários online,
criptógrafos desenvolveram maneiras mais seguras para encriptar mensagens secretas
de olhos curiosos.
>> No entanto, isso é um assunto para outro momento.
Meu nome é Nate Hardison. Este é CS50.