Matemática e Criptografia
Severino Collier Coutinho
UFRJ
Criptologia
Criptos = escondido em grego
• Criptografia
arte de esconder
mensagens
• Criptoanálise
arte de quebrar
mensagens
História
• César foi o
primeiro a utilizar
criptografia como
meio de esconder
informações
secretas.
Código de César
A B C D E F G H I J L M N O P Q R S T U V X Z
C D E F G H I J L MN O P Q R S T U V X Z A B
Exemplo
ESSES ROMANOS SÃO UNS NEURÓTICOS
GUUGU TQOCPQU UCQ XPU PGXTQVLEQU
Problemas
• É fácil decodificar verificando a
freqüência das letras na mensagem.
• Saber codificar implica em saber
decodificar.
• Precisa de canal seguro.
O mesmo se aplica a outros códigos semelhantes
Outras aplicações
O método de contagem de freqüência e
técnicas semelhantes de criptografia
também são usadas na decifração de
escritas antigas.
Exemplos: hieróglifos, linear B
Abre parêntesis...
Hieróglifos egípcios
• Conhecimento da leitura esquecido
desde, pelo menos, 500 d.C.
• Horapolo de Nilópolis: caracteres seriam
ideográficos.
Renascença
• Athanasius Kircher
(1602-1680).
• Segue Horapollo.
• Língua copta.
A chave
• Pedra de Rosetta.
• Descoberta em
1799.
• Mesmo texto escrito em hieróglifos, demótico e grego.
O decifrador
• J.-F. Champollion (17991832).
• Língua derivada do copta.
• Escrita: caracteres ideográficos, alfabéticos e
determinativos.
O alfabeto
Determinativos
= htr = cavalo
• O determinativo é o
desenho do cavalo.
• E preciso acrescentá-lo
porque htr também
significa taxa.
Linear B
• Descoberta em
Creta.
• Decifrado por M.
Ventris em 1953.
• Contagem de
freqüência: língua é
grego.
Vale do Indo
• Ainda não decifrada.
• Inscrições curtas
dificultam a contagem
de freqüência.
Fecha parêntesis...
Tipos de Códigos
• Chave secreta:
• Saber codificar
implica em saber
decodificar.
• Precisa de canal
seguro.
• Chave pública:
• Saber codificar
não implica saber
decodificar.
• Não precisa de
canal seguro.
• Inventado na
década de 1970.
Chave Pública
• Imagem: armadilha para lagosta.
Idéia: problema
fácil de resolver
por um lado e
difícil por outro.
RSA
 Chave
pública
mais
popular
 Inventado em
1976
Rivest
Adleman
Shamir
Número Primo
Número divisível somente por ele
mesmo e pela unidade.
Exemplos
2, 3, 5, 7, 11, 13, 17, ..., 41, 43, 47, ....
213466917-1 tem 4.053.946 algarismos
RSA
Escolha dois números primos p e q.
Calcule n = pq.
• Chave de
codificação:
n = pq.
• Chave de
decodificação são
p e q.
• Pode ser tornada
pública.
• Tem que ser
mantida secreta.
Como quebrar o RSA?
• n = pq é público
• Preciso conhecer p e q para
decodificar a mensagem.
• Logo: basta fatorar n para achar p e
q.
Fatorando 120.
•
•
•
•
120  2 = 60
60  2 = 30
30  2 = 15
15  3 = 5, que é primo.
• Logo: 120 = 2·2 ·2 ·3 ·5.
Fatorar tem alto custo!
• Se n = pq e p, q ~ 1050.
• Começo de 2 e avanço até ~ 1050
• Computador executa 1010 divisões/s.
• Logo preciso esperar 1040s ~ 1031 anos!
Porém ...
O universo só tem 1011 anos!
Portanto...
Achar p e q conhecendo apenas
n = pq é muito difícil.
RSA-129
Mensagem codificada em 1976 usando
uma chave pública n com 129 algarismos.
Com os recursos da época (computadores e algoritmos) deveriam ser necessários quadrilhões de anos para
decodificá-la.
Entretanto...
Decodificada em 1994:
“The magic words are squeamish
ossifrage”
Como foi feito
• 600 computadores de voluntários
• Em 25 países
• Dados reunidos usando um supercomputador
• Tempo total: oito meses!
O que fez a diferença
• Novos algoritmos (crivo quadrático).
• Computadores mais rápidos.
• Popularização dos computadores.
• A internet para interligar tudo.
RSA-160
2152741102718889701896015201312825429257773588
84567598017049767677813314521885913567301105
9773491059602497907111585214302079314665202840
140619946994927570407753
Fatores
454278928584813940716861906497388316561371457
78469793250959984709250004157335359 e
473880906038320161966338323037889519732689229
21040957944741354648812028493909367
Dúvida
Se é difícil fatorar números grandes...
E se um número primo é o que não
tem fatores...
...Então como obter dois primos
grandes para construir a chave
pública n do RSA?
Primalidade
• Não é preciso fatorar para descobrir se
um número é primo ou composto!
• Por exemplo: se n e b são inteiros
positivos tais que n não divide bn-1-1,
então n tem que ser composto.
Algoritmo AKS
Método eficiente (tempo polinomial) para
determinar se um número é primo sem
fatorá-lo.
Descoberto em agosto de 2002 por M.
Agrawal, N. Kayal e N. Saxena.
O Futuro Próximo
• Sistema usa
curvas elípticas.
Grupo da curva elíptica
• Podemos somar
pontos em uma
curva elíptica.
• Isto torna a curva
em um grupo.
ECC
• Fixe uma curva E e P  E.
• Chave secreta: inteiro positivo k.
• Chave pública: Q = kP.
Suponha...
...que Alice quer mandar uma mensagem
para Bernardo...
ECC: codificando
• Alice conhece a curva E, o ponto P  E
e a chave pública Q.
• Para codificar M  E : escolha r
aleatoriamente e calcule (rP, rQ+M).
ECC: decodificando
• Bernardo
conhece a curva E, o ponto P
 E e a chave secreta k.
Decodifica (rP, rQ+M) calculando:
(rQ+M) - k(rP) = r(kP) + M - k(rP) = M.
ECC: quebrando
Calcular k conhecendo Q = kP.
Problema do Logaritmo Discreto
O Futuro Distante
• Peter Shor
(1994): algoritmo
quântico de
fatoração.
• Criptografia
quântica.
As perguntas finais...
Quão próximo, ou distante?
Assim...?
Não!
Assim!
A criptografia quântica já chegou até nós
Que outras surpresas nos
aguardam?
?