CRIPTOSSISTEMAS BASEADOS EM NÚMEROS PRIMOS
Higor Gleidson Costa Cruzeiro
Universidade Católica de Brasília
Curso de Matemática e-mail: [email protected]
José Eduardo Castilho
Universidade Católica de Brasília
Curso de Matemática e-mail: [email protected]
RESUMO
Este trabalho buscou informações sobre algoritmos de criptografia, baseados em funções de chaves
públicas, usados em transmissões de dados na rede mundial de computadores A pesquisa contém uma
fundamentação teórica, como também uma análise sobre a segurança na transmissão de dados dos
algoritmos RSA, RABIN e ELGAMAL.
Palavras-chave: criptossistemas; algoritmos de criptografia.
1. INTRODUÇÃO
A palavra criptografia tem origem no grego, onde cryptos significa oculto, secreto,
escondido e grapho significa escrita, grafia. A criptografia é, então, o estudo de
métodos para transformar uma mensagem originalmente compreensível em algo
incompreensível para todos, exceto para o destinatário legítimo da mensagem que a
tornará legível novamente, podendo interpretar seu conteúdo. O processo de transformar
uma mensagem legível em uma equivalente, mas, ilegível é chamado de codificação. E
o que um usuário legítimo do código usa para tornar compreensível uma mensagem
codificada é denominado decodificação. Em geral, para decodificar uma mensagem é
necessário o conhecimento de uma chave secreta disponível ao usuário legítimo do
código. É possível que pessoas não autorizadas tenham acesso à mensagem codificada e
consigam determinar seu conteúdo ou mesmo a chave de decodificação, quebrando o
código. A este processo chamamos deciframento.
A criptoanálise (cryptos + analysis = decomposição) busca determinar a chave de
decodificação ou decifrar a mensagem sem o conhecimento da chave. Ao estudo ou
ciência que reúne a criptografia e a criptoanálise chamamos de criptologia (SOUZA,
2004). O uso da criptografia já se fazia presente no sistema egípcio de escrita
hieroglífica, há aproximadamente quatro mil anos. Julio César usava um cifrário para
2
comunicar seus planos de batalha aos generais de seu exército. Tal cifra consistia em
transladar as letras do alfabeto três casas adiante. Existem outros códigos primitivos
semelhantes a este como, por exemplo, o cifrário de Vigenère e o cifrário de Hill.
A partir do advento dos computadores, os métodos de codificação baseados em
substituição alfabética tornaram-se inviáveis. Na verdade, o primeiro computador foi
criado para decifrar as mensagens secretas estabelecidas pelo exército alemão durante a
Segunda Guerra Mundial. As mensagens alemãs eram codificadas através de uma
máquina chamada Enigma. Um projeto denominado ULTRA foi desenvolvido na época
em Bletchley Park, Inglaterra, para tentar decifrar o código alemão. Um dos
responsáveis por este projeto era Alan Turing, o idealizador da máquina de Turing.
Como conseqüência deste projeto o primeiro computador foi construído, o Colossus.
Até então, o uso da criptografia estava associada a interesses políticos e militares. Com
a crescente utilização de redes de computadores, a necessidade de se manter
informações sigilosas também cresceu. A criptografia segue, então, uma nova direção,
deixando de servir a interesses puramente militares ou políticos e passa a servir a
cidadãos comuns. Um exemplo disso é a enorme quantidade de transações bancárias,
comerciais feitas através da internet nos dias de hoje.
Um sistema criptográfico é um conjunto de processos que fornece segurança na
transmissão de informações. Este sistema é formado por um:
•
Alfabeto de entrada;
•
Um conjunto de mensagens não codificadas e outro de mensagens codificadas;
•
E um conjunto de funções, onde uma função leva a mensagem não codificada e a
codifica, e outra que faz o inverso.
Quando as chaves ou funções de codificação e decodificação são as mesmas, diz-se que
este é um sistema simétrico ou de chave secreta. Agora no sistema assimétrico a chave
de codificação é publicada, ou seja, de acesso a todos.
Com o advento das operações via tem-se a necessidade das mensagens serem
transmitidas com segurança. Daí a necessidade de se criptografar as mensagens
enviadas pelos simples objetivos:
3
•
Sigilo, onde não interessa que ninguém mais além do receptor desejado entenda a
mensagem.
•
Integridade, para que a mensagem não seja alterada, intencional ou não.
•
Autenticação, onde o receptor tem a certeza que realmente foi a pessoa certa que lhe
enviou aquela mensagem.
•
Não repúdio, que prova a integridade da mensagem, onde evita que a mensagem
seja alterada ou até mesmo negada.
Com o crescimento do comércio eletrônico, o sistema criptográfico assimétrico torna-se
o ponto chave das transações on-line. Com a chave pública, não se tem mais a
necessidade de um contato prévio entre emissor e receptor. Quem deseja receber
informações sigilosas apenas publica sua chave. Depois disso as mensagens
criptografadas só podem ser recuperadas por quem possuir a chave secreta. A idéia do
par de chaves e o seu cálculo foi proposta por Diffie e Hellman em 1978 e baseia-se em
aplicações de funções inversas fáceis de serem calculadas para quem conhece as chaves.
Porém, recuperar a mensagem original a partir da mensagem ilegível é inviável em
questão de tempo. Há uma controvérsia, entre os autores, de quem foi o primeiro
algoritmo a usar as idéias de Diffie e Hellman, não se sabe se foi o RSA (SOUZA,
2004), ou o RABIN (TERADA, 2000).
Este trabalho tem como objetivo a análise de sistemas criptográficos assimétricos
usados nas transmissões de mensagens e dados, principalmente na rede mundial de
computadores e mostrar que eles são realmente seguros. Os algoritmos analisados serão
o RSA, o RABIN e o ELGAMAL.
2. CRIPTOSISTEMAS
Um criptossistema ou um sistema criptográfico consiste de:
•
Um conjunto finito A que chamamos de alfabeto de entrada. O alfabeto de entrada
pode ser o alfabeto binário ou o alfabeto de alguma língua. Na criptografia
computacional, geralmente usa-se o alfabeto binário, mas não se pode esquecer que
qualquer tipo de alfabeto pode ser representado como uma cadeia de strings do
4
alfabeto binário, ou mesmo uma cadeia numérica de codificação, como exemplo o
código ASCII.
•
Um conjunto M formado por cadeias finitas de elementos de A. Chamamos este
conjunto de espaço de mensagens. Cada elemento de M corresponde a um texto
simples, não cifrado.
•
Um conjunto C também formado por cadeias finitas de elementos de A. Este é o
chamado espaço de mensagens codificadas e cada elemento de C corresponde a um
texto cifrado.
•
Um conjunto finito P e S de elementos chamados de chaves que são ferramentas
necessárias para manter oculta uma informação.
•
Um conjunto finito P(m) e S(c) de elementos chamados de funções de chaves, onde
aplicadas as chaves pública e privada, possibilitam criptografar e descriptografar as
mensagens.
•
O espaço E de funções e: M C onde cada função codifica os elementos de M. E é
o espaço de funções de codificação.
•
O espaço D de funções d: C M onde cada função decodifica os elementos de C.
Cada elemento P 1 ∈ P determina uma única bijeção de M em C denotada por e P.1 .
Assim, temos que existe S 1 ∈ S, que determina uma função de decodificação d S.1 que é
inversa à c P.1 . Quando se projeta um sistema criptográfico deve-se estar atento ao fato
de que o sistema deve permanecer seguro mesmo quando os algoritmos de codificação e
de decodificação são de conhecimento público. Logo a segurança do sistema está na
escolha das duas chaves, onde uma codifica e a outra decodifica.
3. CRIPTOGRAFIA DE CHAVE PÚBLICA
Também conhecido como sistema criptográfico assimétrico, possibilita a troca de dados
sem que haja uma prévia troca de informações entre emissor e receptor. A idéia inicial
deste esquema foi proposta através de um modelo de criptossistema, chamado modelo
de chave pública Diffie e Hellman de 1978. Baseado no seguinte esquema: Cada usuário
possui um par de chaves (S,P) onde, S é a sua chave secreta e P a sua chave pública, e
um par de funções de chaves onde, P(m) é a sua função de chave pública e S(c) a sua
5
função de chave secreta, sendo que cada função é uma função inversa da outra. Essas
chaves são relacionadas matematicamente de tal forma que:
•
Se m denota um texto legível, então P(m) denota a aplicação da chave P.
•
Usa-se P para transformar m em P(m) = c.
•
Da mesma forma sendo S(c) a aplicação da chave S, aplica-se S a c e obtém-se S(c)
= m, como S é a função inversa de P temos S(P(m)) = m.
•
O cálculo do par de chaves (S,P) é computacionalmente fácil, ou não há uma perda
significante de tempo.
•
É computacionalmente difícil calcular S a partir do conhecimento de P.
•
Os cálculos de P(m) e S(c) são computacionalmente fáceis para quem conhece as
chaves.
•
É computacionalmente difícil calcular S(c) sem conhecer a chave S.
3.1 Par de chaves e o seu cálculo
A idéia principal da criptografia de chave pública é que cada usuário possui um par de
chaves (S,P) e tem a liberdade de calcular as suas chaves e trocá-las sempre que achar
necessário. Cada usuário calcula o seu par de chaves (S,P), guardando de forma segura
a chave S e publica a chave P. Com a chave pública aplica-se uma função que altera um
texto legível em um texto ilegível. Somente a sua chave secreta, consegue recuperar a
mensagem original. Com a chave secreta aplica-se uma função ao texto ilegível,
recuperando o texto original.
Procedimentos para o cálculo do par de chaves:
•
Calcular dois números inteiros primos (com centenas de bits ou muitas casas
decimais) chamados q e r;
•
Calcular o seu produto n = q.r. Recomenda-se que o comprimento de q seja próximo
de r para tornar inviável a fatoração rápida de n em primos;
•
Calcular um terceiro número chamado s relativamente primo a (q – 1).(r – 1) (que é
igual ao ϕ (n) = ϕ (q ).ϕ (r ) );
6
•
Calcular um inteiro p que satisfaça p.s ≡ 1 mod (q – 1).(r – 1), isto é, p ≡ s −1 mod
ϕ (n) , através do Algoritmo Estendido de Euclides.
•
A seguir o usuário apaga os números p e r do seu sistema.
•
A chave secreta S é guardada com cuidado e a chave pública P é enviada para a
pessoa desejada.
Alguns algoritmos dos mais usados hoje em dia para transações principalmente on-line,
são baseados nesta idéia, que pode até ser simples, porém não menos segura. Como por
exemplo: Algoritmo RSA, Algoritmo RABIN e Algoritmo ELGAMAL.
4. ALGORITMO RSA
Alguns criptossistemas são baseados na dificuldade computacional do problema do
logaritmo discreto, onde:
•
Dados um primo p e inteiros g,t: 0 < g,t < p;
•
Calcular um inteiro s tal que t ≡ g s (mod p).
Por exemplo: p = 17, g = 7 e t = 10, calcular um s tal que 10 = 7 s mod 17. A resposta é s
= 9.
Quando p é relativamente longo (com várias casas decimais), ninguém até hoje (nem
mesmo os pesquisadores especialistas) descobriu um algoritmo eficiente, de tempo
polinomial, para resolver este problema. Um problema é de tempo exponencial se existe
k, tal que f(n) é da ordem n k para uma constante k, caso contrário, o problema é de
tempo polinomial. A idéia então é incorporar esta dificuldade de solução em um
esquema criptográfico. Este algoritmo foi publicado em 1978 e o seu nome é derivado
das iniciais dos seus autores: Ron Rivest, Adi Shamir e Len Adleman.
4.1 Processos para criptografar uma mensagem
•
Inicialmente o usuário deve calcular um par de chaves: a chave pública do
usuário P e a chave secreta S.
•
Nessas condições, a mensagem é convertida em uma seqüência de números, que
pode ser desde uma seqüência binária até uma seqüência criada de acordo com a
7
vontade de quem está criptografando. O usuário pode escrever uma mensagem e
converter suas letras na ordem em que elas aparecem no alfabeto, como por
exemplo: A = 1, B = 2, C = 3 e assim sucessivamente até a letra Z = 26;
•
Essa seqüência gerada é quebrada em blocos que representem números inteiros
m no intervalo [0,n), daí então a seqüência é codificada;
•
Um emissor conhecendo a chave pública efetua os seguintes passos:
•
O emissor calcula m (mod n) = c e envia para o receptor o texto ilegível (onde
p
m é a mensagem e c é chamado de texto ilegível de m, ou a mensagem cifrada);
•
s
O receptor recebe c e calcula c (mod n) = m (onde m é a mensagem
descriptografada ou mensagem original).
•
Exemplo:
Emissor → m = 9
Receptor → m = 9
↓
↑
.m (mod n) = 9 7 (mod 22) ≡ c → c = 15 → c (mod n) = 15 3 (mod 22) ≡ m.
p
s
↓
↑
Chave Pública (p,n) = (7,22)
Chave Secreta (s,n) = (3,22)
4.2 Criptoanálise do RSA
Todo cuidado é pouco com relação à criptografia e com o algoritmo RSA não pode ser
diferente. Viu-se que conhecendo apenas um das chaves é quase impossível descobrir a
mensagem de origem, mas mesmo assim este sistema possui uma fraqueza.
Se alguém conseguisse fatorar o número n em primos q e r, então ele poderia calcular s
que satisfaça p.s = 1 mod (q – 1).(r – 1), é por isso que não recomenda que | q | ≅ | r |
para dificultar a fatoração de n = q.r.
O ponto importante é que até hoje não se conhece um algoritmo rápido para fatorar um
número n, com muitos algarismos, em primos, e conseqüentemente um intruso não
consegue recalcular a chave secreta rapidamente explorando esta fraqueza, mesmo que
esta pessoa seja um estudioso do assunto, e tenha um supercomputador à sua disposição.
8
Para ilustrar a dificuldade de fatorar um inteiro, quando o número n possui 129
algarismos decimais, o intruso gastaria cinco mil MIPS-anos, sendo que um MIPS-ano
significa usar um computador executando um milhão de instruções por segundo durante
um ano, isso utilizando um dos algoritmos mais rápido que se conhece, chamado QS (de
Quadratic Sieve), da autoria de C. Pomerance (TERADA, 2000). Mais precisamente, o
algoritmo QS possui tempo de execução proporcional a e
(ln n ).(ln ln n )
.
Um outro algoritmo para fatoração chamado NFS (de Number Field Sieve) com tempo
1
de execução proporcional a e
2
1,92.(ln n ) 3 .(ln ln n ) 3
de autoria de K. Lenstra, H. W. Lenstra, M.
S. Manasse, e J. M. Pollard é mais rápido que o QS para números com mais de 350 bits,
por ser mais rápido assintoticamente que o QS.
1
lim (
n→∞
e
2
1, 92.(ln n ) 3 .(ln ln n ) 3
e
(ln n ).(ln ln n )
)=∞
Para ilustrar o crescimento das funções QS, NFS e e n , na figura abaixo esta o gráfico de
suas curvas.
Em fevereiro de 1999 foi estabelecido um recorde em fatoração de uma chave RSA de
465 bits (140 casas decimais) pela execução do algoritmo NFS distribuído em centenas
de estações de trabalho, durante vários meses. Em 1996, 512 bits para o módulo n do
RSA era considerado razoavelmente seguro. Mas devido aos eventos mencionados e
devido aos algoritmos QS e NFS, hoje recomenda-se no mínimo 768 bits. Para longo
prazo, recomenda-se desde já adotar 1024 bits (TERADA, 2000). É importante
9
mencionar que até hoje os pesquisadores não conseguiram descobrir qualquer outro
ponto fraco neste sistema de criptografia.
4.3 Autenticação
Pode-se notar que nem sempre temos a certeza de que a mensagem tenha sido enviada
pela pessoa esperada, isso pelo fato de a criptografia ser de chave pública, o que torna
uma das chaves conhecida por grande parte das pessoas que tem acesso ao meio em que
está sendo enviada a mensagem desejada, portando a chave pode ser utilizada por
qualquer pessoa. Por isso, caso Alice tenha um par de chaves S(s,n) e P(p,n), e além
deste exista um outro par de chaves P’(p’,n’) e S’(s’,n’) calculado por Beto, com n’ < n,
pois se n’ > n, então pode existir um n’ > m > n , entrando em contradição com a
condição de existência de m < n. Suponha que Beto quer mandar uma mensagem para
Alice e quer ter certeza de que somente a própria Alice recupere a mensagem m, então
agora ele quer autenticar a mensagem. Para autenticá-la ele procede alguns passos.
Tem-se que o texto legível é alterado para:
1. Beto calcula m s ' (mod n’) ≡ a (a é chamado de código de m assinado por Beto);
2. Beto calcula a p (mod n) ≡ c (onde c é na verdade m assinado por Beto ilegível);
3. Beto envia c para Alice;
4. Alice recebe c e calcula c s (mod n), com isso ela acha a que é m assinado por Beto;
5. Com a Alice calcula a p ' (mod n’) que deve ser igual a m, com isso Alice recupera a
mensagem original que Beto a enviou.
•
Esquema:
Beto
m → m s ' (mod n’) ≡ a → a p (mod n) ≡ c → c
↑
↑
Chave Secreta (s’,n’) Chave Pública (p,n)
Alice
c → c s (mod n) ≡ a → a p ' (mod n’) ≡ m → m
↑
↑
Chave Secreta (s,n) Chave Pública (p’,n’)
10
Neste novo procedimento de envio de texto legível para Alice, temos as seguintes
propriedades muito importantes:
1. Autenticação do destinatário, pois só Alice autêntica possui o valor s utilizado para
converter c em a e assim Beto tem certeza de que só a Alice verdadeira pode ter
recuperado m.
2. Autenticação do remetente, isto é, Alice tem certeza de que só o Beto verdadeiro
pode ter enviado c para ela converter m em a (portanto, a recebe o nome de código
de m assinado por Beto).
3. Verificação de integridade – Alice não consegue alterar m para um outro valor m’ e
dizer a Beto que recebeu este valor no lugar de m, pois Beto vai exigir, em caso de
disputa, que Alice exiba o valor a’ correspondente a m’, e Alice não conseguiria
calcular a’ a partir de m’ sem conhecer s’ da chave secreta do Beto. Esta última
propriedade é essencial em redes de transferência eletrônica de fundos, em que m
corresponde, por exemplo, a um “cheque” de um certo valor m para Alice “sacar” e
ela não consegue alterá-lo para um valor m’ maior que m. Entretanto isso serve para
o inverso também, se eventualmente Beto afirmar falsamente que não enviou m para
Alice, ela pode exibir c e a e mostrar que a é obtida de c usando a chave pública de
Beto, provando assim que Beto está mentindo.
4.4 Testando a funcionalidade do RSA
•
Seja c = P(m) ≡ m s (mod n) a codificação de um bloco m.
•
Como s.p ≡ 1 (mod ϕ (n) ), existe um t tal que s.p = 1 + t . ϕ (n) .
•
Se mdc (m,q) = 1, temos que m q −1 ≡ 1 (mod q) .
•
Então (m q −1 ) t .( r −1) = m t .( q −1).( r −1) ≡ 1 (mod q) ⇒ m 1+ t .( q −1).( r −1) = m s. p ≡ m (mod
q).
•
Agora, se mdc (m,q) = q, então a última congruência é válida novamente pois
cada lado é congruente a 0 módulo q.
11
•
Assim, temos m s. p ≡ m (mod q) em todos os casos. De forma análoga, m s. p ≡
m (mod r). Como q e r são primos distintos, então m s. p ≡ m mod n.
•
Daí, c p = (m s ) p ≡ m mod q.
4.5 Exemplo
•
q = 312.313;
•
r = 123.217;
•
n = 312.313 x 123.217 = 38.482.270.921;
•
ϕ (n) = (q – 1).(r – 1) = 312.312 x 123.216 = 38.481.835.392;
•
p = 25.271.899;
•
s ≡ p −1 mod ϕ (n) = 25.271.899 −1 mod 38.481.835.392 = 28.963.169.491;
•
1 = s . p mod ϕ (n) = 28.963.169.491 x 25.271.899 mod 38.481.835.392 = 1
Um texto legível “abcde” é representado numericamente por m = 0102030405, isto é,
“a” é “01”, “b” é “02”, etc...
E então, sendo m < n, tem-se:
•
m p mod n = 0102030405 25.271.899 mod 38.482.270.921 = 36.647.352.873 = c (onde c
é o texto ilegível ou criptografado);
•
c s mod n = 36.647.352.873 28.963.169.491 mod 38.482.270.921 = 0102030405 = m (onde
m é a mensagem legível ou mensagem decriptografada);
5. ALGORITMO RABIN
Publicado em 1979 por Michael Rabin. Este algoritmo é seguro e baseia-se na
dificuldade computacional de um intruso calcular o texto legível a partir do
conhecimento do texto ilegível correspondente. Onde essa dificuldade é equivalente a
de fatorar um inteiro em primos.
5.1 Processos para criptografar uma mensagem
•
Inicialmente o usuário deve calcular um par de chaves: a chave pública do
usuário P(n) e a chave secreta S(q,r).
12
•
Nessas condições, a mensagem é convertida em uma seqüência de números, que
pode ser desde uma seqüência binária até uma seqüência criada de acordo com a
vontade de quem está criptografando. O usuário pode escrever uma mensagem e
converter suas letras na ordem em que elas aparecem no alfabeto, como por
exemplo: A = 1, B = 2, C = 3 e assim sucessivamente até a letra Z = 26;
•
Essa seqüência gerada é quebrada em blocos que representem números inteiros
m no intervalo 0 ≤ m < n, daí então a seqüência é codificada;
•
Um emissor conhecendo a chave pública efetua os seguintes passos:
•
O emissor calcula m 2 mod n = c e envia para o receptor o texto ilegível (onde m
é a mensagem e c é chamado de texto ilegível de m, ou a mensagem cifrada);
•
O receptor recebe c e conhecendo a chave secreta (q,r), efetua os seguintes
passos:
1. Calcula as quatro raízes quadradas de c (mod n): m 1 , m 2 , m 3 , m 4 ;
2. O texto legível deve ser ou m 1 , m 2 , m 3 , m 4 ;
3. Se m contiver alguma redundância, o receptor será capaz de decidir qual
destas é a mensagem real, pois as outras três raízes não terão tal redundância
com alta probabilidade.
•
Se, eventualmente, um intruso conseguir gravar o texto ilegível c da linha de
comunicação entre o receptor e o emissor, ele não consegue recuperar o valor de
m, pois ele não conhece a chave secreta S do emissor.
5.2 Cálculo das quatro raízes quadradas
Dados dois primos q e r, no caso particular de 4 | (q + 1) e 4 | (r + 1) vamos ver como
calcular as quatro raízes quadradas de c mod (q.r).
Calcula-se inicialmente x 1 e x 2 :
q +1
4
q -1

 2
x1 = c
mod q 
x 1 = c 4 .c = c mod q
⇒


r +1
r -1
2


4
4
x 2 = c mod r 
x 2 = c .c = c mod r
, pelo Teorema de Fermat
13
A seguir, pelo Teorema Chinês do Resto calcula-se x 0 solução do sistema:
x 0 ≡ x 1 mod q

x 0 ≡ x 2 mod r
que é:
x 0 = (x 2 .q.q ( −1) + x 1 .r.r ( −1) ) mod (q.r)
onde p ( −1) e q ( −1) são calculáveis pelo Algoritmo de Euclides Estendido, e são tais que:
q.q
( −1)
+ r.r
( −1)
q.q (-1) ≡ 1 (mod r)
= 1 ⇒  (-1)
r.r ≡ 1 (mod q)
Este x 0 calculado é tal que:
x 02 (mod q) = x 12 .(q.q ( −1) ) mod q ≡ x 12 (mod q) = a (mod q)
x 02 (mod r) = x 22 .(r.r ( −1) ) mod r ≡ x 22 (mod r) = a (mod r)
Portanto, pelo Lema a seguir tem-se que x 02 mod (q.r) ≡ a mod (q.r), ou seja, x 0 é uma
das quatros raízes quadradas de a mod (q.r).
Lema
x 02 mod q ≡ a
x mod (q.r) ≡ a ⇔  2
x 0 mod r ≡ a
2
0
As quatro raízes são:
( −1)
•
x 0 = (x 2 .q.q
•
x '0 = (x 2 .q.q
•
x "0 = (q.r – x 0 ) mod (q.r)
•
x 0'" = (q.r – x '0 ) mod (q.r)
( −1)
+ x 1 .r.r
– x 1 .r.r
( −1)
( −1)
) mod (q.r)
) mod (q.r)
5.3 Criptoanálise do Rabin
Como no Algoritmo RSA, se um intruso conseguisse fatorar o número n em primos q e
r, então ele poderia calcular m a partir de c. Por outro lado se este intruso conseguisse
14
calcular m a partir do conhecimento de c, ele conseguiria fatorar n. Portanto, os
problemas de fatorar n e calcular m são igualmente difíceis. Supondo que a fatoração é
computacionalmente inviável, tem-se que o Algoritmo Rabin é demonstravelmente
seguro.
5.4 Exemplo
Supondo que o texto legível a ser enviado seja DABAC e que a redundância seja repetir
as duas últimas letras, temos que a mensagem será DABACAC. Representando cada
letra por um número: A = 1, B = 2, C = 3, etc. Assim o texto DABACAC é representado
por m = 4121313.
•
q = 1.123;
•
r = 7.723;
•
n = 1.123 x 7.723 = 8.672.929;
•
m = 4.121.313;
•
c = m 2 mod n = 4.121.313 2 mod 8.672.929 = 577.647 = c;
Com c o receptor efetua os seguintes cálculos:
•
x1 = c
p +1
4
r +1
4
mod q = 577.647
1.124
4
7.724
4
mod 1.123 = 1.026;
•
x2 = c
•
q (−1) mod r = (1.123) (−1) mod 7.723 = 1.623;
•
r (−1) mod q = (7.723) (−1) mod 1.123 = 887;
•
(x 2 .q.q (−1) ) mod n = (4.954 × 1.123 × 1.623) mod 8.672.929 = 784.977;
•
(x 1 .r.r (−1) ) mod n = (1.026 × 7.723 × 887) mod 8.672.929 = 3.336.336;
•
x 0 = (x 2 .q.q (−1) + x 1 .r.r (−1) ) mod n = (784.977 + 3.336.336) mod 8.672.929 =
mod r = 577.647
mod 7.723 = 4.954;
4.121.313; a outra raiz é (n - x 0 ) mod n; O receptor reconhece que x 0 é m, pois
contém a redundância estabelecida;
•
x '0 = (x 2 .q.q ( −1) - x 1 .r.r ( −1) ) mod n = (784.977 - 3.336.336) mod 8.672.929 =
6.121.570; que não pode ser m, pois não contém a redundância; a outra raiz é (n
– x '0 ) mod n.
15
Emissor
↓
.m 2 mod n = 4.121.313 2 mod 8.672.929 = c → c = 577.647
↓
Chave Pública (n) = (8.672.929)
Receptor
↓
(x 2 .q.q (−1) + x 1 .r.r (−1) ) mod n = (784.977+3.336.336) mod 8.672.929 = m. → m =
4.123.313
↑
Chave Secreta (q,r) = (1.123,7.723)
6. ALGORITMO ELGAMAL
Este algoritmo incorpora a dificuldade de solução do problema do logaritmo discreto.
Para um primo p > 2 relativamente longo, considera-se um gerador g do conjunto Z *p
dos inteiros não nulos relativamente primos a p.
6.1 Processos para criptografar uma mensagem
•
O receptor escolhe inicialmente um inteiro S tal que 1 ≤ S ≤ p – 2;
•
Junto a um conjunto de chaves K = {(p,g,S,T) : T = g mod p};
•
Os valores p, g e T são públicos e S é secreto;
•
Um emissor escolhe um número aleatório secreto k ∈ Z *p −1 , onde evita-se usar k
s
= p – 1 e recomenda-se usar um k distinto para cada m a ser criptografado;
•
Seja o texto legível m ∈ Z *p . Calcula-se y = g k mod p e z = x.T k mod p. Note
que y,z ∈ Z *p .
•
O texto ilegível é (y,z) que é enviado para o receptor;
16
Emissor → y = g
•
k
mod p; z = m.T k mod p → Receptor.
Observe que T k pode ser considerado como uma chave volátil, ou seja, uma
chave que só é usada para criptografar este m, e a criptografia consiste em
multiplicar T k por m.
(T k = g S .k mod p)
•
O receptor efetua z.(y S ) −1 mod p.
Note que y − S = g
− S .k
= (T k ) −1 mod p .
6.2 Criptoanálise do Elgamal
A segurança baseia-se em dois aspectos:
1. Se o intruso não consegue calcular k então ele não consegue calcular nem T k e
nem z.(T k ) −1 = x, e k é protegido pela dificuldade do problema do logaritmo
discreto. (y ≡ g k (mod p)).
2. Como T ≡ g S (mod p), S também é protegido pelo problema do logaritmo
discreto.
É importante a utilização de um k distinto para cada m a ser criptografado. Se dois
textos legíveis m 1 e m 2 forem criptografados, respectivamente para (y 1 ,z 1 ) e (y 2 ,z 2 )
com um mesmo k e um intruso consegue obtê-los, então
m
z1
= 1 , assim m 2 pode ser
z2
m2
calculado facilmente se m 1 for conhecido.
6.3 Testando a funcionalidade do Elgamal
•
K = {(p,g,S,T) : T ≡ g mod p};
•
Para criptografar m ∈ Z *p , usando a chave (p,g,T) e um número k ∈ Z p −1 ,
s
calcula-se y ≡ g k (mod p) e z ≡ m.T k (mod p);
•
A seguir a prova que a inversa é correta, para y, z ∈ Z *p :
17
= z.(y S ) −1 mod p
= (m.T k mod p).[( g k mod p) S ] −1 mod p
= [m.( g S mod p) k mod p].( g S .k mod p) −1
= [m.( g S .k ) mod p].( g S .k mod p) −1
=m
6.4 Exemplo
•
p = 2.579;
•
g = 2;
•
S = 765;
•
T = 2 765 (mod 2.579) ≡ 949;
•
m = 1.299;
•
k = 853;
Criptografando:
•
y = 2 853 (mod 2.579) = 435;
•
z = 1.299 × 949 853 (mod 2.579) = 2.396;
Decriptografando
•
(y,z) = (435,2.396);
•
2.396 × (435 765 ) −1 (mod 2.579) = 1.299.
Emissor
↓
2 853 (mod 2.579) = y


 → (y,z) = (435,2.396)
853
1.299 × 949 (mod 2.579) = z 
↑
18
Chave Pública (p,g,T) = (2.579,2, 949)
Receptor
[2.396 × (435
↓
]
) mod 2.579 = 1.299 = m → m = 1.299
765 -1
↑
Chave Secreta (S) = (765)
7. CONCLUSÃO
A base de cálculo dos algoritmos está ligada fortemente ao uso de números primos,
aliás, com muitas casas decimais. Isto, portanto, é algo a favor nos três algoritmos, pois
sabemos que não existe uma fórmula para calcular números primos, o que torna inviável
calcular dois números primos a partir do resultado de sua multiplicação. Aliás, esta é
uma fraqueza em comum dos algoritmos RSA e RABIN. Se algum intruso conseguir
obter estes dois números primos, provavelmente ele recuperaria a informação inicial.
Outro ponto em comum é que os três esquemas usam a criptografia de chave pública. O
que possibilita o uso em operações seguras pela rede de computadores. Isto se deve pelo
fato de não precisar mais haver um contato prévio entre as partes interessadas na
informação, as condições de envio tornaram-se mais seguras, pois o sistema usa uma
chave que codifica, que é de acesso público, e outra que decodifica, de acesso restrito
apenas ao receptor. Diferentemente da criptografia de chave simétrica, que usa a mesma
chave para codificar e decodificar, tornando a sua decodificação mais fácil, já que, é
necessário o seu envio da chave para um emissor conseguir codificar uma mensagem.
O ponto forte dos algoritmos RSA e ELGAMAL é fazer uso do problema do logaritmo
discreto, pois não se conhece ainda um algoritmo eficiente para resolvê-lo.
Analisando cada um dos algoritmos tem-se que mesmo com tantas coisas em comum
cada algoritmo possui uma particularidade na sua vulnerabilidade. O Algoritmo RSA
19
baseia-se na dificuldade do problema do logaritmo discreto e da fatoração de um
número inteiro em primos. Se alguém conseguisse fatorar este número inteiro em
primos, poderia calcular s.p = 1 mod (q – 1).(r – 1) e com isso recuperar a mensagem
original. O Algoritmo RABIN baseia-se na dificuldade de fatorar um número inteiro em
primos. Se alguém conseguisse fatorar este número inteiro então, ele poderia calcular m,
já que possui o valor c. O Algoritmo ELGAMAL baseia-se na dificuldade do problema
do logaritmo discreto. Se alguém conseguisse calcular k então conseguiria calcular T k ,
chegando assim ao resultado z.(T k ) −1 que nada mais é que a mensagem original.
Portanto, consegue-se perceber que os sistemas de criptografia exemplificados neste
trabalho dependem bastante dos conceitos de Teoria dos Números. Esta união criou um
esquema, que proporciona nos dias de hoje uma enorme segurança na transmissão de
informações na rede mundial de computadores, já que esta depende de um esquema
realmente seguro, já que está aberta a milhões de pessoas no mundo, que podem através
de recursos tecnológicos tentarem obter estas informações sigilosas. A prova de que
estes algoritmos são seguros é que eles são os mais usados na criptografia de hoje, tanto
na transmissão via rede mundial de computadores, quanto em transações bancárias.
REFERÊNCIAS BIBLIOGRÁFICAS
BASTOS, Eduardo N. F., Introdução à criptografia, 2000, disponível em:
<http://descartes.ucpel.tche.br/modules.php?name=Content&pa=showpage&pid=5>,
acesso em 03/2007.
CAVALCANTE, André L.B. Teoria dos Números e Criptografia, 2005, Revista
Virtual,
Disponível:<http://www.upis.br/revistavirtual/Cavalcante_%20Teoria%20dos%20N%F
Ameros%20e%20Criptografia_2005_UPIS.pdf>, acesso em 03/2007.
ROSA, Rafael Antônio da Silva, Algoritmos básicos em criptografia, 2000,
disponível
em:
<http://www.bibl.ita.br/viiiencita/Algoritmos%20basicos%20em%20cirptografia.pdf>,
acesso em 03/2007.
20
SHOKRANIAN, Salahoddin. Criptografia para iniciantes, 2005, Editora UnB.
SOUSA, Raimundo Cândido de, Criptografia de chave pública: Algoritmos que
possibilitam
a
criação
de
chave
assimétrica,
2006,
disponível
em:
<http://www.matematica.ucb.br/sites/000/68/00000037.pdf>, acesso em 04/2007.
SOUZA, Bianca Amoras de, Teoria dos números e o RSA, agosto de 2004, CampinasSP, dissertação (mestrado em matemática aplicada), UNICAMP.
TERADA, Routo, SEGURANÇA DE DADOS CRIPTOGRAFIA EM REDES DE
COMPUTADOR, 2000, Editora Edgard Blücher LTDA.