RSA
“Curso de Introducción a la Criptografía” 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}
Permite implementar el cifrado y la firma, mediante el RSAP (Problema RSA)
El RSAP es un problema con trampa que se basa en la dificultad del cálculo de la raíz $e$-ésima$\pmod{n}$ para valores de $n$ con ciertas propiedades
RSAP
(el problema RSA)
Supongamos que tenemos un mensaje $m$ y que lo permutamos con la función:
$c = m^e \pmod n$
para recuperar (descifrar) el mensaje original a partir de $c$ hace falta invertir:
$m = \sqrt[e]{c} \pmod n$
pero
sii $n$ no es primo el cálculo de
$m \equiv \sqrt[e]{c} \pmod n$
es computacionalmente difícil para valores de $n$ con factores desconocidos
hemos cifrado un mensaje $m$
pero no hay manera de descifrar el resultado $c$…
…si no conocemos "la trampa"
la trampa
según el teorema de 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$
teniendo esto en cuenta para…
\[ \begin{aligned} c & \equiv m^{e} \pmod n \\ m & \equiv \sqrt[e]{c} \pmod n \leftarrow \text{computacionalmente infactible} \end{aligned} \]
… tomamos un atajo dando la vuelta "por el otro lado", exponenciando suficientemente para llegar otra vez hasta $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} \]
sólo hace falta encontrar 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álculo de $\color{red}d$ es fácil a condición que conozcamos $\phi(n)$
y recordemos que:
$\phi(pq) = (p-1)(q-1)$
para conocer $\phi(n)$ hace falta conocer los factores de $n$ (computacionalmente infactible para valores grandes de $p$ y $q$ y conociendo sólo $n$)
$\color{red}d \equiv e^{-1} \bmod{\phi(n)}$
se debe tener en cuenta que $\phi(n)$ no es primo ($\phi(pq) = (p-1)(q-1)$ producto de números pares)
por tanto:
hace falta vigilar que $e$ sea invertible $\pmod{\phi{(n)}}$
(es decir, que $e$ y $\phi{(n)}$ sean coprimos)
(es decir, que $\text{mcd}(e, \phi{(n)}) = 1$)
$\color{red}d \equiv e^{-1} \bmod{\phi(n)}$
para minimizar la posibilidad que $\text{mcd}(e,\phi{(n)}) \neq 1$, escogemos un exponente $e$ primo, y vigilamos simplemente que $e$ no divida $\phi(n)$
habitualmente $e = 65537$ que, a parte de ser primo, sólo tiene dos $1$ en base $2$ y, por tanto, permite una ejecución rápida de $m^e \pmod n$
y la probabilidad de que generemos una clave privada $d$ que implique que $e|\phi{(n)}$
es $1:65537$
resumen de operación
Algoritmo de generación
- el usuario $\text{u}$ escoge un exponente $e$
(habitualmente $e = 65537$) - escoge aleatoriamente dos primos $p_\text{u}$ y $q_\text{u}$ suficientemente grandes* y suficientemente diferentes**
- 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 Clave pública del usuario $\text{u}$ es $(e, n_\text{u})$
La Clave privada del usuario $\text{u}$ es $(d_\text{u}, (e, n_\text{u}))$
Algoritmos de cifrado y descifrado
para cifrar hacia el usuario $\text{u}$, nos hace falta saber
su clave pública $(e, n_\text{u})$:
$c = m^{e} \pmod{n_\text{u}}$
para descifrar, el usuario puede revertir el cifrado
ya que conoce su clave privada $(d_\text{u}, (e, n_\text{u}))$:
$m = c^{d_\text{u}} \pmod{n_\text{u}}$
Algoritmos de firma y verificación
para firmar, el usuario $\text{u}$ usa su clave privada $(d_\text{u}, (e, n_\text{u}))$:
$c = m^{d_\text{u}} \pmod{n_\text{u}}$
cualquiera puede verificar la firma conociendo su clave pública $(e, n_\text{u})$:
$m = c^{e} \pmod{n_\text{u}}$
debilidades $\rightarrow$ contramedidas
sobre el algoritmo:
- Propiedades multiplicativas de la exponenciación $\rightarrow$ PKCS #1
- $e=3$ con $m$ pequeño $\rightarrow$ PKCS #1
- Factoritzación de $n$ $\rightarrow$ longitud suficiente de $n$, factores $p$ y $q$ distanciados
sobre la implementación:
- Ataques de tiempo $\rightarrow$ randomitzación en la ejecución
- Ataques sobre el consumo, la radiación, etc.
- compromiso de clave: acceso software o físico al sistema
- calidad de los números aleatorios (e.g. $\text{gcd}$ sobre servidores web)
- a futuro: computación cuántica
- …
PKCS #1
Para cifrado: Optimal asymmetric encryption padding
(OAEP)
mezcla un número aleatorio con el valor a cifrar,
de manera que dos cifrados del mismo valor son diferentes
(algoritmo determinista $\rightarrow$ algoritmo probabilístico)
Para firma: Probabilistic Signature Scheme
(PSS)
no firmamos directamente el mensaje si no que firmamos su hash, al cual añadimos un valor aleatorio
(salt) y un relleno (padding) hasta la longitud $n$
(algoritmo determinista $\rightarrow$ algoritmo probabilístico)
Longitud de clave
la dificultad del RSAP $n$ es equivalente a realizar la raíz $e$-ésima modular módulo un $n$ no primo, y es equivalente a factorizar $n$
el mayor $n$ factorizado es de $768$ bit $\Rightarrow$ Desafio RSA-768 (2000 años/CPU)
el NIST
recomienda
$\|n\| \geq 2048$ bit hasta el 2030
generamos y mostramos (PKCS #1) una clave RSA-2048 con $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}$ tiene una solución única para: $
\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 es par}\\
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}$ Se aplica en RSA mediante algoritmo 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}$
OpenSSL: $d_p$ es el $\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}$ ¿para que nos sirve este teorema y estos tres nuevos parámetros en la clave privada? porqué 2. es más rápido ($\approx \times 4$) que $m = c^d \bmod{n}$
RSA
AES
(bits de seguridad)
$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 de los restos chinos
ejemplo simple del CRT
Teorema de los restos chinos
exponent1, $d_q$ es el exponent2 y $q_\text{inv}$ es el coefficient
…pero en lugar de descifrar con $m = c^d \bmod{n}$, lo hacemos así:
(Elgamal, DSA) $\rightarrow$