RSA

A criptografia de chave pública permite que um usuário, Alice, distribua uma chave pública, que outras pessoas podem usar para criptografar mensagens destinadas a ela. Alice, então, utiliza sua chave privada para descriptografar essas mensagens.

As assinaturas digitais permitem que Alice use sua chave privada para "assinar" uma mensagem. Qualquer pessoa pode usar a chave pública de Alice para verificar que a assinatura foi criada com a chave privada correspondente e que a mensagem não foi alterada.

A segurança do RSA baseia-se na dificuldade de fatorar números compostos grandes, ainda considerada um "problema difícil". No entanto, nos últimos anos, o sistema criptográfico recebeu críticas pela facilidade com que pode ser implementado de forma incorreta. Grandes falhas foram descobertas em implementações comuns, sendo a mais notória a vulnerabilidade ROCA, que levou a Estônia a suspender 760.000 cartões de identidade nacionais.

Exponenciação modular

A exponenciação modular é uma operação amplamente utilizada na criptografia e geralmente é representada assim:

2^10 mod 17.

No exemplo acima, temos que 2^10 = 1024, logo teremos: 1024 mod 17 = 4.

Explicação do exemplo acima:

Passo 1: dividir 1024 por 17 usando a divisão inteira, ou seja, determinar quantas vezes cabe

dentro de 1024 sem ultrapassá-lo.

1024/17 = 60 (quociente inteiro).

O quociente é 60, porque 17*60=1020, que é o maior múltiplo de 17 menor ou igual a 1024.

Passo 2: agora, devemos calcular o resto subtraindo 1020 de 1024:

1024 - 1020 = 4.

Portanto, o resto é 4, o que significa que:

1024 mod 17 = 4.

Código em Python:

Chave pública

A criptografia RSA é a exponenciação modular de uma mensagem com um expoente e e um módulo n, que normalmente é o produto de dois primos:

n = p*q.

Juntos, o expoente e o módulo formam uma “chave pública” RSA: (n, e).

EXEMPLO: Devemos “criptografar” o número 12 usando o expoente e = 65537 e os primos p = 17 e q = 23. Que número você obtém como o texto cifrado?

Passo 1: Devemos entender a fórmula da criptografia RSA.

A criptografia RSA é realizada usando a fórmula:

c = m^e mod n, onde:

— c é o texto cifrado (ciphertext) que queremos calcular;

— m é a mensagem original a ser criptografada (neste caso, m = 12);

— e é o expoente público (e = 65537);

— n é o módulo.

Passo 2: Devemos calcular o módulo n e realizar a exponenciação modular.

n = 17 *23 = 391

c = 12^65537 mod 391

Código em Python:

Resultando em c = 248.

Função Totiente de Euler

O RSA baseia-se na dificuldade de fatorar o módulo n. Se os fatores primos puderem ser deduzidos, podemos calcular a Função Totiente de Euler de n e, assim, descriptografar o texto cifrado.

EXEMPLO: Dado n = p*q, com dois primos:

p = 857504083339712752489993810777;

q = 1029224947942998075080348647219.

Qual é o Totiente de Euler ϕ(n)?

A fórmula da Função Totiente de Euler é: ϕ(n) = (p-1)*(q-1).
Como já temos os valores de p e q, apenas aplicaremos as fórmulas:

(p-1) = 857504083339712752489993810776;

(q -1) = 1029224947942998075080348647218;

ϕ(n) = (857504083339712752489993810776)*(1029224947942998075080348647218).

Código em Python:

Resultando em ϕ(n)=882564595536224140639625987657529300394956519977044270821168.

Chave privada

A chave privada d é usada para descriptografar textos cifrados criados com a chave pública correspondente (também é usada para "assinar" uma mensagem, mas veremos isso mais tarde).

A chave privada é a informação secreta, ou "armadilha", que nos permite inverter rapidamente a função de criptografia. Se o RSA for implementado corretamente, e você não tiver a chave privada, a maneira mais rápida de descriptografar o texto cifrado é fatorar o módulo, o que é muito difícil para números inteiros grandes.

No RSA, a chave privada d é o inverso multiplicativo modular do expoente e módulo ϕ(n).

EXEMPLO: Dados dois primos e o expoente e :

p=857504083339712752489993810777;

q=1029224947942998075080348647219;

e = 65537.

Qual é a chave privada d ≡ e^(-1) mod ϕ(n)?

Como já temos os valores de p, q e e, devemos apenas calcular a Função Totiente de Euler que é a mesma do exemplo anterior.
Código em Python:

OBSERVAÇÃO: d é o número que satisfaz a seguinte congruência

(e * d) mod ϕ(n) = 1, portanto, (e * d) ≡ 1 mod ϕ(n)

Resultando em d=121832886702415731577073962957377780195510499965398469843281.

Decriptografia RSA

A descriptografia RSA é o processo de reverter a criptografia RSA usando a chave privada. Ela utiliza a operação de exponenciação modular com a chave privada d e o módulo n, que é o produto dos dois primos p e q. O texto cifrado (ciphertext) é elevado ao expoente d e o resultado é então reduzido pelo módulo n para recuperar a mensagem original (plaintext).

EXEMPLO: Criptografei um número secreto para seus olhos apenas usando os parâmetros da sua chave pública:

n = 882564595536224140639625987659416029426239230804614613279163;

e = 65537.

Utilize a chave privada d encontrada no exemplo anterior para descriptografar este texto cifrado:

c = 77578995801157823671636298847186723593814843845525223303932.

Nesse caso, temos n (produto de p e q), c (texto cifrado) e d (expoente privado).
Para descriptografar c, devemos utilizar a fórmula do RSA que é:

m = c^d mod n.

Código em Python:

Resultando em plain = 201034444866440971949678971851899303368609182195133923828742.

Assinaturas RSA

Como você pode garantir que a pessoa que recebe sua mensagem saiba que foi você quem a escreveu?

Podemos nos proteger contra esses ataques assinando criptograficamente a mensagem.

Imagine que você escreve uma mensagem m. Você cifra essa mensagem com a chave pública do seu amigo:

c = m0^e mod n0

Fatoração

O que é um "primo pequeno"? Houve um Desafio de Fatoração RSA com prêmios em dinheiro dados a equipes que conseguissem fatorar módulos RSA. Isso deu ao público uma visão de quanto tempo diversos tamanhos de chaves permaneceriam seguros. Computadores ficam mais rápidos, os algoritmos melhoram, então, na criptografia, é sempre prudente errar pelo lado da cautela.

Hoje em dia, recomenda-se usar primos com pelo menos 1024 bits de comprimento — multiplicando dois primos de 1024 bits, você obtém um módulo de 2048 bits. O RSA com um módulo de 2048 bits é chamado de RSA-2048.

Alguns dizem que, para realmente se manter à prova de futuro, você deve usar RSA-4096 ou até mesmo RSA-8192. No entanto, há um compromisso aqui: leva mais tempo para gerar números primos grandes e, além disso, exponenciações modulares são previsivelmente mais lentas com um módulo maior.

EXEMPLO: Fatore o número de 150 bits 510143758735509025530880200653196460532653147 em seus dois primos constituintes. Forneça o menor como sua resposta.

Podemos utilizar apenas o Factordb, que nos traz como resultado:

19704762736204164635843.

Exercício Monoprime

Temos que o RSA funciona usando o fato de que

*e**d≡1 (modϕ(n)), sendo que,

(m^e)^d≡m(modn).

Se n for um número primo, temos que

ϕ(n) = n-1,

o que facilita o cálculo de d.

Código em Python:

O que resulta em 0n3_pr1m3_41n7_pr1m3_101.

OBSERVAÇÃO: Primeiramente, podemos colocar o número n no Factordb para saber se é um número primo ou não.

Exercício Manyprime

O grande problema nesse exercício é grande quantidade de primos em que n pode ser fatorado;
Utilizando o Factordb entramos os seguintes primos:

A partir disso, podemos criar uma lista, em Python, com todos esses números primos para determinar ϕ(n). Então, tudo o que precisamos fazer é inicializar ϕ(n)=1 e multiplicar todos os números primos - 1.
Código em Python:

O que resulta em 700_m4ny_5m4ll_f4c70r5.

Exercício Salty

Exercício Modulus Inutilis

Diffie-Helman

Trabalhando com Campos

EXEMPLO: Dado o primo p=991 e o elemento g=209, encontre o elemento inverso d=g^-1, tal que g*d mod 991=1.

Código em Python Brute-Force:

Código em Python Algoritmo de Euclides:

Geradores de grupos

EXEMPLO: Para o campo finito com p = 28151, encontr o menor elemento g que sejaa um elemento primitivo de Fp (um elemento primitivo de um campo finito é um elemento que pode gerar todos os elementos não nulos do campo por meio de potências sucessivas g^n modp).

Código em Python:

Computando valores públicos

O protocolo Diffie-Hellman é utilizado porque o logaritmo discreto é considerado um cálculo "difícil" para grupos cuidadosamente escolhidos.

O primeiro passo do protocolo é estabelecer um primo p e algum gerador do campo finito g. Esses valores devem ser escolhidos cuidadosamente para evitar casos especiais em que o logaritmo discreto pode ser resolvido com algoritmos eficientes. Por exemplo, escolhe-se geralmente um primo seguro p = 2*q +1, onde os únicos fatores de p-1 são {2,q}, em que é outro primo grande. Isso protege o protocolo Diffie-Hellman do algoritmo Pohlig-Hellman.

O usuário então escolhe um inteiro secreto a < p-1 e calcula g^a mod p. Esse valor pode ser transmitido em uma rede insegura e, devido à suposta dificuldade do logaritmo discreto, o inteiro secreto a deve ser inviável de ser calculado. O valor a é conhecido como o valor secreto, enquanto A = g^a mod p é o valor público.

EXEMPLO: Dado os parâmetros NIST

g: 2

p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

Calcule o valor de g^a mod p para:

a: 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815