-
Generación de Claves:- Seleccionemos dos números primos pequeños: \(p = 61\) y \(q = 53\text{.}\)- Calculamos \(n = p \times q = 61 \times 53 = 3233\text{.}\)- Calculamos \(\varphi(n) = (p - 1) \times (q - 1) = 60 \times 52 = 3120\) .- Elegimos \(e = 17\) (un número primo pequeño, coprimo con \(3120\) ).- Encontramos \(d \equiv 2753\) (ya que \(17 \times 2753 \div 3120 = 1\) ).Las claves son: Clave pública \((e, n) = (17, 3233)\) y Clave privada \((d, n) = (2753, 3233)\text{.}\)
-
Encriptación:Supongamos que queremos cifrar el mensaje \(M = 123\text{.}\)Calculamos \(C \equiv 123^{17} \pmod{\varphi(3233)} = 855\text{.}\)El mensaje cifrado \(C\) es \(855\text{.}\)
-
Desencriptación:Calculamos \(M \equiv 855^{2753} \pmod{\varphi(3233)} = 123\text{.}\)el mensaje original \(M = 123\) es recuperado.
Sección 4.2 El Algoritmo RSA
Uno de los grandes problemas de la criptografía es el intercambio de claves entre dos personas que van a sostener comunicación cifrada. Este problema se ha resuelto mediante el uso de la tecnología PKI Párrafo . Antes del uso de las tecnologías de encriptación basadas en curvas elípticas, el algoritmo de claves asimétricas más utilizado era el RSA (desarrollado en 1977 por Ronal Rivets, Adi Shamir y Leonard Adleman).
El Algoritmo RSA define las pautas para un sistema de intercambio de mensajes cifrados, que no requiere del intercambio de claves. RSA se basa en las muy conocidas propiedades número-teóricas de la aritmética modular y los números enteros y en la dificultad de factorizar números muy grandes. Un sistema que además es casi imposible de romper. Cada parte crea dos claves, una privada que mantiene en secreto y una pública que divulga. Centra su operación en la dificultada de factorizar dos números suficientemente grandes (ver: El Logaritmo Discreto; Subsección 3.5.2).
Es necesario comprender este tipo de algoritmos asimétricos, para apreciar las ventajas del uso de curvas elípticas en la encriptación asimétrica.
-
Generación de Claves RSA:Se escogen dos números primos grandes, \(p\) y \(q\text{.}\)Luego se calcula el producto \(n = p \times q\text{.}\)Se calcula la función totient de Euler [Definición 2.2.12]: \(\varphi(n) = (p - 1) \times (q - 1)\text{.}\)Se elige un número entero \(e\) tal que: \(1 \lt e \lt \varphi (n)\) y \(mcd(e, \varphi (n))= 1\text{;}\) con \(e\) y \(\varphi (n)\) coprimos. Lo correcto sería utilizar una \(e\) aleatoria, generada por un algoritmo aleatorio o por ejemplo: por una función que utilice los movimientos aleatorios del ratón.Por último se encuentra un número \(d\) tal que \((d \times e) \div \varphi (n) = 1\) (es decir, \(d\) es el inverso multiplicativo modular de [Nota A.2.6]: \(e \pmod{\varphi(n)}\)).
-
Encriptación RSA:El mensaje está representado como un número entero \(M\) en el rango \(0 \lt M \lt n\text{.}\)Se calcula \(C \equiv M^e \pmod{n}\text{.}\)El mensaje cifrado \(C\) puede ser enviado.
-
Desencriptación RSA:Se calcula \(M \equiv C^d \pmod{n}\text{.}\)El mensaje original \(M\) es recuperado.
En resumen, son generadas las claves pública \((e, n)\) y privada \((d, n)\text{;}\) claves mediante las cuales se establece la comunicación secreta.
Ejemplo 4.2.1. RSA; numérico sencillo.
Ejemplo 4.2.2. RSA; línea de texto.
Supongamos que queremos enviar el mensaje RSA: \(m =\) “CIUDAD DE CUMANA”. Y nuestras claves privada y pública son: \(e=50253\) y \(d = 27917\text{;}\) provenientes de los números primos: \(p = 251\) y \(q = 260\text{,}\) donde \(n = p \times q = 67519\text{;}\) con \(\varphi(67519)=67000\text{:}\)
-
Se divide \(m\) en enteros de longitud fija \(M\) menores que \(m\text{.}\)\begin{equation*} \begin{array}{c|cccc} ASCCI& hexa & decimal & M_{RSA} & descifrado_{RSA} \\ \hline CI & 4349 & 17225 & 58634 & 17225 \\ UD & 5544 & 21844 & 15357 & 21844 \\ AD & 4144 & 16708 & 50966 & 16708 \\ DE & 4445 & 17829 & 54665 & 17829 \\ CU & 4355 & 17237 & 58883 & 17237 \\ MA & 4D41 & 19713 & 60035 & 19713 \\ NA & 4E41 & 19841 & 58777 & 19841 \\ \end{array} \end{equation*}
-
Se calculan todos los \(C\) para todo los \(M\text{;}\) para: ‘CI’, \(M=17225\) ; \(C = (M^e) mod(n) = 58634\text{,}\) obteniéndose el mensaje \(m\) cifrado:\(m(cifrado) = 58634 \enspace 15357 \enspace 50966 \enspace 54665 \enspace 58883 \enspace 60035 \enspace 58777\)
-
Para descifrar, se elevan cada uno de estos números \(C\) a la potencia \(d\) y se toma el residuo \(\pmod{n}\text{:}\)\(t=(C^d) mod(n)\text{;}\) para el primero de ellos \(t_1=17225\text{;}\) estos valores en decimal se expresa en ASCII (cada uno de ellos), para construir el mensaje original. Para el primero: \(t_1=17225_d = 4349_h = CI_{ASCII}\)
- Estos números hexadecimales expresado en ASCII representan los caracteres del mensaje original RSA: \(m = \) “CIUDAD DE CUMANA”.
Sage: 4.2.3. Criptografía RSA.
Algoritmo Sage; Nota A.5.4, para encriptar y desencriptar un mensaje —letra por letra— según el protocolo RSA.
