thumb|372x372px|Excerto de uma cifra de uso único
One-time pad (OTP), em português cifra de uso único ou chave de uso único, é uma técnica de criptografia que não pode ser quebrada se utilizada corretamente.
Visão geral Consiste num algoritmo em que o purotexto é combinado, caractere por caractere, a uma chave secreta aleatória que para isso deve ter, no mínimo, o mesmo número de caracteres do purotexto. Para garantir que a criptografia seja imperscrutável, a chave só deve ser usada uma única vez, sendo imediatamente destruída após o uso. Foi primeiramente descrita pelo banqueiro e criptografista Frank Miller em 1882. Em 1917 foi re-inventada e, poucos anos depois, registrada.
A chave de uso único deriva da cifra de Vernam, cujo nome se deve a Gilbert Vernam, um de seus inventores. O sistema de Vernam consistia numa cifra que combinava uma mensagem com uma chave lida numa fita perfurada. Em sua forma original, o sistema de Vernam era vulnerável porque a fita com as chaves era reutilizada ao chegar ao fim. O uso único veio apenas posteriormente, quando Hoseph Maugorgne percebeu que se a fita fosse totalmente aleatória, a criptoanálise poderia ser impossível.
Se a chave for verdadeiramente aleatória, nunca reutilizada, e mantida em segredo, a cifra de uso único é imperscrutável. Também provou-se que toda a cifra teórica inquebrável deve usar chaves com as mesmas exigências que chaves de OTP.
A expressão "pad" do nome em inglês deve-se ao fato de que cifras de uso único comumente são utilizadas sob a forma de cadernetas, de modo que a folha superior possa ser arrancada e destruída após a utilização. Para facilitar sua ocultação, o bloco era às vezes muito pequeno, sendo quase impossível de ser utilizado sem uma lupa. Imagens acessíveis na Internet mostram cadernetas da KGB, capturadas por agentes oponentes, que cabem na palma da mão ou em uma casca de noz.
Existe muita ambiguidade na terminologia referente a esse tipo de cifra, já que alguns autores usam indistintamente os termos “cifra de Vernam” e “cifra de uso único”, enquanto outros utilizam a expressão "cifra de Vernam" para qualquer cifra de fluxo, inclusive as baseadas em CSPRNG.
História
O banqueiro Frank Miller, em 1882, foi o primeiro a descrever o funcionamento de chaves de uso único para uso em mensagens telegráficas.
Já no século XX, em 1917, foi criado para a AT&T o sistema eléctrico de Gilbert Vernam, patenteado em 1919, que se baseava na tecnologia utilizada no teletipo. Cada caractere na mensagem era electricamente combinado com uma chave contida numa fita perfurada. Joseph Mauborgne, então capitão das forças armadas dos Estados Unidos, percebeu que caso a sequência de caracteres na fita fosse totalmente aleatória, a criptoanálise seria mais difícil. Foi então introduzido o primeiro sistema de fita de uso único.
O próximo passo foi o desenvolvimento do sistema que utilizava a caderneta de papel. Durante muito tempo, os diplomatas usaram códigos e cifras para receber informações confidenciais e também reduzir os custos com telégrafo. Utilizando os códigos, as palavras e as frases eram convertidas em grupos de números (geralmente 4 ou 5 dígitos) usando um livro de códigos que funcionava como uma espécie de dicionário. Para aumentar a segurança, números secretos podiam ser combinados (geralmente por meio de adição modular) com cada grupo de números antes da transmissão, com os números secretos sendo trocados periodicamente. Esse sistema era chamado de superencryption. No início dos anos 1920, três criptografistas alemães — Werner Kunze, Rudolf Schauffler e Erich Langlotz -— que estavam envolvidos em descodificar esses sistemas, perceberam que eles poderiam ser indecifráveis se um número escolhido aleatoriamente fosse usado para codificar cada grupo. Eles possuíam cadernetas de papel idênticas, com grupos de números aleatórios. Cada página tinha um número de série e oito linhas; por conseguinte cada linha tinha seis números de cinco dígitos cada um. Uma página seria usada para codificar uma mensagem e imediatamente destruída. O número serial da página seria enviado com a mensagem codificada, para que o receptor soubesse qual a página a usar. Para descodificar, o destinatário deveria apenas realizar o processo inverso ao de codificação, destruindo a página após terminar. O ministério das relações exteriores alemão pôs o sistema em operação em 1923.
A última descoberta relacionada à cifra de uso único deveu-se a Claude Shannon que, nos anos 1940, comprovou cientificamente a segurança desse sistema. Shannon relatou seus resultados em um relatório confidencial em 1945 e publicou-os abertamente em 1949. Na mesma época, Vladimir Kotelnikov havia provado independentemente a segurança das chaves de uso único. Seus resultados foram registrados em um relatório que aparentemente permanece confidencial. PACS numbers: 01.10.Fv, 03.67.Dd, 89.70.+c and openly in Russian Квантовая криптография и теоремы В.А. Котельникова об одноразовых ключах и об отсчетах. УФН
Exemplo
Suponhamos que Alice deseje emitir a mensagem HELLO ("olá") a Bob. Suponha que ambos estejam de posse de cadernetas que contenham sequências aleatórias idênticas previamente produzidas. Alice escolhe a página apropriada (ainda não-utilizada) da caderneta. O critério de escolha deve ser combinada previamente entre as partes. Geralmente usa-se regras como "usar a primeira folha disponível" ou "usar a folha X para o dia tal".
O material na folha selecionada é a chave para codificação e decodificação da mensagem. Cada letra da cifra será combinada de uma forma padrão a uma letra da mensagem. Geralmente, atribui-se a cada letra um valor numérico: por exemplo, A=0, B=1, e assim por diante, até Z=25. Neste exemplo, a técnica é combinar a chave e a mensagem usando a adição modular. Assim, somam-se os numéricos de cada letra da mensagem ao seu correspondente na cifra. Deve-se lembrar de considerar o módulo 26, de modo que, se uma soma ultrapassa 26, o número deve ser dividido por 26, tomando-se, no lugar dele, apenas o resto da divisão inteira.
No exemplo em questão, portanto, se o material chave começar com XMCKL e a mensagem for HELLO, opera-se do do seguinte modo:
+ 7 (H) 4 (E) 11 (L) 11 (L) 14 (O) mensagem 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) chave = 30 16 13 21 25 soma (mensagem + chave) = 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) soma ao módulo 26 e letras correspondentes
A mensagem cifrada a ser enviada a Bob é, assim, EQNVZ. Bob usa a mesma chave, fazendo o processo inverso para obter o purotexto. Aqui, a chave é subtraída da mensagem cifrada, usando outra vez a aritmética modular:
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) mensagem cifrada - 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) chave = -19 4 11 11 14 subtração (mensagem cifrada - chave) = 7 (H) 4 (E) 11 (L) 11 (L) 14 (O) subtração ao módulo 26 e mensagem decifrada
Por ser utilizada a aritmética modular, se o resultado de uma subtração é um número negativo, deve-se somar 26 a ele para transformá-lo em não-negativo. Desta forma, Bob recupera o texto original de Alice - a mensagem HELLO. Imediatamente após a transmissão, Alice e Bob devem ambos destruir a página em que se encontra a chave, impedindo sua reutilização e evitando um eventual ataque à cifra.
A KGB emite frequentemente sua cifra de uso único dos agentes impressas em folhas minúsculas “de papel do papel flash” - convertido quimicamente a nitrocelulose, que se queima quase imediatamente e não deixa nenhuma cinza. A cifra de uso único clássica de espionagem pode ser executada como um programa do software usando arquivos de dados como a entrada (plaintext) e a saída (mensagem cifrada) e o material chave (a sequência aleatória requerida). A operação de XOR é usada frequentemente para combinar o plaintext e os elementos chaves, e é especialmente atrativa em computadores desde que seja geralmente uma instrução de máquina nativa e é consequentemente muito rápida.
Entretanto, assegurar-se de que o material chave seja realmente aleatório, seja usado somente uma vez, nunca seja conhecido pela oposição, e que seja completamente destruído após o uso, realmente é muito difícil. As partes auxiliares de um software cifra de uso único apresentam desafios reais: fixar a manipulação/transmissão do plaintext, chaves verdadeiramente aleatórias, e um único uso de uma chave.
Tentativa de interceptação
Continuando no mesmo exemplo acima, suponhamos que Eve intercepte a mensagem cifrada de Alice: “EQNVZ.” Se Eve tivesse capacidade infinita de computação, descobriria que a chave “XMCKL” pode produzir o texto “HELLO”, mas descobriria também que a chave “TQURI” produziria a mensagem igualmente plausível “LATER” ("mais tarde"):
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) mensagem cifrada − 19 (T) 16 (Q) 20 (U) 17 (R) 8 (I) possível chave = −15 0 −7 4 17 mensagem cifrada = 11 (L) 0 (A) 19 (T) 4 (E) 17 (R) chave + mensagem (mod 26)
De fato, vemos que, ao tentar decifrar, é possível chegar a qualquer mensagem com o mesmo número dos caracteres fora da mensagem cifrada usando uma chave diferente e nenhuma informação na mensagem cifrada permitirá a Eve fazer uma escolha acertada entre as várias leituras possíveis da mensagem cifrada.
Segurança As cifras de uso único são “informações teoricamente seguras” já que as mensagens cifradas não fornecem nenhuma informação sobre a mensagem original a um criptanalista, exceto seu tamanho máximo possível.O tamanho real de um purotexto pode ser alterado pela adição de caracteres que servem apenas para aumentar o tamanho da mensagem cifrada e dificultar sua decifração. Esse processo, em inglês, é chamado de padding. Assim uma mensagem cifrada de 21 caracteres pode conter seja uma mensagem de 5 caracteres com alguma convenção de padding (por exemplo "-PADDING- HELLO -XYZ-") como uma mensagem real com 21 caracteres. Desse modo, um observador só consegue deduzir o número máximo possível de caracteres, mas não a extensão real da mensagem. Esta é uma noção muito forte de segurança primeiramente desenvolvida e provada matematicamente durante a 2ª Guerra Mundial por Claude Shannon, cujos resultados foram publicados no Jornal Técnico dos Laboratórios Bell em 1949. As cifras de uso único, se usadas corretamente são seguras mesmo se o adversário tiver capacidade computacional infinita.
A maioria de algoritmos convencionais de criptografia, seja simétrica ou assimétrica, usa padrões de teste complexos de substituição e transposição. Para o uso melhor destes atualmente, não se sabe se pode haver um procedimento criptanalítico que possa inverter (ou inverter parcialmente) estas transformações sem saber a chave usada durante a criptografia. Em termos práticos nenhum procedimento como esse é conhecido, embora já possam existir algoritmos de computador que poderiam fazê-lo em tempo “razoável”. Um dos problemas proeminentes centrais não-solucionados da informática carrega neste problema; se P=NP então seria possível que tais algoritmos pudessem ser encontrados, e se ele fossem procurados mais vigorosamente do que são hoje. Mesmo se não, os cripto sistemas atuais do indivíduo poderiam ainda ser quebrados.
Entretanto, a cifra de uso único não seria feita menos segura por uma prova que P=NP. A maioria dos observadores informados acreditam que P≠NP e, em qualquer o caso, muitos duvidam que esta pergunta tenha qualquer relevância prática ao projeto do algoritmo de criptanalise e criptografia. Aplicabilidade da cifra de uso único A segurança perfeita teórica da cifra de uso único aplica-se somente em um ajuste teoricamente perfeito; nenhuma execução do mundo-real de todo o cripto-sistema pode fornecer a segurança perfeita porque as considerações práticas introduzem vulnerabilidades potenciais. Estas considerações práticas da segurança e da conveniência significam que cifra de uso único é, na prática, pouco usada.