Criptografia de Dados
Recursos Computacionais
Álvaro Degas
[email protected]
Roteiro
•
•
•
•
Introdução
Problemas
Conceitos
Criptografia
– chave privadas
– Chave pública
• Conclusões
Introdução
• O que é Criptografia
– Kriptos (Grego): Esconder
– Grapho (Grego): Escrita
– Kripto Grapho: Esconder Escrita
• A criptografia viabiliza a troca de
informações sem que haja o
comprometimento do sigilo
Introdução
• “Arte de tornar incompreensível, com
observância de normas especiais designadas
numa cifra de código, o texto de uma
mensagem escrita com clareza” - Aurélio
• Talvez seja tão antiga quanto a própria
escrita
Introdução
• “A mensagem é sua. Particular, privativa.
Ninguém tem o direito de bisbilhotar” –
Guia de Referência rápida do PGP
• PGP – Prety Good Privacy: Software de
criptografia multi-plataforma – Networks
Associates inc.
Introdução
• Criptografia usada por Júlio César (Imperador de
Roma - 60 a.C.):
– A chave utilizada era muito simples: desloca-se o alfabeto 3
letras e troca-as entre si.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
• Por exemplo, se ele quisesse enviar "Veni, vidi, vici",
qual seria a mensagem criptografada?
Conceitos
• Definições
– Mensagem: A informação que se deseja enviar
– Participantes: O Emissor e o Receptor da
mensagem
– Chaves: Os métodos de se criptografar e
decriptografar mensagens
Chaves de Criptografia
• Registros Irrecuperáveis (não descriptografáveis)
• Chaves Privadas
• Chaves Públicas
• Criptografar: Aplicar sobre a mensagem M uma
função F resultando num objeto C
“incompreensível”
• C = F(M)
Registros Irrecuperáveis
• Pode-se criptografar mas não se pode descriptografar
• Etimologicamente não se trata de
“criptografia”
• Conceito: Uma Mensagem M e uma função
F(M) |  F-1(M)
Registros Irrecuperáveis
• Exemplo:
• Converte M em um número grande (128
bits no mínimo)
• “Enxergar” mensagens como números não é
difícil: Uma tira de bits, várias tiras
(menores) de bits, concatenação de códigos
ASCII, etc. Cada aplicação pode ter a sua.
Registros Irrecuperáveis
• Armazena X(M) mod K – X e K secretos
– K muito grande (128 bits por exemplo)
– X(M) “gera” algo com o aproximadamente o
dobro do tamanho de M
• Uma mensagem N só pode ser igual a M se
X(N) mod K = X(M) mod K
• Pode acontecer de
– X(M) mod K = X(N) mod K com M  N?
Registros Irrecuperáveis
• Claro. O importante é: Qual a chance?
• K com 128 Bits  1038
• 1/1038 =
0,00000000000000000000000000000000000001
• Pequena o suficiente?
Chaves Privadas
•
•
•
•
•
Mecanismo para “embaralhar” a mensagem
De conhecimento apenas dos proprietários
Aplicar uma função F sobre a mensagem
F aqui é inversível!
Somente quem sabe que função foi aplicada
consegue recompor a mensagem original
Chaves Privadas
• Seja M uma mensagem e D o conjunto de
todas as mensagens possíveis, ou seja
– Dados os |M| bits que comporão mensagens, D
é o conjunto de todas as combinações possíveis
destes bits
• P(M) e S(M) são permutações de D (mais
combinações de bits)
Exemplo
• Escolher K um número muito grande (por
exemplo 128 bits)
• Armazenar K em local secreto e seguro. K é a
chave!
• Multiplicar M em blocos de tamanho |K| por K
• “Enxergar” mensagens como números não é
difícil: Uma tira de bits, várias tiras (menores) de
bits, concatenação de códigos ASCII, etc. Cada
aplicação pode ter a sua.
Exemplo
• C = M*K
• C terá o dobro do tamanho de K
• C pode ser enviada pela Internet sem
problemas
• O receptor, que conhece K faz M = C/K
Exemplo
M
C = K*M
Emissor
C
“Xereta”
M = C/K
Receptor
M
Se o “xereta” ler?
• C terá 256 bits “por bloco”
– Cada bloco em M de tamanho |K| multiplicado
pelo próprio K
– K tendo 128 bits
• Encontrar M é possível? Sim. “Basta”
Fatorar C. Um dos fatores será K, donde se
pode encontrar M
Fatorando C
• C tem 256 bits  1.15x1077
• Para se fatorar: testar até a raiz quadrada de
C  3.40x1038 testes
• Não testa os pares  1.70x1038 testes
• Supercomputador: 1025 testes por segundo
• Tempo estimado: 5470,07 séculos
Fatorando C
• Com |K| = 136 (1 byte a mais)... 272 bits 
7.59x1081
• 8.71x1040 testes
• Menos os pares: 4.35x1040 testes
• Mais de 100 vezes maior!
• A máquina teria que ser mais de 100 vezes
mais rápida para igualar os 5470,07 séculos!
Chave Pública
• Algoritmos de Criptografia usando Chaves
Públicas
• Problema: Nem sempre é possível “enviar” a
chave!
• Criptografar: Aplicar sobre a mensagem M uma
função F resultando num objeto C
“incompreensível”
• C = F(M)
Chave Pública
• Decriptografar: Aplicar sobre C a função F-1
resgatando novamente M
• F-1(C)=M
• Se F-1 for secreta e impossível de ser
encontrada, a criptografia é perfeita
• F e F-1 são ditas Chaves de Criptografia (e
Descriptografia obviamente!)
Chave Pública
• O problema da distribuição de Chaves:
• F pode ser conhecida, mas F-1 não pode.
• Para enviar uma mensagem, criptografar
com F. Só quem tem F-1 pode abrir!
• Obviamente F e F-1 tem que ser distintas!
Problemas resolvidos com chave
pública:
• Basicamente dois problemas:
– Exclusão do acesso de terceiros a mensagens de
outrem
– Estabelecer autenticidade de mensagens
(assinatura digital)
Chave Pública
• Cada participante tem uma chave pública e
uma secreta
• Exemplo: Ana e Beto.
– Ana tem as chaves PA e SA
– Beto tem as chaves PB e SB
• As chaves públicas e privadas são
estabelecidas por cada participante
Chave Pública
• As chaves são Funções, conforme já visto,
aplicadas sobre mensagens
• Relembrando: “Enxergar” mensagens como
números não é difícil: Uma tira de bits,
várias tiras (menores) de bits, concatenação
de códigos ASCII, etc. Cada aplicação pode
ter a sua.
Chave Pública
• Seja M uma mensagem e D o conjunto de
todas as mensagens possíveis, ou seja
– Dados os |M| bits que comporão mensagens, D
é o conjunto de todas as combinações possíveis
destes bits
• P(M) e S(M) são permutações de D (mais
combinações de bits)
Chave Pública
• As chaves são funções inversas:
– M=PA(SA(M))=SB(PB(M))  M  D
• Suposições sine qua non:
– Somente Ana computa SA
– Somente Beto computa SB
– Todo mundo computa PA e PB
Exemplo
• Beto manda uma mensagem para Ana:
M
PA
Beto
C=PA(M)
“Xereta”
SA
Ana
• Beto usa PA para criptografar
• Ana usa SA para descriptografar
M
Se o “xereta” ver?
•
•
•
•
C não tem sentido para ele!
PA não o ajuda em nada!
SA não é conhecida dele!
O “xereta” conseguiu uma tira enorme de
Bits Inútil!
Outro Exemplo
• Assinaturas Digitais
• Ana quer assinar um documento
Assina
SA
 = SA(M)
M

PA
M
(M,)
PA()
=?
Ok
Outro Exemplo
• Ana gera a assinatura da mensagem M com
=SA(M)
• Ana envia M e  para Beto
• Beto computa PA() e verifica se é igual a
M
Outro Exemplo
• Se for igual, aceita M como mensagem de
Ana.
• Caso contrário
– Ou a mensagem não é de Ana
– Ou foi corrompida (maliciosamente ou não)
• (M,) pode ser passado de Beto para
qualquer pessoa, que verifica tudo
novamente
Algoritmo RSA
• Criptossistema RSA (Rivest, Shamir,
Adleman)
• Como selecionar as chaves
• Dois números primos muito grandes (de
100 dígitos ou mais cada) p e q
• Calcula n = p*q
Algoritmo RSA
• Calcula (n) = (p-1) * (q-1)
• Selecionar um pequeno número ímpar, (e)
relativamente primo a (n) = (p-1) * (q-1)
• Calcula d = inverso multiplicativo e, mod (n)
• Publica o par P=(e,n) como chave pública
• Guarda S=(d,n) como chave secreta (basta d
pois n é público)
Algoritmo RSA
• Como Criptografar e Decriptografar?
– D = {0,1,2,...,n-1} (mensagens possíveis)
– P(M) = Me mod n
– S(C) = Cd mod n
Um exemplo
• Caso prático:
–
–
–
–
–
p=11
q=13
n=143 (universo de mensagens possíveis)
(n) = 10*12 = 120
e=7 (primo em relação a 120)
Um exemplo
• Como se calcula d?
– d é o inverso multiplicativo de e mod (n) (de 7
mod 120)
• Isso significa que e*d mod (n) = 1
• Extended_euclid(e, (n))
• d é o valor x que retorna de
extended_euclid(7, 120)
Um exemplo
Extended_euclid(a,b)
If b=0
return(a,1,0)
Else
(d’,x’,y’) := extended_euclid(b, a mod
b)
(d,x,y) := (d’, y’, x’ – (a div b)*y’)
while d < 0
d = d + b - 1
return d, y, y)
Um exemplo
•
•
•
•
•
•
d = 103
Supor uma mensagem M = 40
Publica e=7 e n=143. Guarda d=103
C = P(M) = Me mod n = 407 mod 143 = 105
S(C) = Cd mod n = 105103 mod 143 = 40
Que é a mensagem original perfeitamente
recuperada.
Um exemplo
• Considerações de complexidade:
• Fazer a exponenciação de números grandes:
Seja o algoritmo computacionalmente simples
Exp_Modular(a,b,n) /* calcula ab mod n*/
1. d  1
2. Seja <bk, ..., b0> b em binário
3. Para i= k downto 1
4.
d  d2 mod n
5.
Se bi = 1
6.
d  (d*a) mod n
7. Return d
Um exemplo
• 105103 mod 143
• 10310 = 11001112 (k=6)
i
bi
6
1
5
1
4
0
3
0
2
1
1
1
0
1
d(4)
1
14
27
14
53
1
14
d(6)
105
40
27
14
131 105
40
Um exemplo
• Quebrar a criptografia
• Para quebrar o sistema basta encontrar os
valores p e q que geraram n.
• Escolhe-se dois primos grandes e com
uma grande diferença numérica entre si
• Para encontrar os fatores primos de n
– Testar candidatos entre 1 e a raiz quadrada de n
Um exemplo
• Encontrar os fatores de 667
• Raiz de 667 = 25,8...
• Entre 2 e 25 há algum fator, se 667 não for
primo.
• Com efeito, 23 (e por conseguinte 29) é
fator
Um exemplo
• Encontrar os fatores de
123456789012345678901234567890123456
789012347 (45 dígitos)
• Raiz de
123456789012345678901234567890123456
789012347 = algo entre 1022 e 1023
• Desprezando-se os números pares (que não podem
ser primos grandes) restam algo entre 1021 e 1022
candidatos, no mínimo!
Um exemplo
• Suponha uma máquina que faça 1010
divisões por segundo (cada candidato é
testado com uma divisão)
• 1 ano tem 31.536.000 segundos
• 31.536.000*1010 testes por ano
Um exemplo
• Isso é menor que 1018
• Com 1018 testes levar-se-ia 5000 anos!
• Caso a máquina fique 5000 vezes mais
rápida, um aumento de 4 algarismos levaria
os 5000 anos originais para 500.000.000
de anos!
• Eis outro exemplo de problema NP!
Eficiência
• M {0,1,...,n-1}
• Mesmo n = 200 trata apenas mensagens
pequenas (660 bits aproximadamente)
• O processo é lento, as mensagens são
pequenas
Eficiência
• Como resolver?
– Algoritmos de Criptografia (mais rápidos) com
uma chave K aleatória (Huffman pode ser uma
solução)
– Criptografa a mensagem longa com K
– Criptografa K com P
– Envia K(M) e P(K)
Conclusões
• Os algoritmos se baseiam em problemas
não polinomiais
• Métodos exponenciais são extremamente
inviáveis de serem tratados com a máquina
de Turing
• Praticamente TODA a informação sensível
do planeta está guardada por métodos como
estes
Conclusões
• As alternativas para resolver tais problemas
esbarram na complexidade e nos métodos
numéricos
• Computação Quântica:
– A possibilidade é de operar-se N QuBits ao mesmo
tempo, em todos os seus possíveis valores
– “Derruba” a complexidade dos métodos
– Acaba com Criptografia.
Criptografia.
FIM!
“Dize-e com quem andas e dir-te-ei se vou contigo”
Barão de Itararé
Degas