Capítulo 6 – Introdução a Criptografia de Chave-Públicardahab/cursos/mo421-mc889/2014-1s/Welcome_files/... · Entendendo Criptografia – Um Livro Texto para Estudantes e Profissionais

Entendendo Criptografia – Um Livro Texto para Estudantes e Profissionais

por Christof Paar e Jan Pelzl

www.crypto-textbook.com

Capítulo 6 – Introdução a Criptografia de Chave-Pública

ver. 18 de novembro de 2010

Estes slides foram preparados em inglês por Timo Kasper e Christof Paar

Tradução para Português (Brasil) dos slides: Understanding Cryptography – A Textbook for

Students e Practitioners by Christof Paar e Jan Pelzl. Chapter 6 – Introduction to Public-key Cryptography ver. November 18, 2010

Chapter 6 of Understanding Cryptography by Christof Paar e Jan Pelzl

Algumas questões legais (desculpem): Termo de Uso

•  Os slides podem ser usados sem custos. Todos os direitos dos slides permanecem com Christof Paar e Jan Pelzl.

•  O título do livro que dá origem aos slides “Understanding Cryptography” by Springer e o nome dos autores devem permanecer em todos os slides.

•  Se os slides forem modificados, os créditos aos autores do livro e ao livro devem permanecer nos slides.

•  Não é permitida a reprodução de parte ou do todo dos slides em forma impressa sem a permissão expressa por escrito dos autores.

2/27


Conteúdo deste Capítulo

• Criptografia Simétrica Revisitada

• Princípios da Criptografia Assimétrica

• Aspectos Práticos da Criptografia de Chave-Pública

• Algoritmos Importantes de Chave-Pública

• Teoria dos Números Essencial para os Algoritmos de Chave-Pública

3/27








4/27

A seguir

5/29

Duas propriedades dos criptosistemas simétricos (de chave secreta):

•  A mesma chave secreta K é usada para encriptação e decriptação

•  Encriptação e decriptação são funções muito parecidas (ou até idêntico)

 Criptografia Simétrica Revisitada

eK(x) dK(y) x y x

K K

Alice Bob


6/29

 Criptografia Simétrica: Analogia


K K

Safe with a strong lock, only Alice e Bob have a copy of the chave

•  Alice encrypts à locks message in the safe with her chave

•  Bob decrypts à uses his copy of the chave to open the safe

•  Algoritmos Simétricos, p.e., AES e 3DES, são muito seguros, rápidos e generalizados, mas:

•  Problema de distribuição de chaves: A chave secreta deve ser transportada seguramente

•  Número de chaves: Na rede, cada par de usuários requer uma chave individual

à n usuários da rede requerem chaves, cada usuário armazena (n-1) chaves

•  Alice ou Bob podem enganar o outro, porque eles tem chaves idênticas. Exemplo: Alice pode afirmar que ela nunca fez pedido de uma TV on-line para o Bob (ele poderia ter inventado seu pedido). Para previr isso é necessário : irretratabilidade ("non-repudiation“)

7/29

 Criptografia Simétrica: Deficiências

Exemplo:

6 usuários (nós)

chaves (arestas)


15256=

⋅








8/27

A seguir

Ideia Nova: Use o princípio “a velha e boa caixa do correio”:

Todos podem enviar uma carta Mas: Somente o dono tem a chave correta para abrir a caixa

9/29

  Ideia por trás da Criptografia Assimétrica


1976: a primeira publicação de um algoritmo com esse conceito por Whitfield Diffie e Martin Hellman,e também por Ralph Merkle.

10/29

 Criptografia Assimétrica (De Chave-Pública)

Princípio: “Divida” a chave

K

Chave Pública (Kpub) (Encripta)

Chave Secreta (Kpr) (Decripta)


à Durante a geração da chave, um par de chaves Kpub e Kpr é calculado

11/29

 Criptografia Assimétrica: Analogia


Seguro com um cadeado público e cadeado privado:

•  Alice deposita (encripta) uma mensagem com a - não secreta - chave pública Kpub

•  Somente Bob tem a - secreta – chave privada Kpr para recuperar (decripta) a mensagem

(Kpub) (Kpr)

abre deposita

chave pública chave privada








12/27

A seguir

13/29

  Protocolo Básico para a Encriptação de Chave-Pública

Alice Bob

(KpubB,KprB) = K KpubB

x y=eKpubB(x) y

x=dKprB(y)


à Problema da Distribuição de Chave resolvido* (*) pelo menos por agora, chaves públicas precisam ser autenticadas, veja Cap. 13 do Entendendo Criptografia.

14/29

 Mecanismos de Segurança da Criptografia de Chave-Pública

Aqui estão os principais mecanismos que podem ser implementados com criptografia assimétrica:

•  Distribuição de chave (p.e., troca de chaves Diffie-Hellman, RSA) sem o pré-compartilhamento de um segredo (chave)

•  Irretratabilidade e Assinaturas Digitais (p.e., RSA, DSA ou ECDSA) provem integridade de mensagem

•  Identificação, usando protocolos de desafio-resposta com assinaturas digitais.

•  Encriptação (p.e., RSA / Elgamal) Desvantagem: Muito intensivo computacionalmente (1000 vezes mais lento que os Algoritmos Simétricos!)


15/29

  Protocolo Básico de Transporte de Chave 1/2

Na prática: Sistemas Híbridos, incorporando algoritmos assimétricos e simétricos:

1.  Troca de chave (para esquemas simétricos) e assinaturas digitais são feitas com algoritmos assimétricos (mais lentos)

2.  Inscrição dos dados é feita usando cifras simétricas (mais rápidas), p.e., cifras de bloco ou cifras de fluxo


  Protocolo Básico de Transporte de Chave 2/2

Alice

16/29 Chapter 6 of Understanding Cryptography by Christof Paar e Jan Pelzl

Bob

y1 = eKpubB(K) y1

K = dKprB(y1)

Troca de Chave (assimétrico)

y2 = AESK (x) x = AES-1K (y2)

y2

Encriptação de Dados

(simétrico)

(KpubB,KprB) = K KpubB

Escolha uma chave simétrica

aleatória K

mensagem x

Exemplo: Protocolo hibrido com AES como a cifra simétrica








17/27

A seguir

18/29

 Como construir Algoritmos de Chave-Pública Esquemas assimétricos são baseados em uma “função de mão-única” f():

•  Calculando y = f(x) é computacionalmente fácil.

•  Calculando x = f-1(y) é computacionalmente inviável

Funções de mão-única são funções baseadas em problemas matemáticos difíceis. Três famílias principais:

•  Fatoração de inteiros (RSA, ...): Dado um inteiro composto n, encontrar seus fatores primos (Multiplicar dois primes: fácil)

•  Logaritmo Discreto (Diffie-Hellman, Elgamal, DSA, …): Dado a, y e m, encontrar x tal que ax = y mod m (Exponenciação ax : fácil)

•  Curvas Elípticas (EC) (ECDH, ECDSA): Generalização do Logaritmo Discreto

Nota: Os problemas são considerados matematicamente difíceis, mas nenhuma prova existe (até agora).


19/29

  Tamanhos de Chave e Níveis de Segurança

Simétrica ECC RSA, DL Observação

64 Bit 128 Bit ≈ 700 Bit Somente Curto Prazo (poucas horas ou dias)

80 Bit 160 Bit ≈ 1024 Bit Segurança Média

(exceto para ataques de grandes instituições governamentais, etc.)

128 Bit 256 Bit ≈ 3072 Bit Segurança de Longo Prazo (sem computadores quanticos)

•  A complexidade exata do RSA (fatoração) e do DL (Index-Calculus) é difícil de estimar

•  A existencia de computadores quanticos será provavelmente o fim do ECC, RSA e DL (em no minimo 2-3 decadas a frente, e algumas pessoas duvidam de que os CQs existiram algum dia)









20/27

 Algoritmo Euclidiano 1/2

•  Calcule o Máximo Divisor Comum MDC (r0, r1) de dois inteiros r0 e r1

•  O MDC é fácil para números pequenos (MDC em inglês gcd): 1. fatores r0 e r1 2. MDC = Máximo Divisor Comum

•  Exemplo: r0 = 84 = 2 . 2 . 3 . 7 r1 = 30 = 2 . 3 . 5

à O MDC é o produto de todos os fatores primos comuns: 2 . 3 = 6 = MDC (30,84)

•  Mas: Fatorar é complicado (e frequentemente inviável) para números grandes.


 Algoritmo Euclidiano 2/2

•  Observação: MDC (r0, r1) = MDC (r0 - r1, r1)

à Ideia central:

•  Reduza o problema de encontrar o MDC de dois números dados no MDC de dois números menores

•  Repita o processo recursivamente

•  No final MDC (ri, 0) = ri é a resposta do problema original!

Exemplo: MDC (r0, r1) for r0 = 27 e r1 = 21

•  Nota: um método muito eficiente para grandes números: A complexidade cresce linearmente com o numero de bits

Para o algoritmo Euclidiano completo veja o Capitulo 6 do livro “Entendendo Criptografia”.


 Algoritmo Euclidiano Estendido 1/2

•  Estendendo o algoritmo Euclidiano para encontrar o inverso modular de r1 mod r0

•  EEA calcula s,t, e o MDC :

•  Tome a relação do mod r0

à Compare com a definição do inverso modular: t é o inverso de r1 mod r0

•  Note que MDC (r0, r1) = 1 para que o inverso exista.

•  Formula Recursiva para calcular s e t em cada passo

à “tabela magica“ de r, s, t e o quociente q para derivar o inverso com lápis e papel.

(conforme. Sessão 6.3.2 do livro “Entendendo Criptografia”)


 Algoritmo Euclidiano Estendido 2/2

Exemplo:

•  Calcule o inverso modular de 12 mod 67:

•  Da tabela mágica temos

•  Então 28 é o inverso de 12 mod 67.

•  Verifique:

Para o completo Algoritmo Euclidiano Estendido veja o Capítulo 6 do Livro Entendendo Criptografia.


67mod13361228 ≡=⋅

  Função Phi de Euler 1/2

•  Problema novo importante para sistemas de Chave-Pública, p.e., RSA: Dado um conjunto de m inteiros {0, 1, 2, …, m -1}, Quantos números no conjunto são primos entre-si com m ?

•  Resposta: função Phi de Euler Φ(m)

•  Exemplo de conjuntos {0,1,2,3,4,5} (m=6), e {0,1,2,3,4} (m=5)

à 1 e 5 são primos entre si com m=6, à Φ(5) = 4 logo Φ(6) = 2

•  Testando um MDC por numero do conjunto é extremamente lento para um número m grande.


•  Se a fatoração canônica de m é conhecida: (onde pi primos e ei inteiros positivos)

•  então calcule Phi de acordo com a formula

•  Phi é especialmente fácil para ei = 1, p.e., m = p . q à Φ(m) = (p-1) . (q-1)

•  Exemplo m = 899 = 29 . 31: Φ(899) = (29-1) . (31-1) = 28 . 30 = 840

•  Note: Encontrar Φ(m) é computacionalmente fácil se a fatoração de m é conhecida. (caso contrário o cálculo de Φ(m) torna-se computacionalmente inviável para números grandes)

  Função Phi de Euler 2/2


•  Dado um primo p e um inteiro a:

•  Pode-se escrever que

•  Uso: Encontre o inverso modular, se p é primo.

Rescreva para

•  Comparando com a definição do inverso modular

à é o inverso modular modulo um primo p

Exemplo: a = 2, p = 7

•  O Teorema Pequeno de Fermat só funciona se o modulo p é um primo

  Teorema Pequeno de Fermat


  Teorema de Euler

•  Generalização do Teorema Pequeno de Fermat para qualquer modulo inteiro

•  Dados dois inteiros primos entre si a e m :

•  Exemplo: m=12, a=5

1. Calcule a Função Phi de Euler

2. Verifique o Teorema de Euler

•  Teorema Pequeno de Fermat = caso particular do Teorema de Euler

•  Para um primo p:

à Fermat:


29/29

  Lições Aprendidas

•  Algoritmos de Chave-Pública tem capacidades que as cifras simétricas não tem, em particular assinaturas digitais e funções de estabelecimento de chave.

•  Algoritmos de Chave-Pública algoritmos são computacionalmente intensivos (uma maneira simpática de dizer que eles são lentos), e consequentemente são pouco adequados para a criptografia de dados em massa.

•  Somente três famílias de esquemas de Chave-Pública são largamente usados. Isto é consideravelmente menor que o caso dos algoritmos simétricos.

•  O algoritmo Euclidiano estendido permite-nos calcular inversos modulares rapidamente, o que é importante para a maioria dos esquemas de Chave-Pública.

•  A Função Phi de Euler dá-nos o numero de elementos menores que o um inteiro n que são primos-entre-si com n. Isto é importante para o esquema de criptografia RSA.


Documents

Capítulo 6 – Introdução a Criptografia de Chave-Públicardahab/cursos/mo421-mc889/2014-1s/Welcome_files/... · Entendendo Criptografia – Um Livro Texto para Estudantes e Profissionais