Information theoretic security and the one time pad (19 min)

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.