A criptografia é um mecanismo que visa proteger a informação criando um padrão de embaralhamento da mensagem no qual somente as pessoas permitidas podem acessar. Por essa razão, a criptografia se mostra essencial ao funcionamento do mundo moderno, pois reduz significativamente a chance dos dados serem lidos por uma pessoa que não possua a chave secreta. Sem isso, qualquer informação transmitida em uma rede pública, por exemplo, estaria comprometida.
O objetivo principal da criptografia é, portanto, mascarar a mensagem de modo que só o destinatário possa lê-la. Contudo assim como senhas, as criptografias podem ser descobertas e para que isso não aconteça deve-se usar chaves e modelos criptográficos mais difíceis de serem deduzidos. Ao mesmo tempo, deve-se considerar a integridade dos dados. Nada adianta ter uma mensagem bem criptografada se essa não pode ser facilmente descodificada. Assim, entende-se que toda criptografia deve tentar ser o mais confidencial possível sem que perca a sua integridade.
A ideia da criptografia é tão antiga que não se pode precisar a sua origem. O nome deriva do grego, com a junção de kryptós (escondido ou secreto) e graphein (escrita). Acredita-se que ela é contemporânea ao surgimento da escrita. A primeira cifra que se tem conhecimento foi criada pelos hebreus, a cifra de Atbash que esconde uma mensagem com uma simples substituição de caracteres conforme a ordem do alfabeto. A primeira letra, Aleph, era trocada pela última, Tav. A segunda ,Beth, pela penúltima, Shin. E assim por diante.
Há mais de 2500 anos. Espartanos usavam cítalas, bastões de madeira em tamanho definido. Uma tira de couro era enrolada de forma espiralada no bastão e a mensagem escrita. Com a tira desenrolada a mensagem não ficava explícita, podendo ser lida com uma cítala com dimensões semelhantes.
Seguindo o mesmo conceito da cifra havia a cifra de césar, com esse nome por ter sido usado pelo imperador romano Júlio César. A encriptação envolvia uma simples substituição de letras seguindo a ordem do alfabeto. Caso A virasse G, então B viraria H e assim por diante.
Na época esse tipo de criptografia podia ser considerada razoavelmente segura, pois a maioria da população era analfabeta e uma pequena transformação na mensagem ficaria razoavelmente indecifrável. No entanto, ainda há uso dessa forma de cifra em tempos atuais. Bernardo Provenzano, chefe da Cosa Nostra preso em 2006, cifrava as mensagens com uma relação simples em que A correspondia a 4, B a 5 e assim por diante.
As cifras de substituição, em que cada letra é trocada por um símbolo diferente, podem ser desvendadas com base na análise da frequência dos símbolos. Um exemplo desse tipo de desencriptação se encontra em um conto de Edgar Allan Poe, “O escaravelho de ouro”. É curioso notar que a criptografia também existe como um passatempo mental. Poe ficou conhecido por decodificar mensagens, pedindo para seus leitores mandarem códigos a serem desvendados. Também mandava desafios, uma cifra criada pelo escritor só foi quebrada cerca 150 anos depois.
Edgar Allan Poe Cryptographic Challenge
Em um texto certas letras são repetidas um maior número de vezes, no português as vogais A, E, O. Uma suspeita razoável é de que um símbolo com maior frequência no código seja uma dessas letras. Símbolos repetidos seguidamente podem corresponder a 'rr' ou 'ss'. Palavras pequenas são provavelmente preposições como 'de', 'até', 'em', 'por'...
Em 1553, Giovan Battista Bellaso criou uma cifra hoje conhecida como Cifra de Vigenère. Essa cifra usa uma tabela chamada de tabula recta.
Segue o princípio da cifra de césar, mas agora cada letra é codificada por uma forma diferente, seguindo o padrão de uma palavra chave. Por exemplo, se quisermos codificar a mensagem 'COMPREANCHOVASPARAOJANTAR' com a chave 'ALCAPARRAS' , temos:
COMPREANCHOVASPARAOJANTAR
ALCAPARRASALCAPARRASALCAP
Na linha A, coluna C: C
Na linha L, coluna O: Z
Na linha C, coluna M: O
Na linha A, coluna P: P
Na linha P, coluna R: G
e assim por diante
O código formado é: CZOPGERECZOGCSEAIROBAYVAG
Sabendo a chave, a decodificação segue o caminho inverso:
CZOPGERECZOGCSEAIROBAYVAG
ALCAPARRASALCAPARRASALCAP
Na linha A, temos o C na coluna C: C
Na linha L, temos o Z na coluna O: O
Na linha C, temos o O na coluna M: M
E assim por diante...
O receptor então recupera a mensagem.
Um método criado por um major do exército prusso, Friedrich Kasiski, decifrava códigos grandes considerando o uso chave bem menor ao texto cifrado, em que a possibilidade de palavras pequenas serem representadas da mesma forma é bem razoável.
Um estudo mais detalhado sobre a quebra desse método pode ser encontrado em
Cracking the Vigenère Cipher
Os modelos criptográficos discutidos até agora são classificadas como simétricos, uma chave é compartilhada pelo emissor e pelo receptor. O algoritmo de codificação usa a chave que contém as instruções da forma que a mensagem será criptografada. O resultado é transmitido para o receptor que aplica os dados em um algoritmo que decodifica a mensagem de acordo com a chave compartilhada.
A criptografia simétrica é muito utilizada hoje em dia. Podemos citar os principais algoritmos usados: Twofish, Serpent, CAST5, RC6, TDES e AES(Rijndael).
Antes muito restrita no meio militar, a criptografia começou a ser aplicada para fins comerciais. Em 1974 a IBM desenvolveu o Lucifer, mais tarde alterado pela NSA (National Security Agency) e adotado como padrão o DES (Data Encryption Standart). Adotando uma chave de 56 bits, considerada muito fraca atualmente, o padrão DES só foi abandonada em 2002 sendo superado pelo AES ( Advanced Encryption System), com um algoritmo escolhido por meio de uma competição pública. O DES deu origem ao TDES (Triple DES ou 3DES), que consiste em aplicar o algoritmo três vezes seguidas com duas ou três chaves diferentes, o tamanho total da chave então pode ser de 168 bits (3*56) ou de 112 bits (2*56). O TDES é usado para encriptar informações nos programas Microsoft OneNote, Microsoft Outlook 2007 e em algumas outras aplicações.
Em 1997 o NIST (National Institute of Standards and Technology) anuncionou uma competição para escolher o AES. Todo algoritmo que se submeteu como candidato foi colocado em público e com direitos autorais livres. As especificações eram de que a criptografia deveria ser simétrica, com suporte a blocos de 128 bits, e chaves de 128, 192 e 256 bits. 15 algoritmos foram selecionados na primeira fase, dentre os quais 5 passaram para a fase final de seleção: MARS, RC6, Rijndael, Serpent e Twofish. Após várias avaliações da comunidade criptografica internacional o escolhido foi o Rijndael, criado por dois belgas, Vincent Rijmen e Joan Daemen.
A entrada é dividida em blocos de 64 bits
A chave de entrada com 56 bits [64 bits mas com bits em posições múltiplas de 8 descartados (8,16,24,32,40,48,56,64)]
A entrada de 64 bits é dividida em L e R, dois blocos de 32 bits (os bits da esquerda e os bits da direita)
Pegando como exemplo:
Entrada = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Bloco L = 0000 0001 0010 0011 0100 0101 0110 0111
Bloco R = 1000 1001 1010 1011 1100 1101 1110 1111
Chave = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
Os bits em negrito não são usados.
São geradas 16 sub-chaves por meio da permutação de 48 dos 56 bits da chave
Gerando as sub-chaves:
Uma matriz chamada de PC-1 é utilizada para permutar a chave inicial
Seguindo essa matriz, o primeiro bit da primeira sub-chave é o bit na posição 57 da chave geradora (de 1 a 64 excluindo os múltiplos de 8)
Chave = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001 [64 bits]
Chave' = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111 [56 bits]
Chave' é dividida em dois blocos C e D de 28 bits
C(0) são os primeiros 28 bits: 1111000 0110011 0010101 0101111
D(0) os últimos 28 bits: 0101010 1011001 1001111 0001111
C(0) e D(0) são usados para gerar 16 blocos C(N) e 16 blocos D(N) de acordo com a tabela:
N | Deslocamento de bits à esquerda em relação à N-1 |
1 | 1 |
2 | 1 |
3 | 2 |
4 | 2 |
5 | 2 |
6 | 2 |
7 | 2 |
8 | 2 |
9 | 1 |
10 | 2 |
11 | 2 |
12 | 2 |
13 | 2 |
14 | 2 |
15 | 2 |
16 | 1 |
Uma animação que ilustra os processos desse algoritmo pode ser encontrado aqui
The Rijndael Animation
Os dados são representados em uma matriz 4x4 em que cada célula representa um byte, dois dígitos em hexadecimal.
Para uma chave de 128 bits os dados são quebrados em blocos de 128 bits.
A chave gera 10 sub-chaves de 128 bits. Esse passo é explicado posteriormente na animação.
O resultado de uma operação Chave XOR Dados é a entrada para um loop de 9 iterações em que ocorre o seguinte:
1-Há uma transformação por meio de um S-box, saem 128 bits
2-É feito um deslocamento de bits à esquerda em cada linha da matriz
3-O processo de MixColumns não é simples e uma explicação desse processo pode ser encontrado em AES' Galois field
4-AddRoundKey é simplesmente uma operação de XOR entre as colunas. A primeira coluna da entrada XOR primeira coluna da sub-chave resulta na primeira coluna da saída.
Esse loop é repetido 9 vezes, sendo que em cada loop a sub-chave é trocada pela seguinte. No último loop o processo de MixColumns não ocorre.
Um aplicativo para encriptar/desencriptar com o algoritmo de Rijndael pode ser encontrado em
Rijndael Inspector
Pacotes de criptografia com AES:
Python: http://sourceforge.net/projects/cryptkit/
C/C++: http://www.efgh.com/software/rijndael.htm
Java: http://java.sun.com/developer/technicalArticles/Security/AES/AES_v1.html
Na criptografia simétrica a chave é compartilhada pelo emissor e pelo receptor. Um problema inevitável é estabelecer um canal seguro para definir a chave a ser usada. Muito dos ataques a sistemas de criptografia são baseados no sistema que guarda ou transmite a chave secreta e não no algoritmo em si. Um avanço significativo nessa questão foi resolvido com a proposta de uma criptografia assimétrica, em que a chave usada para encriptação é diferente da usada na desencriptação, com a chave usada no processo de codificação podendo ser posta a público. A chave privada, que deve ser guardada de modo seguro, é a que decodifica a mensagem. Essa ideia foi proposta em 1976 por Whitfield Diffie e Martin Hellman, dois matemáticos da Universidade de Stanford. Foi um trabalho pioneiro também por quebrar o monopólio de agências governamentais sobre a criptografia. Um sistema como esse havia sido proposto por algumas agências, mas devido à natureza do assunto foi classificada como confidencial.
Um modelo prático para a criptografia de chave pública só foi possível com o algoritmo RSA, criado por Ron Rivest, Adi Shamir e Leonard Adleman. O RSA se baseia no difícil problema de fatorar grandes números e na matemática modular. Para convencer empresas e agências a adotarem esse modelo de criptografia, o trio citava Gauss, que não fez nenhum progresso em descobrir uma forma fácil de fatoração. Se um dos maiores gênios da matemática não avançou nesse problema, então a criptografia estava segura. Um desafio também foi proposto, uma mensagem criptografada com um número de 129 algarismos foi publicada na Scientific American. Estimavam que o tempo necessário para quebrar esse código seria de milhares de anos. O código foi decifrado 17 anos depois de lançado, tempo suficiente para mostrar que a segurança do RSA era extremamente alta. A RSA Security, empresa fundada pelos criadores do RSA, recomenda a criptografia com números de 230 algarismos. Para informações em que a segurança deve ser feita para um longo prazo são recomendados números com mais de 600 algarismos.
Uma outra forma de criptografia se baseia no problema do logaritmo discreto nas curvas elípticas. Em 1985 Neal Koblitz e Victor Miller perceberam, independentemente, da possibilidade de usar esse problema para codificar dados. A vantagem em relação ao RSA é de que na criptografia de curvas elípticas não é necessário fazer operações com chaves numéricas tão grandes. Para o mesmo nível de segurança do RSA com uma chave de 2048 bits, usa-se uma chave de 160 bits.
Um trabalho sobre as curvas elípticas e a criptografia assimétrica pode ser encontrado em
http://www.gta.ufrj.br/grad/06_2/renan/ecc_renan.html
Um problema que corre com essa criptografia é de que os cálculos envolvidos podem ser pesados demais na encriptação de dados grandes. Portanto o que geralmente há na prática é um sistema híbrido de criptografia simétrica com assimétrica. Este ficando incumbido de codificar a chave a ser usada na criptografia simétrica.
A matemática modular trabalha com uma ideia desenvolvida a partir da calculadora-relógio de Gauss. Imaginando um relógio de 12 horas, representamos 13 horas como 1 hora.
Isso seria 13 = 1 (mod 12), 38 = 2 (mod 12)
Um número a1 representado em um módulo N é o resto da divisão entre a1 e N.
a1%N=b1
Para a1 = b1 (mod N), a2 = b2 (mod N)
Temos:
(a1 + a2) = (b1 + b2) (mod N)
(a1 - a2) = (b1 – b2) (mod N)
(a1 * a2) = (b1 * b2) (mod N)
O pequeno teorema de Fermat assegura que sendo N um número primo p
a1^p=a1 (mod p)
Uma generalização desse teorema desenvolvida por Euler atesta que se tivermos N como o produto de dois números primos p e q
a1^ [(p-1)*(q-1)+1] = a1 (mod p*q)
Essa é a equação que rege a criptografia RSA
Para encriptar dados, pegamos sequências menores que o valor N=p*q. Essa sequência então é elevada a um número primo E (não divisor de (p-1)*(q-1)) e calcula-se o valor em módulo N. Esse valor é a mensagem cifrada.
A chave pública pode ser considerada o conjunto de números N e E.
Para desencriptar a mensagem elevamos o valor a um número D, tal que D*E = 1 (mod (p-1)*(q-1))
Esse valor em módulo N será igual a sequência original.
A chave privada é composta pelo número D e N.
A desencriptação é feita pegando a mensagem cifrada, elevando a D e pegando o resultado em módulo N.
Para N=p*q muito grande, não há um algoritmo (não-quântico) que fatore N de forma rápida. Essa é a base da segurança nessa criptografia.
Podemos aplicar a criptografia vista até agora com o pacote OpenSSL que pode ser encontrado no linux.
As opções de encriptação simétrica que podemos usar são:
Aplicando o aes-128-cbc:
Rodamos os seguintes comandos no terminal para encriptar um arquivo teste.txt
Para desencriptar:
Podemos também usar uma criptografia assimétrica:
Aplicamos o RSA:
Podemos gerar uma chave de 1024 bits com o comando
Esse arquivo contém tanto a chave privada quanto a pública. Para retirar a chave pública desse arquivo temos
Encriptando com o uso da chave pública:
Desencriptando com o uso da chave privada: