[Powered by Google Translate] [Vigenère Cipher]
[Nate Hardison - Harvard University]
[Esta é CS50. - CS50.TV]
Coñeza Alicia.
Alicia ten unha caída por Bob.
Afortunadamente para Alicia, Bob tamén ten ollos para ela.
Desafortunadamente para a súa novela,
non só os pais de Alicia desaprovam Bob,
pero o mellor amigo de Alicia, Evelyn, ten unha paixón secreta por Bob
e egoisticamente quere perder los separados en todos os custos.
Para enviar mensaxes secretas para o outro que os pais de Alicia non pode entender,
>> Alicia e Bob foron usando unha cifra de César,
que funciona a través da transferencia do alfabeto por un certo número de cartas
como un modo para xerar un novo alfabeto.
Cada letra do alfabeto orixinal é entón substituído polo seu letra correspondente
no novo alfabeto desprazado.
Número favorito de Alicia e 3, que Bob sabe,
de xeito que ela usa como a súa clave 3.
Cando cambia o alfabeto inglés por tres letras,
A torna-se D, B torna-se E, C torna-se F,
e así por diante.
>> Cando chega ao final do alfabeto - para as letras X, Y e Z -
ela só implica en torno de volta para o inicio do alfabeto
e X substitutos cun Y, con B e Z con C.
Así, cando Alicia vai para cifrar a súa mensaxe secreta a Bob,
ou sexa, "Atopar me no parque no once horas",
ela só fai as substitucións adecuadas.
M torna-se P, E torna-se H, e así por diante ata que ela non cifrada mensaxe de texto simple
é transformada en texto cifrado cifrado:
"Phhw ph DW WKH sdun DW hohyhq dp"
definitivamente non é o son máis romántico,
pero Alice cren que vai facer.
>> Alicia dá a mensaxe de Evelyn para entregar a casa de Bob.
Pero Evelyn vez leva-lo de volta para o seu cuarto e intenta descifrar o código.
Unha das primeiras cousas Evelyn avisos é que a letra H ocorre sete veces na mensaxe,
veces máis do que calquera outra letra.
Sabendo que a letra E é a máis común no idioma inglés,
produciron preto de 13% do tempo,
Evelyn suposicións que H foi substituídos por E, a fin de facer a mensaxe secreta
e intenta usar unha chave de 3 a decifra-lo.
>> Dentro de minutos, Evelyn descobre plans de Alicia e maldosamente chama os pais de Alicia.
Alicia e Bob tomara CS50, terían coñecido deste
frecuencia de análise-ataque á cifra de César,
que permite que sexa roto rapidamente.
Eles poderían ter sabido que a cifra é facilmente suxeitos a un ataque de forza bruta,
polo cal Evelyn podería tentar todos os posibles 25 teclas,
ou quendas do alfabeto inglés,
co fin de descifrar a mensaxe.
Por 25 teclas e non 26?
>> Ben, proba cambiar calquera carta por 26 posicións, e vai ver o porqué.
En calquera caso, un ataque de forza bruta levaría Evelyn un pouco máis
pero non o suficiente para impedir-la de frustrar os plans de Alicia e Bob,
especialmente se Evelyn ten a axuda dun ordenador
que podería rasgar todos os 25 casos nun instante.
Entón, este problema tamén atormentado outros, que usaron a cifra de César,
e, polo tanto, as persoas comezaron a experimentar con cifras de substitución máis complexas
que o uso de valores de desprazamento múltiples en vez de só un.
Un dos máis coñecidos deles é chamado de cifra de Vigenère.
Como podemos obter valores de desprazamento múltiples?
Ben, en vez de usar un número como a clave, usan unha palabra para a clave.
Imos usar cada letra a clave para xerar un número,
eo efecto é que nós imos ter varios César cifra estilo claves para o desprazamento de letras.
>> Imos ver como funciona isto, criptografando mensaxe de Alicia para Bob:
Atopar me no parque de once horas
Eu, persoalmente, creo que o Bacon é delicioso,
entón imos usar isto como a clave.
Se tomamos a mensaxe no seu criptografía, formato de texto simple,
vemos que son 25 letras.
Bacon só 5 letras, por iso necesitamos repetir 5 veces
para facelo coincidir coa lonxitude do texto simple.
>> Bacon Bacon Bacon Bacon Bacon.
Como un breve separadamente, o número de letras en texto simple
non dividir limpa polo número de letras en clave,
Nós só rematar a repetición final da nosa clave cedo,
usando só as letras que necesitabamos para facer todo igual-se.
Agora imos para atopar os valores de desprazamento.
>> Nós imos facer isto usando a posición de cada letra do noso clave - Bacon -
no alfabeto da a Z.
Dende que somos científicos da computación, nós gústanos de comezar a contar desde cero en vez de un,
entón imos dicir que a posición da primeira letra de Bacon - B -
está na posición 1 na A con índice cero para alfabeto Z,
non 2, e a posición da é cero e non 1.
Usando este algoritmo, podemos atopar os valores de desprazamento para cada letra.
>> Para cifrar o texto simple e xerar texto cifrado,
Nós só desprazar cada letra do texto claro pola cantidade especificada,
así como facemos coa cifra de César, que inclúen de Z a A volta necesario.
M queda desprazado por un lugar para facer N.
O primeiro é que non cambia en todo, pero cambiamos o E segundo por 2 lugares para G
e T por 14 lugares para H.
Traballar co texto simple, imos acabar con,
"Negh ZF av HUF pcfx BT gzrwep onza"
De novo, non moi romántico-son, pero definitivamente enigmático.
Se Alicia e Bob tiña coñecemento Vigenère cifra,
serían salvo de miradas indiscretos Evelyn?
¿Que pensas?
¿Quere entrar na súa conta bancaria, o seu banco decidiu usar
>> Vigenère cifra para cifrar a súa comunicación a través da súa contrasinal como chave?
Se eu fose ti, eu non faría.
E mentres Evelyn pode ser mantido ocupado o tempo suficiente para Alicia e Bob teñen a súa reunir-se,
non paga a pena para Alicia e Bob oportunidade.
Vigenère cifra é relativamente fácil de romper se sabe o tamaño da clave
porque, entón, pode tratar o texto cifrado cifrado
como o produto de algunhas cifras Caesar entrelazadas.
>> Atopar a lonxitude da clave non é moi difícil, tamén.
Se a mensaxe de texto simple orixinal é longo o suficiente para que algunhas palabras ocorren varias veces,
finalmente, vai ver a repetición xurdindo na codificación de texto cifrado,
como neste exemplo, onde ve Moncy aparecen dúas veces.
Ademais, pode realizar un ataque de forza bruta contra a cifra.
Isto fai levar moito máis que un ataque de forza bruta contra a cifra de César,
o que se pode facer case instantaneamente con un ordenador
pois en vez de 25 casos para comprobar que ten 26 ⁿ - 1 posibilidades,
onde n é a lonxitude da clave descoñecida.
>> Isto é porque cada letra da clave pode ser calquera dos 26 letras,
A a Z, e unha persoa intelixente poderían tentar empregar unha chave que non se pode acceder nun dicionario,
o que significa que tería que probar todas as combinacións de letras estrañas, como ZXXXFF,
e non só un par cen mil palabras no dicionario.
A menos 1 entra na matemática porque non vai querer usar unha chave con só un é,
unha vez que o noso alfabeto con índice cero que lle daría o mesmo efecto
como a utilización dunha cifra de César cunha clave de cero.
En calquera caso, 26 ⁿ - 1 non queda gran rapidamente,
pero mentres vostede definitivamente non quere tentar romper unha cifra a man desta forma,
este é sempre factible cun ordenador.
Afortunadamente para Alicia e Bob, e para servizos bancarios en liña,
criptógrafos desenvolveron formas máis seguras para cifrar mensaxes secretas
de ollos curiosos.
>> Con todo, iso é un tema para outro momento.
O meu nome é Nate Hardison. Este é CS50.