Matemática e Criptografia

Severino Collier Coutinho

UFRJ

Criptologia

• Criptografia arte de esconder mensagens

• Criptoanálise arte de quebrar mensagens

Criptos = escondido em grego

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 ZC D E F G H I J L M N 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 escri-to em hieróglifos, de-mótico e grego.

O decifrador

• J.-F. Champollion (1799-1832).

• Língua derivada do copta.

• Escrita: caracteres ideo-grá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: armadi-lha para lagosta.

Idéia: problema fácil de resolver por um lado e difícil por outro.

RSA

Chave públicamais popular

Inven-tado em 1976

Rivest Shamir

Adleman

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

• Chave de codificação: n = pq.

• Pode ser tornada pública.

• Chave de decodificação são p e q.

• Tem que ser mantida secreta.

Escolha dois números primos p e q.

Calcule n = pq.

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 algaris-mos.

Com os recursos da época (computado-res 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 supercom-putador

• 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-1602152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753

Fatores

45427892858481394071686190649738831656137145778469793250959984709250004157335359 e

47388090603832016196633832303788951973268922921040957944741354648812028493909367

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?

?