História da Criptografia

Aldo Catella Abrahão Amadeu Almeida Coco

Bernardo Maia Rodrigues Maisa Horta Canguçu de Souza

História das Ciências Exatas

• Criptografia (kriptós = escondido, oculto; grápho =

grafia) : é a arte ou ciência de escrever em cifra ou em

códigos, de forma a permitir que somente o destinatário

a decifre e compreenda.

• A criptografia transforma textos originais, chamados

texto original (plaintext) ou texto claro (cleartext), em

uma informação transformada, chamada texto cifrado

(ciphertext), texto código (codetext) ou simplesmente

cifra (cipher), que usualmente tem a apararência de um

texto randômico ilegível.

Introdução

• Esteganografia é o estudo e uso das técnicas

para ocultar a existência de uma mensagem

dentro de outra.

• Um exemplo de esteganografia é a brincadeira

que muitas crianças fazem utilizando limões

para decifrar algo escrito em um papel.

• Enquanto a criptografia oculta o significado da

mensagem a esteganografia oculta a existência da linguagem

Criptografia x Esteganografia

• Criptografia Clássica: se iniciou no Egito Antigo e vai até a Cifra de César

• Criptografia médieval: Se inicia com os arabes com Al-Kandi, com sua análise de frequencia e vai até o início do século XIX com a Criptografia Japonesa

• Criptografia moderna: Se inicia com a Cifra de Babbage e termina no embate entre Enigma e Colossus durante a segunda guerra

• Criptografia Contemporânea: Utilização de computadores para criptográfia, e metodos como o RSA

Divisões da história da criptografia

• 3500 A.C: Início da escrita • 100 A.C: Cifra de César • 800 D.C: Criptanálise e análise de frequencia de

Qur’an • 1553 D.C: Cifra de Vigenère • 1918 D.C: Invenção da Enigma • 1943 D.C: Criação do Colossus deciframento da

Enigma • 1977 D.C: Invenção do RSA

Datas Marcantes para criptografia

• Iniciou-se no Egito há 4500 anos de forma bem rustica

• Utilizada de forma mais séria pelos povos da Mesopotamia para esconder informações há 3000 anos

• Os hebreus há 2500 anos utilizaram pela primeira vez a substituição de Cifras

• Por fim os Espartanos utilizaram a Scytale e os Atenienses a técnica batizada de Quadrado de Políbio

Criptografia Classica

Scytale

• Técnica de criptografia mais conhecida da antiguidade

• Consiste em uma simples técnica de criptografia na qual cada letra é substituída por outra, que se apresenta no alfabeto abaixo dela um número fixo de vezes

• Por exemplo, com uma troca de três posições, A seria substituído por D, B se tornaria E, e assim por diante.

• O nome do método é em homenagem a César, que o usou para se comunicar com os seus generais.

Cifra de César

Exemplo da Criptografia de César

• Aplicar uma função modular nas letras do alfabeto

• X = valor da letra

• Y = valor depois do deslocamento

• Ex: (x+3) = y mod 26

• Exemplo:

• Normal: a ligeira raposa marrom saltou sobre o cachorro

cansado

• Cifrado: D OLJHLUD UDSRVD PDUURP VDOWRX

VREUH R FDFKRUUR FDQVDGR

Funcionamento da Cifra de César

• Criptográfia semelhante a cifra de César • Ocorre por motivações religiosas • Inclui algumas cifras multi-alfabeticas, de modo

rustico • Ahmad al-Qalqashandi(1355-1418) escreve a

enciclopédia de 14 volumes chamada ”Subh al-a 'sha” na qual um dos volumes se dedica a criptologia.

Criptográfia Árabe

Criptografia Arabe

• Na Europa medieval a Cifra de César continua sendo utilizada

• Durante a renascença a criptográfia se torna difundida na Itália devido a rivalidade das diversas cidades-estados presentes no país

• Porém por serem parecidas as mensagens eram constantemente quebradas

• Em 1553 surge a Cifra de Vigenére

Criptográfia Medieval

• Como dito anteriormente várias das mensagens trocadas eram quebradas devido a facilidade de se entender a cifra de César

• Por volta de 1460 o italiano Leon Battista Alberti sugere em um ensaio a utilização de dois alfabetos cifrados, usados alternadamente, porém ele não conseguiu desenvolver sua ideia transformando-a num sistema completo de cifragem

• Em 1553 Blaise de Vigenère(1523-1596) aperfeiçou a ideia orginal através do conhecimento de Alberti, Johannes Trithemius (1462 – 1516) e Giovanni Porta (1541 - 1615), mesclando as ideias dos 3 para formar uma nova cifra, coerente e poderosa

• A cifra ficou conhecida como cifra de Vigenère em homenagem ao homem que a desenvolveu em sua forma final.

Cifra de Vigenère

• A cifra de Vigenère consiste em até 26 alfabetos distintos para criar a mensagem cifrada.

• O primeiro passo é montar o chamado quadrado de Vigenère, um alfabeto normal seguido de 26 alfabetos cifrados, cada um deslocando uma letra em relação ao alfabeto anterior. Em resumo, o remetente da mensagem pode, por exemplo, cifrar a primeira letra de acordo com a linha 5, a segunda de acordo com a linha 14 e a terceira de acordo com a linha 21, e assim por diante.

• A cifra polialfabética de Vigenère era considerada indecifrável e tornou-se conhecida pela expressão francesa Le chiffre indéchiffable.

Cifra de Vigenère

Tabela da Cifra de Vigenère

• Após Vigenére, não houve avanços significativos na criptografia durante 300 anos

• Por volta de 1850, Charles Babbage cria o primeiro sistema matemático de quebra da Cifra de Vigenére, durante a guerra da Criméia

• Na mesma década Edgar Allan Poe utiliza-se de metodos sistemáticos para o mesmo fim

• Nesta epoca o método de Babbage se torna um segredo do estado Inglês, que detinha 25% das terras do planeta.

Criptografia no Século XIX

• Ainda durante a Primeira Guerra os métodos de Babbage eram segredo do estado inglês

• Porém foi com os métodos de Poe que os inglês quebraram as cifras alemãs durante a primeira guerra.

• Ironicamente foi por causa dessa quebra de mensagens que a espiã Mata Hari foi fuzilada pela Triplice entente

• Ainda durante a primeira guerra a marinha inglesa quebrou os códigos navais alemães através de cabos de telegrafos que ligavam o embaixador Alemão no México e a Alemanha

Criptografia na Primeira Guerra

• Com seus códigos todos descobertos durante a primeira guerra os alemães precisaram reinventar a criptografia

• Com isso foi inventada a maquina Enigma, amplamente utilizada na segunda guerra

Criptografia entre Guerras

• Desenvolvida por Arthur Scherbius em 1918, a Enigma

levantou um grande interesse por parte da marinha de guerra

alemã em 1926, quando passou a ser usado como seu

principal meio de comunicação e ficaram conhecidas como

Funkschlüssel C.

• O exército elaborou sua própria versão, em 1928, a Enigma G,

e passou a ser usado por todo o exército alemão, tendo suas

chaves trocadas mensalmente.

• A decodificação de uma mensagem criptografada pela Enigma era considerada impossível na época (já que para tal, seria necessário uma alta força bruta computacional).

Enigma

Enigma

• A engima é uma combinação de sistemas

mecânicos e elétricos.

• Seu mecanismo consiste em um teclado, em

conjunto com discos rotativos dispostos em filas,

e um mecânismo de avanço que vária entre as

diversas versões da máquina.

• O movimento continuo dos rotores provoca

diferentes combinações na criptografia

Funcionamento da Enigma

• Ao digitar uma tecla o circuito completa-se e a corrente eletrica flui pelos

componentes. Por fm se codifica a letra escrita no teclado. Por exemplo, ao codificar

a mensagem RET..., o operador primeiro tecla em R, acende-se uma luz por

exemplo, T - que será a primeira letra da cifra resultante. O operador prossegue

teclando E, acende-se outra luz, e assim sucessivamente.

• Os rotores são o coração da Engima. Com aproximadamente 10 cm de diâmetro,

cada um é um disco feito de borracha dura ou baquelite com uma série de pinos de

metal salientes dispostos em círculo num dos lados; no outro lado situa-se uma série

de contactos eléctricos.

• Os pinos e os contactos eléctricos representam o alfabeto — tipicamente as 26 letras

de A até Z.

• Apenas por si próprio, um rotor não permite fazer mais que uma criptografia simples:

uma cifra de substituição. Por exemplo, o pino correspondente à letra E pode ser

ligado ao contacto para a letra T no lado oposto. A complexidade resulta do uso de

vários rotores em sequência (habitualmente três ou mais) e no movimento regular

dos rotores. Isto leva a uma criptografia muito mais complexa e robusta.

Ciframento na Enigma

Rotores

• A Colossus foi uma máquina eletronica utilizada pelos ingles para ler mensagens criptografadas pelos alemães na segunda guerra mundial. É considerado o primeiro computador programavel da historia.

• Foi criada por Tommy Flowers e Alan Turing para solucionar o problema proposto por Max Newman.

• A colossous quebrava mensagens alemãs em uma velocidade bastante rapida, além disso ela era uma máquina que criava códigos criptograficos ingles, e até mesmo alemães

• Seu projeto foi mantido em segredo até a década de 1970.

Colossus

Colossus

• Até 1942 um dos grandes trunfos da Alemanha era o fato de nenhum país aliado ter conseguido quebrar seus códigos de criptografia

• Porém nesse ano uma das máquinas foi roubada pelos ingleses, que mantiveram isso como segredo de estado

• Com a engima em maõs, os ingles desenvolveram a Colossus, que enfim conseguiu quebrar os códigos gerados pela enigma

• Se não bastasse isso, o projeto de Alan Turing foi ambicioso ao ponto de gerar cifras da enigma para enganar os alemães

Colossus x Enigma

• Apesar do principal foco ter sido o embate de Colossus x Enigma houve outras formas de criptografia na época

• Outra batalha de criptografica marcante foi a de Japão x Estados Unidos, na qual a criptografia japonesa utilizada desde do século XVI foi quebrada pela marinha americana.

• Porém ironicamente foi poucas horas antes do ataque a Pearl Harbor

Criptografia na Segunda Guerra

• Criptografia mais acessível (não só grandes empresas e governo)

• Até década de 70: pouca divulgação • 1975: DES (Data Encryption Standart) – IBM/NIST • Interesse público geral/acadêmico • 1976: Whitfield Diffie e Martin Hellman publicam

“New Directions of Criptography”

Criptografia Moderna

• Mesma chave criptografa e descriptografa

• Exemplos: – DES, Triple DES – IDEA – RC2, RC4, RC5 (RSA)

Criptografia Simétrica

• Nova abordagem • Par de chaves matematicamente relacionadas • Um par de chaves por usuário • Chave privada

– Mantida em segredo

• Chave pública – Publicada

• É possível gerar chave pública a partir da primária • Não é possível gerar chave privada a partir da pública

Criptografia Assimétrica

• Texto criptografado por uma chave é descriptografado por outra

Criptografia Assimétrica

• Metodo de criptografia através de números primos • O RSA se dá pelo número de chave n, no qual n = p.q

e p e q são números primos • Normalmente n chega a ter mais de 100 digitos

RSA

RSA - Funcionamento

• Função Hash: Injetora • Apenas um sentido, mapeia valores de um grande

domínio em um pequeno domínio • Modificação mínima na entrada modifica saída • Fácil de computar mas difícil reverter

Autenticação

• Criptografia Assimétrica – Correio eletrônico – Web (SSL, Secure HTTP) – VPN’s – SSH – Proteção da chave privada

• Hardware removível • Guardar criptografada

• Função Hash – Autenticação – Message Digest – Senhas, sistemas operacionais

Aplicações práticas

Aplicações práticas

Aplicações práticas

• Dificuldade: Problema de fatoração de inteiros – Encontrar divisor não trivial de um número composto – Caso mais difícil (atualmente): fatores são dois primos,

eleitos ao acaso, de tamanho aproximado

• Colisão – Dois conjuntos de dados com o mesmo hash – Extremamente difícil de ser computado

Quebrando a Criptografia

• Ataques – Força Bruta – Dicionário – Decomposição (Primos conhecidos, facilmente

computáveis etc) – Contagem de Frequencia – Man-in-the Middle – Replay Attack – Rainbow Tables

Quebrando a Criptografia

• Ataque contra DES – Computação distribuída – Voluntários – 22 Horas e 15 Minutos – Chave 56 bits (pequena)

Ataques Famosos: DES

• CSS: Content Scramble System – 1996 – 40 bits – Proteção de conteúdo de DVD’s

• Chave CSS: licenciadas pela DVD Copy Control Association – Incorporadas nos DVD’s, drives e players – Módulo para descriptografia

• Evitar cópias bit-a-bit da mídia • Obrigar empresas a criarem produtos “compatíveis”:

obter e pagar licenciamento

Ataques Famosos: CSS

• Outubro 2009: Jon Lech Johansen e 2 colaboradores anônimos quebraram o CSS

• “DVD” Jon – Norueguês – 15 anos – Motivação: Assistir DVD’s no Linux

• DeCSS • Engenharia reversa • Chave máxima de 40 bits (regulamentado pelo

governo dos Estados Unidos)

Ataques Famosos: CSS

• Código fonte: http://torch.cs.dal.ca/~hannon/decss.c • MPAA, governo dos EUA: Proibição de distribuição

do código • Movimento “42 Ways to distribute DeCSS”

Ataques Famosos: CSS

• 25th Chaos Communication Congress (2008) • “MD5 considered harmful today: Creating a rogue

CA certificate” • Colisão MD5, autoridade certificadora falsa

Ataques Famosos: Colisão Certificados MD5

• PS3 Farm (computação distribuída) • Alexander Sotirov, Marc Stevens, Jacob Appelbaum,

Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger

Ataques Famosos: Colisão Certificados MD5

Ataques Famosos: Colisão Certificados MD5

Ataques Famosos: Colisão Certificados MD5

• 26th Chaos Communication Congress (2009) • GSM: Sistema de telefonia mais popular existente • Criptografia: A5/1 • Pesquisadores: Karsten Nohl e Chris Paget • Computação: Rainbow Tables

– Time-Memory Trade-off – Recuperar Message Digest a partir do Hash

• Descriptografia em tempo real • Live demo cancelada: intimação/processo

Ataques Famosos: GSM (Telefonia)

Ataques Famosos: GSM (Telefonia)

• WEP: Wired Equivalent Privacy • IEE 802.11 • Sinais de rádio, Wi-Fi • Pacotes criptografados com RC4 • Vulnerabilidades • IV/Vetor de iniciação (24 bits) + Chave Secreta (40 ou

104 bits) • Chave Secreta é a mesma para todos usuários • Captura de Pacotes e IV`s: WEP quebrado em

menos de 10 minutos

Ataques Famosos: WEP

Ataques Famosos