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 – Brasiljsergiomat@lsi.cefetmg.br

9 de junho de 2010

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Decifrar

ler a mensagem sem autorizacao

Decodificar

ler a mensagem com autorizacao

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Introducao

Decifrar

ler a mensagem sem autorizacao

Decodificar

ler a mensagem com autorizacao

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Um pouco de Historia

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta

Saber codificar implica em saber decodificar.

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta

Saber codificar implica em saber decodificar.

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta

Saber codificar implica em saber decodificar.

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta

Saber codificar implica em saber decodificar.

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta

Saber codificar implica em saber decodificar.

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta

Saber codificar implica em saber decodificar.

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Existem dois tipos de codigos criptograficos:

1 Chave secreta

Saber codificar implica em saber decodificar.

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Basicamente, o RSA se baseia nos seguintes fatos:

Existem infinitos numeros primos.

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Basicamente, o RSA se baseia nos seguintes fatos:

Existem infinitos numeros primos.

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

- 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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

- 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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

- 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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Exemplos

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

2 21 ≡ 5 (mod 2), pois 21 : 2 tem resto 1 e 5 : 2 tambem.

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Exemplos

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

2 21 ≡ 5 (mod 2), pois 21 : 2 tem resto 1 e 5 : 2 tambem.

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Exemplos

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

2 21 ≡ 5 (mod 2), pois 21 : 2 tem resto 1 e 5 : 2 tambem.

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

- 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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

- 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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

Em geral, temos que

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

- 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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

- 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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Fundamentacao Teorica do RSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Metodologia

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Exemplo

Portanto, a mensagem codificada e

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

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

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 Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos

CriptografiaRSA: uma

aplicacao dosnumerosprimos

Profo JoseSergio

Itens

Motivacao

Introducao

Um pouco deHistoria

FundamentacaoTeorica doRSA

Metodologia

Exemplo

Como quebraro RSA?

Referencias

Profo Jose Sergio Criptografia RSA: uma aplicacao dos numeros primos