3
Pró-Reitoria de Graduação
Curso de Licenciatura em Matemática
Trabalho de Conclusão de Curso
[Digite o
título do
documento]
[Digite o subtítulo do
PRÓ-REITORIA
DE GRADUAÇÃO
documento]
TRABALHO DE CONCLUSÃO DE CURSO
CRIPTOGRAFIA RSA
Sherley
Matemática
Autor:
Amanda Oliveira Fonseca
CIFRA
DE HILL
Orientador: Haendel Lins
Autor: Elaine da Silva Mantovani
Orientador: Sinval Braga de Freitas
Brasília - DF
2012
4
AMANDA OLIVEIRA FONSECA
CRIPTOGRAFIA RSA
Artigo apresentado ao curso de graduação em
Matemática da Universidade Católica de
Brasília, como requisito parcial para obtenção
do Título de Licenciado em Matemática.
Orientador: Haendel Lins
Brasília
52012
3
Artigo de autoria de Amanda Oliveira Fonseca, intitulado “CRIPTOGRAFIA RSA”,
apresentado como requisito parcial para obtenção do grau de Licenciado em Matemática da
Universidade Católica de Brasília, em 29 de novembro de 2012, defendido e aprovado pela
banca examinadora abaixo assinada:
_____________________________________________________
Prof. Haendel Lins
Orientador
Matemática – UCB
_____________________________________________________
Prof. MSc. Sinval Braga de Freitas
Matemática - UCB
_____________________________________________________
Prof. MSc. Vilmondes Rocha
Matemática – UCB
Brasília
2012
3
CRIPTOGRAFIA RSA
AMANDA OLIVEIRA FONSECA
Resumo:
Esse artigo foi desenvolvido, primeiramente, pela curiosidade de como fazer aplicações
utilizando a Teoria dos Números, pois ao estudar esta disciplina durante o curso de
Licenciatura em Matemática muitos não sabem aplicá-la ou não a compreendem. E para
quebrar paradigmas, este artigo mostra como é feito o uso da Matemática em um ramo que
necessita transmitir muita segurança para seus usuários. Para iniciar este trabalho, haverá uma
breve história de quando surgiu a criptografia, relatando as mais importantes. A partir daí, o
tema limita-se apenas ao Algoritmo RSA, no qual é abordado a pré-codificação e em seguida
a codificação e a decodificação. É claro que, para obter segurança, é preciso utilizar números
muito grandes, mas será feita apenas uma mostra da criptografia RSA para provar porque ele
é o sistema de chave-pública mais utilizado.
Palavras-chave: Teoria dos números. Criptografia. Algoritmo RSA. Chave-pública.
1. INTRODUÇÃO
Sabe-se que nos últimos tempos houve uma popularização das redes sociais e um
avanço da internet e meios eletrônicos. Com esse crescimento, é preciso mais segurança para
os documentos. Então foram criadas senhas para que não ocorram falsificações. Isso foi feito
utilizando técnicas de criptografia dinâmicas e eficientes.
As bases desses estudos estão em Teoria da Informação e em Teoria dos Números,
áreas da matemática para se aplicar em segurança de dados. Dessa forma, foi estudado o
algoritmo RSA e até onde responde sua segurança.
Essa pesquisa é necessária para demonstrar a dinâmica do que às vezes não faz sentido
quando se estuda apenas a teoria. Dessa forma, poderá ser útil tanto para profissionais e
estudantes de Engenharia de Computação, Comunicação, quanto para curiosos da
Matemática, que, muitas vezes, não compreendem onde aplicar alguns conceitos estudados,
como por exemplo, teoremas de Euler e Fermat, a função φ de Euler, entre outros conceitos.
2. A ARTE DA CRIPTOGRAFIA
Do grego, criptografia quer dizer “escrita secreta”, ou seja, são adotadas técnicas para
aplicar em uma mensagem legível e transformá-la em ilegível para que apenas remetente e
destinatário a conheça.
Desde a invenção da escrita, houve a necessidade de obter informações secretas entre
as pessoas, então apareceram vários métodos de escrita secreta, mais o primeiro conhecido é a
Cifra de César que data 58 a.C e recebe esse nome devido Júlio César (Imperador Romano).
4
A cifra de César era de forma manual e monoalfabética, ou seja, utilizava-se apenas
um alfabeto cifrado, onde cada letra do alfabeto correspondia a três letras à frente.
Tabela 1: Cifra de César
B
C
D
E
F
G
A
D
N
Q
O
R
P
S
Q
T
E
H
F
I
G
J
H
K
I
L
J
M
K
N
L
O
M
P
R
U
S
V
T
W
U
X
V
Y
W
Z
X
A
Y
B
Z
C
Com a facilidade em criptografar e decriptografar, cifras monoalfabéticas já não eram
tão seguras, pois bastava encontrar uma sílaba que a cifra era quebrada. Com o
desenvolvimento da criptoanálise (método utilizado para quebrar uma cifra) e a contagem de
frequência de caracteres as cifras monoalfabéticas já não tinham mais segurança nas
informações. Após essa guerra entre Criptografia e Criptoanálise, houve um grande avanço na
arte de esconder e enfim, o novo método criptográfico era polialfabético, ou seja, utilizava
mais de um alfabeto cifrado. Então, Blaise Vigenère utilizou o método polialfabético que era
muito seguro para a época e demorou 291 anos para ser quebrado, se baseava na cifra de
César, utilizando 26 alfabetos codificados. O quadro dessas codificações utilizadas por Blaise,
era chamado de “Quadrado de Vigenère”.
Tabela 2: Quadrado de Vigenère
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Para utilizar o quadrado de Vigenère, era preciso uma mensagem e uma chave para
cifrar. Por exemplo, se a mensagem fosse NÃO e a chave TIM o texto cifrado ficaria GIA.
Para cifrar por esse método, procuramos, na 13ª linha (que começa com a letra N), a letra que
está na coluna T (no caso, G). Mas digamos que a mensagem fosse AMANDA e a chave para
cifrar fosse à mesma utilizada anteriormente, TIM, então era preciso repetir a chave até obter
o mesmo número de letras da mensagem, ou seja, a chave seria TIMTIM e logo a mensagem
cifrada seria TUMGLM.
Com a evolução tecnológica e o descoberta dos primeiros computadores houve um
grande avanço na criptografia e a necessidade de mais segurança. Foi então que, em 1978, foi
publicado o algoritmo de chave-pública conhecido como algoritmo RSA, baseado nos estudos
de Diffie-Hellman sobre chaves assimétricas.
5
3. CRIPTOGRAFIA RSA
A criptografia RSA recebe este nome devido a seus criadores, Rivest, Shamir e
Adleman, pesquisadores do Massachussets Institute of Technology (MIT). O RSA não é o
único código de chave-pública, mas atualmente é o mais utilizado em aplicações comerciais.
(Coutinho,2005). Seus estudos foram baseados na Matemática, mais precisamente em
conhecimentos básicos da Teoria dos Números. O que dificulta a quebra desse algoritmo é a
fatoração de enormes números inteiros em primos.
Nesse sistema, o usuário possui duas chaves, uma pública (P ) que pode ser divulgada
e utilizada por qualquer pessoa. Essa chave criptografa uma mensagem, ou seja, qualquer
pessoa pode criptografar algo. Já a chave privada ou secreta (S ) decodifica a mensagem. É
mais sigilosa, pois apenas o destinatário a conhece e consegue decriptografá-la. Se x é um
texto legível, S é a chave secreta e P a chave pública, então a aplicação S ( x) = y e
P ( y ) = x . Para quem conhece as chaves, os cálculos são computacionalmente fáceis, mas
para quem não as conhece torna-se complicado calcular S a partir da chave P . (TERADA,
2008).
Dessa forma, esse sistema mostra-se seguro e eficaz, dificultando a ação de pessoas
não autorizadas.
3.1. ENTENDENDO O SISTEMA RSA
A codificação de uma mensagem não é tão complexa quanto imaginamos, mas para
que não haja erro é preciso alguns conhecimentos e cuidados. A base do RSA está no produto
de dois números primos extremamente grandes e a quebra só será possível, devido a
fatoração. Porém, não é preciso ter um conhecimento profundo, basta apenas uma breve
introdução de Teoria dos Números e já conseguimos criptografar uma mensagem no sistema
RSA. O cuidado necessário consiste em fazer uma pré-codificação, para que não haja nenhum
duplo sentido ou ambiguidade ao codificarmos ou decodificarmos uma mensagem.
3.1.1. Pré-Codificação
Segundo Coutinho, a pré-codificação é necessária para que não haja ambiguidade na
mensagem, ou seja, a mensagem criptografada pelo usuário deve ser a mesma recebida e
decodificada pelo destinatário. Para que não ocorra erro, é preciso fazer com que cada letra
tenha um número que a corresponda, e podemos fazer da seguinte maneira:
A
11
N
24
Tabela 03: Codificação
B
C
D
12
13
14
O
25
P
26
Q
27
E
15
F
16
G
17
H
18
I
19
J
20
K
21
L
22
M
23
R
28
S
29
T
30
U
31
V
32
W
33
X
34
Y
35
Z
36
6
Outra atenção que devemos ter é quanto ao espaço entre as palavras, caso a mensagem
seja um texto ou uma frase. Por esse motivo, nosso espaço corresponderá ao número 55.
Portanto, para o nome AMANDA FONSECA, teríamos a seguinte codificação:
1123112414115516252429151311.
Mas o que aconteceria se a tabela fosse a seguinte?
A
1
N
14
Tabela 04: Erro
B
C
2
3
O
15
P
16
D
4
E
5
F
6
G
7
H
8
I
9
J
10
K
11
L
12
M
13
Q
17
R
18
S
19
T
20
U
21
V
22
W
23
X
24
Y
25
Z
26
Agora a palavra para ser codificada seria ADAO que, em números, é igual a 14115.
Ao decodificar, o destinatário poderia interpretar as letras AD como N, pois recebe o número
14 na tabela, ou AO como KE, e rapidamente a mensagem ADAO passaria a ser NKE. Por
esse motivo cada letra deve corresponder a dois algarismos, pois assim evitamos
ambiguidades.
3.1.2. Codificando e decodificando uma mensagem no RSA
Para codificar no sistema RSA, precisamos de dois números primos que tenham
valores diferentes, que receberão o nome de p e q . Eles serão necessários para a codificação
e decodificação de uma mensagem e apenas o usuário terá acesso a esses números. A partir
deles vamos obter n : basta apenas multiplicar p e q .
n = p.q
(1)
Os valores utilizados para a codificação são o par de chaves (n, e) , logo essa será
chamada de chave-pública, onde e é um menor número relativamente primo a φ (n) e deve
satisfazer as condições do “pequeno teorema de Fermat”, ou seja, mdc (φ (n), e) = 1.
(TERADA, 2008).
Para calcular a função φ (n) de Euler é preciso conhecer p e q , pois essa função é
multiplicativa e para números primos o cálculo é da seguinte forma:
φ (n) = ( p − 1).(q − 1)
(2)
Segundo Terada, se considerarmos uma mensagem legível expressa em números
inteiros e separada em blocos representado por x , então, 0 ≤ x ≤ n − 1 , ou seja, cada bloco
não poderá ser negativo e deverá ser menor que n . Então, em cada bloco que foi separado,
será aplicada a congruência a seguir:
x e ≡ y (mod n)
(3)
7
Ao dividirmos x e por n, obtemos o resto y que será a mensagem codificada, pois,
x e ≡ y (mod n) é o mesmo que x e = kn + y , para qualquer k ∈ Ζ .
Para decodificar uma mensagem, utilizaremos também um par de chaves (n, d ) . Esta
será a chave privada, pois apenas o usuário e o destinatário terão acesso a ela. O n é o mesmo
utilizado na codificação e o d é um número inverso ao e módulo φ (n) . (Coutinho,2005).
e.d ≡ 1 (mod φ (n))
(4)
Após encontrar d , já é possível decodificar, para isso, aplicaremos a congruência em
y para voltarmos à mensagem original x .
y d ≡ x (mod n)
(5)
Mas seguintes aplicações servem para quando mdc ( x, n) = 1 de forma que:
x kφ ( n )+1 ≡ x (mod n)
(6)
Pois se multiplicarmos d nos expoentes da congruência (3), obtemos:
x e.d ≡ y d (mod n)
(7)
E a equação (4) nos informa que e.d ≡ 1 (mod φ (n)) , então:
e.d = 1 + kφ (n), ∀ k ∈ Ζ
(8)
x e.d = x1+ kφ ( n ) ≡ x (mod n)
(9)
Assim;
Por (7) e (9) provamos a equação (5).
Mas, nem sempre o bloco será um número relativamente primo a n , pois x pode variar de 0 a
n − 1 . Então, como ter a certeza de que a mensagem decodificada é realmente a que foi
codificada? Como podemos provar que o mesmo acontece quando x não é primo de n ?
Se o mdc ( x, n) ≠ 1 , então x e n têm um fator primo em comum, só pode ser p ou q , pois
n = p.q . Dessa forma, x é múltiplo de p , de q ou de p.q .
Caso 1: p | x , então x = t. p , para algum t inteiro. Então x e q são primos entre si, pois caso
contrário x seria múltiplo de n . Neste caso temos:
x ≡ 0 (mod p )
(10)
Mas como o mdc ( x, q ) = 1 , então o teorema de Euler nos garante que:
x φ ( q ) ≡ 1 (mod q )
(11)
8
Lembrando que φ ( p.q ) = φ ( p ).φ (q ) , então vale demonstrar que:
x kφ ( n )+1 =
x kφ ( p ).φ ( q ) x =
1kφ ( p ) x = x (mod q )
(12)
(13)
(14)
Como x = 0(mod p ) , podemos concluir que:
x kφ ( n )+1 = x (mod p )
(15)
Segundo as equações (14) e (15) é provado que x kφ ( n )+1 − x é divisível por p e q , ou seja,
também é divisível por n , então:
x kφ ( n )+1 = x (mod n)
(16)
Caso 2: Este caso terá o mesmo resultado do primeiro, pois apenas vamos trocar os papéis de
p e q.
Caso 3: Quando o mdc ( x, n) = n , ou seja, n | x , então a congruência será da seguinte forma:
x ≡ 0 (mod n)
(17)
Para o teorema de Euler, temos a seguinte afirmação:
x φ ( n ) ≡ 0 (mod n)
(18)
x kφ ( n )+1 = x (mod n)
(19)
Como x ≡ 0 (mod n) , então:
Enfim, é provada que a mensagem decodificada será a mesma que anteriormente foi
codificada.
4. SOLUÇÕES NUMÉRICAS
Para entender melhor, faremos uma pequena “receita” mostrando os passos do
algoritmo RSA. Para isso, não utilizaremos números grandes. Para facilitar o entendimento,
usaremos números primos pequenos. Vamos utilizar o exemplo antes codificado, AMANDA
FONSECA, lembrando antes que é preciso separar os blocos e eles não podem ultrapassar o
nosso valor n . Para isso, é necessário saber primeiramente os valores de p e q . Sejam
p = 11 e q = 17 , então n = 187 e, portanto, φ (n) = 160 , logo e = 3 , pois é o menor primo que
vai satisfazer o mdc (φ (n), e) = 1 . Agora que temos a chave-pública, já é possível separar os
blocos:
9
112-31-124-141-155-162-52-42-91-51-3-11
Dessa forma evitamos também a contagem da frequência em que aparece uma letra,
dificultando a quebra. A partir daí, vamos aplicar a seguinte congruência da equação (3) em
cada bloco separadamente. Ao aplicar no primeiro bloco teremos:
112 3 ≡ 184 (mod187)
Assim, o primeiro bloco codificado, que antes era 112, passou a ter um valor de 184,
que é o resto da divisão de 112 3 por 187 . Após aplicar essa congruência em todos os blocos,
teremos a seguinte mensagem codificada:
184-58-159-91-144-83-171-36-148-187-27-22
Portanto, se algum intruso obtiver essa mensagem, não conseguirá decifrá-la, a menos
que conheça d que é inverso de e , pois a chave para decodificar a mensagem é (n, d ) , sendo
que n é um valor conhecido por fazer parte da chave de codificação. Para calcular d basta
aplicarmos a equação (4) e teremos o seguinte:
3.d ≡ 1 (mod 160)
Logo, tem-se d = 107. Enfim, vamos aplicar a congruência da equação (5) para
decodificarmos o primeiro bloco:
184107 ≡ 112 (mod187)
Portanto, se aplicarmos corretamente o algoritmo RSA ao decodificarmos, teremos a
mesma mensagem antes codificada:
112-31-124-141-155-162-52-42-91-51-3-11
5. RESULTADOS E CONCLUSÕES
Conclui-se que ao longo da história criptográfica, pode-se perceber uma grande
evolução ligada à tecnologia e um avanço intelectual da população, pois se hoje fosse
utilizada a cifra de César, por exemplo, seria na verdade uma brincadeira de criança. É claro
que todos os métodos antes utilizados respondiam as necessidades dos povos da época, quanto
mais evolução, é preciso mais segurança.
Portanto o método RSA qualquer pessoa consegue codificar e, se a codificação for
utilizada de forma correta, a segurança pode ser garantida. O que não se pode afirmar é que
esse método é inquebrável, pois, sempre depende da forma correta de utilização.
Com esse artigo consegui entender melhor a teoria estudada em sala de aula e me
mostrou o quão necessário é a Matemática, pois a partir dela conseguimos obter segurança em
nossas transações comerciais, entre outros.
10
O tema desse artigo vai muito além do que foi apresentado e as dificuldades na parte
matemática também, envolvendo conhecimentos mais avançados envolvendo tanto teoria dos
números quanto cálculo, álgebra e outros.
REFERÊNCIAS BIBLIOGRÁFICAS
COUTINHO, S.C. Números inteiros e criptografia RSA. Rio de Janeiro, IMPA, 2005.
FRANÇA, Waldizar B. de Araújo. Criptografia. Disponível em:
<www.matematica.ucb.br/sites/000/68/00000041.pdf>. Acesso em: 23 set 2012.
SANTOS, Plínio José de Oliveira. Introdução à Teoria dos números. 3. ed. IMPA, 2007.
SHOKRANIAN, Salahoddin. Criptografia para iniciantes. Brasília: Universidade de
Brasília, 2005.
SILVA, Eduardo Augusto Moraes. Um estudo do sistema criptográfico RSA. Disponível
em:
<http://www.ucb.br/sites/100/103/TCC/12005/EduardoAugustoMoraesSilva.pdf>.
Acesso em: 19 nov 2012.
SOBRAL, João Bosco M. Gerenciamento de chaves simétricas. Maio, 2006. Disponível
em: <www.inf.ufsc.br/~bosco/...seg/Gerenciamento-Chave-Simetrica.ppt>. Acesso em: 10
nov 2012.
TERADA, Routo. Segurança de dados: criptografia em redes. 2. ed. São Paulo: Edgard
Blucher, 2008.
SINGH,
Simon.
O
livro
dos
códigos.
Disponível
<http://tigredefogo.wordpress.com/2008/01/03/livro-o-livro-dos-codigos-simon-singhprimeiro-capitulo. Acesso em: 05 dez 2012.
Amanda Oliveira Fonseca ([email protected])
Curso de Matemática, Universidade Católica de Brasília
EPCT – QS 07 – Lote 01 – Águas Claras – Taguatinga – CEP.: 72966-700
em: