RSA

Teoremas

Teorema 1 - Pequeno Teorema de Fermat

Para todo o aNa \in \N e para todo o pp primo,

appaa^p\equiv_pa

Teorema 2

Para todo o aNa \in \N e para todo o pp primo, se ap=1a \frown p = 1

ap1p1a^{p-1}\equiv_p 1
Demonstração

Pelo Teorema 1

appaa(ap1)paa^p\equiv_pa \quad \Leftrightarrow \quad a(a^{p-1})\equiv_pa

Como apa\frown p, aa tem inverso módulo pp.
Seja a~ã esse inverso,

a~×a×ap1pa~×aap1p1ã\times a\times a^{p-1} \equiv_p ã \times a\\ a^{p-1}\equiv_p 1

QED

Teorema 3

Para todos os primos pp e qq distintos, para todo o eNe \in \N, tal que e(p1)(q1)=1e \frown (p-1)(q-1) = 1, então
Para todo o MNM \in \N, tal que 0M<pq=N0 \leq M < pq = N.

MedNMdinverso de e moˊdulo (p1)(q1)M^{ed} \equiv_N M\\ d \rightarrow \text{inverso de }e\text{ módulo }(p-1)(q-1)
Demonstração

Sejam MM, NN, pp, qq, dd e ee tais que respeitam as condições do Teorema que se está a Demonstrar,

Primeiro, estuda-se a relação entre pp e MM.

  1. Caso 1 M=p˙\rightarrow M = \dot{p}\quad (MM é múltiplo de pp)
M=kp,kZMp0Medp0MedpM, porque Mp0M = kp, \quad k \in Z\\ M \equiv_p 0\\ M^{ed}\equiv_p 0\\ M^{ed} \equiv_p M ,\quad\text{ porque } M \equiv_p 0
  1. Caso 2 Mp=1\rightarrow M \frown p =1\quad (MM não é múltiplo de pp)

Pelo Teorema 2,

Mp1p1M^{p-1}\equiv_p 1
(Mp1)k(q1)p(1)k(q1),kZMk(p1)(q1)p1Med×Mk(p1)(q1)pMedMed+k(p1)(q1)pMed(M^{p-1})^{k(q-1)}\equiv_p (1)^{k(q-1)}, \quad \forall k \in \Z\\ M^{k(p-1)(q-1)}\equiv_p 1\\ M^{ed}\times M^{k(p-1)(q-1)}\equiv_p M^{ed}\\ M^{ed+k(p-1)(q-1)}\equiv_p M^{ed}

Como ee e dd são inversos módulo (p1)(q1)(p-1)(q-1), ou seja, ed(p1)(q1)1ed \equiv_{(p-1)(q-1)}1
Existe um λZ\lambda \in \Z :

ed+λ(p1)(q1)=1ed + \lambda(p-1)(q-1) = 1

Então, como a expressão acima é válida para um kZk \in \Z qualquer, também será válida para k=λk=\lambda.
Nesse caso:

Med+λ(p1)(q1)pMedMpMedM^{ed+\lambda(p-1)(q-1)}\equiv_p M^{ed}\\ M \equiv_p M^{ed}

Acabamos de provar que,

MedpMM^{ed} \equiv_p M

Logo, também podemos concluir

MedqMM^{ed} \equiv_q M

Uma vez que a relação entre MM e qq é equivalente à relação entre MM e pp.

Como o sistema:

{xpMxqM\left\{ \begin{aligned} x \equiv_p \quad M\\ x \equiv_q \quad M \end{aligned} \right.

Pelo Teorema Chinês dos Restos tem solução única módulo N=pqN=pq, visto que pp e qq são dois primos diferentes

E acabamos de provar que:

{MedpMMedqM\left\{ \begin{aligned} M^{ed} \equiv_p \quad M\\ M^{ed} \equiv_q \quad M \end{aligned} \right.

Chegamos à conclusão:

MedNMM^{ed}\equiv_N M

:::details Explicação da última conclusão

Do Sistema acima, tem-se:

{Medpk1=MMedqk2=Mpk1=qk2\left\{ \begin{aligned} M^{ed} -pk_1 = M\\ M^{ed} -qk_2 = M \end{aligned} \right.\\ pk_1 = qk_2

Como pp e qq são primos diferentes,

k1=qtek2=pt,tZk_1=qt \quad e \quad k_2=pt, \qquad t \in \Z

Ou seja,

Med(pq)t=MMedNt=MMedNMM^{ed} - (pq)t = M\\ M^{ed} - Nt = M\\ M^{ed} \equiv_N M

RSA - Metodologia

Passo 1 - Criação das Chaves

O Recetor da mensagem a ser encriptada cria uma Chave Pública, que enviará ao Emissor, e uma Chave Privada que só o próprio terá acesso.

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

  1. Escolhe-se e partilha-se uma codificação numérica para o tipo de mensagem a receber.
    A seguinte imagem mostra um exemplo para mensagens de texto em caracteres ASCII.
    Uma imagem

  2. Escolhem-se 2 primos pp e qq diferentes

  3. Escolhe-se ee, tal que e(p1)(q1)=1e \frown (p-1)(q-1)=1

  4. Determina-se dd, o inverso de ee módulo (p1)(q1)(p-1)(q-1)

  5. Comunica-se a Chave Pública (N,e)(N,e) e guarda-se a Chave Privada (N,d)(N,d), onde N=pqN = pq.

Passo 2 - Encriptação

Com a codificação numérica escolhida pelo Recetor:

  1. Escolhe-se um número inteiro BB menor ou igual ao número de dígitos do número NN.
  2. Divide-se a mensagem numérica a enviar em blocos de BB dígitos: M1,,MkM_1,\dots,M_k
  3. Verifica-se se NMi=1,i=1,,kN\frown M_i=1, \quad i =1,\dots,k
  4. Transforma-se cada bloco MiM_i num bloco RiR_i, onde RiN(Mi)e,i=i,,kR_i \equiv_N (M_i)^e, \quad i=i,\dots,k
    Os R1,,RkR_1,\dots,R_k são a mensagem encriptada
  5. Envia-se a mensagem R1,,RkR1,\dots, R_k

Passo 3 - Desencriptação

  1. Determinar Mi,i=1,,kM_i, \quad i=1,\dots,k.

    MiN(Ri)dM_i \equiv_N (R_i)^d
  2. Converter a mensagem numérica para a mensagem final, através da codificação usada.

Exemplo

Vamos codificar (e descodificar) a mensagem:

MD\text{MD}

Com os 2 primos já escolhidos: 4343 e 5959
O expoente (e):11(e): \quad 11
O tamanho dos blocos: 44
E a codificação: Uma imagem

  1. Chave Pública e Privada
N=43×59=2537N = 43\times59 = 2537

Como já se sabe ee, conclui-se que a Chave Pública é:

(2537,11)(2537,11)

Falta determinar o inverso de ee, módulo (431)(591)=2436(d)(43-1)(59-1) = 2436 \quad (d)
Queremos resolver a Eq. Diofantina:

1=(e×d)+(2436×k)iaiqidimi02436101112210125212213152443401=(11×433)+(2436×(2))d=4331= (e\times d)+(2436 \times k)\\ \begin{array}{c|c|c|c|} i & a_i & q_i & d_i & m_i\\ \hline 0 & 2436 & & 1 & 0\\ 1 & 11 & 221 & 0 & 1\\ 2 & 5 & 2 & 1 & -221\\ 3 & 1 & 5 & -2 & 443\\ 4 & 0 \end{array}\\ 1 = (11 \times 433)+(2436\times (-2))\\ d = 433

O que significa que a Chave Privada é:

(2537,433)(2537,433)
  1. Encriptar a mensagem com a chave (2537,11)(2537,11)

A mensagem MD\text{MD}, com a codificação escolhida e usando blocos de 44 dígitos, traduz-se:

12031203
Verificar N primo com 1203

UPDATE: Segundo a professora Joana Ventura, podemos passar este passo à frente, a não ser que seja pedido no enunciado.

Continuando, neste passo calcula-se o mdcmdc de NN e dos Blocos, verificando se dá sempre 11.
Neste exemplo só temos 11 bloco.

iaiqi02537112032213193245411252561270 mdc eˊ 1\begin{array}{c|c|c} i & a_i & q_i \\ \hline 0 & 2537 & \\ 1 & 1203 & 2 \\ 2 & 131 & 9 \\ 3 & 24 & 5 \\ 4 & 11 & 2 \\ 5 & 2 & 5 \\ 6 & 1 & 2 \\ 7 & 0 \end{array}\\~\\ \text{mdc é 1} \quad \checkmark

Agora calcula-se RN(M)eR \equiv_N (M)^e, onde N=2537N=2537 e M=1203M=1203.
Como 11=8+2+1,R2537(1203)8+2+111 = 8+2+1, \quad R \equiv_{2537} (1203)^{8+2+1}

12032253714472092537111912034253711192253712521612537142012038253714202253720164002537202212038+2+125372022×1119×12032537272192945425372450R=2450\begin{array}{|} 1203^2 & \equiv_{2537} & 1447209\\ & \equiv_{2537} & 1119\\ 1203^4 & \equiv_{2537} & 1119^2\\ & \equiv_{2537} & 1252161\\ & \equiv_{2537} & 1420\\ 1203^8 & \equiv_{2537} & 1420^2\\ & \equiv_{2537} & 2016400\\ & \equiv_{2537} & 2022\\ 1203^{8+2+1}& \equiv_{2537} & 2022\times1119\times1203\\ & \equiv_{2537} & 2721929454\\ & \equiv_{2537} & 2450\\ \end{array}\\ R = 2450
  1. Desencriptação com a chave (2537,433)(2537,433)

Encontrar o MM, tal que

M2537(2450)433M \equiv_{2537} (2450)^{433}

Como 433=256+128+32+16+8+2+1433 = 256 + 128 +32+16+8+2+1

245022537600250025372495245042537249522537622502525371764245082537176422537311169625371334245016253713342253717795562537111924503225371119225371252161253714202450642537142022537201640025372022245012825372022225374088484253713772450256253713772253718961292537990 245043325372450256×2450128×245032×245016×24508×24502×245012537(990×1377)×(1420×1119)×(1334×2495)×24502537(861×818)×(2323×2450)2537(1549×859)245043325371203M=1203\begin{array}{|} 2450^2 & \equiv_{2537} & 6002500\\ &\equiv_{2537} & 2495\\ 2450^4 & \equiv_{2537} & 2495^2\\ & \equiv_{2537} & 6225025\\ & \equiv_{2537} & 1764\\ 2450^8 & \equiv_{2537} & 1764^2\\ & \equiv_{2537} & 3111696\\ & \equiv_{2537} & 1334\\ 2450^{16} & \equiv_{2537} & 1334^2\\ & \equiv_{2537} & 1779556\\ & \equiv_{2537} & 1119\\ 2450^{32} & \equiv_{2537} & 1119^2\\ & \equiv_{2537} & 1252161\\ & \equiv_{2537} & 1420\\ 2450^{64} & \equiv_{2537} & 1420^2\\ & \equiv_{2537} & 2016400\\ & \equiv_{2537} & 2022\\ 2450^{128} & \equiv_{2537} & 2022^2\\ & \equiv_{2537} & 4088484\\ & \equiv_{2537} & 1377\\ 2450^{256} & \equiv_{2537} & 1377^2\\ & \equiv_{2537} & 1896129\\ & \equiv_{2537} & 990\\ \end{array}\\~\\ \begin{array}{|} 2450^{433} &\equiv_{2537}& 2450^{256} \times 2450^{128} \times 2450^{32} \times 2450^{16} \times 2450^{8} \times 2450^{2} \times 2450^{1}\\ &\equiv_{2537}& (990 \times 1377) \times (1420 \times 1119) \times (1334 \times 2495) \times 2450\\ &\equiv_{2537}& (861\times 818) \times (2323\times2450)\\ &\equiv_{2537}& (1549\times 859)\\ 2450^{433} &\equiv_{2537}& 1203 \end{array}\\ M = 1203

NOTA

No último passo, foi feito o produto dos números 2 a 2 e o resultados foi logo passado a módulo 25372537