Agora que vimos alguns exemplos de cifras históricas, todas as quais são mal
quebrado, vamos mudar de assunto e falar sobre cifras que são muito melhores
projetado. Mas antes de fazermos isso, eu quero em primeiro lugar, definir com mais precisão o que é um
cifra é. Então, primeiro de tudo, uma cifra é, na verdade, lembre-se uma cifra é composta de
dois algoritmos. Há um algoritmo de encriptação e um algoritmo de descriptografia. Mas
, na verdade, uma cifra é definida por um triplo. Assim, o conjunto de todas as chaves possíveis,
que eu estou indo para denotar pelo script K, e às vezes eu vou chamar esta a tecla de espaço,
é o conjunto de todas as chaves possíveis. Há neste conjunto de todas as mensagens possíveis e este
conjunto de todos os textos cifrados possíveis. Ok, então este triplo em algum sentido define o
ambiente durante o qual a cifra é definido. E, em seguida, a cifra em si é um
par de algoritmos eficientes E e D. E é o algoritmo de criptografia; D é o
algoritmo de descriptografia. Claro que, E leva chaves e mensagens. E cifra saídas
textos. E o algoritmo de decodificação leva chaves e mensagens cifradas. Então envia mensagens.
E os únicos requisitos é que estes algoritmos são consistentes. Eles satisfazem
que é chamado de propriedade correção. Assim, para cada mensagem no espaço de mensagem.
E cada chave. No espaço de chave, é melhor que seja o caso que se eu encriptar o
mensagem com a chave K e então eu descriptografar usando o KI mesma chave era melhor voltar
a mensagem original que eu comecei com. Portanto, esta equação aqui é que é chamado de
equação consistência e cada cypher tem para satisfazê-lo, a fim de ser uma cifra
caso contrário não é possível decifrar. Uma coisa que eu queria salientar é que eu
colocar a palavra eficiente aqui entre aspas. E a razão de eu fazer isso é por causa eficiente
significa coisas diferentes para pessoas diferentes. Se você está mais inclinado para
teoria, meio eficiente é executado em tempo polinomial. Então, algoritmos E e D tem que ser executado em
tempo polinomial no tamanho de seus insumos. Se você for mais prática
inclinadas, eficaz executado dentro de um determinado período de tempo. Assim, por exemplo,
E algoritmo pode ser obrigado a tomar menos de um minuto para criptografar um gigabyte de
dados. Agora de qualquer forma, a palavra tipo eficiente de captura de ambas as noções e você pode
interpretá-la em sua cabeça do jeito que você gostaria. Eu estou indo só para manter
referindo a ele como citações eficientes e colocar nele, como eu disse se você é teoria
inclinado pensar nisso como tempo polinomial, caso contrário, pensar nele como
concretas limitações de tempo. Outro comentário que quero fazer é, na verdade algoritmo E.
É muitas vezes um algoritmo aleatório. O que isto significa é que, como sua criptografia
mensagens, e algoritmo vai gerar bits aleatórios para si, e que vai
usar esses bits aleatórios realmente criptografar as mensagens que são dadas a ele. No
outro lado, o algoritmo de decodificação é sempre uma determinística. Em outras palavras dadas
chave ea saída de texto cypher é sempre a mesma. Não depende de qualquer
aleatoriedade que é usada pelo algoritmo. Ok, então agora que entendemos o que é um
cifra é melhor, eu quero tipo de mostrar-lhe o primeiro exemplo de uma cifra segura.
Chama-se uma almofada de tempo uma Foi desenhado por volta Vernam no início do
século XX. Antes que eu realmente explicar o que o Cyper é, vamos
estado em que, na terminologia que acabamos de ver. Assim, o espaço de mensagem para o
cypher Vernam para a almofada de um tempo é o mesmo que o espaço de texto cypher que é
apenas o conjunto de todas as cadeias binárias terminou. Isso, isso só significa todas as seqüências de
bits, um de zero caracteres. O espaço de chave é basicamente o mesmo que a mensagem
espaço que é novamente simplesmente o embed de todas as strings binárias. Assim, uma chave no uma
Time Pad é simplesmente uma seqüência aleatória grande, é uma seqüência aleatória de bits. Isso é tão
desde que a mensagem a ser encriptada, contanto que a mensagem. Ok, agora que nós temos
tipo especificado de que está a cifra é definida sobre nós realmente podemos especificar como
cypher as obras e é realmente muito simples. Então, basicamente as cyphertexts.
que é o resultado de cifrar uma mensagem com uma chave particular, é simplesmente
XOR a dos dois. Basta K XOR M. [inaudível] ver um exemplo rápido de
presente. Lembre-se que XOR, isso acrescido com um círculo. XOR significa além
modulo dois. Então, se eu levar uma mensagem especial, por exemplo, 0110111. E tomar uma
chave particular, dizer 1011001. Quando eu calcular a criptografia da mensagem
usando o [inaudível], tudo o que eu faço é calcular o XOR dos dois
cordas. Em outras palavras, eu faço módulo de adição ou dois pouco a pouco. Então, eu tenho um,
um, zero, um, um, um, zero. Isso é um texto cifrado. E depois como faço para descriptografar? Eu
acho que eles poderiam fazer tipo da mesma coisa. Então eles decifrar um texto cifrado usando
uma chave particular. O que eu faço é XOR da chave eo texto cifrado de novo. E assim todo o
temos que verificar é que ele satisfaz os requisitos de consistência. E eu vou
fazer isso uma vez e depois lentamente a partir de agora eu estou indo supor que tudo isso é simples, para
você. Então nós vamos fazer, nós vamos ter a certeza de que se eu decifrar uma cifra
texto, que foi criptografado usando uma chave particular, é melhor eu ficar. Voltar ao
mensagem M. Então o que acontece aqui? Bem, vamos ver. Então, se eu olhar para a criptografia
de k e m, este é apenas k XOR m por definição. Qual é a decodificação de k XOR
m usando k? Isso é apenas k XOR (k XOR m). E assim desde que eu disse que é XOR
além modulo dois, além disso é associativa, por isso este é o mesmo que (k XOR k)
XOR m, que é simplesmente como você sabe k XOR k é um zero, e zero nada XOR
é simplesmente m. Ok, então isso realmente mostra que o one-time pad é de fato uma cifra,
, mas não diz nada sobre a segurança do Cyper. E nós vamos falar
sobre a segurança da cifra em apenas um minuto. Primeiro de tudo, deixe-me perguntar
lhe uma pergunta, só para ter certeza que estamos todos em sincronia. Suponha que você é dado um
m mensagem ea encriptação de que a mensagem usando a almofada de uma vez. Então tudo
você recebe é a mensagem eo texto cifrado. A minha pergunta é, dado este
par M e C, pode, na verdade descobrir a chave caminho um tempo de que foi usado no
criação de C a partir de m?
Então eu espero que todos vocês percebem que, na verdade, dada a mensagem em
o texto cifrado é muito fácil para recuperar o que é a chave. Em particular, a chave é
simplesmente M XOR C. Em seguida, veremos que, se não é imediatamente óbvio para você nós
ver porque isso é, no caso, um pouco mais tarde, na conversa, na palestra. Ok tudo bem
para o bloco 1 vez é um muito legal do ponto de vista de desempenho tudo o que você está fazendo
é você exo anel-chave na mensagem então é um rápido, super super. Cypher para
criptografar e descriptografar mensagens muito longas. Infelizmente é muito
difíceis de usar na prática. A razão é difícil de usar é as teclas são
essencialmente enquanto a mensagem. Assim, se Alice e Bob querem comunicar
segurança, então você sabe que a Alice quer enviar uma mensagem final para Bob, antes que ela começa
até mesmo enviando o primeiro bit da mensagem, ela tem de transmitir uma chave para Bob, que é tão
enquanto que a mensagem. Bem, se ela tem uma maneira de transmitir uma chave segura para Bob que é
enquanto a mensagem, ela pode também usar que mesmo mecanismo para transmitir também
a própria mensagem. Assim, o facto de que a chave é tão longa como a mensagem é bastante
problemático e faz com que a almofada de um tempo muito difícil usar na prática.
Embora nós vamos ver que a idéia por trás do one-time pad é realmente muito útil
e vamos ver que um pouco mais tarde. Mas por agora quero me concentrar um pouco mais sobre
segurança. Assim, as perguntas são óbvias, você sabe, porque é a one-time pad é seguro?
Por que é uma cifra boa? Então, para responder a essa pergunta, a primeira coisa que temos de
resposta é: o que é uma cifra segura para começar? O que é um, o que faz cifra
seguro? Ok, então o estudo, a segurança de cifras, temos que falar um pouco
sobre teoria da informação. E de fato a primeira pessoa, para estudar a segurança de cifras
rigorosamente. É muito famoso, você sabe, o pai da teoria da informação, Claude
Shannon, e ele publicou um famoso artigo de volta em 1949, onde ele analisa a
segurança do one-time pad. Assim, a idéia por trás de definição de Shannon de segurança é
o seguinte. Basicamente, se tudo que você começa a ver-se o texto cifrado, então você deve
saber absolutamente nada sobre o texto sem formatação. Em outras palavras, o texto cypher
devem revelar nenhuma informação sobre o texto sem formatação. E você vê por que demorou
alguém que inventou a teoria da informação para chegar a essa noção, porque você tem
para formulize, formalmente explicar o que é que a informação sobre o texto simples, na verdade
dizer. Ok é isso que Shannon fez e assim deixa eu te mostrar definição de Shannon,
eu vou, eu vou escrevê-lo lentamente em primeiro lugar. Então, o que Shannon disse é que você sabe suponha que
ter um ED cifra que é definido por KM triplo e C como antes. Então, KM e
C definir a tecla de espaço, o espaço de mensagem eo espaço de texto cifrado. E quando dizemos
que o texto cifrado pena, dizemos que a cifra tem segredo perfeito se o
seguinte condição segura. Acontece a cada duas mensagens M zero e M1 em
espaço a mensagem. Para cada duas mensagens a única exigência que eu vou colocar em
estas mensagens é que eles têm o mesmo comprimento. É assim que nós somos apenas, vamos ver por que
essa exigência é necessária em apenas um minuto. E para cada cyphertext, no
espaço cyphertext. Ok? Assim, para cada par de mensagens método e para cada cifra
texto, é melhor que seja o caso que, se eu perguntar, qual é a probabilidade de que,
criptografar N zero com K, woops. Criptografia N zero com K dá C, ok? Assim
quão provável é que, se pegar uma chave aleatória? Qual é a probabilidade de que quando criptografar N
zero, obtemos C. Essa probabilidade deve ser o mesmo que quando criptografar N1. Ok, então
a probabilidade de criptografar n um e ficando c é exactamente o mesmo que o
probabilidade de criptografar n zero e ficando c. E como eu disse, onde o
chave, a distribuição, é sobre a distribuição da chave. Então, a chave é
uniforme no espaço de chave. Assim, k é uniforme em k. E eu estou muitas vezes vai escrever k seta
com um r pouco acima dele para denotar o facto de que k é uma variável aleatória que é
uniformemente amostrados no espaço k-chave. Ok, esta é a parte principal de Shannon
definição. E vamos pensar um pouco sobre o que esta definição realmente diz.
Então, o que significa que estas duas probabilidades são as mesmas? Bem, o que
diz é que se eu sou um atacante e eu interceptar um determinado texto cifrado c, então
na realidade, a probabilidade de que o texto é a cifra de criptografia de n zero é
exatamente o mesmo que a probabilidade de que ele é o de n incryption um. Porque
essas probabilidades são iguais. Então, se eu tenho, tudo o que tenho a C texto cifra que é
tudo o que eu ter interceptado Eu não tenho idéia se o texto cifra veio da M de zero
ou o texto cifra veio de um M porque mais uma vez a probabilidade de obter C é
igualmente prováveis se M Zero está sendo criptografado ou uma M estão sendo criptografados. Assim
aqui, temos a definição declarou novamente. E eu só quero escrever estas propriedades
novamente mais precisamente. Então, vamos escrever isso de novo. Então, o que definição [inaudível]
significa é que, se me é dado um texto cifrado em particular, eu não posso dizer de onde veio
a partir de. Eu não posso dizer se é, se a mensagem que foi criptografada. Ou é zero ou N N
um e, de fato, esta propriedade é verdadeira para todas as mensagens. Para todos estes N zero, para
todos os N zero e N. Assim, não só não posso dizer if'c 'veio N zero ou um N,
eu não posso dizer se ela veio de N duas ou três ou N N quatro ou cinco N porque todos
eles têm a mesma probabilidade de produzir o text'c cypher '. Então, o que isso significa realmente
é que se você está criptografia de mensagens com uma almofada de um tempo, então de fato a mais
adversário poderoso, eu realmente não me importo como você é inteligente, o mais poderoso
adversário. Pode aprender nada sobre o texto puro, não aprendeu nada sobre a planície
texto. A partir do texto cifrado. Assim, para dizê-lo em mais uma maneira, basicamente o que este
prova é que não há, não há nenhuma cifra ataque só de texto em uma cifra que
tem segredo perfeito. Agora, ataques de cifras na verdade não são os únicos ataques possíveis.
E, de fato, outros ataques pode ser possível, outros ataques podem ser possíveis.
Ok. Agora que entendemos o sigilo total, os meios, a questão é, podemos
cifras compilação que realmente têm sigilo perfeito? E acontece que nós não
tem que olhar muito longe, o fato de um padrão de tempo tem segredo perfeito. Então, eu
quer provar que isso é os primeiros resultados da China e eu quero provar esse fato para
você, é uma prova muito simples, então vamos seguir em frente e olhar para ele e apenas fazê-lo. Então, nós
necessidade de tipo de interpretar o que isso significa, o que é essa probabilidade de que EKM
Z é igual a C. Portanto, não é realmente tão difícil de ver que, para cada mensagem e
cada cyphertext a probabilidade de que a encriptação de N sob uma chave K do
probabilidade de que, isso é igual a C, a probabilidade de que a nossa escolha aleatória de chave
por definição. Tudo o que é, é basicamente o número de chaves. Kay, instruir Kay.
tal forma que, também. Se eu criptografar. E com k eu fico c. Então, eu literalmente contar o número
de chaves e divido pelo número total de chaves. Certo? Isso é o que significa que
se eu escolher uma chave aleatória, que mapeia tecla M para c. Direito. Então, é basicamente o número
de chave que mapa n para c dividido pelo número total de chaves. Esta é a sua
probabilidade. Então, suponha que nós tivemos uma cifra de tal forma que para todas as mensagens e todos os
textos cifrados, acontece que se eu olhar para este número, o número de k, k, e k,
e que tais, k, m é igual a c. Em outras palavras, eu estou olhando para o número de chaves
esse mapa para m c. Suponhamos que este número passa a ser uma constante. Então, dizer que
passa a ser dois, três, ou dez ou quinze anos. Ele só hap, passa a ser um
absoluta constância. Se for esse o caso, então por definição, para toda a n0 e n1 e
para todos c, esta probabilidade tem de ser a mesma porque o denominador é o mesmo,
o numerador é o mesmo, é tão constante e, portanto, a probabilidade é
sempre o mesmo para todos os N e C. E assim se esta propriedade é verdadeira, então a cifra tem
ter, a cifra tem segredo perfeito. Ok, então vamos ver o que podemos dizer sobre
quantidade esta que a almofada de uma vez. Assim, o sec-, assim, a pergunta é, se eu
tem uma mensagem em um texto cifrado, quantas teclas de um bloco de tempo estão lá [inaudível]
mapa, esta mensagem acaba, portanto, o [inaudível] C? Assim, por outras palavras, quantas as teclas são
lá, de tal modo que M XOR K é igual a C? Então eu espero que você tenha todos responderam um. E
vamos ver porque isso é o caso. Para o bloco uma vez, se temos que, a criptografia
de K de M sob K é igual a C. Mas, basicamente, bem, por definição, que
implica que K XOR M é igual a C. Mas, que também diz simplesmente que K tem para igualar
para M XOR C. Sim, eu apenas X mais de ambos os lados por M e eu recebo que K deve ser igual ao
M XOR C. Ok? Então, o que é que diz que, para a almofada de uma vez, na verdade, o
número de teclas, em K, mostra a EKM, é igual a C. Isto é simplesmente um, e este
vale para todas as mensagens de texto cifrado. E assim, novamente, com o que dissemos antes, ele só
diz que o bloco tem um tempo, o segredo perfeito. Sigilo total e que
completa a prova deste [inaudível] muito, muito simples. Muito, muito simples
lema. Agora o engraçado é que mesmo que este lema é tão simples de
provar, de fato, comprova uma afirmação muito forte novamente. Esta basicamente diz para
tempo o [inaudível] não há ataque de texto cifrado único. Assim, ao contrário do
cifra de substituição, ou a cifra de Vigenère, ou as máquinas de rolo, todos aqueles
poderia ser quebrada pelo texto cifrado somente ataque. Acabamos de provar que a one-time
almofada, que é simplesmente impossível. Dada a cyphertext, você simplesmente não aprende nada sobre
o texto original. No entanto, como podemos ver, isso simplesmente não é o fim da história. Eu
média, são fizemos? Quer dizer, basicamente, estamos a fazer com o curso agora, porque nós
tem um jeito. Para criptografar, de modo que um atacante não pode recuperar alguma coisa sobre o nosso
método. Então, talvez estamos a fazer com o curso. Mas, na verdade, como veremos, há
são outros ataques. E, na verdade, a almofada de tempo não é realmente um tal
cifra segura. E, de fato, existem outros ataques que são possíveis, e vamos
ver isso em breve. Ok? Enfatizo novamente o fato de que ele tem segredo perfeito faz
não significa que o bloco de momento é a cifra segura para utilizar. Okay. Mas como dissemos
o problema com a almofada de tempo é um que a chave secreta é muito longo. Se você tivesse
uma forma de. Comunicando a chave secreta ao longo para o outro lado. Você pode muito bem
uso que mesmo método exacto para também transmitir a mensagem para o outro lado,
caso em que você não precisaria de uma cifra, para começar. Ok? Então, o problema novamente
é o tapete uma vez tinha as chaves realmente longos e então a questão óbvia é que há
cifras outros que tem sigilo total e, possivelmente, têm muito, muito mais curtos chaves?
Bem, então a má notícia é o Shannon, depois de provar que o one-time pad tem
sigilo total, mostrou-se um outro teorema que diz que na verdade se tem uma cifra
sigilo total, o número de chaves em a cifra deve ser pelo menos o número de
mensagens que a cifra pode manipular. Ok, então, em particular, o que isto significa é que se eu
tem segredo perfeito. Então, necessariamente o número de chaves, ou melhor, a duração da minha
chave, deve ser maior do que o comprimento da mensagem. Assim, de facto, uma vez que a uma
pad tempo nos satisfaz com a igualdade, a almofada de uma vez é uma cifra, ideal que
tem segredo perfeito, ok? Então, basicamente, o que isto mostra é que esta é uma
noção interessante. A almofada de tempo uma é uma cifra interessante. Mas, na verdade, em
realidade, é realmente muito difícil de usar. É difícil de usar, na prática, mais uma vez,
devido a estas chaves longas. E assim, essa noção de sigilo perfeito, apesar de
é bastante interessante, basicamente diz que ele realmente não nos diz o
cifras práticas vão ser seguro. E nós vamos ver, mas, como dissemos, o
idéia por trás do bloco uma vez é muito bom. E nós vamos ver, na próxima palestra,
como fazer isso em um sistema prático.