3. Criptografia Assimétrica
Criptografia Assimétrica
• Criado em 1976 por Diffie & Hellman;
• Também conhecido como criptografia de
chave pública;
• Motivado pelo problema de distribuição de
chaves simétricas;
Criptografia Assimétrica
• Usa uma chave pública e uma chave privada;
• As chaves formam um par e trabalham em
conjunto;
• O que uma chave cifra a outra chave decifra;
Criptografia Assimétrica
• A chave pública todos podem conhecer;
• A chave privada apenas o dono pode
conhecer;
• Função de chaves: f(x) = y;
• Conhecendo y é muito difícil descobrir o valor
de x;
• Baseado na complexidade matemática;
Criptografia Assimétrica
Criptografia Assimétrica
Criptografia Assimétrica
Criptografia Assimétrica
Criptografia Assimétrica
Criptografia Assimétrica
Algoritmos Assimétricos
• Como fazer um algoritmo assimétrico válido?
• Usam duas técnicas:
– Aritmética exponencial modular;
– Curvas elípticas;
Algoritmos Assimétricos
• Dois algoritmos mais conhecidos:
– RSA e ElGamal;
• Algoritmos RSA:
• É o mais usado comercialmente;
• Cifra blocos de tamanho variado = n;
Algoritmo RSA
• O par de chaves é derivado de n;
• n é um número muito grande;
• n é resultado de dois números primos muito
grandes = p & q;
• p & q devem ter mais de 100 dígitos cada um;
Algoritmo RSA
• Um invasor pode conhecer a chave pública e o
número n;
• Mas não conhece p & q;
• Logo ele não consegue gerar a chave privada;
Algoritmo RSA
• Escolher dois números primos grandes (>
10^100) p e q
• Calcular n = p * q
• Escolher um número “e” relativamente primo
com (p – 1) * (q – 1)
• Calcular d de forma que e * d = 1 mod (p – 1) *
(q – 1), isto é, d = e-1 mod (p – 1) * (q – 1)
• Publicar (n, e) – chave pública, manter (n, d) –
chave privada – e p, q em segredo
Algoritmo RSA
•
•
•
•
KU = {e, n}
KR = {d, n}
Cifrar: M^e mod n
Decifrar: C^d mod n
• Invasor não consegue descobrir “d” a partir de
“e” e “n”
Algoritmo RSA
•
•
•
•
•
•
•
p= 7 e q = 17;
n = 119;
Totiente de n = 96;
e relativamente primo a 96 = 5;
d = 77;
KU = {5, 119}
KR = {77,119}
Algoritmo RSA
•
•
•
•
•
•
•
KU = {5, 119}
KR = {77, 119}
M = 19
Cifrar: 19^5 mod 119 = 66
C = 66
Decifrar: 66^77 mod 119 = 19
Obs: na prática a chave é bem maior, mais de
130 dígitos;
Hash e algoritmos
• Funções hash, ou message digests ou funções
one-way;
• Função hash: y = f(x);
• y é facilmente calculado;
• x é computacionalmente complexo;
Hash e algoritmos
• Uma função hash gera um resumo de sua
entrada;
• A partir do resumo não deve ser possível
encontrar-se a entrada;
• Não deve ser possível encontrar uma entrada
que gere um resumo específico;
Hash e algoritmos
• É usado para gerar impressão digital de
arquivos (por exemplo);
• Também é usado em certificados e assinatura
digital;
Hash e algoritmos
• Alguns algoritmos são: MD5, SHA-1, SHA-2 ou
SHA-256;
• SHA é o padrão do NIST;
• SHA-224, 256, 384 e 512;
Hash e algoritmos
Padd ing
(1 a 512 b its)
Tamanho da
M ensagem
(K mod 2 64 )
L x 512 bits = N x 32 bits
K b its
M ensagem
512 b its
512 b its
512 b its
512 b its
Y1
Yq
Y L-1
Y0
Va lor
Inic ia l
160
100...0
512
512
160
H SHA
512
160
H SHA
CV 1
CV q
512
160
H SHA
CV L-1
H SHA
A = 67452301 B = EFCDAB89
C = 98BADCFE D = 10325476
E = C3D2E1F0
160 b its
d igest
Assinatura Digital
• A criptografia assimétrica permite a
implementação de assinatura digital;
• Assinar é cifrar algo com a chave privada;
• Assinar toda a informação a ser enviada é um
processo muito caro computacionalmente;
Assinatura Digital
Fonte
M
E
Destino
M
EKRa(M)
KRa
D
KUa
M
Assinatura Digital
• É necessário cifrar todo o conteúdo para
garantir a origem?
Assinatura Digital
• Não!!!
• Basta cifrar apenas o hash do conteúdo;
• O hash irá garantir a autenticidade e a
integridade de todo o conteúdo;
Assinatura Digital – Transmissão
Assinatura Digital – Recepção