Entendendo Criptografia - INSTITUTO DE COMPUTAÇÃOrdahab/cursos/mo421-mc889/2014-1s/Welcome_files/... · Aspectos de Implementação • O criptosistema RSA usa somente uma operação

Entendendo Criptografia – Um Livro Texto para Estudantes e Profissionais

por Christof Paar e Jan Pelzl

www.crypto-textbook.com

Capítulo 7 – O Criptosistema RSA ver. 7 de dezembro de 2010

Estes slides foram preparados em inglês por Benedikt Driessen, Christof Paar and Jan Pelzl

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

Students and Practitioners by Christof Paar and Jan Pelzl.

Chapter 7 – The RSA Cryptosystem ver. December 7, 2010

Chapter 7 of Understanding Cryptography by Christof Paar and 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

•  O Criptosistema RSA

•  Aspectos de Implementação

•  Encontrando Primos Grandes

•  Ataques e Contramedidas

•  Lições Aprendidas

3/27








4/27

A seguir

5 /34 Chapter 7 of Understanding Cryptography by Christof Paar and Jan Pelzl

 O Criptosistema RSA

•  Em 1976, Martin Hellman e Whitfield Diffie publicaram o artigo que foi o marco para as chaves publicas.

•  Em 1977, Ronald Rivest, Adi Shamir e Leonard Adleman propuseram o criptosistema assimétrico RSA

•  Até o momento, o RSA é o criptosistema assimétrico mais largamente usado embora a criptografia de curvas elípticas (ECC) está se tornando cada vez mais popular.

•  O RSA é principalmente usado para 2 aplicações

•  Transporte de chaves (i.e., simétrica) (conforme Capítulo 13 do livro Entendendo Criptografia)

•  Assinaturas Digitais (conforme Capítulo 10 do livro Entendendo Criptografia)


 Encriptação e Decriptação

•  As operações do RSA são feitas sobre o anel inteiro Zn (i.e., aritmética módulo n), onde n = p * q, com p, q sendo primos grandes.

•  Encriptação e decriptação são simplesmente exponenciações no anel.

•  Na prática x, y, n e d são números inteiros muito grandes (≥ 1024 bits)

•  A segurança do esquema depende do fato que é muito difícil derivar o “expoente privado” d dada a chave pública (n, e)

Definição

Dado a chave pública (n,e) = kpub e a chave privada d = kpr , escrevemos

y = ekpub(x) ≡ xe mod n

x = dkpr(y) ≡ yd mod n

onde x, y ε Zn.

Chamamos ekpub() a operação de encriptação e dkpr() a de decriptação.


 Geração de Chave •  Como todos os sistemas assimétricos, o RSA tem uma fase de

iniciação durante o qual as chaves públicas e privadas são calculadas

Observação: •  Escolher os dois números primos grandes e distintos p, q (no passo 1) não é

trivial •  MDC(e, Φ(n)) = 1 garante que e tem um inverso, então sempre existe a chave

privada d

Algoritmo: Geração de Chave RSA Key

Saída: chave pública: kpub = (n, e) e chave privada: kpr = d

1.  Escolha dois números primos grandes p, q

2.  Calcule n = p * q

3.  Calcule Φ(n) = (p-1) * (q-1)

4.  Selecione um expoente publico e ε {1, 2, …, Φ(n)-1} tal que MDC (e, Φ(n) ) = 1

9.  Calcule a chave privada d tal que d * e ≡ 1 mod Φ(n)

10.  RETURN kpub = (n, e), kpr = d


 Exemplo: o RSA com números pequenos

ALICE

Mensagem x = 4

y = xe ≡ 43 ≡ 31 mod 33

BOB

1.  Escolha p = 3 e q = 11

2.  Calcule n = p * q = 33

3.  Φ(n) = (3-1) * (11-1) = 20

4.  Escolha e = 3

5.  d ≡ e-1 ≡ 7 mod 20

yd = 317 ≡ 4 = x mod 33

Kpub = (33,3)

y = 31








9/27

A seguir


 Aspectos de Implementação

•  O criptosistema RSA usa somente uma operação aritmética (exponenciação modular) a qual o faz um esquema assimétrico conceitualmente simples.

•  Mesmo conceitualmente simples, devido ao uso de números bem grandes, o RSA é ordens de magnitude mais lento que os esquemas simétricos, p.e., DES, AES

•  Quando implementando o RSA (especialmente em um ambiente limitado como smartcards e telefones celulares) uma atenção especial deve ser dada a escolha correta dos algoritmos aritméticos.

•  O algoritmo eleve_ao_quadrado-e-multiplique permite uma exponenciação rápida, mesmo de números bem grandes…


 Eleve_ao_quadrado-e-Multiplique •  Princípio básico: Varra os bits do expoente da direita para a esquerda

e eleve_ao_quadrao/multiplique o operando de acordo com o valor do bit.

•  Regra: Eleve ao quadrado em cada iteração (Passo 4) e multiplique o resultado corrente por x se o bit do expoente hi = 1 (Passo 6)

•  Fazendo a redução Modulo em cada passo mantem o operando y pequeno

Algoritmo: Eleve_ao_quadrado-e-Multiplique para xH mod n

Entrada: Expoente H, elemento base x, Modulo n

Saída: y = xH mod n

1.  Determine a representação binária H = (ht, ht-1, ..., h0)2

2.  y = x

3.  FOR i = t-1 TO 0

4.  y = y2 mod n

5.  IF hi = 1 THEN

6.  y = y * x mod n

7.  RETURN y


 Exemplo: Eleve_ao_quadrado-e-Multiplique

•  Calcule x26 sem redução modulo

•  Representação binária do expoente: 26 =(1,1,0,1,0)2=(h4,h3,h2,h1,h0)2

•  Observe como o expoente evolui em x26 = x11010

Passo Expoente Binário Oper Comentário

1 x = x1 (1)2 Iniciação, processa h4

1a (x1)2 = x2 (10)2 QUAD Processando h3

1b x2 * x = x3 (11)2 MULT h3 = 1


2b - (110)2 - h0 = 0


3b x12 * x = x13 (1101)2 MULT h1=1


4b - (11010)2 - h0 = 0


 Complexidade do Alg. Eleve_ao_quadrado-e-Multiplique •  O algoritmo Eleve_ao_quadrado-e-Multiplique tem uma

complexidade logarítmica, i.e., ele roda em tempo proporcional ao tamanho em bits do expoente (ao invés do seu valor absoluto).

•  Dado um expoente com t+1 bits H = (ht,ht-1, ..., h0)2

com ht = 1, precisamos das seguintes operações •  # de Elevações ao quadrado = t •  Média do # de multiplicações = 0.5 t •  Complexidade Total: #QUAD + #MULT = 1.5 t

•  Os expoentes são escolhidos aleatoriamente, então 1.5 t é uma boa estimativa do número médio de operações.

•  Note que cada elevação ao quadrado e cada multiplicação são operações com números muito grandes, p.e., inteiros de 2048 bits.


 Técnicas para aumentar a velocidade

•  A exponenciação modular é intensiva computacionalmente

•  Mesmo com o algoritmo eleve_ao_quadrado-e-multiplique, o RSA pode ser muito lento em dispositivos restritos tais como smart cards.

•  Alguns truques importantes:

•  Expoente publico e pequeno

•  Teorema do Chinês Resto (CRT)

•  Exponenciação com pré-computação (não coberta aqui)


 Encriptação rápida com o expoente publico pequeno. •  Escolher um expoente publico pequeno e não enfraquece a

segurança do RSA

•  Um expoente publico pequeno melhora significativamente a velocidade da encriptação RSA.

•  Este é um truque comumentemente usado (p.e., no SSL/TLS, etc.) e faz do RSA o mais rápido esquema assimétrico com respeito a encriptação!

Chave Pública e como uma string binária #QUAD + #MULT

21+1 = 3 (11)2 1 + 1 = 2

24+1 = 17 (1 0001)2 4 + 1 = 5

216 + 1 (1 0000 0000 0000 0001)2 16 + 1 = 17


 Decriptação rápida com o CRT

•  Escolher uma chave privada d pequena resulta em fraquezas na segurança!

•  De fato, d deve ter no mínimo 0,3t bits, onde t é o tamanho em bits do modulo n

•  Entretanto, o Teorema Chinês do Resto (CRT) pode ser usando para acelerar (um pouco) a exponenciação da chave privada d

•  Baseado no CRT podemos substituir a o calculo de:

xd mod Φ(n) mod n

por dois cálculos:

xd mod (p-1) mod p e xd mod (q-1) mod q

onde q e p são “pequenos” comparados com n


 Principio básico da exponenciação baseada no CRT

•  O CRT envolve três passos distintos:

(1) Transformação do operando no domínio do CRT

(2) Exponenciação modular no domínio do CRT

(3) Transformação inversa para o domínio do problema

•  Esses passos são equivalentes a uma exponenciação modular no domínio do problema.

x

xp

xq

Xpd mod (p-1) mod p

Xqd mod (q-1) mod q

xd mod n Domínio do Problema

Domínio do CRT


 CRT: Passo 1 – Transformação

•  A transformação no domínio do CRT requer o conhecimento de p e q

•  p e q são somente conhecidos pelo dono da chave privada, então o CRT não pode ser aplicado para acelerar a encriptação.

•  A transformação calcula (xp, xq) os quais são a representação de x no domínio do CRT. Eles podem ser facilmente calculados por:

xp ≡ x mod p e xq ≡ x mod q


 CRT: Passo 2 – Exponenciação

•  Dados dp e dq tais que

dp ≡ d mod (p-1) e dq ≡ d mod (q-1)

uma exponenciação no domínio do problema requer duas exponenciações no domínio do CRT

yp ≡ xpdp mod p e yq ≡ xq

dq mod q

•  Na prática, p e q são escolhidos para ter a metade do tamanho em bits de n, i.e., |p| ≈ |q| ≈ |n|/2


 CRT: Passo 3 – Transformação inversa

•  A transformação inversa requer duas vezes a inversão modular, o que é computacionalmente custoso

cp ≡ q-1 mod p e cq ≡ p-1 mod q

•  Com a inversão modular montamos yp, yq para obter o resultado y mod n in no domínio do problema

y ≡ [ q * cp ] * yp + [ p * cq ] * yq mod n

•  Tipicamente os primos p e q não mudam frequentemente, portanto o custo da inversão pode ser desconsiderado pois as duas expressões:

[ q * cp ] e [ p * cq ] podem ser pre-calculadas e armazenadas.


 Complexidade do CRT •  Ignoramos os passos de transformação e transformação inversa pois seus

custos podem ser desconsiderados dentro de considerações razoáveis. •  Assumindo que n tem t+1 bits, ambos p e q terão aproximadamente t/2

bits. •  A complexidade é determinada pelas duas exponenciações no domínio do

CRT. Os operandos terão somente t/2 bits. Para as exponenciações usamos o algoritmo de eleve_ao_quadrado-e-multiplique:

•  # quadrados (uma exp.): #SQ = 0.5 t •  # média de multiplicações (uma exp.): #MUL = 0.25t •  Complexidade total: 2 * (#MUL + #SQ) = 1.5t

•  Isto parece dar na mesma que exponenciações regulares, mas desde que os operandos tem metade do tamanho em bits comparados com o expoente original, então cada operação (i.e., multipl. e quadrado) é 4 vezes mais rápida!

•  Então o CRT é 4 vezes mais rápido que uma exponenciação direta.








22/27

A seguir


 Encontrando Números Primos Grandes

•  Gerar chaves para o RSA requer encontrar 2 primos grandes p e q tais que n = p * q seja suficientemente grande.

•  O tamanho de p e q é tipicamente metade do tamanho desejado de n

•  Para encontrar os primos, inteiros aleatórios são gerados e sua primalidade testada:

•  O Gerador de Números Aleatórios (RNG) deve ser não previsível senão um adversário pode adivinhar a fatoração de n

RNG Teste de Primalidade p' “p‘ é primo”

OR “p‘ é composto”

a

Candidato a primo


 Testes de Primalidade

•  Fatorar p e q para testar a primalidade é tipicamente inviável.

•  Entretanto, não estamos interessados na fatoração, queremos saber apenas se p e q são compostos.

•  Tipicamente os testes de primalidade são probabilísticos, i.e., eles não tem acuracidade de 100%, mas sua saída é correta com muita alta probabilidade

•  Um teste probabilístico tem duas saídas:

•  “p‘ é composto“ – sempre verdadeiro

•  “p‘ é um primo“ – verdadeiro com uma certa probabilidade

•  Dentre os bem-conhecidos testes de primalidade estão os seguintes:

•  Teste de Primalidade de Fermat

•  Teste de Primalidade de Miller-Rabin


 Teste de Primalidade de Fermat •  Ideia Básica: Todos os primos satisfazem o Teorema Pequeno de

Fermat, i.e., se um número p‘ é encontrado tal que ap‘-1 ≡ 1 mod p‘, então ele não é um primo.

•  Para certos números (“Números de Carmichael”) o teste frequentemente retorna “p‘ parece ser um primo“, embora estes números sejam compostos. Portanto, o Teste de Miller-Rabin Test é preferido.

Algoritmo: Teste de Primalidade de Fermat

Entrada: Candidato a primo p‘, parâmetro de segurança s

Saída: “p‘ é composto“ ou “p‘ parece ser um primo“

1.  FOR i = 1 TO s

2.  escolha aleatoriamente a ε {2,3, ..., p‘-2}

3.  IF ap‘-1 ≡ 1 mod p’ THEN

4.  RETURN “p‘ é composto“

5.  RETURN “p‘ parece ser um primo“


 Teorema para o teste de Miller-Rabin

•  O Teste de Miller-Rabin é mais poderoso e baseado no seguinte teorema:

•  Este teorema pode ser convertido em um algoritmo.

Teorema

Dada a decomposição de um impar candidato a primo p‘

p‘ – 1 = 2u * r

onde r é impar. Se pudermos encontrar um inteiro tal que

ar ≡ 1 mod p‘ e ar2j ≡ p‘ - 1 mod p‘

Para todo j = {0,1, ..., u-1}, então p‘ é composto.

Senão ele é provavelmente um primo.


 Teste de Primalidade de Miller-Rabin

Algoritmo: Teste de Primalidade de Miller-Rabin

Entrada: Candidato a primo p‘ com p‘-1 = 2u * r e parâmetro de segurança s

Output: “p‘ é composto“ ou “p‘ parece ser um primo“

1.  FOR i = 1 TO s

2.  escolha aleatoriamente a ε {2,3, ..., p‘-2}

3.  z ≡ ar mod p’

4.  IF z ≠ 1 AND z ≠ p’-1 THEN

5.  FOR j = 1 TO u-1

6.  z ≡ z2 mod p’

7.  IF z = 1 THEN


9.  IF z ≠ p‘-1 THEN


11.  RETURN “p‘ parece ser um primo“








28/27

A seguir


 Ataques e Contramedidas 1/3

•  Há dois tipos de ataques distintos aos criptosistemas

•  Ataques analíticos tentam quebrar a estrutura matemática do problema subjacente do RSA

•  Ataques de implementação tentam atacar a implementação no mundo real explorando as fraquesas inerentes da maneira como o RSA é implementado no software ou no hardware.


 Ataques e Contramedidas 2/3 O RSA é exposto tipicamente aos seguintes vetores de ataques analíticos

•  Ataques Matemáticos

•  O melhor ataque conhecido é a fatoração de n para obter Φ(n)

•  Pode ser prevenido usando modulo n suficientemente grande

•  O recorde corrente de fatoração é 664 bits. Então, é recomendado que n deva ter um tamanho entre 1024 e 3072 bits

•  Ataques de Protocolo

•  Exploram a maleabilidade do RSA, i.e., a propriedade que o texto encriptado tem de ser transformado em um outro texto encriptado que é decriptado em um texto em claro correlacionada -, sem conhecimento da chave privada.

•  Pode ser prevenido com um preenchimento (“padding”) apropriado.


 Ataques e Contramedidas 3/3

•  Ataques de implementação podem ser um dos seguintes:

•  Analise de Canal Colateral

•  Explora os vazamentos físicos da implementação do RSA (p.e., consumo de potencia, emanação EM, etc.)

•  Ataques de Indução a Falha

•  Induzindo falhas nos dispositivos enquanto o CRT é executado podem produzir um vazamento da chave privada.

Mais informações sobre os ataques podem ser encontradas na 7.8 do livro

“Entendendo Criptografia”








32/27

A seguir


 Lições Aprendidas •  O RSA é o sistema criptográfico de chave pública mais largamente

usado.

•  O RSA é usado principalmente para o transporte de chaves e assinaturas digitais.

•  A chave pública e pode ser um inteiro pequeno, porém a chave privada d precisa ter o tamanho em bits do modulo n

•  O RSA depende do fato de que é difícil fatorar n

•  Corrente um número de 1024 bits não pode ser fatorado, mas o progresso em fatoração pode alcançado essa capacidade em 10-15 anos. Então, o RSA com modulo de 2048 ou 3076 bits deve ser usado para uma segurança de longo prazo.

•  Uma implementação ingênua do RSA permite vários ataques, e na prática o RSA deve ser usado juntamente com preenchimento (“padding”).

Documents

Entendendo Criptografia - INSTITUTO DE COMPUTAÇÃOrdahab/cursos/mo421-mc889/2014-1s/Welcome_files/... · Aspectos de Implementação • O criptosistema RSA usa somente uma operação