Criptografia Numaboa
Uma nova linguagem matemática
Sex 30 Nov 2007 20:13 |
- Detalhes
- Categoria: Curso de Criptologia
- Atualização: Quarta, 17 Junho 2009 19:43
- Autor: vovó Vicki
- Acessos: 12509
Quando comecei a me interessar pela criptologia, principalmente pela criptoanálise (criptoanalistas são os hackers!), percebi que não seria possível ignorar a matemática. Era uma situação muito incômoda: a curiosidade era enorme mas, como acontece com a maioria das pessoas, a ciência dos números me intimidava. A pergunta que me fiz foi a seguinte: deveria desistir logo de cara ou enfrentar o medo? Foi daí que descobri que a matemática é apenas um idioma que pode ser aprendido como outro qualquer
O modelo da criptologia
O objetivo fundamental da criptografia é permitir que duas pessoas, geralmente chamadas de Alice e Bob, possam se comunicar através de um canal inseguro de modo que um "inimigo", o Oscar, não possa entender o que está sendo transmitido. Este canal pode ser uma linha telefônica, uma rede de computadores ou outro meio de comunicação qualquer. Estes são os personagens desta história.
A informação que Alice quer enviar para o Bob, chamada de texto claro ou texto aberto, pode ser um recado em português (ou qualquer outra língua), dados numéricos, um arquivo de som, etc e tal - a estrutura da informação não importa. Alice cifra o texto claro usando uma chave predeterminada e envia o texto cifrado resultante através de um canal inseguro... inseguro porque o Oscar pode bisbilhotar este canal e interceptar a mensagem da Alice.
Acontece que o espião Oscar não entende chongas da mensagem interceptada porque não é capaz de decifrá-la. Por outro lado, o Bob, que conhece a chave, pode decifrar o texto e recontruir a mensagem original.
Este é o modelo clássico da criptologia: Alice e Bob fazendo criptografia e Oscar tentando fazer criptoanálise.
Um pouco da linguagem matemática
Para começar a aprender o "idioma" matemático, aqui está o primeiro termo do nosso "dicionário", o C:
- Conjunto é uma coleção de coisas. Por exemplo, uma coleção de CDs é um conjunto, uma coleção de carros miniatura é um conjunto e assim por diante.
Csignifica "pertence". Se chamarmos o conjunto de carros miniatura de M e esta coleção tiver uma Ferrari vermelha, então podemos escrever que "F pertence a M" ou FCM.
O modelo matemático da criptologia
Um criptossistema é um quíntuplo, ou seja, é um sistema onde cinco "entidades" precisam ser consideradas (A, C, K, E, D):
- O conjunto finito de mensagens claras é chamado de A (textos Abertos).
- O conjunto finito de mensagens cifradas é chamado de C.
- K, também conhecido como espaço das chaves, é o conjunto das chaves possíveis e
k é uma das chaves do conjunto. - Uma regra de cifragem será chamada de ek, onde e vem de encriptação e k da chave usada. Portanto, k
CK e, para cada chave pertencente ao conjunto de chaves, haverá uma encriptação diferente que pertence ao conjunto ekCE. - Para cada regra de cifragem haverá uma regra de decifração d e k será a chave usada. As regras de decifração pertencem ao conjunto D, ou seja, dk
CD.
DICIONÁRIO | |
Pertence a | |
Conjunto finito de mensagens claras A | |
Conjunto finito de mensagens cifradas C | |
Conjunto das chaves (espaço das chaves) K | |
Uma chave (k) do espaço das chaves (K), ou seja, k | |
Regra de cifragem ek que pertence ao conjunto de regras de cifragem E, ou seja, ek | |
Regra de decifração dk que pertence ao conjunto de regras de decifração D, ou seja, dk |
O dicionário vai nos ajudar a entender a seguinte "frase" matemática:
Para cada C existe uma C E com uma C D correspondente.
Trocando imagens e símbolos por palavras: Para cada CHAVE pertencente ao CONJUNTO DE CHAVES existe uma REGRA DE CIFRAGEM que pertence ao CONJUNTO DE REGRAS DE CIFRAGEM que tem uma REGRA DE DECIFRAÇÃO correspondente que pertence ao CONJUNTO DE REGRAS DE DECIFRAÇÃO.
ek e dk são funções. A função de cifragem pode ser usada num texto claro x e isto é "dito" matematicamente como ek(x). O resultado é que o texto claro é transformado em texto cifrado, ou seja, ek: A -> C. Com a função de decifração ocorre o contrário, o que pode ser dito como dk: C -> A.
A função de cifragem ek(x) transforma o texto claro x num texto cifrado, portanto, podemos chamar ek(x) de texto cifrado. Se aplicarmos a função de decifração correspondente a este texto cifrado, obtemos novamente o texto claro. Veja como podemos dizer isto de forma resumida na linguagem matemática:
dk(ek(x)) = x para qualquer texto claro x C A
Já estamos começando a ganhar tempo escrevendo as coisas "matematicamente"
Noção de Protocolo
Para Alice e Bob se comunicarem usando um determinado criptossistema será preciso estabelecer certas regras de comunicação que os dois conheçam e obedeçam: é o chamado protocolo.
Neste exemplo, Alice e Bob escolhem uma das chaves do conjunto de chaves (k C K). Isto pode ser feito num encontro pessoal ou através de um canal seguro - em todo caso, longe dos olhos do Oscar. Mais tarde, digamos que Alice queira enviar uma mensagem para Bob através de um canal inseguro. Esta mensagem é constituída por caracteres que podem ser expressos como
x = x1 x2 ... xn
Como n indica o número de caracteres da mensagem, é claro que n precisa ser maior do que zero porque, se for zero, não existe mensagem nenhuma. A forma matemática de dizer isto é n > 1 e significa n maior ou igual a 1. Além disto, já sabemos que a mensagem, seja ela qual for, pertence ao conjunto de textos claros, ou seja, x C A.
Cada caracter da mensagem clara pertence ao conjunto de caracteres desta mensagem e, como esta mensagem pertence ao conjunto de mensagens claras A, os caracteres também fazem parte deste conjunto A. Se chamarmos cada caracter de xi, o valor de i precisa ser igual ou maior do que 1 e menor ou igual ao número de caracteres da mensagem (que já chamamos de n). Então:
xi C A onde n > 1 e 1 < i < n
Cada xi é cifrado usando a regra de cifragem ek especificada pela chave escolhida. Alice faz os seguintes cálculos:
yi = ek(xi), 1 < i < n
para obter a mensagem cifrada
y = y1 y2 ... yn
Quando Bob recebe a mensagem cifrada de Alice, ele aplica a regra de decifração dk em y1 y2 ... yn e obtém novamente a mensagem clara x1 x2 ... xn
Um pouco mais de matemática
A função de cifragem (ou regra de encriptação) precisa ser uma função injetiva. Que negócio é este? Bem, a regra ek, quando aplicada, pode dar apenas um resultado. Funções que dão apenas um resultado são chamadas de injetivas, injetoras, unívocas ou 1-1. A importância do uso de funções 1-1 na criptografia fica clara no seguinte exemplo:
y = ek(x1) = ek(x2) onde x1 é diferente de x2.
Neste caso, quando Bob for decifrar y, ele encontra dois resultados diferentes. Qual deles deve ser usado? Nenhum! O sistema está bichado porque a função de cifragem usada não era unívoca.