Resumos LEIC-A
IST LEIC-AGitHub
Edit page

Criptografia RSA (Cheat Sheet)

Teoremas

Teorema 1 - Pequeno Teorema de Fermat

Para todo o a∈Na \in \N e para todo o pp primo,

ap≡paa^p\equiv_pa

Teorema 2

Para todo o a∈Na \in \N e para todo o pp primo, se a⌢p=1a \frown p = 1

ap−1≡p1a^{p-1}\equiv_p 1

Teorema 3

Para todos os primos pp e qq distintos, para todo o e∈Ne \in \N, tal que e⌢(p−1)(q−1)=1e \frown (p-1)(q-1) = 1, então
Para todo o M∈NM \in \N, tal que 0≤M<pq=N0 \leq M < pq = N.

Med≡NMd→inverso de e moˊdulo (p−1)(q−1)M^{ed} \equiv_N M\\ d \rightarrow \text{inverso de }e\text{ módulo }(p-1)(q-1)

Chave Pública e Privada

Escolhem-se 2 primos pp e qq diferentes Escolhe-se ee, tal que e⌢(p−1)(q−1)=1e \frown (p-1)(q-1)=1 Determina-se dd, o inverso de ee módulo (p−1)(q−1)(p-1)(q-1) Comunica-se a Chave Pública (N,e)(N,e) e guarda-se a Chave Privada (N,d)(N,d), onde N=pqN = pq.

A Chave Pública servirá para encriptar a mensagem e a Chave Privada para a desencriptar.

Com os 2 primos já escolhidos: 1313 e 55
O expoente (e):11(e): \quad 11

N=13×5=65N = 13\times5 = 65

Falta determinar o inverso de ee, módulo (13−1)(5−1)=48(d)(13-1)(5-1) = 48 \quad (d)
Queremos resolver a Eq. Diofantina:

1=(e×d)+(48×k)iaiqidimi048101114012421−4331−293133−13401= (e\times d)+(48 \times k)\\ \begin{array}{c|c|c|c|} i & a_i & q_i & d_i & m_i\\ \hline 0 & \smartcolor{red}{48} & & 1 & 0\\ 1 & 11 & 4 & 0 & 1\\ 2 & 4 & 2 & 1 & -4\\ 3 & 3 & 1 & -2 & 9\\ 3 & 1 & 3 & 3 & \smartcolor{orange}{-13}\\ 4 & 0 \end{array}\\

Como −13<0\smartcolor{orange}{-13} < 0 temos de somar −13+48\smartcolor{orange}{-13} +\smartcolor{red}{48}

Logo d=35d = 35

A Chave Pública é (65,11)(65,11)

A Chave Privada é (65,35)(65,35)

EZHACKS