CRIPTOGRAFIA DE CHAVE PÚBLICA –
O PAPEL DA ARITMÉTICA EM PRECISÃO MÚLTIPLA
Aline Sousa da Silveira* (IC), Antonio Cândido Faleiros (PQ)
Divisão de Ensino Fundamental – IEF
Instituto Tecnológico de Aeronáutica
Contato: [email protected]
Resumo
A criptografia de chave pública é um método de codificação muito utilizado hoje em dia, e estudos
profundos foram feitos para o aperfeiçoamento da segurança desse sistema. Entretanto, essa ciência
precisa ser constantemente aprimorada devido ao avanço exponencial da velocidade dos computadores,
os quais estão se tornando cada vez mais capazes de fazer uma criptoanálise eficiente em um tempo
relativamente curto. Um fator importante para garantir a segurança de um cifrário é o tamanho das
chaves, que precisam ter centenas ou mesmo milhares de bits. Contudo, as variáveis inteiras sem sinal
comuns de um processador de 32 bits podem armazenar valores apenas de zero a 232 – 1, então, é
necessário descobrir maneiras de representar os números grandes em um computador e operar com eles.
Esse é um dos objetivos desta pesquisa: estudar aritmética de precisão múltipla, a ciência que cria
algoritmos que fazem cálculos com números representados em mais de uma variável. Esses algoritmos já
estão implementados em uma biblioteca gratuita, a GMP (GNU Multiple Precision), cujo estudo foi outro
objetivo da pesquisa. A meta final deste trabalho foi a implementação de dois dos cifrários de chave
pública mais utilizados, RSA e ElGamal, usando a biblioteca GMP.
Abstract
Public-key cryptography is a wide-spread ciphering method nowadays, and deep studies have been made
on the enhancement of the security of this system. However, this science needs to be continuously
improved due to the exponential advancement of the speed of the computers, which are becoming more
and more able to do an efficient cryptanalysis in a relatively short time. An important factor to guarantee
the safeness of a cryptosystem is the size of the keys, which need to have a length of hundreds or even
thousands of bits. Nevertheless, the standard unsigned integer variables of a 32-bit processor can only
store values from zero to 232 – 1, so, it is necessary to discover ways to represent the big numbers in a
computer and operate with them. This is one of the objectives of this approach: to study multiple-precision
arithmetic, the science of creating algorithms which make computations with numbers represented in
more than one variable. These algorithms are already implemented in a free library, the GMP (GNU
Multiple Precision), whose study was another objective of the approach. The final goal of this work was
the implementation of two of the most used public-key cryptosystems, RSA and ElGamal, using the GMP
library.
1. INTRODUÇÃO
Com o advento da Internet, a criptografia tornou-se uma ciência essencial para a segurança das
informações que circulam por todo o mundo. Existem muitos tipos de dados que devem ser mantidos em
sigilo, como correspondências pessoais, senhas para transações financeiras, dados governamentais e
outros. Devido a isso, foram feitas pesquisas exaustivas sobre como melhorar os métodos criptográficos
de forma a dificultar a criptoanálise (descoberta do código por pessoa indesejada).
Na criptografia de chave pública, a entidade que deseja receber informações secretas divulga
publicamente números inteiros positivos que constituem sua chave pública. Qualquer pessoa que deseje
enviar essas informações usa essa chave em um algoritmo de chave pública para criptografar a mensagem.
* Bolsista do CNPq – Brasil
Depois de cifrada, essa mensagem só poderá ser decodificada pela entidade que publicou a chave, pois
apenas ela possui a chave privada, que deve ser usada no algoritmo de decodificação.
Os algoritmos de chave pública devem ser funções de difícil inversão, para que o público em geral
não consiga obter a chave privada a partir da chave pública. Além disso, os inteiros envolvidos devem ser
extremamente grandes, da ordem de centenas de dígitos decimais (centenas ou milhares de bits), para que
um computador avançado não consiga testar todas as combinações possíveis em tempo hábil. Entretanto,
as variáveis inteiras positivas comuns de um processador de 32 bits conseguem armazenar apenas
números até 232 – 1, e é preciso utilizar maneiras especiais para operar com números maiores que esses.
Um dos objetivos deste trabalho de iniciação científica foi, justamente, aprender maneiras de se
representar inteiros grandes (denominados inteiros de precisão múltipla) no computador e operar com
eles. Foram estudados algoritmos de operações básicas, modulares, exponenciais e outros, além de
estruturas de dados para a implementação desses algoritmos. Hoje em dia, existem bibliotecas prontas de
funções que usam esses algoritmos e o estudo de uma delas, a GMP (GNU Multiple Precision), foi outro
dos objetivos do trabalho. E, finalmente, foram implementados com o uso da GMP os cifrários mais
usados na criptografia de chave pública atual, o RSA e o ElGamal.
2. METODOLOGIA
As etapas deste trabalho seguiram a ordem abaixo:
• Na referência [1], estudo dos principais algoritmos de precisão múltipla, envolvendo
operações básicas, modulares, exponenciação rápida e outras;
• Estudo das estruturas de dados das referências [2], [3] e [4];
• Comparação entre essas estruturas de dados;
• Estudo do manual da GMP (referência [5]);
• Integração da GMP em um compilador C++;
• Estudo e implementação do RSA, utilizando as funções da biblioteca GMP;
• Estudo e implementação do ElGamal, utilizando as funções da biblioteca GMP.
3. OPERAÇÕES EM PRECISÃO MÚLTIPLA
3.1. Representação de inteiros em base b
A grafia usual de um número, por exemplo, 4351, segue determinadas regras. Uma delas é o valor
posicional: cada dígito desse número representa um acréscimo que, além de depender do dígito em si,
depende da sua posição no número. A primeira posição contando da direita para a esquerda é ocupada
pelo dígito 1, o qual tem valor relativo 1.100 = 1. Já o 5, como está na segunda posição, tem valor 5.101 =
50. Seguindo essa consideração, o 3 tem valor relativo 300 (3.102) e o 4, 4000 (4.103). O número final é a
soma dos valores relativos de seus dígitos.
Nesse caso, o número 4351 foi escrito na base 10, pois essa era a base das exponenciações que
eram multiplicadas por cada dígito para resultar em seu valor relativo. Pode-se usar outras bases, um
exemplo é a base 2, usada nos computadores; outros são as bases 4, 8 e 16 (que usa letras para representar
os dígitos excedentes), usadas para simplificar as notações em base 2. O valor relativo de cada dígito
segue a mesma regra da base 10, por exemplo, (110101)2 = 1.25 + 1.24 + 0.23 + 1.22 + 0.21 + 1.20 = (53)10.
Se a base for denotada por b, o número de dígitos possíveis é sempre b e seus valores absolutos são de
zero a b-1.
A utilidade desse raciocínio para este trabalho é que ele pode ser estendido às variáveis inteiras do
computador. Em um processador de 32 bits, como cada variável inteira sem sinal do tipo longo (unsigned
long) pode armazenar um número de zero a 232 – 1, elas podem ser consideradas como dígitos de base 232.
Dessa forma, um inteiro positivo grande pode ser representado como um vetor de variáveis unsigned long,
com o expoente do valor relativo de cada dígito sendo igual ao índice da variável no vetor.
A definição formal de inteiro de precisão múltipla é: inteiro representado por mais de um dígito.
No caso citado acima, seriam os números maiores que 232 – 1. Contudo, na prática, os dígitos da base mais
usada ocupam a metade dos bits da variável, no caso dos processadores de 32 bits, essa base é 216. A razão
para isso é que é necessário fazer operações com esses dígitos, inclusive multiplicações, e esses resultados
não podem exceder a capacidade máxima das variáveis. Isso ficará mais claro a seguir, quando serão
tratados os algoritmos de precisão múltipla.
3.2. Operações básicas
Os algoritmos clássicos para as quatro operações aritméticas básicas: adição, subtração,
multiplicação e divisão com resto são adaptações computacionais dos métodos aprendidos na escola
primária para a execução dessas operações com inteiros de precisão múltipla em base 10. Por exemplo, na
adição, começa-se somando os dígitos da primeira posição contando da direita para a esquerda,
denominados dígitos menos significativos. Se o valor exceder a base (10 no método de lápis e papel, 216 no
computador), é feita uma redução módulo b (deixa-se no dígito do resultado apenas o valor do resto da
divisão da soma por b), soma-se o quociente à soma dos próximos dígitos dos dois números e guarda-se a
soma total no próximo dígito do resultado. Esse processo é repetido até o último dígito do maior número
e, se essa soma exceder b, o quociente é guardado em um dígito a mais. Esse dígito que é somado à
próxima soma de dígitos é denominado carry e, na adição, pode valer zero ou um.
A subtração é análoga, com carry igual a zero ou -1, sendo -1 quando o resultado da subtração for
negativo. A redução de números negativos módulo b é feita somando sucessivamente b até o resultado
ficar positivo. No caso do computador, como estamos lidando com variáveis sem sinal (apenas o carry
com sinal) e o resultado, se for negativo terá módulo menor que b, essa base é somada diretamente ao
resultado, o qual, se necessário, sofre uma redução módulo b convencional antes de ser atribuído ao dígito
correspondente da soma.
No método escolar para a multiplicação, cada dígito de um dos fatores é multiplicado por todos os
outros dígitos do outro fator, primeiramente pelo menos significativo, com redução módulo b e adição de
carry, se necessário (nesse caso, o carry pode variar de zero a b-1. Multiplica-se todos os resultados
parciais por bi, onde i é o índice do dígito do primeiro fator mencionado (isso é apenas um deslocamento
da representação em base b para a esquerda: acréscimo de zeros) e soma-se todos eles ao resultado final. O
algoritmo computacional é um pouco diferente: à medida que os produtos parciais são calculados, eles são
somados diretamente ao dígito correspondente a i + j, onde i e j são os índices dos dígitos envolvidos,
também com redução módulo b e adição de carry, se houver necessidade. Há um algoritmo para elevar
números ao quadrado que toma vantagem da existência de produtos parciais repetidos e tem
aproximadamente o dobro da eficiência do algoritmo de multiplicação convencional.
Para a divisão, no método escolar, verifica-se qual é o menor número formado pelos dígitos mais
significativos do dividendo que é maior que o divisor, descobre-se qual é o maior dígito cujo produto pelo
divisor é menor que o número verificado, atribui-se ao dígito mais significativo do quociente o valor desse
dígito, subtrai-se do número primeiramente verificado o produto e acrescenta-se ao final da diferença o
próximo dígito não utilizado do dividendo. Repete-se esse procedimento para o número resultante desse
acréscimo e o divisor, atribuindo o dígito encontrado ao próximo dígito do quociente, até acabarem os
dígitos do dividendo. A última diferença resultante é o resto. No algoritmo computacional, há um método
para encontrar os dígitos do quociente no qual é necessário o teste de apenas três valores para cada dígito.
Esse método é detalhado na referência [2].
3.3. Operações modulares
Como já mencionado, a redução modular consiste em encontrar o resto da divisão do número pelo
módulo pretendido. O algoritmo clássico de redução modular em precisão múltipla é aplicar o algoritmo
de divisão ao número e ao módulo e tomar o resto. Entretanto, esse é o algoritmo básico que demanda
maior esforço computacional, devido à grande quantidade requerida de subtrações e multiplicações em
precisão múltipla. Existem alguns algoritmos de redução modular 1que procuram evitar essa divisão. Na
adição e subtração modulares, quando os inteiros envolvidos são menores que o módulo m, a redução é
bastante simples. Na adição, se a soma for menor que m, o resultado da redução é ela própria, se for
maior, subtrai-se dela m, apenas uma vez. Na subtração, se o resultado for positivo, ele é mantido, se for
negativo, soma-se m. Se estiverem sendo usadas apenas variáveis sem sinal, pode-se fazer a comparação
entre as magnitudes e, se a do minuendo for a menor, soma-se m a ele antes da subtração.
Na multiplicação, como o resultado pode ser muitas vezes maior que o módulo, é bastante usado o
algoritmo clássico. Há métodos que são mais eficientes em determinadas situações, como a Redução de
Montgomery, em exponenciações, e a Redução de Barrett, quando se fazem muitas reduções com o
mesmo módulo. Todos esses algoritmos são descritos na referência [1].
3.4. Exponenciações modulares
Graças a uma propriedade das operações modulares, (a.b) mod m = (a mod m . b mod m) mod m
(a mod m é a redução de a módulo m), é possível se fazer exponenciações modulares no computador. A
maneira mais óbvia para isso seria calcular xy mod m com y multiplicações e reduções sucessivas de x. No
entanto, o fato de o expoente poder ter até milhares de bits torna essa operação inviável.
O método mais clássico de exponenciação modular rápida é a exponenciação binária. Seja A a
variável onde será guardado o resultado de xy mod m e S uma variável auxiliar. Primeiramente, atribui-se
1 à variável A e x a S. Se o bit menos significativo de y for 1 (y ímpar), multiplica-se A por S. Em
seguida, divide-se y por 2 (essa divisão é apenas um deslocamento para a direita da representação binária
de y), atribui-se a S o valor de S2 mod m e, se o bit menos significativo do novo valor de y for 1,
multiplica-se novamente A por S. Repete-se esse procedimento até o valor de y ser zero e retorna-se o
valor de A (na segunda iteração, S será igual a x2 mod m; na terceira, x4 mod m, e assim por diante). O
número de iterações será o número de bits de y.
Há outros métodos mais eficientes, como a exponenciação em blocos de k bits e a exponenciação
de Montgomery, que evita o algoritmo clássico de divisão nas reduções modulares. Além desses, há os
algoritmos de expoente fixo e os de base fixa, vantajosos quando se fazem muitas exponenciações com o
mesmo expoente e com a mesma base, respectivamente. Os algoritmos de expoente fixo são úteis na
codificação e decodificação do RSA e na decodificação do ElGamal. Os algoritmos de base fixa são úteis
na codificação do ElGamal. Todos os métodos aqui mencionados estão descritos na referência [1].
3.5. Outras operações
Além das mencionadas acima, as outras aplicações de interesse criptográfico estudadas foram o
teorema chinês do resto, enunciado na referência [1], e a determinação do máximo divisor comum, com
destaque para o algoritmo de Euclides estendido, que é útil devido à sua possível utilização para encontrar
o inverso de um número x módulo m. x-1 mod m é um número y entre 1 e m – 1 tal que (x.y) mod m = 1.
Ele só existe se mdc (x,m) = 1 e, se existir, é único. Esse conceito é importantíssimo para a criptografia e,
neste trabalho, é usado no RSA.
4. ESTRUTURAS DE DADOS
Após a criação de um algoritmo, é necessário implementá-lo no computador. No caso das
operações em precisão múltipla, deve-se encontrar uma maneira eficiente de representar os inteiros, e a
representação em um vetor de dígitos em base b é a mais comumente usada. Além do valor do inteiro, é
bom que seja gravado em uma variável o seu número de dígitos, para leitura conveniente pelos algoritmos.
Isso pode ser feito usando um dos elementos do vetor ou em uma estrutura contendo um vetor para o valor
do número em base b e uma variável simples para o número de dígitos.
As estruturas de dados mencionadas nas referências [2], [3] e [4] são ligeiramente diferentes. Na
referência [4], são usadas variáveis de 32 bits e base 216. Na referência [2], é também usada a base 216,
mas as variáveis do vetor são do tipo int, com apenas 16 bits. Os resultados das operações são gravados
em uma variável simples de 32 bits e apenas a redução módulo b é gravada nos dígitos. Isso é vantajoso
apenas devido à redução de memória ocupada, mas não diminui o tempo de execução dos algoritmos, pois
o número de dígitos dos inteiros envolvidos é o mesmo. Na referência [3], a base usada é a capacidade
máxima do processador. Isso pode ser feito na programação em assembly, já que se tem acesso ao bit de
carry do processador, mas na programação em alto nível, é necessário usar a metade dos bits.
5. BIBLIOTECA GMP
A biblioteca GMP, cujo manual é a referência [5], possui algoritmos eficientes de precisão
múltipla reunidos em funções prontas, as quais necessitam apenas serem chamadas. Pode operar com
inteiros, racionais e números de ponto flutuante e as funções inteiras, que são as de interesse para a
criptografia, são aproximadamente 150. Ela foi incorporada ao compilador Visual C++ 7.0 e usada na
implementação dos cifrários RSA e ElGamal.
A GMP define o tipo inteiro de precisão múltipla, de tamanho variável e expansível, como mpz_t
e todas as funções inteiras começam com mpz_. Essas variáveis precisam ser inicializadas e, quando não
forem mais usadas, terem seus espaços limpos. Um exemplo de função inteira é mpz_powm (mpz_t rop,
mpz_t base, mpz_t exp, mpz_t mod), que é a exponenciação modular e atribui a rop o valor de
baseexp mod mod. Por convenção, a variável de saída é sempre o primeiro argumento. As variáveis mpz_t
já são de chamada por referência, por isso, elas podem ser passadas a funções criadas pelo usuário e ter
seus valores alterados dentro da função sem necessidade da passagem de ponteiros.
A GMP possui também comandos de entrada e saída, respectivamente gmp_scanf e gmp_printf,
que lêem e imprimem números grandes na sua representação normal em base 10. Com o acréscimo da
biblioteca stdio.h, a GMP pode também ler e imprimir os números grandes em arquivos, em qualquer base
de 2 a 36, sendo que essa última utiliza os dígitos de 0 a 9 e todas as letras do alfabeto inglês. Com esses
comandos e mais as funções de operações internas, a implementação dos cifrários se tornou bastante
simples.
6. CIFRÁRIOS DE CHAVE PÚBLICA
Para se criptografar uma mensagem, é necessário primeiro transformá-la em um número. Para
isso, nesta implementação dos cifrários RSA e ElGamal, dividiu-se a mensagem em pacotes de 127
caracteres no RSA e 63 no ElGamal, devido ao fato de, no RSA, os números envolvidos terem 1024 bits e,
no ElGamal, 512. A uma variável mpz_t, somou-se o valor numérico do código ASCII do primeiro
caractere, o do segundo caractere multiplicado por 256 (o tamanho de um byte), o do terceiro multiplicado
por 2562 e assim por diante. Depois disso, criptografaram-se os números assim formados da mensagem
inteira e eles foram gravados em um arquivo. Para decifrar, aplicou-se o algoritmo de decodificação,
foram feitas divisões sucessivas por 256 e, em cada uma delas, transformou-se o resto em um caractere
com esse código ASCII e esse caractere foi impresso em outro arquivo. Os detalhes da codificação são
descritos a seguir.
6.1. RSA
Para implementar um sistema RSA, primeiramente uma entidade A gera dois números primos
aleatórios grandes p e q e os multiplica, dando origem ao número n. Em seguida, ela calcula φ = (p-1)(q-1)
e gera um número aleatório e menor que φ tal que mdc (e,φ) = 1. Depois disso, A calcula d = e-1 mod φ. A
chave pública é {e,n} e a chave privada é {d,n}.
Para criptografar uma mensagem m, uma entidade B adquire a chave pública de A, calcula c = me
mod n e envia c para A. Para decifrá-la, A calcula m = cd mod n. A segurança desse método está na
dificuldade em decompor um número grande em fatores primos, principalmente se esses fatores também
forem grandes. Se alguém conseguisse descobrir p e q a partir de n, poderia calcular φ e, como e é público,
calcularia d usando o algoritmo de Euclides estendido. Para que o RSA seja seguro, e e d não devem ser
pequenos.
6.2. ElGamal
No ElGamal, todas as entidades podem ter os mesmos números p e α, sendo p um número primo
grande e α um gerador de Zp* (conjunto {x | 1 ≤ x ≤ p – 1}). Gerador de Zp* é um número α tal que a
função αx mod p seja injetora nesse conjunto. Então, uma entidade A gera um número aleatório a entre 1 e
p – 1 e calcula β = αa mod p. A chave pública será {β,p,α} e a chave privada, {a}.
Para cada m, B gera um número aleatório k e calcula γ = αk mod p e δ = (m.βk) mod p, enviando,
em seguida, {γ,δ} para A, que decifra a mensagem calculando m = (γp – 1 – a. δ) mod p (γp – 1 – a é igual a α-ak
e δ é igual a m.αak). A segurança do ElGamal está baseada na dificuldade em se tirar logaritmos discretos
de números grandes, ou seja, de se obter a a partir de β, p e α (a = logαβ mod p). a e β devem ser grandes,
além disso, deve-se escolher um k diferente para cada m.
7. CONCLUSÃO
Analisando os fatores de segurança dos cifrários apresentados, conclui-se que a aritmética de
precisão múltipla é uma necessidade para a criptografia moderna devido ao crescente avanço dos
computadores, que se tornam capazes de fazer uma criptoanálise cada vez mais rápida, para números cada
vez maiores. Alguns dos algoritmos estudados são bastante eficientes e vários deles estão reunidos na
biblioteca GMP, que facilita muito a implementação dos sistemas criptográficos. Para um processador de
32 bits, a maior base possível em uma programação de alto nível é 216, esse número, aliado a um bom
algoritmo, já torna viáveis os cálculos.
Todo esse trabalho de iniciação científica visou entender a relação entre a aritmética de precisão
múltipla e a criptografia de chave pública, objetivo que foi atingido. A implementação dos cifrários
funcionou bem e tem um nível de segurança aceitável para aplicações criptográficas reais. Esse nível só
foi possível graças ao uso dos inteiros de precisão múltipla. Portanto, a pesquisa teve uma boa utilidade
prática, além de ter sido uma excelente fonte de aprendizado.
AGRADECIMENTOS
Agradecemos ao aluno de mestrado Gabriel Marchesan Almeida, por sua ajuda na integração da
GMP em um compilador do Windows, o Visual C++ 7.0.
REFERÊNCIAS BIBLIOGRÁFICAS
1. Menezes, A.J.; Oorschot, P.C. van; Vanstone, S.A.; Handbook of Applied Cryptography; CRC
Press, 1996.
2. Welschenbach, M.; Cryptography in C and C++; Apress, 2001.
3. Gathen, J. von zur; Gerhard, J.; Modern Computer Algebra; Cambridge University Press, 2003.
4. Rosing, M.; Implementing Elliptic Curve Cryptography; Manning, 1999.
5. Granlund, T.; The GNU MP, The Multiple Precision Arithmetic Library; Edition 4.1.2, Free
Software Foundation, 2002.