Siguiente: Generación de llaves Un nivel arriba: Algoritmos básicos Anterior: Algoritmos básicos

Encriptamiento

De manera aún más restringida, si p y q son primos, n=p q y $\lambda(n)=\mbox{\rm m.c.m.}(p-1,q-1)$ entonces también vale

$$e\cdot d\mbox{\rm mod }\lambda(n)=1\ \Rightarrow\ a^{ed}\mbox{\rm mod }n = a.$$

Observamos que si se conoce p,q, entonces dado e se calcula, mediante el Algoritmo de Euclides para el Cálculo del Máximo Común Divisor, a su inverso multiplicativo d en el anillo $Z\!\!\!Z^*_{\mbox{\scriptsize m.c.m.}(p-1,q-1)}$. Cualquier ataque contra el sistema de encriptamiento tiene como objetivo calcular d. Los procedimientos de encriptamiento y desencriptamiento mostrados en el algoritmo (4.1) son correctos.

  

Figure 4.1: Encriptado y desencriptado RSA.

Ejemplo. Consideremos dos primos grandes: p = P₂₃₀₀₇=262231 y q = P₂₃₀₀₈ = 262237. Su producto es entonces n = p q = 68766670747 el cual número se escribe con un número de bits igual a $\lfloor \log_2 n\rfloor + 1=37$. Si se toma el exponente e = 12521 se tiene que e es primo relativo con el mínimo común múltiplo de p-1 y q-1. Sea $\lambda = \mbox{\rm m.c.m.}(p - 1, q - 1) = 11461024380$. De hecho, se tiene $1=d\cdot e + k\cdot \lambda$, donde d = 1132280741 y k = -1237. Para un valor como m = 1562435 el código correspondiente es

$$c = m^e\mbox{\rm mod }n = 56009798215$$

y, en efecto, si calculamos la potencia correspondiente al exponente d,

$$m' = c^d\mbox{\rm mod }n = 1562435,$$

vemos que ésta coincide con el mensaje original m.


Ejemplo. Como un segundo ejemplo, consideremos la cadena de caracteres

Mexicanos al grito de guerra

al tomar uno a uno los caracteres

M , e , x , i , c , a , n , o , s , , a , l , , g , r , i , t , o , , d , e , , g , u , e , r , r , a

y al ponerlos en código ASCII, obtenemos la sucesión de números

77, 101, 120, 105, 99, 97, 110, 111, 115, 32, 97, 108, 32, 103, 114, 105, 116, 111, 32, 100, 101, 32, 103, 117, 101, 114, 114, 97

Al tomarlos de cuatro en cuatro, cada tira de cuatro números se interpreta como un entero, entre 0 y 256⁴-1, escrito en base 256. Aplicamos pues una conversión de base 256 a base 10. Los 28 caracteres dan 7 números:

$$\begin{array}{ccccccc} 1298495593 & 1667329647 & 1931501932 & 543650409 & 1953439844 & 1696622453 & 1701999201 \end{array}$$

Aplicamos a cada uno la función de encriptamiento:

$$\begin{array}{ccccccc} 63933001817 & 25675825739 & 519015522... ...78589175 & 28389357636 & 14741227757 & 32565199854 \end{array}$$

y al aplicar la función de reconversión a base 256

226, 180, 48, 89, 250, 102, 2, 75, 53, 91, 123, 217, 184, 101, 235, 247, 156, 35, 56, 68, 110, 165, 72, 237, 149, 9, 131, 238

que son códigos correspondientes a los caracteres

â , ' , 0 , Y , ú , f , $\langle$no-imprimible$\rangle$ , K , 5 , [ , { , Ù , $\angle$ , e , ë , $\div$ , $\langle$no-imprimible$\rangle$ , # , 8 , D , n , $Y\!\!\!\!\!\!\!=$ , H , í , $\langle$no-imprimible$\rangle$ , , $\langle$no-imprimible$\rangle$ , î

algunos de los cuales no son imprimibles. La cadena yuxtapuesta es

â'0Yúf$\langle$no-imprimible$\rangle$K5[{Ù$\angle$eë $\div\langle$no-imprimible$\rangle$#8Dn $Y\!\!\!\!\!\!\!=$Hí$\langle$no-imprimible$\rangle$ $\langle$no-imprimible$\rangle$î

Ahora procediendo en sentido inverso, partiendo de

$$\begin{array}{ccccccc} 63933001817 & 25675825739 & 519015522... ...78589175 & 28389357636 & 14741227757 & 32565199854 \end{array}$$

calculamos la función de desencriptamiento, para obtener

$$\begin{array}{ccccccc} 1298495593 & 1667329647 & 1931501932 & 543650409 & 1953439844 & 1696622453 & 1701999201 \end{array}$$

la cual sucesión efectivamente coincide con la ``original''

$$\begin{array}{ccccccc} 1298495593 & 1667329647 & 1931501932 & 543650409 & 1953439844 & 1696622453 & 1701999201 \end{array}$$

Siguiente: Generación de llaves Un nivel arriba: Algoritmos básicos Anterior: Algoritmos básicos