26 Criptografia RSA

26.1 A teoria da criptografia RSA

Na área da criptografia, a suposição geral é que dois parceiros (que podem ser duas pessoas, ou dois computadores) querem trocar informação sigilosa usando um canal de comunicação que está disponível para terceiros. Os dois parceiros geralmente chamam-se A(lice) e B(ob) e um possível terceiro chama-se E(va). Assume-se que as mensagens enviadas por Alice e Bob são números. A Eva consegue interceptar as mensagens enviadas. O objetivo é desenvolver métodos seguros de codificação para as mensagens que podem garantir que Eva não vai conseguir descodificar as mensagens interceptadas.

Um método, conhecido como criptografia RSA, foi desenvolvido pelos matemáticos Ron Rivest, Adi Shamir, and Leonard Adleman e foi publicado em 1977.

Exercício 26.1 Lembre que a função $\varphi$ de Euler é definida como \[ \varphi(n)=|\{a\in\{1,\ldots,n\}\mid \mbox{mdc}(a,n)=1\}| \] para todo natural $n$. Demonstra, para primos $p$ e $q$ distintos, que \[ \varphi(pq)=(p-1)(q-1). \]

Assuma que Alice quer enviar uma mensagem para Bob. Eles seguem os seguintes passos:

Bob escolhe um número $n$ tal que $n$ é produto de dois primos $p$ e $q$ e escolhe um número $e\in\{2,\ldots,n-1\}$ tal que $\mbox{mdc}(e,\varphi(n))=1$. Isso implica que $e$ é invertível módulo $\varphi(n)$; ou seja existe $d\in\{1,\ldots,\varphi(n)\}$ tal que \[ ed\equiv 1\pmod{\varphi(n)}. \]
Bob publica o par $(n,e)$ dos números. Este é a chave pública do Bob e está disponível publicamente para toda pessoa que quer enviar mensagem sigilosa para o Bob. Em particular esta chave é conhecida por Alice.
O Bob guarda os números $(\varphi(n),d)$ em sigilo. Esta é a chave privada do Bob.
A mensagem da Alice é um número $b$ entre $1$ e $n$. A Alice vai calcular \[ C(b)=\mbox{o resto de $b^e$ por $n$}. \] Note que Alice conhece os números $e$ e $n$ e consegue calcular $C(b)$ (usando o algoritmo de exponenciação rápida.) O número $C(b)$ é a mensagem codificada.
Alice envia $C(b)$ para o Bob.
Ao receber a mensagem $c=C(b)$ da Alice, Bob calcula \[ D( c)=\mbox{o resto de $c^d$ módulo $n$}. \] O número obtido $D(c)$ é a mensagem descodificada.
O número $D(c)$ coincide com a mensagem original $b$ da Alice; ou seja, o Bob conseguiu descodificar a mensagem da Alice.

Exemplo 26.1 Assuma que $n=11\cdot 7=77$. Neste caso, $\varphi(n)=10\cdot 6=60$ e pode-se escolher $e=13$. A chave pública de Bob é $(77,13)$ e esta chave é disponível publicamente. O inverso $d$ de $e$ módulo 60 satisfaz a equação \[ de+60k=1 \] com algum $k$ e assim pode ser encontrado usando o Algoritmo de Euclides. De fato, $d=37$. A mensagem que a Alice manda para o Bob é um número entre $1$ e $76$. Assuma que a mensagem da Alice é o número 30. Então Alice calcula o resto de $30^{13}$ módulo $77$ que dá $72$. Então o mensagem da Alice é $C(30)=72$. Ao receber esta mensagem, o Bob calcula o resto de $D(72)=72^{37}\equiv 30\pmod{77}$ que foi a mensagem original da Alice

Vimos no exemplo como o método funciona, mas queremos entender teoricamente porque ele funciona.

Teorema 26.1 Usando a notação acima, $D(C(b))=b$ para todo $b\in\{1,\ldots,n-1\}$. Ou seja, usando a função $D$, o Bob consegue descodificar a mensagem da Alice

Comprovação. Lembre que \[ D(C(b))=(b^e)^d=b^{ed}\pmod n. \] Para provar que $D(C(b))=b$, precisa-se verificar que $b^{ed}\equiv b\pmod n$; ou seja $n\mid (b^{ed}-b)$. Como $n=pq$ é produto de dois primos, é suficiente (e necessário) verificar que $p\mid (b^{ed}-b)$ e $q\mid (b^{ed}-b)$. Nós fazemos esta verificação para $p$, o primo $q$ pode ser tratado com argumento igual.

Primeiro, se $p\mid b$, então $p\mid (b^{ed}-b)$ e a afirmação é verdadeira. Assuma agora que $p\nmid b$ e lembre que o Pequeno Teorema de Fermat implica neste caso que $b^{p-1}\equiv 1\pmod p$. Como $ed\equiv 1\pmod{\varphi(n)}$, tem-se que \[ ed=k\varphi(n)+1=k(p-1)(q-1)+1 \] com algum $k$ inteiro. Então \[ b^{ed}=b^{k(p-1)(q-1)+1}=(b^{p-1})^{k(q-1)}\cdot b\equiv b\pmod p. \] Obtivemos então que $b^{ed}\equiv b\pmod n$ que equivale à afirmação que $D(C(b))=b$ que implica que o método usado por Bob vai descodificar a mensagem da Alice.

A segurança do método está baseado no fato que para aplicar a função $D$ de descodificação, o Bob precisa calcular o valor de $d$ que precisa do valor de $\varphi(n)=(p-1)(q-1)$. Claramente, se alguém sabe $p$ e $q$ então consegue calcular $\varphi(n)$ e também a chave privada $d$. Mas a chave pública contém o apenas o número $n$ e não os seus fatores $p$ e $q$. Neste momento nós não conhecemos nenhum algoritmo que pode ser usado para fatorar números muito grandes.

O seguinte resultado implica que a determinação de $\varphi(n)$ é computacionalmente equivalente à determinação dos fatores $p$ e $q$ de $n$.

Lema 26.1 Conhecendo o valor de $\varphi(n)$ (além do valor de $n$), pode-se determinar os primos $p$ e $q$ com uma computação eficiente

Comprovação. Assuma que conhecemos o valor de $n$ e $\varphi(n)$. Primeiro, \[ \varphi(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1 \] e assim conhecemos $p+q=n-\varphi(n)+1$. Além disso, \[ (p+q)^2-4n=p^2+2pq+q^2-4pq=p^2-2pq+q^2=(p-q)^2 \] e assim \[ p-q=\sqrt{(p+q)^2-4n}. \] Isto implica, que conseguimos determinar o valor de $p-q$. Sabendo $p+q$ e $p-q$, é fácil determinar $p$ e $q$

Vale mencionar que existe um algoritmo quântico eficiente para determinar a fatoração de um número. Este algoritmo é conhecido como o Algoritmo de Shor e foi publicado em 1994. Este algoritmo neste momento não implica nenhum perigo para a segurança de mensagens criptografadas, mas no futuro os computadores quânticos podem se desenvolver o suficiente para poder quebrar o algoritmo RSA. Neste momento muitos matemáticos trabalham no desenvolvimento e algoritmos que são seguros contra ataques de computadores quânticos (criptografia pós-quântica).

26.2 Um exemplo detalhado em Python

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 factorint
import random
from 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, e
        
    while E != 0:        
        D = E % 2 # the last binary digit of E         
        if D == 1:
            P = (A*P) % n
            E = (E-1)//2
        else:
            E = E//2
        A = (A*A) % n
    return 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, 1
    if a < 0:
        a = -a
        sign_a = -1
    
    if b < 0:
        b = -b
        sign_b = -1
    
    #x0*a + y0*b = a
    #x*a + y*b = b
    
    while 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:
        return False
        
    u %= n
    if u < 0:
        u += n
    
    return 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 = 0
    while q % 2 == 0:
        q = q//2
        k = k+1
    
    r = ExpModN( b, q, n )
    if r == 1:
        return True
    
    
    for i in range( 0, k ):
        if r == n-1:
            return True
        r = r*r % n
        
    return False

def TesteMillerRabin( n, k = 0):
        
    if k == 0:
        k = floor(log( n )) + 1
        
    for i in range( k ):
        b = random.randint( 2, n-2 )
        if not 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 += 1
    
    while True:
        if TesteMillerRabin( p, 20 ) == "PROVAVELMENTE PRIMO":
            break
        p += 2
        
    return 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.

p_comp = floor( .4*2048 )
q_comp = 2048-p_comp

p = primo_aleatório( p_comp )
q = primo_aleatório( q_comp )
n = p*q

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, 0
    while type( 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 )
False
factorint( n )
...não há resposta...