CONCEITOS MATEMÁTICOS ENVOLVIDOS NO
FUNCIONAMENTO DA CRIPTOGRAFIA RSA
Cristiane Moro1
Raquel Cerbaro2
Andréia Beatriz Schmid3
Resumo: A criptografia visa garantir que somente pessoas autorizadas tenham acesso a informações
reservadas. Para enviar uma mensagem com dados sigilosos a uma pessoa é preciso codificar a
mensagem e torná-la ilegível para qualquer pessoa interceptar. A pessoa que recebe a mensagem
deve possuir o mesmo sistema criptográfico, para assim decodificar o texto, e assim poder lê-lo. O
RSA é um sistema criptográfico de chave pública, criado em 1978 por Ron Rivesti, Adi Shamir e Len
Adleman. O seu funcionamento consiste na multiplicação de dois números primos muito grandes
gerando um terceiro número. Para quebrar essa criptografia, seria necessária a fatoração desse
número para encontrar os dois números primos que o geraram, porém, para isso é necessário um
poder muito alto de processamento, o que acaba inviabilizando a tarefa, pois atualmente não existem
algoritmos de fatoração eficientes para números primos grandes. A segurança deste método baseiase na complexidade dos conceitos matemáticos inseridos na teoria dos números. Têm-se como
objetivo descrever o funcionamento da criptografia RSA, compreendendo a importância da
matemática para a segurança deste algoritmo. Trata-se de uma pesquisa bibliográfica, fundamentada
em livros, trabalhos, monografias e artigos. Aborda-se as etapas do processo criptográfico RSA, que
inicia na pré-codificação, passa pela codificação da mensagem até a sua decodificação, onde retorna
a mensagem original, mostrando após, por que o método funciona. Conclui-se, que o RSA é uma
aplicação da matemática, baseada na utilização de conceitos de congruência, fatoração e
primalidade, que por sua vez garante a segurança do método pela complexidade matemática
envolvida.
Palavras-chave: Criptografia RSA. Fatoração. Primos. Segurança.
1
Universitária do Curso de
[email protected].
Matemática-
Licenciatura
plena/ACEA/UNOCHAPECÓ.
E-mail:
Universitária do Curso de Matemá[email protected].
Licenciatura
plena/ACEA/UNOCHAPECÓ.
E-mail:
2
3
Mestra em modelagem matemática. Professora do curso de Matemática- UNOCHAPECÓ. E-mail:
[email protected].
1. Introdução
Apresentar-se-á uma conceituação geral da criptografia, donde será abordado
exclusivamente o método criptográfico assimétrico, que é atualmente um dos mais
utilizados na segurança de dados, o RSA.
Enfatiza-se, assim, o método criptográfico RSA, apresentando seus conceitos,
mostrando as etapas utilizadas para o uso do método, abordando os conceitos
matemáticos inseridos em seu funcionamento, que promovem então a sua
segurança.
A criptografia é uma área de extrema importância nos dias atuais, pela
necessidade da segurança de dados. Ela pode ser simétrica ou assimétrica. Abordase neste trabalho a criptografia assimétrica.
A
criptografia
tem
por
objetivo
principal
garantir
a
circulação
e
armazenamento de mensagens com segurança. Convertendo dados legíveis em
algo sem sentido, com a capacidade de recuperar os dados originais a partir desses
dados sem sentido. Segundo Cavalcante (2004, p.1)
A criptografia é a ciência que estuda as formas de se
escrever uma mensagem em código. Trata-se de um
conjunto
de
técnicas
que
permitem
tornar
incompreensível uma mensagem originalmente escrita
com clareza, de forma a permitir que apenas o
destinatário a decifre e compreenda.
Na criptografia de chave assimétrica utiliza-se duas chaves, a pública e a
privada. A chave pública é acessível a todos que desejam manter informações, com
ela é feita a codificação da mensagem. Já para a decodificação é necessária a
chave privada, que deve ser secreta, pois só quem possui essa chave poderá ler a
mensagem.
2. Materiais e métodos
Este trabalho apresenta-se como uma pesquisa bibliográfica, conceituando as
principais características da criptografia RSA. Foram realizadas leituras e discussões
acerca do tema criptografia RSA, objetivando perceber a importância da criptografia
RSA como segurança de redes e os conceitos matemáticos inseridos nela.
Realizando pesquisas que abordassem o assunto de forma geral, tendo a
matemática como instrumento do processo criptográfico.
Sendo a pesquisa na área da matemática aplicada e ter como tema a
criptografia RSA, tem-se que ela pode ser estendida a todos os estudantes de
matemática e sistemas de informação, bem como interessados em segurança de
dados em redes.
3. Resultado e discussão
Criptografia RSA
A criptografia RSA foi inventada em 1978 por Ron Rivesti, Adi Shamir e Len
Adleman que na época trabalhavam no Massachussets Institute Of technology. As
letras RSA correspondem as inicias dos sobrenomes dos inventores do algoritmo.
Segundo Gimenez (p.16)
O algoritmo RSA constitui um exemplo de aplicação de
várias teorias matemáticas em uma solução bastante
elegante para o problema de criptografia assimétrica, ou
de chave pública, onde as partes não possuem uma
chave secreta previamente definida e dependem de um
canal inseguro para se comunicar, como é o caso da
internet.
Desta
forma,
esse
algoritmo
se
aplica
perfeitamente em transações eletrônicas envolvendo
negócios e/ou comércio pela internet.
O RSA é muito utilizado em aplicações comerciais e a segurança desse
método se dá pela complexidade matemática, encontrada na Teoria dos números.
Para a implementação do RSA necessita-se de dois números primos grandes,
que vamos chamar aqui de p e q. O produto desses dois números primos será
chamado de n, que é a chave usada para a codificação da mensagem, ou seja, é a
chave pública. Para a decodificação basta apenas fatorar n para encontrar p e q.
Assim, a ideia principal teoricamente é simplória, porém atualmente não existem
algoritmos de fatoração eficientes para números primos grandes, pois geralmente
esses primos possuem mais de 150 algarismos, garantindo então a segurança do
método. Na sequência apresenta-se o processo do método criptográfico RSA.
Conceitos matemáticos envolvidos na criptografia RSA
Agora será feito um estudo sobre alguns princípios básicos da Teoria dos
números para a compreensão da criptografia RSA.
Números primos
Desde a antiguidade até os tempos atuais, os números primos tem atraído a
atenção de muitos estudiosos. Foram criados diversos métodos para testar a
primalidade de um número, como crivo de Eratóstenes.
Atualmente, a primalidade de números está recebendo mais atenção, pelo
fato de ser usado em diversos métodos criptográficos, como o RSA.
Definição 1. Um número p
IN se diz primo se:
i)
p 0 e p 1;
ii)
Os únicos divisores de p são 1 e p.
Um número a
IN,
e
é chamado composto se a não é primo.
Proposição 1. Se p é primo e p/ab, então p/a ou p/b.
Operações com congruências
Teorema 1: Se a
b(mod m) e se c
d(mod m) então
i) a+c
b+d(mod m)
ii) a-c
b-d(mod m)
iii) ac
bd(mod m)
Corolário: Se a
b(mod m) e se c é um inteiro qualquer, então:
Teorema 2: Se ac
i) a+c
b+c(mod m)
ii) a-c
b-c(mod m)
iii) ac
bc(mod m)
bc(mod m) e se mdc(c,m)=1 então a
b(mod m).
Teorema de fermat II
Se p é um primo e se p não divide a, então
(mod p).
Demostração: Tomamos os p – 1, primeiros múltiplos positivos de a, isto é, os
inteiros
a, 2a, 3a,..., (p - 1)a
Como p a e p 2, 3, ..., (p - 1) e p é primo, nenhum destes números é múltiplo de p.
Sejam r, s tal que
onde
(mod p)
p / ra – as
(r - s)
p / (r – s)
O que é um absurdo pela afirmação anterior.
Logo,
tal que
temos que
(mod p)
Então ra e sa deixam restos diferentes quando divididos por p, (
).
Logo, cada um desses p – 1 números são congruentes a 1, 2, ..., p -1 módulo
p. Então:
a. 2a . 3a... (p – 1)a
1. 2. 3...(p - 1) (mod p)
(p - 1)!
Como p é primo, p ( p -1)!
Corolário: Se p é primo, então
(p - 1)! (mod p)
mdc (p, (p -1)!)= 1
1 (mod p)
(mod p) , qualquer que seja os inteiros a.
Teorema chinês do resto
Sejam
inteiros positivos entre si, dois a dois, isto é, tais que o
mdc(
) = 1 se i j
Nestas condições, o sistema de congruências lineares:
Tem uma única solução módulo
Demonstração: Seja
Como os inteiros
mdc (
.
o produto de todos os inteiros
, exceto
são primos entre si, dois a dois, o mdc (
) = 1,
) = 1, pois
de modo que a congruência linear
(mod
)
(1)
Tem uma única solução
(mod
).
Posto isso, mostra-se que o inteiro
..
É uma solução do sistema considerado.
Com efeito, se
, então
e
(mod
) o que implica
..
E como o inteiro
é uma solução
da congruência linear (1) temos:
e
Logo,
é a solução do sistema.
Teorema de Euler
Definição 1: A função
de Euler de um inteiro positivo m, denotada por ( m),
é definida como o número de inteiros positivos menores ou iguais a m que são
relativamente primos com m.
Teorema de Euler: Se m é um inteiro positivo e a é um inteiro tal que
mdc(a,m)=1, então
1 (mod m)
Prova: Escrevendo
(m)= { ,
,
, ...,
, tem-se:
(
...
(mod m)
Logo,
...
Como mdc(
(mod m)
) =1, pode-se cortar o termo comum dos dois lados,
então:
1 (mod m)
Processo da criptografia RSA
Após conhecidos os principais conceitos matemáticos envolvidos na
criptografia RSA, mostrar-se-á as etapas necessárias para a codificação e
decodificação de uma mensagem.
Pré-codificação
Nessa etapa deve-se converter a mensagem em uma seqüência de números.
Ira-se supor que a mensagem original é um texto que não possui números e todas
as letras são maiúsculas. Logo, a mensagem é constituída pelas letras que formam
as palavras e pelos espaços entre palavras.
Na pré-codificação converte-se as letras em números usando uma tabela de
conversão:
Quadro 1: Tabela de conversão.
A
B
C
D
E
F
G
H
I
J
K
L
M
10
11
12
13
14
15
16
17
18
19
20
21
22
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
23
24
25
26
27
28
29
30
31
32
33
34
35
O espaço entre duas palavras será substituído pelo número 99, quando for
feita a conversão. Por exemplo, a frase AMO VOCÊ é convertida no número
1022249931241214.
Precisa-se então escolher os parâmetros do sistema RSA, que são dois
números primos distintos p e q. E temos a multiplicação deles n. Logo, n= pq.
Agora tem-se que dividir o grande número em blocos. Sendo que, esses
blocos devem ser menores que n, porém o bloco não pode iniciar com o número
zero. Por exemplo, escolhendo p= 17 e q= 23, então n= 391. Logo a mensagem
convertida será dividida em tais blocos: 102 – 224 – 99 – 312 – 41 – 214.
Codificação
No processo de codificação precisa-se de n=p.q e de um número inteiro
positivo e tal que:
Mdc (e, (p-1)(q-1))=1
O par (n,e) é chamado de chave de codificação do sistema RSA, é a chave
pública.
O bloco codificado:
C(b) = resto da divisão de
por n.
Onde b é o bloco. Ou seja,
C
No exemplo, temos:
(mod n)
Mdc (e, (p-1)(q-1))=1
Mdc (e, 16.22)=1
Mdc (e, 352)=1 , menor número é o 3.
Logo, e=3.
Codificando os blocos da mensagem anterior tem-se: o bloco 102 da
mensagem deve ser codificado com o resto da divisão de 102³ por 391. Fazendo as
contas, obtêm-se: C(102) = 34. Procede-se da mesma maneira com os outros
blocos, conforme segue no quadro 2:
Quadro 2: Codificação de AMO VOCÊ.
b
102
224
99
312
41
214
e
3
3
3
3
3
3
C
34
129
228
12
105
320
n
391
391
391
391
391
391
Desta forma a mensagem codificada será: 34-129-228-12-105-320.
Decodificação
Como p= 17, q= 23 e e = 3 tem-se:
n= p.q= 391
(p-1)(q-1)= 16. 22= 352
ed 1 (mod 352)
Pelo algoritmo euclidiano
352= 3._+1
1= 352+ (-117). 3
Logo o inverso de 3 módulo 352 é -117. Mas d deve ser >0, logo
d= 352-117= 235
Então, a decodificação dos blocos será feita da seguinte maneira:
D (34) = resto da divisão de
Pelo teorema chinês do resto:
por 391
Utilizando o Teorema de Fermat II:
11 -12
-3.4 (mod 23)
².
256
3 (mod 23)
12 (mod 23)
-3. 12
Então:
Da última congruência segue que
Substituindo na anterior
Como
-36
-13
10 (mod 23)
Como o inverso de 6 módulo de 17 é 3, tem-se:
Substituindo:
Obtendo:
Veja no quadro 3 os seguintes resultados gerados pela decodificação:
Quadro 3: Decodificação dos blocos.
C
34
129
228
12
105
320
d
235
235
235
235
235
235
n
391
391
391
391
391
391
b
102
224
99
312
41
214
Logo a mensagem decodificada é: 102 – 224 – 99 – 312 – 41 – 214. Voltando
então para a mensagem original.
Por que o método funciona
Todo método criptográfico só é válido se decodificando um bloco codificado
obtêm-se novamente o bloco inicial. No caso do sistema RSA, isto se verifica se
D(c(b)) =b. Será que isto sempre acontece?
A igualdade pode ser mostrada provando que
D(c(b)) b (mod n),
Pois tanto D(c(b)) quando b estão entre 1 e n-1, e desta forma só podem ser
congruentes módulo n se forem iguais (isto significa o fato de escolher b menor que
n).
Lembrando que
C(b)
(mod n)
D(c)
(mod n)
Tem-se:
D(c(b))
D( )
Como n=pq, vamos calcular
(mod n)
(mod p) e
(mod q).
Sabe-se que d é o inverso de e módulo (p-1)(q-1), logo
ed 1(mod (p-1)(q-1))
ed= 1+k(p-1)(q-1)
(mod n)
Supondo que p b, pelo teorema de Fermat II:
(mod p)
(mod p)
Se p b, temos que b 0 (mod p) ou seja,
Analogamente,
b(mod q).
b(mod p), qualquer que seja b.
Daí tem-se que
- b é divisível por p e q. Como p e q são primos distintos,
isto é, mdc(p,q)=1, temos que pq
. Como n=pq, conclui-se que
b(mod n), para todo b
Conclusão:
.
D(c(b))= b.
4. Considerações finais
O artigo produzido procurou conceituar a matemática que fundamenta a
criptografia RSA, salientando sua importância e definindo seus conceitos. Foram
realizadas leituras e discussões acerca do tema criptografia, objetivando perceber a
importância da criptografia como segurança de redes e os conceitos matemáticos
inseridos nela, em seguida, foram realizadas pesquisas que abordassem o assunto
de forma geral, tendo a matemática apenas como instrumento do processo
criptográfico.
Tendo em vista a questão de segurança e privacidade, na criptografia RSA,
encontra-se uma inteligência capaz de garantir essas questões, de tal forma que é
possível fazer um estudo e compreender o método a partir de conceitos
matemáticos, inseridos na Teoria dos Números. Assim, visto a explosão do comércio
eletrônico e a consequente necessidade de assegurar dados nos dias atuais, vê-se
a importância do estudo da criptografia, e aprofundamento da matemática que é
base do funcionamento desse método.
Apesar do estudo de números primos ser bastante antigo, merece a atenção
dos matemáticos pelo fato de a segurança do RSA estar na dificuldade em fatorar
um número composto, o que é no mínimo curioso.
Pelo fato de a pesquisa ser desenvolvida na área da matemática aplicada e
por ter como tema a criptografia, entende-se que ela pode ser estendida a todos os
estudantes de matemática e sistemas de informação, bem como interessados em
segurança de dados em redes.
5. Referências
BUCHMANN, Johannes. Indução à criptografia. São Paulo: Berkeley Brasil, 2002.
BURNET, Steve. Criptografia e segurança. Rio de Janeiro: Campos, 2002.
CAVALCANTE, André L.B. Teoria dos números e Criptografia. Disponível em:
http://system7.upis.br/revistavirtual/Cavalcante_%20Teoria%20dos%20N%FAmeros
%20e%20Criptografia_2005_UPIS.pdf. Acesso em: 23 nov.2010.
COUTINHO, S.C. Números inteiros e criptografia RSA. 2.ed. Rio de Janeiro:
IMPA/SBM, 2000.
COUTINHO, Severino Collier. Criptografia. Programa de iniciação científica
OBMEP.
DOMINGUES, Hygino H.. Fundamentos da Aritmética. São Paulo: Atual, 1991.
GIMENEZ, José Roberto Bollis. Implementação do algoritmo RSA. Disponível em:
http://www.unesp.br/ ~jroberto/rsa.pdf. Acesso em: 01 mai. 2011.
OLIVEIRA, Ednei Rodrigues. Criptografia RSA. Disponível em:
http://www.ime.unicamp.br.torres/ENSINO/MONOGRAFIAS/ednei_RSA.pdf. Acesso
em: 18 set. 2010.
PIMENTEL, Elaine Gouvêa. Teoria dos números e criptografia RSA. Minas
Gerais: Abril, 2006.
SILVA, Elen Viviane Pereira da. Introdução a criptografia RSA. Disponível em:
http://www.impa.br/opencms/pt/eventos/downloads/jornadas_2006/trabalhos/jornada
s_elen_pereira.pdf. Acesso em: 15 out. 2010.
STALLINGS, William. Criptografia e segurança de redes: princípios e práticas. 4.
ed. São Paulo: Pearson Prentice Hall, 2008.