Nesta página, vamos realizar uma computação em Python para ilustrar o processo de gerar as chaves, criptografar e descriptografar, usando criptografia RSA. Note que a computação feita aqui é só para ilustrar como combinar os algoritmos estudados neste bloco para criptografia; na pratica, algumas tarefas (tal como a escolha de primos aleatórios) devem ser resolvidas com muito mais cuidado.
Primeiro, precisamos carregar algumas bibliotecas.
from sympy import factorintimport randomfrom math import floor, log
Vamos precisar das funções ExpModN (exponenciação rápida) e XMDC (Algoritmo Estendido de Euclides) que foram definidas em aulas anteriores:
def ExpModN( a, e, n ): A, P, E = a, 1, ewhile E !=0: D = E %2# the last binary digit of E if D ==1: P = (A*P) % n E = (E-1)//2else: E = E//2 A = (A*A) % nreturn P
def XMDC(a,b): x0, x =1, 0; y0, y =0, 1# nós trabalhamos com números positivos, mas aceitamos argumentos negativos sign_a, sign_b =1, 1if a <0: a =-a sign_a =-1if b <0: b =-b sign_b =-1#x0*a + y0*b = a#x*a + y*b = bwhile b>0: q, r = a // b, a%b a, b = b, r#atualizar x, x0, y, y0 x, x0 = x0 - q*x, x y, y0 = y0 - q*y, y return a, sign_a*x0, sign_b*y0
O algoritmos de gerar as chaves públicas e privadas necessita a computação de inverso modular. Isso pode ser feito facilmente usando o algoritmo estendido de Euclides, mas nós colocamos aqui uma função que vai resolver esta tarefa:
def inverso_modular( a, n ): d, u, v = XMDC( a, n )if d !=1:returnFalse u %= nif u <0: u += nreturn u
Para escolher os primos \(p\) e \(q\), precisaremos de um teste de primalidade. Usaremos o Teste de Primalidade de Miller. Este teste não é deterministico, terá uma probabilidade pequena de erro, mas esta probabilidade pode ser reduzida para um nível tão baixa que na prática um número que passa por este teste pode ser tratado como primo.
def IsStrongPseudoPrimeInBase( n, b ): q = n-1 k =0while q %2==0: q = q//2 k = k+1 r = ExpModN( b, q, n )if r ==1:returnTruefor i inrange( 0, k ):if r == n-1:returnTrue r = r*r % nreturnFalse
def TesteMillerRabin( n, k =0):if k ==0: k = floor(log( n )) +1for i inrange( k ): b = random.randint( 2, n-2 )ifnot IsStrongPseudoPrimeInBase( n, b ):return"COMPOSTO"return"PROVAVELMENTE PRIMO"
A seguinte função será usada para escolher um primo aleatório de certo comprimento na base binária. A ideia, e tomar um número aleatório do comprimento desejado, verificar se ele e primo, e se não, aumentar o número até obtermos um número que é (pseudo)primo.
def primo_aleatório( nr_bits ): p, is_pr =0, False p = random.randint( 2**(nr_bits-1), 2**nr_bits-1 )if p %2==0: p +=1whileTrue:if TesteMillerRabin( p, 20 ) =="PROVAVELMENTE PRIMO":break p +=2return p
Para gerar as chaves públicas e privadas, vamos escolher dois primos aleatórios \(p\) e \(q\) tais que o comprimento do produto \(n=pq\) é 2048. Seguimos a recomendação que o comprimento de um dos primos seja 40% do comprimento do produto, enquanto o outro contribua com 60% ao comprimento total. Com essa condição, a chave será mais resistente aos ataques para fatorar o produto.
Vamos agora computar as chaves \(e\) e \(d\) usadas para criptografar e descriptografar. A seguinte função vai devolver um número aleatório entre \(2\) e \(n\), invertível módulo \(\varphi(n)=(p-1)(q-1)\) junto com seu inverso.
def key_pair( p, q ): n, phin = p*q, (p-1)*(q-1) d, e =False, 0whiletype( d ) ==bool: e = random.randint( 1, n ) d = inverso_modular( e, phin )return e, d
Rodamos a função que acabamos de definir para gerar as chaves:
e, d = key_pair( p, q )
Verifiquemos que \(ed\equiv 1\pmod{\varphi(n)}\).
e*d %((p-1)*(q-1))1
Agora definamos as funções de criptografar e descriptografar. Definimos estas funções com expressões-lambda.
C =lambda a: ExpModN( a, e, n )D =lambda b: ExpModN( b, d, n )
Assuma que a mensagem da Alice é um número aleatório \(a\) entre \(1\) e \(n\). Alice vai criptografar esta mensagem como \(b=C(a)\) e vai enviar ao Bob. Ao receber a mensagem \(b\), o Bob vai descriptografar a mensagem da Alice como \(c=C(b)\). Pelo que provamos na aula, \(c\) coincide com a mensagem original \(a\); ou seja \(c=a\).
a = random.randint( 1, n )b = C(a)c = D(b)a == c
Para ilustrar a dificuldade de quebrar a criptografia RSA, usaremos a chave usada pelo site ufmg.com em novembro de 2022. O número \(n\) usada por esta página pode ser acesso pelas funcionalidades da segurança do browser. A chave aparece como um número hexadecimal com o carater “:” separando pares de dígitos. O seguinte código transforma este número para um número inteiro de Python.
n ="C1:D9:49:08:FF:1B:2B:F7:F9:81:E7:EA:CB:21:6B:FC:DA:39:6B:0B:21:8D:A8:19:5F:D5:B3:84:8C:5B:D7:3A:E6:8F:9A:0C:63:AD:F3:FB:BE:27:A7:36:36:3F:24:57:0F:17:68:32:1E:8E:87:92:9E:B7:09:1B:44:81:78:3E:50:1E:A8:BC:D4:E1:83:BB:99:4B:30:66:3F:EB:6D:6A:1F:02:71:02:86:4C:00:D6:F3:6C:3A:61:61:18:21:6F:A8:39:A2:33:B8:31:86:8B:91:FE:F8:69:15:AA:AF:CC:DA:39:8A:E6:13:75:F7:D9:E7:F4:39:C1:35:AF:D5:E7:E1:4C:3E:A6:F2:11:B1:E2:A8:89:29:AE:89:31:1C:E7:F7:89:BF:04:DD:61:02:A1:2D:28:4C:DE:54:62:1E:D5:3C:4A:75:1A:49:24:1E:69:0F:F2:7A:4A:21:4A:57:39:DC:97:68:90:D9:3C:95:55:59:A1:49:3F:E1:D9:07:CE:B6:CE:32:84:0F:F0:F1:7C:A8:78:93:48:69:32:4D:37:7E:4D:96:2E:84:52:90:67:03:AE:F5:31:1C:B0:26:8A:89:BC:01:0B:EA:80:D7:A4:5B:4A:F0:78:0C:AB:E3:A6:A7:88:F1:CD:B9:96:EB:5B:B9:BF:6E:E3:EC:28:A2:CD"n = n.replace( ':', '' )n =int( n, base =16 )
Agora para quebrar a criptografia, é necessário fatorar este número. Verificar que o número não é pseudoprimo para a base \(2\) (e então não é primo) é fácil, mas fatorar é difícil e de fato não pode ser feito usando as funcionalidades de Python.
IsStrongPseudoPrimeInBase( n, 2 )Falsefactorint( n )...não há resposta...