Primos y criptografía · Definición

Criptosistema RSA

teoría de números elementalprimos y criptografía

Antes de empezar necesitas conocer

RSA permite que cualquiera cifre mensajes con una clave pública, mientras solo el dueño de la clave privada puede descifrarlos. Su seguridad se apoya en que factorizar n = pq es computacionalmente difícil.

Definición

El criptosistema RSA es un método de cifrado de clave pública basado en la dificultad de factorizar el producto de dos primos grandes. Usa el teorema de Euler y el inverso modular para cifrar y descifrar mensajes.

\[c \equiv m^{e} \pmod{n}, \quad m \equiv c^{d} \pmod{n}\]

Sean \( p \) y \( q \) primos distintos, \( n = pq \) y \( \varphi(n) = (p-1)(q-1) \). Si elegimos \( e \) con \( \operatorname{mcd}(e, \varphi(n)) = 1 \) y calculamos \( d \) como inverso modular de \( e \) módulo \( \varphi(n) \), entonces \( m^{ed} \equiv m \pmod{n} \) para todo \( m \), por el teorema de Euler y el teorema chino del resto.

Con \( p = 3 \), \( q = 11 \) tenemos \( n = 33 \) y \( \varphi(n) = 20 \). Tomando \( e = 3 \), el inverso de 3 módulo 20 es \( d = 7 \), de modo que el mensaje \( m = 4 \) se cifra como \( c \equiv 4^3 \equiv 31 \pmod{33} \) y se recupera como \( 31^7 \equiv 4 \pmod{33} \).

Un error típico es calcular d como inverso de e módulo n en lugar de módulo \( \varphi(n) \). Con \( n = 33 \) y \( e = 3 \) ese inverso ni siquiera existe, porque \( \operatorname{mcd}(3, 33) = 3 \), así que el exponente debe trabajarse módulo \( \varphi(n) \).

Para pensar

¿Por qué d debe calcularse módulo \( \varphi(n) \) y no módulo \( n \)?

Porque \( ed \equiv 1 \pmod{\varphi(n)} \) es lo que hace funcionar el teorema de Euler; con \( n = 33 \) y \( e = 3 \) ni siquiera existe inverso.

Ejercicios 10

  1. ¿Qué módulo se usa para calcular el exponente d en RSA?
  2. Si p = 5 y q = 7, ¿cuál es el valor de n?
  3. Para p = 5 y q = 7, ¿cuál es el valor de φ(n)?
  4. ¿Qué condición debe cumplir el exponente público e en RSA?
  5. ¿Qué teorema garantiza que \( m^{ed} \equiv m \pmod{n} \) en RSA?
  6. Con p = 3, q = 11 y e = 3, halla d tal que 3d ≡ 1 (mod 20).
  7. Con n = 33 y d = 7, ¿cuál es el descifrado de c = 31?
  8. Si e = 5 y φ(n) = 24, ¿cuál es el inverso modular d de e?
  9. Con p = 5 y q = 11, calcula φ(n) y el exponente e = 3 mínimo válido.
  10. Con \( p = 3 \), \( q = 11 \) y \( e = 7 \), demuestra si \( e \) es válido y halla \( d \); luego verifica que \( 4^{ed} \equiv 4 \pmod{33} \).

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 10
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2