Alice e Bob querem compartilhar segredos entre eles. Como poderão fazer isto de maneira segura? Neste post veremos um pouco sobre criptografia e mostraremos como Teoria dos Números pode nos ajudar nessa história.
Criptografia é o campo de estudo dos métodos de transmissão de informações com segurança. Ou seja, estamos interessados em enviar mensagens de maneira segura. Dizemos que uma informação é transmitida com segurança se toda fonte não autorizada é incapazes de obter acesso à informação transmitida.
Para fins técnicos, assumiremos que uma mensagem é uma sequência numérica. Emissor é aquele que está interessado em compartilhar uma mensagem e receptor é aquele que está autorizado a ter acesso ao conteúdo da mensagem. Um interlocutor é um emissor ou um receptor. No nosso caso, Alice quer enviar uma mensagem para Bob. Portanto, iremos nos referir ao emissor como Alice e ao receptor como Bob.
Um método de encriptação é uma maneira de codificar (ou criptografar) a mensagem de tal modo que seja possível reobter a mensagem original por um processo de decodificação. Num método de encriptação, o responsável pela codificação é o emissor, o qual se usa de uma chave de codificação para codificar a mensagem; enquanto o responsável pela decodificação é o receptor, o qual usa uma chave de decodificação para decodificar a mensagem. De modo geral, tal processo se dá por meio de um algoritmo, o qual chamamos de algoritmo de encriptação ou cifra. Classicamente, existem dois tipos de cifra: o de chave simétrica (ou chave privada) e o de chave assimétrica (ou chave pública).
Cifra de chave simétrica. Uma cifra de chave simétrica é aquela na qual a chave de codificação está relacionada, de alguma maneira, com a chave de decodificação, podendo até serem iguais. Algoritmos deste tipo são mais vulneráveis, pois exigem que o emissor e o receptor compartilhem entre si alguma informação de maneira tal que ambos possam determinar as suas respectivas chaves. Além do mais, se alguém possui em mãos a chave de codificação, este será capaz de determinar a chave de decodificação.
Se Alice e Bob optam por usar uma cifra de chave privada, para que Alice possa enviar uma mensagem para Bob, eles devem proceder da seguinte maneira. Primeiro, Alice e Bob marcam um encontro secreto em um shopping e determinam, juntos, uma chave para a cifra. Os dois anotam a chave e vão para as suas casas. Ao chegar lá, Alice escreve a sua mensagem e, com a chave determinada pelo os dois, codifica a mensagem. Então ela envia para o email de Bob a mensagem criptografada. Bob, ao receber a mensagem codificada, usa a chave para decodificar a mensagem.
Se Alice e Bob optam por usar uma cifra de chave privada, para que Alice possa enviar uma mensagem para Bob, eles devem proceder da seguinte maneira. Primeiro, Alice e Bob marcam um encontro secreto em um shopping e determinam, juntos, uma chave para a cifra. Os dois anotam a chave e vão para as suas casas. Ao chegar lá, Alice escreve a sua mensagem e, com a chave determinada pelo os dois, codifica a mensagem. Então ela envia para o email de Bob a mensagem criptografada. Bob, ao receber a mensagem codificada, usa a chave para decodificar a mensagem.
One time pad. Um exemplo de cifra de chave simétrica é o one time pad. Neste algoritmo, uma mensagem é uma sequência binária de 0's e 1's, por exemplo
$$100111001011$$
A chave de codificação e a chave de decodificação são iguais e é também uma sequência binária de 0's e 1's de mesmo tamanho que a mensagem:
$$111100101100$$
Considere a operação $\oplus$ dígito a dígito dada por $0\oplus 0= 1\oplus 1=0$ e $1\oplus 0 = 0\oplus 1=1$. A mensagem codificada é o resultante da $\oplus$ entre a mensagem original e a chave de codificação. Assim, teremos $$ 100111001011 \oplus 111100101100 = 011010100111$$
como a mensagem codificada. Observe que o receptor poderá reobter a mensagem original apenas aplicando o mesmo processo em cima da mensagem codificada, ou seja, a mensagem original é o resultante da $\oplus$ entre a mensagem codificada e a chave de decodificação, que é a mesma da codificação. Observe também que somente quem tem a chave é quem pode decodificar a mensagem.
Esta cifra recebe o nome de "one time pad" pelo fato dela só poder ser usado uma única vez. Isto por quê se alguém tem conhecimento de duas mensagens codificadas pela mesma chave, este poderá "quebrar" o código apenas usando uma estratégia de quebra baseada na frequência de dígitos. Estratégias deste tipo são muito comuns e extremamente úteis e eficazes quando se quer quebrar uma mensagem codificada.
Uma das cifras de chave simétrica mais popular é o AES (Advanced Encryption Standard). Esta cifra possui base teórica na Teoria de Galois. É um algoritmo extremamente eficiente e é hoje utilizado como cifra padrão pelo Governo Americano.
Cifra de chave pública. Uma cifra de chave assimétrica, ou de chave pública, como é mais conhecido, é aquela na qual as chaves de codificação e de decodificação não possuem relação alguma entre si. Assim, se alguém tem conhecimento da chave de codificação, este não será capaz de decodificar a mensagem.
Se Alice e Bob optam por usar uma cifra de chave pública, então para que Alice possa enviar uma mensagem para Bob, eles devem proceder da seguinte maneira. Primeiro Bob determina duas chaves, uma a qual ele deve manter em sigilo (esta é a que chamamos de chave privada) e outra a qual ele deve disponibilizar publicamente, por exemplo, no seu Facebook (esta é a que chamamos de chave pública). Alice, então, deve usar a chave pública do Bob para codificar sua mensagem e só então enviar a mensagem criptografada para o Bob, podendo, inclusive, postar lá na timeline do Facebook dele. Bob, ao receber a mensagem criptografada, usará a sua chave privada para decodificar a mensagem. Como ele é o único que detém conhecimento da chave privada, somente ele será capaz de decodificar a mensagem de Alice. E como a chave pública não tem relação alguma com a chave privada, ninguém será capaz de determinar a chave privada mesmo que Bob tenha disponibilizado a sua chave pública no Facebook.
RSA. A cifra de chave pública mais popular é certamente a cifra RSA, cujo o nome é uma homenagem aos inventores desta cifra, Ron Rivest, Adi Shamir, e Leonard Adleman (veja imagem abaixo, na qual eles aparece na ordem da esquerda para à direita). O algoritmo de encriptação do RSA é feito sobre o anel dos inteiros módulo $n$, $\mathbb{Z}_n= \{0,1,\ldots,n-1 \}$, onde uma mensagem (criptografada ou não) é um elemento de $\mathbb{Z}_n $.
O algoritmo de encriptação RSA é fundamentado no teorema de Euler. Se $n$ é um inteiro positivo, a função $\phi$ de Euler, denotada por $\phi(n)$, é definida como sendo o número de inteiros positivos menores do que ou iguais a $n$ que são relativamente primos com $n$. Se $n$ se decompõe como $n=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, então sabe-se que $$\phi(n) = n \left( 1 -\frac{1}{p_1} \right) \left( 1 -\frac{1}{p_2} \right)\cdots\left( 1 -\frac{1}{p_k} \right). $$
O Teorema de Euler pode então ser enunciado como segue.
O teorema acima é um resultado clássico de teoria elementar dos números e pode ser encontrada em qualquer livro introdutório de teoria dos números. Para a cifra RSA usaremos na verdade apenas um caso particular do Teorema de Euler correspondendo a $n = pq$, onde $p$ e $q$ são números primos. Em tal caso temos $\phi(n) = \phi(pq) = (p-1)(q-1)$.
O Protocolo. No que segue, iremos descrever o protocolo da cifra RSA.
Gerando as chaves: Bob gera dois números primos $p$ e $q$ e calcula seu produto $n = pq$. Em seguida, ele gera um número $d$ primo com $(p-1)(q-1)$ (falaremos mais sobre isso posteriormente) e determina o número $e$ como o inverso multiplicativo de $d$ módulo $(p-1)(q-1)$, i.e.,
$$ed\equiv 1 \quad (\mathrm{mod}\; (p-1)(q-1)).$$
Ele então disponibiliza publicamente os números $n$ e $e$. Assim, o par $(n,e)$ é a chave pública do Bob. Os números $p$ e $q$ devem ser mantidos em segredos; na verdade, é permitido até esquecê-los, uma vez que eles não terão importância para o que segue no protocolo. O número $d$ deve ser guardado de maneira segura, uma vez que este deverá ser a chave privada do Bob.
Criptografando a mensagem: Alice deve determinar a sua mensagem como um número inteiro positivo $m$ menor do que $n$ (se a mensagem for muito longa, ela pode até quebrá-la em pedaços menores). Ela, então, calcula o resto de $m^e$ módulo $n$, o qual denotaremos por $c$. Temos então que
$$c \equiv m^e \quad(\mathrm{mod}\; n).$$
Tal número $c$ representa a mensagem criptografada da Alice. Ela pode enfim enviar a mensagem criptografada $c$ para Bob.
Descriptografando a mensagem: Para descriptografar a mensagem, Bob deverá computar o resto de $c^d$ módulo $n$, o qual denotaremos por $m'$. Portanto,
$$ m' \equiv c^d \quad (\mathrm{mod}\; n).$$
Acontece que teremos $m' = m$ (como veremos abaixo), portanto Bob terá assim descriptografado a mensagem de Alice.
Por que funciona? Para analisarmos o algoritmo, devemos levar em conta dois principais pontos: a mecânica e a segurança. Ou seja, devemos verificar que as operações envolvidas no protocolo são de fato coerentes e então devemos analisar porquê alguém que não detém conhecimento da chave privada é incapaz de decifrar a mensagem cifrada enviada por Alice.
Mecânica. O ponto chave da mecânica do protocolo é verificarmos que de fato $m'=m$. Com efeito, temos
$$ m' \equiv c^d \equiv \equiv (m^e)^d \equiv m^{ed} \quad (\mathrm{mod}\; n).$$
Como $\phi(n) = \phi(pq) = (p-1)(q-1)$, temos que
$$ed \equiv 1 \quad (\mathrm{mod} \; \phi(n)). $$
Portanto, $ed = t \phi(n) +1$, para algum $t \in \mathbb{Z}$. Daí
$$ m' \equiv m^{t \phi(n) +1} \equiv (m^{\phi(n)})^t m \equiv m \quad (\mathrm{mod}\; n),$$
onde usamos o Teorema de Euler para garantir que $m^{\phi(n)} \equiv 1$, módulo $n$. E como $m$ e $m'$ são ambos inteiros positivos menores do que $n$, temos $m=m'$, como queríamos.
Segurança. O que torna a cifra RSA segura é o fato de não conhecermos bons algoritmos de fatoração. Para ilustrar isto, iremos neste ponto adicionar uma terceira personagem a esta história: Eva.
Eva quer saber qual foi a mensagem que Alice enviou para Bob, mas ela só tem acesso a mensagem criptografada (o inteiro $m$) e a chave pública do Bob (os números $n$ e $e$). Eva pode pensar basicamente em duas estratégias: determinar a chave privada do Bob $d$ ou determinar diretamente a mensagem de Alice $m$.
Para a primeira estratégia, Eva teria que descobrir um número $\underline{d}$ tal que
$$e\underline{d}\equiv 1 \quad (\mathrm{mod} \;\phi(n)).$$
A princípio, não parece ser difícil determinar tal $\underline{d}$, uma vez que Eva tem conhecimento dos inteiros $n$ e $e$. Contudo, o inteiro que ela precisa para computar $\underline{d}$ é na verdade o número $\phi(n)$. Não se conhece nenhum método eficiente de calcular $\phi(n)$ sem que não seja necessário fatorar $n$. Então o problema determinar $\underline{d}$ se reduz ao problema da fatoração de $n$.
Para a segunda estratégia, Eva teria que descobrir um número $\underline{m}$ tal que
$$c \equiv \underline{m}^e \quad(\mathrm{mod}\; n).$$
Uma vez que Eva tem conhecimento dos inteiros $c$, $n$ e $e$, não parece ser difícil determinar $\underline{m}$. A maneira mais natural seria determinar um número $\underline{d}$ tal que
$$\underline{d} e \equiv 1 \quad(\mathrm{mod} \; \phi(n)), $$
porque aí teremos
$$\underline{m} \equiv c^{\underline{d}} \quad(\mathrm{mod}\; n).$$
Mas como já vimos, isto se reduz ao problema de fatoração de $n$. Ademais, não se conhece nenhuma outra estratégia eficiente para determinar $\underline{m}$ que não se reduza ao problema da fatoração.
Então, nos dois casos, reduzimos o prolema da quebra do algoritmo RSA para o problema da fatoração. Na prática, os números envolvidos no protocolo do RSA são números enormes (com 100 até 200 dígitos). E esta é uma das razões de ser difícil de quebrar o RSA, já que o tempo necessário para fatorar números grandes é astronômico.
Observe que para Bob poder gerar as chaves é necessário ele determinar dois números primos $p$ e $q$. O ideal é que estes números sejam grandes. Um fato importante é que não é difícil encontrar um número primo de maneira aleatória dentro de um intervalo (como o intervalo dos números de 100 dígitos, por exemplo). Num futuro post mostrarei isto.
A aritmética modular é que nos permite calcular potências dos números envolvidos no protocolo (como $m^e$) sem muito trabalho, mesmo se tratando de números grande. A computação dos inversos multiplicativos envolvidos no protocolo do RSA é também feito sem muita dificuldade, uma vez que isto se reduz ao algoritmo de Euclides. Por exemplo, dado $e$, podemos calcular o inteiro $d$ como sendo inverso de $e$ módulo $(p-1)(q-1)$ usando algoritmo de Euclides. Tudo que temos que exigir é que $e$ seja primo com $(p-1)(q-1)$. Se não for, considere um outro $e$ escolhido aleatoriamente. Não é difícil mostrar que encontrar um tal $e$ desta forma é tão "rápido" quanto encontrar um número primo aleatório.
Pois bem, agora Alice e Bob podem trocar correspondências sem que Eva bisbilhote. Por hoje, isso é tudo. Até a próxima!
Referências.
[1] Jeffrey Hoffstein, Jill Pipher, J.H. Silverman. An introduction to mathematical cryptography. Undergraduate Texts in Mathematics. Springer, 2008.
[2] Christof Paar, Jan Pelzl. Understanding Cryptography. Springer, 2010.
[3] L. Lovász, J. Pelikán, K. Vesztergombi. Matemática Discreta. Textos Universitários. SBM, 2005.
O algoritmo de encriptação RSA é fundamentado no teorema de Euler. Se $n$ é um inteiro positivo, a função $\phi$ de Euler, denotada por $\phi(n)$, é definida como sendo o número de inteiros positivos menores do que ou iguais a $n$ que são relativamente primos com $n$. Se $n$ se decompõe como $n=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, então sabe-se que $$\phi(n) = n \left( 1 -\frac{1}{p_1} \right) \left( 1 -\frac{1}{p_2} \right)\cdots\left( 1 -\frac{1}{p_k} \right). $$
O Teorema de Euler pode então ser enunciado como segue.
Teorema 1. (Euler) Se $n$ é um inteiro positivo e $a$ é um inteiro com $\mathrm{mdc}(a,n) = 1$, então $$a^{\phi(n)} \equiv 1 \;(\mathrm{mod}\; n). $$
O teorema acima é um resultado clássico de teoria elementar dos números e pode ser encontrada em qualquer livro introdutório de teoria dos números. Para a cifra RSA usaremos na verdade apenas um caso particular do Teorema de Euler correspondendo a $n = pq$, onde $p$ e $q$ são números primos. Em tal caso temos $\phi(n) = \phi(pq) = (p-1)(q-1)$.
O Protocolo. No que segue, iremos descrever o protocolo da cifra RSA.
Gerando as chaves: Bob gera dois números primos $p$ e $q$ e calcula seu produto $n = pq$. Em seguida, ele gera um número $d$ primo com $(p-1)(q-1)$ (falaremos mais sobre isso posteriormente) e determina o número $e$ como o inverso multiplicativo de $d$ módulo $(p-1)(q-1)$, i.e.,
$$ed\equiv 1 \quad (\mathrm{mod}\; (p-1)(q-1)).$$
Ele então disponibiliza publicamente os números $n$ e $e$. Assim, o par $(n,e)$ é a chave pública do Bob. Os números $p$ e $q$ devem ser mantidos em segredos; na verdade, é permitido até esquecê-los, uma vez que eles não terão importância para o que segue no protocolo. O número $d$ deve ser guardado de maneira segura, uma vez que este deverá ser a chave privada do Bob.
Criptografando a mensagem: Alice deve determinar a sua mensagem como um número inteiro positivo $m$ menor do que $n$ (se a mensagem for muito longa, ela pode até quebrá-la em pedaços menores). Ela, então, calcula o resto de $m^e$ módulo $n$, o qual denotaremos por $c$. Temos então que
$$c \equiv m^e \quad(\mathrm{mod}\; n).$$
Tal número $c$ representa a mensagem criptografada da Alice. Ela pode enfim enviar a mensagem criptografada $c$ para Bob.
Descriptografando a mensagem: Para descriptografar a mensagem, Bob deverá computar o resto de $c^d$ módulo $n$, o qual denotaremos por $m'$. Portanto,
$$ m' \equiv c^d \quad (\mathrm{mod}\; n).$$
Acontece que teremos $m' = m$ (como veremos abaixo), portanto Bob terá assim descriptografado a mensagem de Alice.
Por que funciona? Para analisarmos o algoritmo, devemos levar em conta dois principais pontos: a mecânica e a segurança. Ou seja, devemos verificar que as operações envolvidas no protocolo são de fato coerentes e então devemos analisar porquê alguém que não detém conhecimento da chave privada é incapaz de decifrar a mensagem cifrada enviada por Alice.
Mecânica. O ponto chave da mecânica do protocolo é verificarmos que de fato $m'=m$. Com efeito, temos
$$ m' \equiv c^d \equiv \equiv (m^e)^d \equiv m^{ed} \quad (\mathrm{mod}\; n).$$
Como $\phi(n) = \phi(pq) = (p-1)(q-1)$, temos que
$$ed \equiv 1 \quad (\mathrm{mod} \; \phi(n)). $$
Portanto, $ed = t \phi(n) +1$, para algum $t \in \mathbb{Z}$. Daí
$$ m' \equiv m^{t \phi(n) +1} \equiv (m^{\phi(n)})^t m \equiv m \quad (\mathrm{mod}\; n),$$
onde usamos o Teorema de Euler para garantir que $m^{\phi(n)} \equiv 1$, módulo $n$. E como $m$ e $m'$ são ambos inteiros positivos menores do que $n$, temos $m=m'$, como queríamos.
Segurança. O que torna a cifra RSA segura é o fato de não conhecermos bons algoritmos de fatoração. Para ilustrar isto, iremos neste ponto adicionar uma terceira personagem a esta história: Eva.
Eva quer saber qual foi a mensagem que Alice enviou para Bob, mas ela só tem acesso a mensagem criptografada (o inteiro $m$) e a chave pública do Bob (os números $n$ e $e$). Eva pode pensar basicamente em duas estratégias: determinar a chave privada do Bob $d$ ou determinar diretamente a mensagem de Alice $m$.
Para a primeira estratégia, Eva teria que descobrir um número $\underline{d}$ tal que
$$e\underline{d}\equiv 1 \quad (\mathrm{mod} \;\phi(n)).$$
A princípio, não parece ser difícil determinar tal $\underline{d}$, uma vez que Eva tem conhecimento dos inteiros $n$ e $e$. Contudo, o inteiro que ela precisa para computar $\underline{d}$ é na verdade o número $\phi(n)$. Não se conhece nenhum método eficiente de calcular $\phi(n)$ sem que não seja necessário fatorar $n$. Então o problema determinar $\underline{d}$ se reduz ao problema da fatoração de $n$.
Para a segunda estratégia, Eva teria que descobrir um número $\underline{m}$ tal que
$$c \equiv \underline{m}^e \quad(\mathrm{mod}\; n).$$
Uma vez que Eva tem conhecimento dos inteiros $c$, $n$ e $e$, não parece ser difícil determinar $\underline{m}$. A maneira mais natural seria determinar um número $\underline{d}$ tal que
$$\underline{d} e \equiv 1 \quad(\mathrm{mod} \; \phi(n)), $$
porque aí teremos
$$\underline{m} \equiv c^{\underline{d}} \quad(\mathrm{mod}\; n).$$
Mas como já vimos, isto se reduz ao problema de fatoração de $n$. Ademais, não se conhece nenhuma outra estratégia eficiente para determinar $\underline{m}$ que não se reduza ao problema da fatoração.
Então, nos dois casos, reduzimos o prolema da quebra do algoritmo RSA para o problema da fatoração. Na prática, os números envolvidos no protocolo do RSA são números enormes (com 100 até 200 dígitos). E esta é uma das razões de ser difícil de quebrar o RSA, já que o tempo necessário para fatorar números grandes é astronômico.
Observe que para Bob poder gerar as chaves é necessário ele determinar dois números primos $p$ e $q$. O ideal é que estes números sejam grandes. Um fato importante é que não é difícil encontrar um número primo de maneira aleatória dentro de um intervalo (como o intervalo dos números de 100 dígitos, por exemplo). Num futuro post mostrarei isto.
A aritmética modular é que nos permite calcular potências dos números envolvidos no protocolo (como $m^e$) sem muito trabalho, mesmo se tratando de números grande. A computação dos inversos multiplicativos envolvidos no protocolo do RSA é também feito sem muita dificuldade, uma vez que isto se reduz ao algoritmo de Euclides. Por exemplo, dado $e$, podemos calcular o inteiro $d$ como sendo inverso de $e$ módulo $(p-1)(q-1)$ usando algoritmo de Euclides. Tudo que temos que exigir é que $e$ seja primo com $(p-1)(q-1)$. Se não for, considere um outro $e$ escolhido aleatoriamente. Não é difícil mostrar que encontrar um tal $e$ desta forma é tão "rápido" quanto encontrar um número primo aleatório.
Pois bem, agora Alice e Bob podem trocar correspondências sem que Eva bisbilhote. Por hoje, isso é tudo. Até a próxima!
Referências.
[1] Jeffrey Hoffstein, Jill Pipher, J.H. Silverman. An introduction to mathematical cryptography. Undergraduate Texts in Mathematics. Springer, 2008.
[2] Christof Paar, Jan Pelzl. Understanding Cryptography. Springer, 2010.
[3] L. Lovász, J. Pelikán, K. Vesztergombi. Matemática Discreta. Textos Universitários. SBM, 2005.
Nenhum comentário:
Postar um comentário
Use cifrões para inserir um comando TeX. Por exemplo: "Afirmo que $\$ $\sqrt {2} $\$ $ é irracional".