Nº.61 UNIVERSO Dez 2016 | Jan 2017

.
Ricardo Dahab
27/4/16

Um pouquinho da Teoria dos Números

A Teoria dos Números é a mais antiga área da Matemática; estuda os números inteiros e as relações entre eles. Inicialmente, nossos antepassados preocuparam-se com o conjunto dos números naturais, isto é, N = {1, 2, 3…}, de que precisavam para contar objetos, comparar quantias e assim por diante. Mais tarde, quando houve necessidade, incluíram nesse conjunto o zero e os números negativos, formando assim o conjunto dos números inteiros Z = {….-3, -2, -1, 0, 1, 2, 3….}.

Com o passar dos anos, questões a respeito dos números foram aparecendo, à medida em que a humanidade explorava e tentava explicar os fenômenos naturais, os astros, enfim, a natureza. As primeiras manifestações dessas questões mais complexas datam de quase dois milênios antes de Cristo 1. Já na Grécia antiga, Pitágoras, Euclides e outros desenvolveram e deram a forma atual a conceitos como divisibilidade e primalidade.

Modernamente, a Teoria dos Números trata de questões teóricas bastante profundas e abstratas e, até poucas décadas atrás, nenhuma aplicação prática dessas teorias era conhecida. De fato, um matemático muito famoso pelo seu estudo da Teoria dos Números, G. H. Hardy, chegou a dizer que nada de útil para a humanidade jamais viria dos seus estudos 2. Desde 1976, porém, a Teoria dos Números encontrou sua grande vitrine, a criptografia. É disso que trata este texto. Antes de mais nada, porém, necessitamos de alguns conceitos básicos.

Divisibilidade e o máximo divisor comum

No ensino fundamental, aprendemos a operação de divisão de um inteiro a por outro inteiro b ≠ 0. Ao dividir a por b obtemos um número inteiro (quociente) q e outro inteiro (resto) r, este último não negativo e menor que b, tal que a = q x b + r. Por exemplo, 19 dividido por 5 resulta em q = 3 e r = 4. Quando r = 0, isto é, não há resto positivo, dizemos que b divide a (ou a é divisível por b), escrevendo b | a. Por exemplo, 3|15.

Quando a e b são dois números inteiros, o máximo divisor comum (mdc) de a e b e aquele número d tal que d divide ambos a e b, e é o maior número inteiro com essa propriedade. Por exemplo, mdc (27,18) = 9. Quando dois números têm mdc igual a 1, dizemos que os números são coprimos ou primos entre si. Por exemplo, 27 e 10 são coprimos.

Números primos e fatoração de inteiros

Um número positivo é primo se é divisível somente por 1 e por si mesmo. Os primeiros números primos são 2, 3, 5, 7, 11, 13, 17….. Existem infinitos números primos.

Um teorema famoso da Teoria dos Números diz que todo número inteiro pode ser escrito de forma única como um produto de um ou mais números (fatores) primos, por exemplo,

45 = 3 × 3 × 5 = 32 x 5,8 = 2 × 2 × 2 = 23, e 2100 = 22 x 3 × 52 x 7. Fatorar um número inteiro é exibir os seus fatores primos, isto é a sua fatoração. Assim, 22 x 3 × 52 x 7 é a fatoração de 2100.

Métodos para fatoração e testes de primalidade

Um fato importante para nós aqui é o de que não se conhecem métodos eficientes (nem mesmo com o uso de computadores poderosíssimos) capazes de fatorar números “muito grandes". Números muito grandes, no contexto da criptografia, são números com centenas ou milhares de algarismos. Por outro lado, conhecem-se métodos bastante rápidos para produzir números primos muito grandes.

Um pouquinho de criptografia clássica

Até meados do século 20, a criptografia era vista como a arte de transformar textos legíveis em textos ilegíveis, isto é, em sequências de letras, números e símbolos que não carregam informação alguma. O objetivo sempre foi o de esconder o significado real de mensagens trocadas entre duas pessoas, de forma que somente elas, de posse da regra que transformava o texto ilegível no legível, pudessem entender o seu significado.

Chamamos de encriptação ao ato de transformar um texto legível (ou texto claro) em um texto ilegível (texto encriptado). O método usado para reverter a encriptação é chamado de decriptação. A encriptação consiste não somente em um método, mas necessita também de uma informação sigilosa (a chave criptográfica), de conhecimento exclusivo das pessoas trocando mensagens. Assim, chamando de M o texto claro, de C o texto encriptado, de Enc( ) e Dec( ) aos métodos de encriptação e decriptação, e K a chave criptográfica, temos que C = EncK(M) e M = DecK(C).

Por exemplo, em textos compostos por letras do alfabeto, poderíamos supor que o método de encriptação substitui cada letra por outra letra n posições à frente no alfabeto: supomos que após a letra ‘z’ viria a letra ‘a’ e assim em diante. A chave, neste caso, é n. Assim, supondo n = 3, ao texto claro

 A câmara dos deputados fez um papelão

 corresponderia o texto encriptado (desprezamos os espaços em branco e acentos nas letras):

 D fdpdud grv ghsxwdgrv ihc xp sdshodr

O correspondente método de decriptação é fácil de deduzir: tomamos as letras n posições para trás no alfabeto. Esse método é conhecido na literatura como Cifra de César. Na era dos computadores como a nossa, esse método não é recomendado, já que é muito fácil de ser “quebrado”. Mesmo sem computadores, decriptar um texto desses é tarefa simples. Outros métodos simples consistem em embaralhar letras, substituições de letras por outras de acordo com uma tabela etc. Métodos mais robustos foram inventados ao longo dos anos, os mais famosos tendo sido empregados na Segunda Guerra Mundial, que usavam dispositivos eletromecânicos como as maquinas Enigma e Lorenz. Mesmo assim, tais métodos são hoje totalmente obsoletos, em vista do poder computacional disponível em um simples smartphone. Outros métodos que foram propostos e estão em uso resistem a ataques computacionais muito mais poderosos. 

Criptografia de chave pública

Modernamente, o que chamamos de criptografia é mais do que a encriptação de mensagens, abarcando grande número de técnicas matemáticas para provimento dos mais variados requisitos da segurança da informação como sigilo, autenticação, integridade, irretratabilidade etc.

Uma das grandes inovações trazidas pela criptografia moderna foi a possibilidade da comunicação sigilosa entre duas pessoas que jamais tenham se encontrado ou trocado qualquer informação previa. Conforme explicamos acima, a chave criptográfica K é de conhecimento exclusivo das pessoas em comunicação e, portanto, deve ser combinada entre elas, em sigilo, antes de qualquer outra comunicação sigilosa. Tradicionalmente isso era feito pessoalmente, ou por meio de mensageiros confiáveis. Modernamente, no contexto das redes de computadores, esse procedimento não é prático nem desejável.

Imagine duas pessoas que hoje usam WhatsApp, um serviço que anunciou, recentemente, o emprego de comunicação encriptada de ponta a ponta. Isto é, as mensagens são encriptadas e decriptadas nos telefones das pessoas em comunicação, trafegando pela internet totalmente encriptadas. Nem mesmo o dono do serviço WhatsApp sabe como decriptar essas mensagens, não estando sujeito, portanto, a pressões de governos ou outras organizações. Como pode ser que duas pessoas que jamais se viram, sabendo somente os números de telefones envolvidos, possam constituir um canal de comunicação tão seguro?

A resposta está na criptografia de chave pública. Proposta por W. Diffie e M. Hellman, em um artigo muito importante de 1976 5, o fundamento dessa técnica é muito simples: a chave de encriptação não deve ser igual a chave de decriptação. Vamos desenvolver essa ideia usando dois personagens populares na literatura criptográfica: Alice e Beto.

Suponha que Alice e Beto, individualmente e em sigilo, criem para si um par de chaves, que chamaremos de chave pública e chave privada. Denotamos o par de chaves de Alice por (AP, AR), onde AP é a chave pública e AR é a chave privada. Similarmente, o par de Beto é (BP; BR). Agora, cada um deles publica a sua chave pública e guarda, em sigilo e muito bem protegida, a sua chave privada.

Para encriptar uma mensagem M1 e enviá-la para Beto, Alice calcula o texto encriptado C1 da seguinte forma:

C1 = EncBP (M1)

Beto, por sua vez, decripta o texto encriptado enviado por Alice, calculando:

M1 = DecBR(C1)

Veja que somente chaves de Beto foram usadas na transmissão de Alice para Beto. Por outro lado, se Beto quiser enviar uma mensagem encriptada M2 para Alice, deve calcular:

C2 = EncAP (M2)

Alice, então, decripta o texto C2, reavendo M2:

M2 = DecAR(C2)

Note que somente chaves de Alice foram usadas na transmissão de Beto para Alice.

É importante notar que, qualquer outra pessoa, mesmo conhecendo as chaves públicas de Alice e Beto (afinal, as chaves são públicas), não conseguirá decriptar as mensagens C1 ou C2. Isto porque, para isso, são necessárias as chaves privadas de Alice e Beto, que somente eles possuem. Uma outra condição importante e evidente, é que o conhecimento da chave pública de alguém não revela a correspondente chave privada, embora as duas devam estar necessariamente relacionadas.

A publicação do artigo de Diffie e Hellman teve tremenda repercussão, muito embora não trouxesse um método concreto para implementar a dramática mudança de paradigma que se anunciava. Isso somente ocorreu pouco mais de ano depois, com a proposta do RSA, que descrevemos a seguir.

RSA: o mais popular sistema criptográfico moderno

Em outro trabalho de enorme repercussão, Ronald Rivest, Adi Shamir e Leonard Adleman 6 propuseram um método bastante simples para concretizar as ideias de Diffie e Hellman. Esse método, que ficou conhecido como RSA, usa conceitos básicos da Teoria dos Números, de forma engenhosa.

Vamos precisar antes de um pouco mais de notação: usamos a mod n para denotar o resto da divisão de a por n. Além disso, se r = a mod n, escrevemos a ≡ r (mod n), e dizemos que a é congruente a r módulo n. Por exemplo, 4 = 36 mod 8 e, portanto, 36 é congruente a 4 módulo 8, isto é, 36 ≡ 4 (mod 8).

Vamos agora descrever os passos para que Alice gere o seu par de chaves, já acompanhados de um exemplo numérico:

  1. Primeiramente, Alice gera dois números primos distintos, aleatoriamente, que chamaremos de p e q, digamos p = 11 e q = 13.
  2. Calcula n = p x q e z = (p – 1) x (q – 1). Neste caso, temos n = 11 × 13 = 143, e z = 10 × 12 = 120.
  3. Sorteia, aleatoriamente, um número e > 1 tal que mdc (e, z) = 1. Ha vários números que satisfazem essa condição no nosso caso, em que z = 120. Digamos que e = 7.
  4. Calcula o número d > 1 tal que e x d ≡ 1 (mod z). Para um dado valor de e só existe um d que satisfaz a essa condição. Neste caso, d é forçosamente igual a 103.
  5. Pronto! A chave pública de Alice é o par de números (e; n) = (7; 143) e a chave privada é o número d = 103. Veja que ninguém, exceto Alice, conhece qualquer das quantias p; q; z; d

Estamos prontos para descrever como Beto enviaria uma mensagem encriptada para Alice, usando a chave pública (e; n) = (7; 143). Em primeiro lugar, vamos convencionar que a mensagem que Beto quer enviar é um número inteiro entre 2 e n – 1, isto é, 2 e 142. Isto não é uma dificuldade, pois há vários procedimentos padronizados pela indústria de informática para conversão de textos e outros dados em números inteiros. Vamos supor que no nosso caso a mensagem M a ser encriptada seja igual a 9. A operação de encriptação é, simplesmente

C = Me mod n.

Isto é, C é o resto da divisão de Me (M elevado ao expoente e) por n. A decriptação de C dá-se de forma também simples, mas utilizando a chave privada d de Alice, isto é:

M = Cd mod n.

Vamos ao nosso exemplo numérico, encriptando M para obter C:

Me mod n = 97 mod 143 = 4782969 mod 143 = 48 = C.

Decriptando C, obtemos:

Cd mod n = 48103 mod 143 =

147179542864413390932905874598546181639251936892466523613443978367211970099291186214823254748
398552012096889459507908005379761817179818012220584043608748735887372647076462592 mod 143 = 48;

conforme esperávamos! Deixamos a verificação das contas para o nosso leitor! Use uma calculadora para números muito grandes; há muitas disponíveis na internet 3. Os cálculos acima justificam-se em razão de várias propriedades dos números inteiros que não discutiremos aqui.

O RSA na prática

O número enorme que obtivemos acima não é incomum em contextos criptográficos. O RSA é suscetível a um ataque, se existir um método rápido e eficiente para calcular a fatoração de números muito grandes, o que já dissemos que não existe. Você consegue descrever um ataque ao RSA se estiver de posse de um tal método eficiente para fatoração?

Para evitar que o RSA seja atacado por computadores modernos, é preciso usar números muito grandes. Por exemplo, os números primos p e q precisam ter pelo menos 500 algarismos, o que produz um valor de n de 1000 algarismos! Além disso, é importante que os métodos para geração de primos sejam, de fato, aleatórios, ou podemos ter a situação indesejável de duas pessoas acabarem gerando o mesmo valor de n, e que conhecem a fatoração de n!

Aplicações

Conforme já comentamos, o WhatsApp encripta mensagens usando criptografia de chave pública, não com o RSA, mas com um método que também usa técnicas da Teoria dos Números, chamado de Método das Curvas Elípticas, mais adequado a dispositivos computacionais de poder limitado, como telefones. De qualquer modo, o paradigma é o mesmo: cada telefone gera o seu próprio par de chaves, pública e privada, e disponibiliza a chave pública para os demais da comunidade WhatsApp.

Outras aplicações comuns são aquelas que utilizam chaves públicas para gerar canais encriptados para transmissão de senhas e outras informações privadas, como números de cartão de credito, quando fazemos acesso a websites que requeiram essas informações, como sites de compras, webmail etc.

Leituras adicionais 

Ao leitor interessado em mais detalhes técnicos sobre o RSA, indicamos o livro de S.C. Coutinho 4. Para leituras sobre criptografia através dos tempos, o livro de Simon Singh 7.

Referências

1   https://en.wikipedia.org/wiki/Number theory.

2   https://en.wikiquote.org/wiki/G. H. Hardy#A Mathematician.27s Apology .281941.29.

3   https://defuse.ca/big-number-calculator.htm.

4   Números inteiros e criptografia RSA. Instituto de Matemática Pura e Aplicada e Sociedade Brasileira de Matemática, 2 edition, 2000.

5   W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644-654, November 1976.6   Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120-126, 1978.

7   Simon Singh. The Code Book: the evolution of secrecy from Mary, Queen of Scots, to Quantum Cryptography. Doubleday, 1999.