Álgebra Abstrata: Teoria e Aplicações

Subseção 7.2.1 O Criptossistema RSA

O Criptossistema RSA introduzido por R. Rivest, A. Shamir, e L. Adleman em 1978, se baseia na dificultade de fatorar número grandes. Ainda que não seja difícil encontrar dois primos grandes e multiplicá-los, fatorar um número de 150 dígitos que seja o produto de dois primos grandes iria requerer 100 milhões computadores operando 10 milhões de instruções por segundo durantes 50 milhões de anos com os melhores algoritmos conhecidos no princípio da década de 1990. Mesmo que os algoritmos tenham melhorado, fatorar um produto de dois primos grandes segue sendo computacionalmente proibitivo.

O Criptossistema RSA funciona como segue. Suponha que escolhemos dois números primos \(p\) e \(q\) de 150 dígitos cada um. Depois calculamos seu produto \(n= pq\) e também calculamos \(\phi(n) = m = (p - 1)(q-1)\text{,}\) donde \(\phi\) é a função \(\phi\) de Euler. Agora começamos a escolher inteiros aleatórios \(E\) até que encontremos um que seja relativamente primo com \(m\text{;}\) isto é, escolhemos \(E\) tal que \(\gcd(E, m) = 1\text{.}\) Usando o algoritmo de Euclides, podemos encontrar um número \(D\) tal que \(DE \equiv 1 \pmod{m}\text{.}\) Os números \(n\) e \(E\) agora são públicos.

Suponha que a pessoa B (Bob) deseja enviar para pessoa A (Alice) uma mensagem através de um canal aberto (público). Como \(E\) e \(n\) são conhecidos por todo mundo, qualquer um pode encriptar mensagens. Bob primeiro converte sua mensagem em uma cadeia numérica de acordo com algum procedimento, digamos \(\text{A} = 00, \text{B} = 02, \ldots, \text{Z}= 25\text{.}\) Se for necessário, decomponha sua mensagem de maneira que cada pedaço seja um inteiro positivo menor que \(n\text{.}\) Suponha que \(x\) é um desses pedaços. Bob forma o número \(y = x^E \mod n\) e envia \(y\) para Alice. Para que Alice recupere \(x\text{,}\) ela só precisa calcular \(x = y^D \bmod n\text{.}\) Só Alice conhece \(D\text{.}\)

Examinemos agora porque o criptossistema RSA funciona. Sabemos que \(DE \equiv 1 \pmod{ m}\text{;}\) logo, existe \(k\) tal que

Devemos considerar dois casos. No primeiro caso suponha que \(\gcd(x, n) = 1\text{.}\) Então, pelo Teorema 6.3.2,

Desta maneira vemos que Alice recupera a mensagem original \(x\) quando calcula \(y^D \bmod n\text{.}\)

Para o outro caso, suponha que \(\gcd(x, n) \neq 1\text{.}\) Como \(n = pq\) e \(x \lt n\text{,}\) sabemos que \(x\) é um múltiplo de \(p\) ou um múltiplo de \(q\text{,}\) mas não de ambos. Descreveremos somente a primeira possibilidade, pois a outra é completamente similar. Então existe um inteiro \(r\text{,}\) com \(r \lt q\) e \(x = rp\text{.}\) Notemos que temos \(\gcd(x, q) = 1\) e que \(m=\phi(n)=(p - 1)(q - 1)=\phi(p)\phi(q)\text{.}\) Então, usando o Teorema 6.3.2, mas agora mod \(q\text{,}\)

Existe um inteiro \(t\) tal que \(x^{km}=1 + tq\text{.}\) Logo, Alice também recupera a mensagem neste caso,

Podemos perguntar agora como alguém tentaria violar o criptossistema RSA. Para encontrar \(D\) dados \(n\) e \(E\text{,}\) necessitamos fatorar \(n\) e encontrar \(D\) usando o algoritmo de Euclides. Se sabemos que \(667 = 23 \cdot 29\) no Exemplo 7.2.1, poderíamos recuperar \(D\text{.}\)

Subseção 7.2.2 Verificação da Mensagem

Existe um problema de verificação de mensagens nos criptossistemas de chave pública. Como a chave codificadora é de conhecimento público, qualquer um tem a capacidade de enviar uma mensagem codificada. Se Alice recebe uma mensagem de Bob, ela gostaria de poder verificar que realmente foi que Bob que enviou a mensagem. Suponha que a chave encriptadora de Bob é \((n', E')\) e sua chave decriptadora é \((n', D')\text{.}\) Além disso, suponha que a chave encriptadora de Alice é \((n, E)\) e que sua chave decriptadora é \((n, D)\text{.}\) Como as chaves encriptadoras são de conhecimento público, ambos podem trocar mensagens quando desejarem. Bob quer garatir a Alice que a mensagem que está enviando é autêntica. Antes de enviar a mensagem \(x\) a Alice, Bob decripta \(x\) com sua própia chave secreta:

Qualquer um pode transformar \(x'\) de volta a \(x\) encriptando, mas só Bob tem a habilidade de formar \(x'\text{.}\) Agora Bob encripta \(x'\) com a chave pública de Alice formando

uma mensagem que só Alice pode decriptar. Alice decripta a mensagem e logo encripta o resultado com a chave de encriptação de Bob para ler a mensagem original, uma mensagem que só pode ter sido enviada por Bob.

Subseção 7.2.3 Nota Histórica

A ideia de encriptar mensagens secretas vem desde a Grécia e Roma Antiga. Como sabemos, Júlio César usou um código de deslocamento simples para mandar e receber mensagens. No entanto, o estudo formal de encriptar e decriptar mensagens provavelmente começou com os árabes nos anos 1400. Nos séculos XV e XVI, matemáticos, tais quais Alberti e Viete, descobriram que criptossistemas monoalfabéticos não ofereciam uma segurança real. No século XIX, F. W. Kasiski estabeleceu métodos para violar sistemas em que uma letra do texto encriptado podia representar mais de uma letra do texto claro, se a mesma chave fosse usada várias vezes. Este descobrimento levou ao uso de criptossistemas com chaves que eram usadas só uma vez. A criptografia obteve fundamentos matemáticos firmes com os trabalhos de gente como W. Friedman e L. Hill no começo do século XX.

O périodo que seguiu a Primeira Guerra Mundial viu a criação de máquinas especializadas na encriptação e decriptação de mensagens e os matemáticos trabalharam arduamente na criptografia durante a Segunda Guerra Mundial. Os esforços para violar os criptossistemas das nações do Eixo foram organizados na Inglaterra e nos Estados Unidos por matemáticos notáveis como Alan Turing e A. A. Albert. Os Aliados obtiveram uma tremenda vantagem na Segunda Guerra Mundial ao romper os sistemas de encriptação produzidos pela máquina Enigma da Alemanha e os cifrados Púrpura do Japão.

Em 1970, o interesse na criptografia comercial começou a se solidificar. Havia uma necessidade crescente de proteger transações bancárias, dados informáticos e emails eletrônicos. No começo dos anos 1970, IBM desenvolveu e implementou LUZIFER, o precursor do padrão de encriptação de dados do National Bureau of Standards dos Estados Unidos.

O conceito de um criptossistema de chave pública, devido a Diffie e Hellman, é muito recente (1976). Ele foi mais tarde desenvolvido por Rivest, Shamir e Adleman com o criptossistema RSA (1978). Ainda não sabemos o quão seguro esse criptossistema é. O criptossistema da mochila de decisão, fundamentado por Merkle e Hellman, foi quebrado. É ainda uma pergunta se o sistema RSA pode ou não ser violado. Em 1991, os Laboratórios RSA publicaram uma lista de semiprimos (números que tem exatamente dois fatores primos) com um prêmio em dinheiro para quem pudesse fatorá-los (http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm¹). Por mais que o desafio tenha terminado em 2007, muitos desses números ainda não foram fatorados.

Houve bastante controversia com relação a investigação de criptossistemas e com a criptografia por si só. Em 1929, quando Henry Stimson, Secretário de Estado de Herbert Hoover, dissolveu a Câmara Negra (a divisão de criptografia do Departamento de Estado) com a justificativa ética de que “os cavalheiros leêm a correspondência de outros.” Durante as últimas duas décadas do século XX, a Agência Nacional de Segurança (NSA) queria manter em segredo a informação sobre criptografia, ainda que a comunidade científica pedisse pelo direito de publicar a ciência básica relacionada ao assunto. Atualmente, a pesquisa com relação a criptografia matemática e à teoria dos números computacionais é muito ativa, e os matemáticos têm a libertade de publicar seus resultados nestas áreas.