Seminário ccet

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Criptografia RSA: uma aplicacao dos numerosprimos

Profo Jose Sergio

Universidade Estadual de Montes ClarosDepartamento de Ciencias Exatas/Centro de Ciencias Exatas e Tecnologicas

Caixa Postal 126 – 39401-089 – Montes Claros – MG – [email protected]

9 de junho de 2010

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos



Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

1 Motivacao

2 Introducao

3 Um pouco de Historia

4 Fundamentacao Teorica do RSA

5 Metodologia

6 Exemplo

7 Como quebrar o RSA?

8 Referencias




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Motivacao

Relembrar alguns conceitos basicos da Teoria dosNumeros.

Relembrar a definicao de Numeros Primos e suas principaispropriedades.

Mostrar uma das milhares de aplicacoes diretas damatematica no cotidiano do ser humano.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Motivacao







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Motivacao







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Encaminhar mensagens de forma segura e uma praticaantiga (Grecia Antiga).

Nos dias de hoje o sigilo de informacoes e fundamental.

As mensagens transmitidas pela internet podem serinterceptadas com certa facilidade.

Portanto, e necessario codifica-las.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Para manter tais informacoes em sigilo, foi necessario criarcodigos difıceis de serem quebrados, mesmo com a ajudade computadores.

O codigo (metodo) mais utilizado nos dias de hoje e oRSA.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Para manter tais informacoes em sigilo, foi necessario criarcodigos difıceis de serem quebrados, mesmo com a ajudade computadores.

O codigo (metodo) mais utilizado nos dias de hoje e oRSA.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

O RSA, foi criado em 1978, por R. L. Rivest, A. Shamir eL. Adleman, quando trabalhavam no M.I.T.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

A implementacao do metodo depende da obtencao de doisnumeros primos muito grandes.

Daı a existencia desse trabalho, que dentre outras coisas,apresenta um algoritmo de verificacao de primalidade.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

A implementacao do metodo depende da obtencao de doisnumeros primos muito grandes.

Daı a existencia desse trabalho, que dentre outras coisas,apresenta um algoritmo de verificacao de primalidade.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Criptologia = kryptos (esconder) + logos(estudo)

estudo do oculto

Criptografia = kryptos (esconder) + graphia(escrita)

arte de esconder mensagens




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Criptologia = kryptos (esconder) + logos(estudo)

estudo do oculto

Criptografia = kryptos (esconder) + graphia(escrita)

arte de esconder mensagens




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Decifrar

ler a mensagem sem autorizacao

Decodificar

ler a mensagem com autorizacao




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Decifrar

ler a mensagem sem autorizacao

Decodificar

ler a mensagem com autorizacao




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

O primeiro a utilizar a criptografia como meio de esconderinformacoes secretas foi Cesar.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


O codigo de Cesar foi utilizado por muito tempo paratransmitir mensagens militares.

Ela e um tipo de cifra de substituicao na qual cada letrado texto e substituıda por outra, que se apresenta noalfabeto abaixo dela um numero fixo de vezes.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


O codigo de Cesar foi utilizado por muito tempo paratransmitir mensagens militares.

Ela e um tipo de cifra de substituicao na qual cada letrado texto e substituıda por outra, que se apresenta noalfabeto abaixo dela um numero fixo de vezes.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Um exemplo do codigo de Cesar e o seguinte:

A B C D E F G H I J K L M

D E F G H I J K L M N O P

N O P Q R S T U V W X Y Z

Q R S T U V W X Y Z A B C




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Basicamente, o que o codigo acima faz, e transladar as letrasdo alfabeto.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Dessa forma, a codificacao de “Pesquisa cientıfica” sera:

Shvtxlvd flhqwlifld

Ja a decodificacao de “D Pdwhpdwlfd h mlqgd!” e:

A Matematica e linda!




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Dessa forma, a codificacao de “Pesquisa cientıfica” sera:

Shvtxlvd flhqwlifld

Ja a decodificacao de “D Pdwhpdwlfd h mlqgd!” e:

A Matematica e linda!




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


E um metodo interessante, mas com imperfeicoes graves:

E de facil decodificacao (frequencia das letras).

Saber codificar implica em saber decodificar.

Precisa de um canal seguro.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias









Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias









Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta


Precisa de canal seguro.

2 Chave Publica

Saber codificar nao implica saber decodificar.

Nao precisa de canal seguro.

O mais popular e o RSA.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias



1 Chave secreta



2 Chave Publica







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias



1 Chave secreta



2 Chave Publica







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias



1 Chave secreta



2 Chave Publica







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias



1 Chave secreta



2 Chave Publica







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias



1 Chave secreta



2 Chave Publica







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias



1 Chave secreta



2 Chave Publica







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Basicamente, o RSA se baseia nos seguintes fatos:

Existem infinitos numeros primos.

Quanto maior for um numero, mais difıcil de fatora-lo.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Basicamente, o RSA se baseia nos seguintes fatos:

Existem infinitos numeros primos.

Quanto maior for um numero, mais difıcil de fatora-lo.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Sendo assim, para entender o RSA e necessario:

Um bom conhecimento de resultados da Teoria dosNumeros.

Principalmente dos que se referem aos numeros primos.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Sendo assim, para entender o RSA e necessario:

Um bom conhecimento de resultados da Teoria dosNumeros.

Principalmente dos que se referem aos numeros primos.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


- Numeros Primos (Definicao e exemplos)

Um numero inteiro positivo p 6= 1 e dito primo, se possuiapenas dois divisores.

Portanto, esses divisores devem ser a unidade e o proprionumero.

Exemplos: 2, 3, 5, 7, 11, 13, 17,..., 41, 43, 47, ...




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias





Exemplos: 2, 3, 5, 7, 11, 13, 17,..., 41, 43, 47, ...




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias





Exemplos: 2, 3, 5, 7, 11, 13, 17,..., 41, 43, 47, ...




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Exemplo de um algoritmo de verificacao de primalidade,implementado em linguagem JAVA.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Vamos, agora, estudar a Matematica basica para seentender o RSA

- Congruencia Modulo n:

Dizemos que a, b ∈ Z sao congruentes modulo n se, esomente se, a e b deixam o mesmo resto na divisao por n.Quando isso ocorrer, escrevemos

a ≡ b (mod n)




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Exemplos

1 15 ≡ 3 (mod 4), pois 15 : 4 tem resto 3 e 3 : 4 tambem.


3 10 ≡ 5(mod 5), pois deixam resto 0 na divisao por 5.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Exemplos







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Exemplos







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


- Anel dos Inteiros Modulo n, Zn:

Indicaremos por a a classe de todos os inteiroscongruentes a a modulo n. Exemplo:

1 Em modulo 4 temos

0 = {...,−8,−4, 0, 4, ...}1 = {...,−7,−3, 1, 5, ...}2 = {...,−6,−2, 2, 6, ...}3 = {...,−5,−1, 3, 7, ...}

Portanto, Z4 = {0, 1, 2, 3}




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


- Anel dos Inteiros Modulo n, Zn:

Indicaremos por a a classe de todos os inteiroscongruentes a a modulo n. Exemplo:

1 Em modulo 4 temos

0 = {...,−8,−4, 0, 4, ...}1 = {...,−7,−3, 1, 5, ...}2 = {...,−6,−2, 2, 6, ...}3 = {...,−5,−1, 3, 7, ...}

Portanto, Z4 = {0, 1, 2, 3}




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Em geral, temos que

Zn = {0, 1, ..., n − 1}




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


- Unidades em Zn:

Dizemos que a e uma unidade em Zn quandoa · x ≡ 1 (mod n), para algum x ∈ Zn.

Em Z6 temos

U(Z6) = U(6) = {1, 5} pois,

1 · 1 = 1 ≡ 1 (mod 6).

5 · 5 = 25 ≡ 1 (mod 6).




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


- Funcao ϕ de Euler:

Se p e q sao dois numeros primos distintos, definimos a funcaoϕ de Euler da seguinte forma:

ϕ(p) = p − 1 e ϕ(pq) = (p − 1)(q − 1)




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Encontrar a funcao ϕ de Euler para x ∈ Z+, significadescobrir:

“quantos inteiros positivos t, com t < x , sao coprimoscom x , ou seja, onde mdc(x , t) = 1.”

Exemplo:

ϕ(9) = 6, ja que nesse caso, t ∈ {1, 2, 4, 5, 7, 8}.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias




Exemplo:





Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias




Exemplo:





Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


A implementacao do RSA necessita de uma chave publica e deuma chave privada.

Chave publica: par ordenado de numeros, utilizado paracodificar uma mensagem.

Chave privada: par ordenado de numeros, utilizado paradecodificar uma mensagem previamente codificada.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


A implementacao do RSA necessita de uma chave publica e deuma chave privada.

Chave publica: par ordenado de numeros, utilizado paracodificar uma mensagem.

Chave privada: par ordenado de numeros, utilizado paradecodificar uma mensagem previamente codificada.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia

Escolhe-se p e q primos distintos.

Calcula-se n = pq.

Calcula-se ϕ(n) = (p − 1)(q − 1).

Encontra-se e, tal que 1 < e < ϕ(n) commdc(ϕ(n), e) = 1.

Encontra-se d , tal que d · e ≡ 1 (mod ϕ(n)), isso e, d e oinverso de e mod (ϕ(n)).

O par (n, e) sera a chave publica.

O par (n, d) sera a chave privada.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia


Calcula-se n = pq.

Calcula-se ϕ(n) = (p − 1)(q − 1).








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia


Calcula-se n = pq.

Calcula-se ϕ(n) = (p − 1)(q − 1).








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia


Calcula-se n = pq.

Calcula-se ϕ(n) = (p − 1)(q − 1).








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia


Calcula-se n = pq.

Calcula-se ϕ(n) = (p − 1)(q − 1).








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia


Calcula-se n = pq.

Calcula-se ϕ(n) = (p − 1)(q − 1).








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia


Calcula-se n = pq.

Calcula-se ϕ(n) = (p − 1)(q − 1).








Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia

Converte-se as letras da mensagem em numeros, usando atabela ASCII.

Teremos uma sequencia numerica que deve ser quebradaem blocos menores do que n.

Cada bloco m sera codificado usando a seguinte receita:

C (m) = me (mod n) = k

Para recuperar a mensagem codificada, usaremos a receita:

D(k) = kd (mod n) = m




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia










Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia










Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia










Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia

A Tabela ASCII (American Standard Code for InformationInterchange) e usada pela maior parte da industria decomputadores para a troca de informacoes.

Cada caracter e representado por um codigo de 8 bits (umbyte).

Apresetamos a seguir um resumo da tabela ASCII.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

Vamos codificar a palavra PRIMO, usando p = 7 e q = 11.

n = p · q = 77,

ϕ(n) = (7− 1) · (11− 1) = 6 · 10 = 60,

e = 7 pois, 1 < 7 < ϕ(n) e mdc(ϕ(n), 7) = 1.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo


n = p · q = 77,

ϕ(n) = (7− 1) · (11− 1) = 6 · 10 = 60,

e = 7 pois, 1 < 7 < ϕ(n) e mdc(ϕ(n), 7) = 1.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo


n = p · q = 77,

ϕ(n) = (7− 1) · (11− 1) = 6 · 10 = 60,

e = 7 pois, 1 < 7 < ϕ(n) e mdc(ϕ(n), 7) = 1.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

A chave publica (chave de codificacao) sera

(n, e) = (77, 7)

d = 43, ja que

43 · 7 = 301 ≡ 1 (mod 60).

Logo, a chave privada (chave de decodificacao) e o par

(77, 43).




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo


(n, e) = (77, 7)

d = 43, ja que

43 · 7 = 301 ≡ 1 (mod 60).


(77, 43).




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo


(n, e) = (77, 7)

d = 43, ja que

43 · 7 = 301 ≡ 1 (mod 60).


(77, 43).




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

- Tabela de Codificacao

A Tabela de codificacao que itulizaremos e a seguinte:

A B C D E F G H I J K L M

10 11 12 13 14 15 16 17 18 19 20 21 22

N O P Q R S T U V W X Y Z

23 24 25 26 27 28 29 30 31 32 33 34 35




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

Dessa forma, podemos concluir que

PRIMO = 2527182224.

Uma forma de quebrar esse numero em blocos de valoresmenores que 77 e

2, 5, 2, 71, 8, 2, 22, 4




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

Dessa forma, podemos concluir que

PRIMO = 2527182224.

Uma forma de quebrar esse numero em blocos de valoresmenores que 77 e

2, 5, 2, 71, 8, 2, 22, 4




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

A codificacao de cada bloco acima e dada por:

C (2) = 27 (mod 77) = 51 C (5) = 57 (mod 77) = 47

C (71) = 36 C (8) = 57

C (22) = 22 C (4) = 60




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

Portanto, a mensagem codificada e

51− 47− 51− 36− 57− 51− 22− 60




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

Para decodificar cada bloco ja codificado faremos o seguinte:

D(51) = 5143 (mod 77) = 2 D(47) = 4743 (mod 77) = 5

D(36) = 71 D(57) = 8

D(22) = 22 D(60) = 4

Logo, a sequencia decodificada sera

2− 5− 2− 71− 8− 2− 22− 4

Que corresponde, via tabela de conversao, a palavra

PRIMO.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

Para decodificar cada bloco ja codificado faremos o seguinte:

D(51) = 5143 (mod 77) = 2 D(47) = 4743 (mod 77) = 5

D(36) = 71 D(57) = 8

D(22) = 22 D(60) = 4

Logo, a sequencia decodificada sera

2− 5− 2− 71− 8− 2− 22− 4

Que corresponde, via tabela de conversao, a palavra

PRIMO.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?

A chave de decodificacao e (n, d).

Todos conhecem n, mas d so e conhecido por uma pessoaatorizada.

Para alguem nao autorizado encontrar d ele deve:

1 Conhecer ϕ(n).

2 Para conhecer ϕ(n) e necessario conhecer p e q.

3 Entao, basta fatorar n.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?




1 Conhecer ϕ(n).






Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?




1 Conhecer ϕ(n).






Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?




1 Conhecer ϕ(n).






Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?




1 Conhecer ϕ(n).






Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?




1 Conhecer ϕ(n).






Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?

Mas, na implementacao do RSA, sao usados dois primosmuito grandes.

Eles sao da ordem aproximada de 1050.

Um computador executa cerca de 1010 divisoes porsegundo.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?







Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?

Logo, o tempo gasto para se fatorar um numero da ordemde 1050 e aproximadamente:

1050

1010 = 1040 segundos ' 1031 anos

Idade do universo ' 1011 anos !!!!




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?


1050

1010 = 1040 segundos ' 1031 anos





Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?


1050

1010 = 1040 segundos ' 1031 anos





Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?

Portanto, encontrar p e q conhecendo apenasn = pq e muito difıcil.

E e por isso, que garantimos a seguranca dometodo.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

Como quebrar o RSA?

Portanto, encontrar p e q conhecendo apenasn = pq e muito difıcil.

E e por isso, que garantimos a seguranca dometodo.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias

1 [1] Coutinho, S.C., Numeros Inteiros e Criptografia RSA,

IMPA, Serie de Computacao e Matematica - Segunda Edicao.

2 [2] Hefez, A., Elementos de Aritmetica, SBM, Textos

Universitarios.

3 [3] Oliveira, P.E.R.; Andrade, P.T.E.; Oliveira, R.L.G., RSA -

UFU.

4 [4] Filho, Joel G. Silva. Informacao, Codificacao e Seguranca

de Dados. Unb - Faculdade de Tecnologia - Departamento de

Engenharia Eletrica.

5 [5] Domingues, J.S., Utilizacao de Algoritmos de Primalidade

na Criptografia RSA. DPPG - CEFET MG.




Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias




Universitarios.


UFU.









Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias




Universitarios.


UFU.









Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias




Universitarios.


UFU.









Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias




Universitarios.


UFU.









Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria


Metodologia

Exemplo

Como quebraro RSA?

Referencias


Documents

Seminário ccet