Criptografia assimétrica com o RSA
Devido a dificuldade de troca de chaves, os algoritmos assimétricos são o principal motor de comunicações cifradas sobre SSL, como o HTTPS. De fácil compreensão, o RSA é um interessante método matemático que permite a cifra assimétrica baseado em números primos. E você pode brincar de RSA com a sua calculadora bc de linha de comando.
Parte 2: A teoria dos algoritmos assimétricos
Um algoritmo de criptografia assimétrico, mais popularmente conhecido como algoritmos de chave pública e privada, consiste no uso de duas chaves distintas. Uma delas é usada para cifrar dados e a outra para decifrar, ou seja, o que uma chave faz, a outra desfaz.
Como exemplo, considere que duas pessoas desejam enviar dados sigilosos pelos correios. Usarão uma caixa fechada com um cadeado para isto. O problema é como enviar a chave, já que uma pessoa poderia capturá-la e realizar uma cópia. Diffie e Hellman pensaram na ideia de dois cadeados, com duas chaves, conforme descrito no artigo Fundamentos da criptografia assimétrica. Porém tem uma maneira ainda mais fácil de realizar esta comunicação.
Caso um emissor C queira enviar dados para um receptor F usando os correios, o procedimento poderia ser o seguinte:
Usando a analogia do cadeado, pode-se considerar que o cadeado aberto é uma das chaves de cifragem, justamente aquela que só serve para cifrar (bater o cadeado). A chave do cadeado é que serve para abrir.
F poderia pedir a um grande fabricante de cadeados que confeccionasse milhares deles, todos iguais e abertos por uma única chave. Estes cadeados poderiam ser espalhados em supermercados, ferragens, lojas de conveniência. Todo mundo teria acesso fácil a um destes cadeados abertos. Quando alguém desejar enviar algo para F, basta pegar um cadeado aberto em algum posto de gasolina e usar ele para fechar uma caixa, enviado-a para F. Assim o cadeado aberto seria, analogicamente, a chave pública de F.
Para que isto funcione, algumas propriedades são muito importantes sob o risco de comprometer o sigilo:
Trazendo a analogia para os termos criptográficos, a propriedade 2 significa que o algoritmo deve resistir a criptoanálise enquanto que a propriedade 3 significa que deve resistir a força bruta.
A propriedade de número dois é a mais complicada. Facilmente se percebe que para cadeados normais ela não é atendida, pois qualquer chaveiro, mesmo nem tão habilidoso assim, consegue em minutos confeccionar uma nova chave para um cadeado, se puder analisá-lo. Eles conseguem até mesmo abrir um cadeado já fechado ou se existe muita pressa em abrir a caixa, nada que um alicate não resolva (propriedade 1).
Diffie e Hellman foram os primeiros acadêmicos a descobrir uma função matemática de mão única e a usaram como base ao protocolo de troca de chaves. Tentaram, sem sucesso, chegar ao assimétrico. Para que o assimétrico fosse possível, esta função de mão única precisa ser desfeita, mas apenas por quem conhece algum segredo em especial. Precisavam, desta forma, tornar a função de mão única reversível.
E foi isto que Ronald Rivest, Adir Shamir e Leonard Adlemann conseguiram.
Como exemplo, considere que duas pessoas desejam enviar dados sigilosos pelos correios. Usarão uma caixa fechada com um cadeado para isto. O problema é como enviar a chave, já que uma pessoa poderia capturá-la e realizar uma cópia. Diffie e Hellman pensaram na ideia de dois cadeados, com duas chaves, conforme descrito no artigo Fundamentos da criptografia assimétrica. Porém tem uma maneira ainda mais fácil de realizar esta comunicação.
Caso um emissor C queira enviar dados para um receptor F usando os correios, o procedimento poderia ser o seguinte:
- C requisita a F um cadeado;
- F vai em uma ferragem, compra um cadeado qualquer e o envia aberto para C, mantendo consigo a chave;
- C recebe pelos correios o cadeado aberto de F;
- C usa o cadeado para fechar a caixa e a envia para F.
Usando a analogia do cadeado, pode-se considerar que o cadeado aberto é uma das chaves de cifragem, justamente aquela que só serve para cifrar (bater o cadeado). A chave do cadeado é que serve para abrir.
F poderia pedir a um grande fabricante de cadeados que confeccionasse milhares deles, todos iguais e abertos por uma única chave. Estes cadeados poderiam ser espalhados em supermercados, ferragens, lojas de conveniência. Todo mundo teria acesso fácil a um destes cadeados abertos. Quando alguém desejar enviar algo para F, basta pegar um cadeado aberto em algum posto de gasolina e usar ele para fechar uma caixa, enviado-a para F. Assim o cadeado aberto seria, analogicamente, a chave pública de F.
Para que isto funcione, algumas propriedades são muito importantes sob o risco de comprometer o sigilo:
- o cadeado é muito forte e uma vez fechado, só a chave pode abrí-lo;
- mesmo aberto, o cadeado não possui informações suficientes para que um chaveiro, mesmo habilidoso, consiga confeccionar uma nova chave para ele;
- o número de chaves possíveis inviabiliza que um chaveiro, mesmo com muito tempo, pudesse tentar cada uma delas.
Trazendo a analogia para os termos criptográficos, a propriedade 2 significa que o algoritmo deve resistir a criptoanálise enquanto que a propriedade 3 significa que deve resistir a força bruta.
A propriedade de número dois é a mais complicada. Facilmente se percebe que para cadeados normais ela não é atendida, pois qualquer chaveiro, mesmo nem tão habilidoso assim, consegue em minutos confeccionar uma nova chave para um cadeado, se puder analisá-lo. Eles conseguem até mesmo abrir um cadeado já fechado ou se existe muita pressa em abrir a caixa, nada que um alicate não resolva (propriedade 1).
Diffie e Hellman foram os primeiros acadêmicos a descobrir uma função matemática de mão única e a usaram como base ao protocolo de troca de chaves. Tentaram, sem sucesso, chegar ao assimétrico. Para que o assimétrico fosse possível, esta função de mão única precisa ser desfeita, mas apenas por quem conhece algum segredo em especial. Precisavam, desta forma, tornar a função de mão única reversível.
E foi isto que Ronald Rivest, Adir Shamir e Leonard Adlemann conseguiram.
parabéns elgio!
[]'s