RSA
“Curs d'Introducció a la criptografia” by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto
RSA
{Ron Rivest, עדי שמיר (Adi Shamir), Leonard Adleman; 1978}
Permet implementar el xifrat i la signatura, mitjançant l'RSAP (Problema RSA)
L'RSAP és un problema amb trampa que es basa en la dificultat del càlcul de l'arrel $e$-èssima$\pmod{n}$ per a valors d'$n$ amb certes propietats
RSAP
(el problema RSA)
Suposem que tenim un missatge $m$ i que el permutem amb la funció:
$c = m^e \pmod n$
per recuperar (desxifrar) el missatge original a partir de $c$ cal invertir:
$m = \sqrt[e]{c} \pmod n$
però
sii $n$ no és primer el càlcul d'
$m \equiv \sqrt[e]{c} \pmod n$
és computacionalment difícil* per valors d'$n$ amb factors suficientment grans (i desconeguts)
hem xifrat un missatge $m$
però no hi ha manera de desxifrar-ne el resultat $c$...
...si és que no coneixem "la trampa"
la trampa
segons el teorema d'Euler:
$m^{\phi(n)} \equiv 1 \pmod n$
$(m^{\phi(n)})^t \equiv 1 \pmod n$
$m^{t \phi(n)} \equiv 1 \pmod n$
$m^{t \phi(n)}m \equiv m \pmod n$
$m^{t \phi(n)+1} \equiv m \pmod n$
$m^{t \phi(n)+1} \equiv m \pmod n$
tenint-ho en compte per...
\[ \begin{aligned} c & \equiv m^{e} \pmod n \\ m & \equiv \sqrt[e]{c} \pmod n \leftarrow \text{computacionalment infactible} \end{aligned} \]
...agafem una drecera donant la volta "per l'altra banda", exponenciant suficientment per arribar un altre cop a $m$:
\[ \begin{aligned} c & \equiv m^{e} \pmod n \\ m & \equiv c^{\color{red}d} \pmod n \qquad \rightarrow m \equiv m^{e\color{red}d} \pmod n \end{aligned} \]
$m^{t \phi(n)+1} \equiv m \pmod n$
\[ \begin{aligned} c & \equiv m^{e} \pmod n \\ m & \equiv c^{\color{red}d} \pmod n \qquad \rightarrow m \equiv m^{e\color{red}d} \pmod n \end{aligned} \]
només cal trobar un $\color{red}d$ que:
$e\color{red}d = t \phi(n) + 1$
$e\color{red}d \equiv 1 \bmod{\phi(n)}$
$\color{red}d \equiv e^{-1} \bmod{\phi(n)}$
$\color{red}d \equiv e^{-1} \bmod{\phi(n)}$
el càlcul de $\color{red}d$ és fàcil a condició que coneguem $\phi(n)$
i recordem que:
$\phi(pq) = (p-1)(q-1)$
per a conèixer $\phi(n)$ cal conèixer els factors d'$n$ (computacionalment infactible per valors grans de $p$ i $q$ i coneixent només $n$)
$\color{red}d \equiv e^{-1} \bmod{\phi(n)}$
s'ha de tenir en compte que $\phi(n)$ no és primer ($\phi(pq) = (p-1)(q-1)$ producte de nombres parells)
per tant:
cal vigilar que $e$ sigui invertible $\pmod{\phi{(n)}}$
(és a dir, que $e$ i $\phi{(n)}$ siguin coprimers)
(és a dir, que $\text{mcd}(e, \phi{(n)}) = 1$)
$\color{red}d \equiv e^{-1} \bmod{\phi(n)}$
per a minimitzar la possibilitat de que $\text{mcd}(e,\phi{(n)}) \neq 1$, escollim un exponent $e$ primer, i vigilem simplement que $e$ no divideixi $d$
habitualment $e = 65537$ que, a banda de ser primer, només té dos $1$ en base $2$ i, per tant, permet una execució ràpida d'$m^e \pmod n$
i la probabilitat de que generem una clau privada $d$ que impliqui que $e|\phi{(n)}$ és $1:65537$
resum d'operació
Algorisme de generació
- l'usuari $\text{u}$ escull un exponent $e$
(habitualment tothom fa servir $e = 65537$) - escull aleatòriament dos nombres primers $p_\text{u}$ i $q_\text{u}$ prou grans* i prou diferents**
- calcula $\phi(n_\text{u}) = (p_\text{u}-1)(q_\text{u}-1)$
- calcula $d_\text{u} = e^{-1} \bmod{\phi(n_\text{u})}$
La Clau pública de l'usuari $\text{u}$ és $(e, n_\text{u})$
La Clau privada de l'usuari $\text{u}$ és $(d_\text{u}, (e, n_\text{u}))$
Algorismes de xifrat i desxifrat
per a xifrar cap a l'usuari $\text{u}$, ens cal saber
la seva clau pública $(e, n_\text{u})$:
$c = m^{e} \pmod{n_\text{u}}$
per a desxifrar, l'usuari pot revertir el xifrat
ja que coneix la seva clau privada $(d_\text{u}, (e, n_\text{u}))$:
$m = c^{d_\text{u}} \pmod{n_\text{u}}$
Alg/ de signatura i verificació
per a signar, l'usuari $\text{u}$ fa servir la seva clau privada $(d_\text{u}, (e, n_\text{u}))$:
$c = m^{d_\text{u}} \pmod{n_\text{u}}$
qualsevol pot verificar la signatura coneixent la seva clau pública $(e, n_\text{u})$:
$m = c^{e} \pmod{n_\text{u}}$
debilitats $\rightarrow$ contramesures
sobre l'algorisme:
- Propietats de l'exponenciació $\rightarrow$ PKCS #1
- Casos especials sobre $\pmod{n}$ $\rightarrow$ PKCS #1
- Factorització d'$n$ $\rightarrow$ longitud suficient d'$n$
sobre la implementació:
- Atacs de temps $\rightarrow$ randomització en l'execució
- Atacs sobre el consum, la radiació, etc.
- compromís de clau: accés software o físic al sistema
- qualitat dels nombres aleatoris (e.g. $\text{gcd}$ sobre servidors web)
- a futur: computació quàntica
- ...
PKCS #1
Per xifrat: Optimal asymmetric encryption padding
(OAEP)
barreja un nombre aleatori amb el valor a xifrar,
de manera que dos xifrats de mateix valor són diferents
(algorisme determinista $\rightarrow$ algorisme probabilístic)
Per signatura: Probabilistic Signature Scheme
(PSS)
no signem directament el missatge si no que signem el hash, al qual afegim un random
(salt) i un farciment (padding) fins la longitud $n$
(algorisme determinista $\rightarrow$ algorisme probabilístic)
Longitud de clau
la dificultat de l'RSAP $n$ és equivalent a fer l'arrel quadrada modular mòdul un $n$ no primer, i és equivalent a factoritzar $n$
el major $n$ factoritzat és de $768$ bit $\Rightarrow$ Desafiament RSA-768 (2000 anys/CPU)
el NIST
recomana
$\|n\| \geq 2048$ bit fins el 2030
generem i mostrem (PKCS #1) una clau RSA-2048 amb $e=65537$
$
\begin{aligned}
x &\equiv a_1 \pmod{n_1} \\
x &\equiv a_2 \pmod{n_2} \\
&\vdots \\
x &\equiv a_i \pmod{n_i}
\end{aligned}$ té una solució única per: $
\begin{aligned}
x &\equiv a \pmod{n_1 n_2 \cdots n_i}
\end{aligned}$ $
\begin{aligned}
x &\equiv a_p \pmod{p} \\
x &\equiv a_q \pmod{q} \\
&\Downarrow \\
x &\equiv a \pmod{pq}
\end{aligned}$ $
\begin{aligned}
x &\equiv 0 \pmod{2} \rightarrow \text{x és parell}\\
x &\equiv 3 \pmod{5} \rightarrow \text{x en decimal, acaba en 3 o en 8}\\
&\Downarrow \\
x &\equiv 8 \pmod{10} \rightarrow \text{x en decimal acaba en 8}
\end{aligned}$ aplicació a RSA (algorisme de Garner) $\begin{aligned}
d_p &= e^{-1} \bmod{(p-1)} \\
d_q &= e^{-1} \bmod{(q-1)} \\
q_\text{inv} &= q^{-1} \bmod{(p-1)} \\
\end{aligned}$
$\begin{aligned}
m_1 &= c^{d_p} \bmod{p} \\
m_2 &= c^{d_q} \bmod{q} \\
m &= m_2 + \bigg(q_\text{inv} (m_1 - m_2) \bmod p\bigg)
\end{aligned}$ per què ens serveix aquest teorema?
RSA
AES
(bits de seguretat)
$1024$
$\leftrightarrow$
$80$
$80$
$2048$
$\leftrightarrow$
$112$
$112$
$3072$
$\leftrightarrow$
$128$
$128$
$15360$
$\leftrightarrow$
$256$
$256$
pràctica: openssl
$
openssl genrsa
-F4
2048
|
openssl rsa
-text
-noout
modulus: ... $\rightarrow \color{red}{n}$
publicExponent: 65537 (0x10001) $\rightarrow \color{red}{e}$
privateExponent: ... $\rightarrow \color{red}{d}$
prime1: ... $\rightarrow \color{red}{p}$
prime2: ... $\rightarrow \color{red}{q}$
exponent1: ... $\rightarrow$ ??
exponent2: ... $\rightarrow$ ??
coefficient: ... $\rightarrow$ ??
$ _
Teorema dels Residus Xinesos
exemple senzill del CRT
Teorema dels Residus Xinesos
PVK):
perquè 2. és més ràpid que $m = c^d \bmod{n}$(Elgamal, DSA) $\rightarrow$