Criptografia

Criptografia

Criptografia (Do Grego kryptós, "escondido", e gráphein, "escrita") é o estudo dos princípios e técnicas pelas quais a informação pode ser transformada da sua forma original para outra ilegível, de forma que possa ser conhecida apenas por seu destinatário (detentor da "chave secreta"), o que a torna difícil de ser lida por alguém não autorizado. Assim sendo, só o receptor da mensagem pode ler a informação com facilidade.

Nos dias atuais, onde grande parte dos dados é digital, sendo representados por bits, o processo de encriptação é basicamente feito por algoritmos que fazem o embaralhamento dos bits desses dados a partir de uma determinada chave ou par de chaves, dependendo do sistema criptográfico escolhido

De facto, o estudo da criptografia cobre bem mais do que apenas cifragem e decifragem. É um ramo especializado da teoria da informação com muitas contribuições de outros campos da matemática e do conhecimento, incluindo autores como Maquiavel, Sun Tzu e Karl von Clausewitz. A criptografia moderna é basicamente formada pelo estudo dos algoritmos criptográficos que podem ser implementados em computadores.

O estudo das formas de esconder o significado de uma mensagem usando técnicas de cifragem tem sido acompanhado pelo estudo das formas de conseguir ler a mensagem quando não se é o destinatário; este campo de estudo é chamado criptoanálise.

Criptologia é o campo que engloba a Criptografia e a Criptoanálise.

As pessoas envolvidas neste trabalho, e na criptografia em geral, são chamados criptógrafos, criptólogos ou criptoanalistas, dependendo de suas funções específicas.

Termos relacionados à criptografia são Esteganografia, Código, Criptoanálise e Criptologia.

A Esteganografia é o estudo das técnicas de ocultação de mensagens dentro de outras, diferentemente da Criptografia, que a altera de forma a tornar seu significado original ininteligível. A Esteganografia não é considerada parte da Criptologia, apesar de muitas vezes ser estudada em contextos semelhantes e pelos mesmos pesquisadores.

Uma informação não-cifrada que é enviada de uma pessoa (ou organização) para outra é chamada de "texto claro" (plaintext). Cifragem é o processo de conversão de um texto claro para um código cifrado e decifragem é o processo contrário, de recuperar o texto original a partir de um texto cifrado.

Diffie e Hellman revolucionaram os sistemas de criptografia existentes até 1976, a partir do desenvolvimento de um sistema de criptografia de chave pública que foi aperfeiçoado por pesquisadores do MIT e deu origem ao algoritmo RSA.

Cifras

A cifra é um ou mais algoritmos que cifram e decifram um texto. A operação do algoritmo costuma ter como parâmetro uma chave. Tal parâmetro costuma ser secreto (conhecido somente pelos comunicantes).

Na linguagem não-técnica, um Código secreto é o mesmo que uma cifra. Porém, na linguagem especializada os dois conceitos são distintos. Um código funciona manipulando o significado, normalmente pela substituição simples de palavras ou frases. Uma cifra, ao contrário, trabalha na representação da mensagem (letras, grupos de letras ou, atualmente, bits).

Por exemplo, um código seria substituir a frase "Atacar imediatamente" por "Mickey Mouse". Uma cifra seria substituir essa frase por "sysvst ozrfosyszrmyr". No Dia D, por exemplo, as praias de desembarque não eram conhecidas pelo seu nome próprio, mas pelos seus códigos (Omaha, Juno, etc.).

Basicamente, códigos não envolvem chave criptográfica, apenas tabelas de substituição ou mecanismos semelhantes.

Objetivos

A criptografia tem quatro objetivos principais:

1. confidencialidade da mensagem: só o destinatário autorizado deve ser capaz de extrair o conteúdo da mensagem da sua forma cifrada. Além disso, a obtenção de informação sobre o conteúdo da mensagem (como uma distribuição estatística de certos caracteres) não deve ser possível, uma vez que, se o for, torna mais fácil a análise criptográfica.
2. integridade da mensagem: o destinatário deverá ser capaz de determinar se a mensagem foi alterada durante a transmissão.
3. autenticação do remetente: o destinatário deverá ser capaz de identificar o remetente e verificar que foi mesmo ele quem enviou a mensagem.
4. não-repúdio ou irretratabilidade do remetente: não deverá ser possível ao remetente negar o envio da mensagem.

Nem todos os sistemas ou algoritmos criptográficos são utilizados para atingir todos os objetivos listados acima. Normalmente, existem algoritmos específicos para cada uma uma destas funções. Mesmo em sistemas criptográficos bem concebidos, bem implementados e usados adequadamente, alguns dos objetivos acima não são práticos (ou mesmo desejáveis) em algumas circunstâncias. Por exemplo, o remetente de uma mensagem pode querer permanecer anônimo, ou o sistema pode destinar-se a um ambiente com recursos computacionais limitados, ou pode não interessar a confidencialidade.

Criptologia

Criptologia é a disciplina científica que reúne e estuda os conhecimentos (matemáticos, computacionais, psicológicos, filológicos, etc.) e técnicas necessários à criptoanálise (solução de criptogramas) e à criptografia (escrita codificada).

Inicialmente seu estudo era mais restrito a meios acadêmicos, sistemas de segurança bancários e inteligência militar devido a sua aplicação em mensagens sigilosas durante períodos de guerra, assuntos de estado e na espionagem mas, ultimamente, tem recebido especial atenção devido à generalização de operações comerciais por intermédio de meios eletrônicos, onde as transações devem ser processadas sigilosamente e de forma segura, de preferência com o menor custo possível, uma vez que mensagens criptografadas consomem muito tempo de processamento e banda de transmissão.

É possível se supor que a Criptografia tenha raízes históricas contemporâneas ao surgimento da escrita, mas os primeiros registros obtidos da utilização de técnicas criptográficas é com os egípicios cerca de 2000 a.C.. Entre os babilônios também existem exemplos de uma utilização complexa e ordenada, mas ainda não podia ser considerada uma ciência.

A utilização, por escribas hebreus, de uma cifra de substituição para a confecção do Livro de Jeremias por volta do séc VI a.C., é um exemplo de como já se utilizavam técnicas criptográficas de modo sistemático. César (séc. I a.C.) com uma cifra de transposição, simples mas eficiente à sua época (a cifra de César), marca a utilização que viria a ser, nos anos que se seguiram e até a nossa época, uma das mais importantes: o uso militar.

O registro mais antigo que se tem notícia a respeito de um trabalho publicado sobre criptoanálise vem dos árabes que eram matemáticos muito respeitados e desenvolveram estudos nessa área. Abu Yusuf Ya 'qub ibn Is-haq ibn as-Sabbah ibn 'omran ibn Ismail al-Kindi, conhecido como o filósofo dos árabes, foi autor de 290 livros sobre medicina, astronomia, matemática, linguística e música. Seu maior tratado, contudo, foi redescoberto apenas em 1987 no Arquivo Sulaimaniyyah Ottoman em Istambul, na Turquia, é intitulado "Um Manuscrito sobre Decifração de Mensagens Criptográficas" e versava sobre a análise de freqüências em textos encriptados.

No séc. XVIII Blaise de Vigenère estudou criptografia. É bastante conhecido depois de no século XIX, por erro, lhe ter sido atribuída a autoria da cifra de Vigenère.

Esteganogafria

O termo esteganografia vem do grego e significa "escrita coberta". É um ramo particular da criptologia que consiste, não em fazer com que uma mensagem seja ininteligível, mas em camuflá-la, mascarando a sua presença. Ao contrário da criptografia, que procura esconder a informação da mensagem, a esteganografia procura esconder a EXISTÊNCIA da mensagem.

Contrariamente à criptografia, que cifra as mensagens de modo a torná-las incompreensíveis, a esteganografia esconde as mensagens através de artifícios usando imagens ou um texto que tenha sentido, mas que sirvam apenas de suporte (como o alfabeto biliteral de Francis Bacon ou as famosas cartas de George Sand). A idéia é a mesma das grelhas de Cardano e do "barn code": mesclar a mensagem numa outra, onde apenas determinadas palavras devem ser lidas para descobrir o texto camuflado.

O primeiro uso confirmado da esteganografia está em "As Histórias" de Heródoto e remonta ao século V a.C.: um certo Hístio, querendo fazer contato secreto com seu superior, o tirano Aristágoras de Mileto, escolheu um escravo fiel, raspou sua cabeça e escreveu na careca a mensagem que queria enviar. Esperou que os cabelos crescessem e mandou o escravo ao encontro de Aristágoras com a instrução de que deveriam raspar seus cabelos.

Ainda nas "As Histórias" de Heródoto consta que, para informar os espartanos de um ataque iminente dos persas, o rei Demaratos utilizou um estratagema muito especial: pegou tabletes, retirou-lhes a cera, gravou na madeira a mensagem secreta e recobriu os tabletes novamente com cera. Deste modo, os tabletes, aparentemente virgens, não chamaram a atenção e chegaram até as mãos dos gregos. O problema foi que os gregos não imaginavam que a cera que tinham importado continha mais do que apenas cera. Foi Gorgo, a mulher de Leônidas, quem teve a idéia de raspar a cera e bisbilhotar o fundo das caixinhas que a transportava - leu a mensagem, avisou os gregos e garantiu a vitória sobre os persas.

Na China antiga também se usava a esteganografia. Escreviam-se mensagens sobre seda fina e o pequeno retalho era transformado numa bolinha que era recoberta por cera. Para transportar a mensagem, obrigavam um mensageiro engolir a bolinha, ir até o destinatário e entregá-la depois de… éééécccaaaa.

No século XVI, o cientista italiano Giovanni Porta descobriu como esconder uma mensagem num ovo cozido: escrevia sobre a casca do ovo cozido com uma tinta contendo uma onça de alume (± 29 g) diluída em cerca de meio litro de vinagre. A solução penetrava na casca e se depositava sobre a superfície branca do ovo. Depois, bastava o destinatário abrir o ovo para ler a mensagem.

O historiador da Grécia antiga, Enéias, o Tático, teve a idéia de enviar uma mensagem secreta fazendo minúsculos furos em certas letras de um texto qualquer. A sucessão destas letras marcadas fornecia o texto secreto. Dois mil anos mais tarde, remetentes ingleses empregaram o mesmo método, não para garantir o segredo de suas cartas, mas para evitar o pagamento de taxas de correio muito caras. Na realidade, antes da reforma do serviço postal ao redor de 1850, enviar uma carta custava cerca de um shilling para cada cem milhas de distância. Os jornais, no entanto, eram isentos. Graças a furinhos de agulha, os ingleses espertos enviavam suas mensagens gratuitamente transformando folhas de jornal em verdadeiras peneiras Este procedimento também foi utilizado pelos alemães durante a Primeira Guerra Mundial. Durante a Segunda Guerra, eles aperfeiçoaram o método marcando letras de jornais com tintas "invisíveis" ao invés de fazerem furos.

Os espiões alemães da Segunda Guerra utilizavam micropontos para fazer com que suas mensagens viajassem discretamente. Eram fotografias do tamanho de um ponto (.) que depois eram ampliadas para que a mensagem aparecesse claramente. Era uma espécie de microfilme colocado numa letra, num timbre, etc.

Em 1999, Catherine Taylor Clelland, Viviana Risca e Carter Bancroft publicaram na revista Nature "Hiding messages in DNA microdots" (escondendo mensagens em micropontos de DNA). Como qualquer material genético é formado por cadeias de quatro nucleotídeos (Adenina, Citosina, Guanina e Timina), podemos comparar estas cadeias a um alfabeto de quatro letras: A, C, G e T. Além disso, como os cientistas atualmente podem fabricar cadeias de DNA com um conjunto predeterminado de nucleotídeos, nada os impede de atribuir a um grupo de três nucleotídeos uma letra do alfabeto, um número ou sinais de pontuação (por exemplo, "A"=CGA, "B"=CCA, etc) e compor uma "mensagem genética". Para disfarçar as pistas, pode-se misturar algumas outras sequências aleatórias de nucleotídeos. Para complicar as coisas, o resultado é apenas visível ao microscópio eletrônico. Uma possível aplicação deste método esteganográfico seria, por exemplo, uma empresa que produz uma nova espécie de tomate e inclui sua marca de fábrica nas moléculas do tomate afim de evitar imitações.

Cifras

A cifra é um ou mais algoritmos que cifram e decifram um texto. A operação do algoritmo costuma ter como parâmetro uma chave. Tal parâmetro costuma ser secreto (conhecido somente pelos comunicantes).

Cifra de César

Em criptografia, a Cifra de César, também conhecida como cifra de troca ou ainda código de César, é uma das mais simples e conhecidas técnicas de encriptação. É um tipo de cifra de substituição em que cada letra do texto é substituída por outra, que se apresenta no alfabeto abaixo dela um número fixo de vezes. Por exemplo, com uma troca de 3 posições, A seria substituído por D, B viraria E e assim por diante. O nome do método teve origem numa técnica semelhante usada por Júlio César para se comunicar com os seus generais.

O sistema de encriptação de uma cifra de César serve frequentemente de base ou é incorporado como parte de esquemas mais complexos, como a cifra de Vigenère, e continua tendo aplicações modernas, como no sistema ROT13. Como todas as cifras de substituição monoalfabéticas, a cifra de César é facilmente decifrada e na prática não oferece essencialmente nenhuma segurança na comunicação.

cifra_cesar.png
A ação da Cifra de César é mover cada letra do alfabeto um número de vezes fixo abaixo no alfabeto. Este exemplo está com uma troca de 3, então o B do texto normal se torna E no texto cifrado.

Exemplo

A transformação pode ser representada alinhando-se dois alfabetos; o alfabeto cifrado é o alfabeto normal rotacionado à direita ou esquerda um número fixo de posições. Por exemplo, aqui está uma cifra de César usando uma rotação à esquerda de 3 posições (o parâmetro de troca, 3 neste caso, é usado como chave e deve ser transmitido por um canal seguro).

Normal: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cifrado: DEFGHIJKLMNOPQRSTUVWXYZABC

Para criptografar uma mensagem, simplesmente observe cada letra da mensagem na linha "Normal" e escreva a letra correspondente da linha "Cifrado". Para decriptografar, faça o contrário.

Normal: A LIGEIRA RAPOSA MARROM SALTOU SOBRE O CACHORRO CANSADO
Cifrado: D OLJHLUD UDSRVD PDUURP VDOWRX VREUH R FDFKRUUR FDQVDGR

A encriptação também pode ser representada usando aritmética modular, primeiro transformando as letras em números, de acordo com o esquema: A = 0, B = 1,…, Z=25. A encriptação de uma letra x por uma troca fixa n pode ser descrita matematicamente como,

ENC.png

A desencriptação é feita de modo similar,

dec.png

História

A cifra de César foi assim nomeada após Júlio César que, de acordo com Suetónio, a usava com uma troca de 3 posições para proteger mensagens de significado militar:

Se ele tinha qualquer coisa confidencial a dizer, escrevia cifrado, isto é, mudando a ordem das letras do alfabeto, e nenhuma palavra poderia ser compreendida. Se alguém quisesse decifrar a mensagem e entender seu significado, deveria substituir a quarta letra do alfabeto, a saber 'D', por 'A', e assim por diante com as outras.

Embora César tenha sido o primeiro a ser lembrado por usar este esquema, outras cifras de substituição já eram conhecidas e usadas anteriormente. O sobrinho de Júlio César, Augusto também usou a cifra, mas com troca de uma posição:

Sempre que escrevia cifrado, escrevia B para A, C para B, e o resto das letras com o mesmo princípio, usando AA para X.[2]

Existem evidências de que Júlio César usava sistemas mais complicados também, e um escritor, Aulus Gellius, refere-se a um tratado cifrado, entretanto perdido:

Existe até mesmo um tratado ingenuamente escrito pelo gramático Probus sobre o significado secreto das letras na composição das epístolas de César.[3]

É desconhecido o quão efetiva seria a cifra de César nesta época, mas é provável que tivesse uma razoável segurança, não apenas porque poucos dos inimigos de César eram alfabetizados, mas porque muitos menos seriam capazes de considerar a utilização de criptoanálise. Assumindo que um inimigo interceptasse a mensagem, não existiam registros naquela época de nenhuma técnica para a solução de uma simples cifra de substituição. Os registros sobreviventes mais recentes datam do século IX, no mundo Árabe, com a descoberta da análise de frequência.

No século XIX, a seção de anúncios pessoais nos jornais foi usada algumas vezes para trocar mensagens criptografadas usando esquemas simples de encriptação. Kahn (1967) descreve alguns exemplos de comunicação secreta entre amantes que usavam a cifra de César no The Times. Até mesmo em 1915 a cifra de César continuava em uso: o exército russo empregou-a em substituição às cifras mais complicadas que provaram serem muito difíceis para uso das tropas. No entanto, os criptoanalistas alemães e austríacos tiveram pouca dificuldade em descriptografar suas mensagens.

As Cifras de César podem ser encontradas actualmente em brinquedos para crianças como os anéis descodificadores. No algoritmo ROT13 é executado uma cifra de César com troca de 13 posições, um método simples de ofuscar o texto em alguns fóruns da Internet para obscurecer o texto (como a parte final de uma piada ou spoilers), mas não como método de encriptação).

A cifra de Vigenère usa uma cifra de César com uma troca diferente em cada posição do texto; o valor da troca é definido usando uma palavra-chave repetida. Se a palavra-chave 1) escolhida aleatoriamente e 2) for tão longa quanto a mensagem (não se repetindo), o sistema resultante seria teoricamente indecifrável - equivalente à cifra "one-time pad".

Decifrando

A cifra de César pode ser facilmente decifrada mesmo num cenário em que se tenha apenas o texto cifrado. Duas situações podem ser consideradas: 1) o interceptador conhece (ou adivinha) que algum tipo de cifra de substituição simples foi usada, mas não especificamente que é um código de César; e 2) o atacante sabe que a cifra de César foi usada, mas não sabe o valor de troca.

No primeiro caso, a cifra pode ser decifrada usando as mesmas técnicas usadas para resolver qualquer outro tipo de cifra de substituição simples, como a análise de frequência ou verificando os padrões de palavras. Enquanto resolve, é provável que o atacante rapidamente perceba a regularidade da solução e deduza que a cifra de César foi o algoritmo específico empregado.

No segundo exemplo, decifrar o esquema é ainda mais fácil. Sabendo que há apenas um número limitado de possibilidades (26 em português, se incluirmos as letras K, W e Y e desconsiderarmos o Ç e letras acentuadas), elas podem ser testadas por turno num ataque de força bruta. Uma forma de conseguir o enunciado é escrevendo o texto cifrado numa tabela com todas as possíveis trocas. O exemplo dado refere-se ao texto cifrado "ExeuyiEksve"; o texto decifrado corretamente é instantaneamente reconhecido apenas olhando a tabela, na troca de 4 posições. Outra forma de executar este método é escrever, para cada letra do texto cifrado, o alfabeto inteiro na vertical, alinhando então as colunas para formar o texto cifrado numa das linhas, e o texto decifrado deverá aparecer em uma das outras linhas resultantes.

Outra forma de usar a técnica de força bruta é comparando as frequências de distribuição das letras. Fazendo um gráfico com a frequência das letras do texto cifrado, e sabendo o que esperar daquelas letras na linguagem original, pode-se facilmente identificar o valor da troca verificando quantas rotações são necessárias para os gráficos ficarem coincidentes ou muito parecidos. Este método é conhecido como análise de frequência. Por exemplo, na língua portuguesa a frequência das letras A, E, (geralmente mais frequentes), e Y, W (tipicamente menos frequentes) são particulamente distintas. Os computadores podem auxiliar nesta análise, medindo (quantificando) em como a frequência atual combina com a distribuição esperada.

Para a maioria dos textos, muito provavelmente, só se encontrará um texto decifrado plausível, porém para textos muito pequenos, múltiplas opções são possíveis. Por exemplo, o texto cifrado qxq poderia, plausivelmente, ser decifrada para "ovo" ou "ele" (assumindo que o texto está em português).

Encriptações múltiplas não melhoram a segurança do código. Isto ocorre por que duas trocas, supondo, troca A e troca B, seriam equivalentes a uma troca de A + B. Em termos matemáticos, a encriptação sobre várias chaves formaria um grupo.

Cifra de Vigenère

A cifra de Vigenère é um método de encriptação que usa um série de diferentes cifras de César baseadas em letras de uma senha. Trata-se de uma versão simplificada de uma mais geral cifra de substituição polialfabética, inventada por Leone Battista Alberti cerca de 1465.

A invenção da cifra de Vigenère é erradamente atribuída a Blaise de Vigenère; encontra-se originalmente descrita por Giovan Batista Belaso no seu livro datado de 1553 com o título La cifra del. Sig. Giovan Batista Belaso.

Esta cifra é muito conhecida porque é fácil de perceber e de pôr em prática, parecendo, a quem tem pouca prática, que é inquebrável (indecifrável). Consequentemente, muitos programadores implementaram esquemas de encriptação nas suas aplicações que são no essencial cifras de Vigenère, e que são facilmente quebradas por qualquer criptanalista.

Descrição

Numa cifra de César, cada letra do alfabeto é deslocada da sua posição um número fixo de lugares; por exemplo, se tiver uma deslocação de 3, A torna-se D, B fica E, etc. A cifra de Vigenère consiste no uso de várias cifras de César em sequência, com diferentes valores de deslocamento ditados por uma "palavra-chave".

Para cifrar, é usada uma tabela de alfabetos que consiste no alfabeto escrito 26 vezes em diferentes linhas, cada um deslocado ciclicamente do anterior por uma posição. As 26 linhas correspondem às 26 possíveis cifras de César. Uma palavra é escolhida como "palavra-chave", e cada letra desta palavra vai indicar a linha a ser utilizada para cifrar ou decifrar uma letra da mensagem.

Por exemplo, supondo que se quer encriptar o texto:

ATACARBASESUL ("atacar base Sul")

Escolhendo a chave e repetindo-a até ter o comprimento do texto a cifrar, por exemplo, se a chave for"LIMAO":

LIMAOLIMAOLIM

A primeira letra do texto, A, é cifrada usando o alfabeto na linha L, que é a primeira letra da chave. Basta olhar para a letra na linha L e coluna A na grelha de Vigenère, e que é um L. Para a segunda letra do texto, ver a segunda letra da chave: linha I e coluna T , que é B, continuando sempre até obter:
Texto: ATACARBASESUL
Chave: LIMAOLIMAOLIM
Texto cifrado: LBMCOCJMSSDCX

A decriptação é feita inversamente.

Vigenere-square.png
A grelha de Vigenère, conhecido também por tabula recta, usado para encriptação e decriptação

A cifra de Vigenère pode ser vista algebricamente. Se as letras A–Z forem mapeadas nos números inteiros 0–25, e a adição módulo 26 for aplicada, a encriptação pode ser escrita:

enc2.png

e a decriptação,

dec2.png

O Exército Brasileiro, no seu curso de comunicações, utiliza esse método como uma das formas de encriptar uma mensagem.

Decifrando

O método de decriptação seguinte foi desenvolvido por Charles Babbage. A ideia motivadora da cifra de Vigenère é que as cifras polialfabéticas são mais difíceis de quebrar por análise de frequência, mas têm uma fraqueza se a chave é curta e constantemente repetida: como resultado, palavras comuns como "de" vão provavelmente aparecer encriptadas segundo as mesmas letras da chave, levando à descoberta de padrões repetidos no texto.

Vigenère inventou de fato, uma cifra mais robusta: a cifra de autochave, mas o nome de "cifra de Vigenère" está associado à cifra polialfabética. As duas cifras são habitualmente confundidas, e ambas chamadas "le chiffre indéchiffrable", ou seja, "cifra indecifrável". Durante mais de 300 anos esta cifra foi julgada inquebrável, mas Charles Babbage e Friedrich Kasiski, independentemente um do outro, encontraram um modo de a resolver em meados do século XIX.

Outros

Esses tópicos não estão no escopo deste site e foram citados apenas para motivar a pesquisa posterior:

  • Algoritmos Simétricos
  • Algoritmos Assimétricos
  • Assinatura Digital
  • Hash

Vídeos

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License