Cada usuario U debe elegir sus claves, pública y privada, mediante el siguiente protocolo:   

• U elige dos números primos grandes p y q (se recomienda que ambos primos tengan entre 116 y 155 dígitos) y calcula su producto (n=p·q). El conjunto de mensajes a utilizar por el usuario U será el grupo multiplicativo . El número de elementos de este grupo es ϕ(n), donde ϕ es el indicador de Euler .  
  

En este caso, al ser n un producto entre dos primos distintos, ϕ(n) se calcula del siguiente modo  

ϕ(n) = ϕ(p·q) = (p - 1) (q - 1) 

• A continuación U elige un entero e, con 2 < e < ϕ(n), de modo que

mcd(e, ϕ(n)) = 1 

• Ahora el usuario U calcula d, el inverso de e módulo ϕ(n), por lo que se verifica que 1 < d < ϕ(n) y

e · d ≡1 mod(ϕ(n)) 

Nota: El cálculo de este inverso se puede hacer automáticamente con Maple y es eficiente pues utiliza el algoritmo extendido de Euclides. 

De este modo U ya tiene su clave pública, la pareja (n,e), y su clave privada, que es el número d. Se deberá mantener secretos los números p, q y ϕ(n), ya que si se conocen p y q es muy fácil calcular ϕ(n) y descubrir la clave privada d a partir de la clave pública.
 

Los valores e y d son los denominados exponente de cifrado y exponente de descifrado, respectivamente. El elemento n se denomina módulo del criptosistema RSA.

A continuación veremos unos ejemplos de generación de claves con la función Genera_clave de la librería HerramientasRSA .  

Los ejemplos son modificables a gusto del lector. 

La función contiene dos parámetros, el primero es un entero K que define la longitud de los primos p y q, el segundo parámetro es un nombre en el que se almacenará la clave privada. La función obtiene una clave pública (la clave privada se almacena en el nombre que pongamos) obtenida a partir de la pareja de primos p y q. Recordamos que la clave pública la forman el par (n,e). 

La clave pública es: 

>	clavePublica:=Genera_clave(3,clavePrivada);

 

(2.1.1.1)

 

>

 

En este ejemplo n sería el primer número del par anterior, 

>	n:=clavePublica[1];

 

(2.1.1.2)

 

y e, el exponente de cifrado, el segundo. 

>	e:=clavePublica[2];

 

(2.1.1.3)

 

El valor de la clave privada es 

>	clavePrivada;

 

(2.1.1.4)

 

La forman n, al igual que en la pública, y d, el exponente de descifrado: 

>	d:=clavePrivada[2];

 

(2.1.1.5)

 

Para comprobar si son correctas, veremos si la clave pública es inversa de la privada y para ello realizamos la siguiente operación. 

>	e * d mod (numtheory[phi](n));

 

(2.1.1.6)

 

>

 

El resultado de la multiplicación módulo phi de n es 1, por lo que corroboramos que la clave pública y la privada son inversas entre sí, y por lo tanto que es un par de claves válido. 

Supongamos que dos usuarios A y B desean comunicarse un mensaje m, que estará escrito en un alfabeto A y se puede convertir a un número entero mediante la función Mensaje_numérico . En este caso es B el que quiere enviarle el mensaje a A. Para ello realizará las siguientes operaciones: 

• B consulta la clave pública de A, el par (nA , eA).

• B representa el mensaje m como un elemento de   , esto quiere decir que pertenecerá al rango {0,1, ... ,nA - 1 } y además será primo con nA.  Si es necesario dividirá el mensaje m en trozos de menor tamaño para que el equivalente numérico de cada trozo sea menor que nA. Ver enlace

• B calcula el valor del criptograma
  

c = (mod nA) 

  que envía a A.
 

La restricción de mcd(m,n)=1 no es una condición demasiado restrictiva ya que la probabilidad de que no se cumpla es despreciable. La probabilidad de que el número elegido m dé problemas viene dada por la siguiente expresión: 

cuyo valor es prácticamente despreciable si p y q son grandes. 

Ahora pondremos en práctica lo explicado utilizando la función RSA de la librería " HerramientasRSA" , los ejemplos dados a continuación son modificables. 

La función RSA tiene tres argumentos: 

• Primer argumento: es el mensaje, en este caso  será el mensaje a cifrar. En el ejemplo cifraremos el mensaje: "Primer mensaje cifrado por RSA."

>	mensaje:="Primer mensaje cifrado por RSA.";

 

(2.1.2.1)

 

• Segundo argumento: el alfabeto, que será el alfabeto con el que cifraremos el mensaje. En el ejemplo usaremos el alfabeto Castellano que hemos definido como:

>	alfabeto:=Castellano;

 

(2.1.2.2)

 

2.1.3 Descifrado de mensajes 

Cuando A recibe el criptograma, para recuperar el mensaje original m, debe realizar el siguiente proceso: 

A usa su clave privada  dA y realiza el siguiente cálculo a cada elemento perteneciente al criptograma: . Después obtiene el equivalente de texto de cada número y concatena todas las cadenas de caracteres. 

Con esto se recupera el mensaje ya que:  

≡ m (mod ) 

                                                                                (Esto es por la consecuencia del teorema de euler) 

Para descifrar podemos utilizar de nuevo la función RSA contenida en la librería " HerramientasRSA ", aunque esta vez  se invocará con los parámetros adecuados para descifrar: 

3.1.1 Firma 

En el caso de que el usuario B desee enviar un mensaje m al usuario A junto con su firma digital, en primer lugar deberá obtener el criptograma del mensaje cifrado con la clave pública de A, kA: 

3.1.2 Verificación 

A continuación veremos los pasos que ha de realizar A para verificar que el mensaje ha sido enviado por B. 

• Primero, A determinará la rúbrica de B a través de s y su clave privada.

r = =   

• Seguidamente, deberá comprobar que la rúbrica es la correspondiente al mensaje enviado por B.

s = = m 

Si B quiere enviar un mensaje m cifrado y firmado a A, deberá realizar lo siguiente: 

• B  calcula su rúbrica r con la operación:

r ≡ (mod nB) 

• B cifra la rúbrica con la clave pública de A, eA y nA de la siguiente manera:

s ≡ (mod nA) 

Por último, B enviará la pareja (c,s), c es el criptograma correspondiente al mensaje m, cifrado con la clave pública de A. 

En el protocolo de Firma digital, basado en RSA, el distinto tamaño de los módulos de las claves de A y B puede dar problemas, cuando al hacer los cálculos módulo nA se obtiene un número mayor que módulo nB. 

Para solventar  este  problema se puede hacer lo siguiente: 

• Si nB<nA entonces  

• Si nA<nB entonces  

Ahora procederemos a usar la función Firma_RSA contenida en la librería " HerramientasRSA " para ejemplificar cómo se firma un mensaje. 

Esta función tiene 4 parámetros de entrada. 

• alfabeto, que será con el cual cifraremos el mensaje. En este caso usaremos:

>	alfabeto:= Castellano;

 

(3.2.1.1)

 

• mensaje, que cifraremos y firmaremos. En este primer ejemplo utilizaremos el siguiente: "Ejemplo de mensaje cifrado y firmado por el usuario A."

>	mensaje:="Ejemplo de mensaje cifrado y firmado por el usuario B.";

 

(3.2.1.2)

 

• clave privada del usuario B, que será el que cifre el mensaje. En este ejemplo es la siguiente: 

  >	publica_B:=Genera_clave(3,privada_B);

   

  (3.2.1.3)

   

  >	privada_B;

   

  (3.2.1.4)

   

   

  • clave pública de A, que generamos a continuación:
   

  >	publica_A:=Genera_clave(3,privada_A);

   

  (3.2.1.5)

   

  >

   

   

  A continuación realizaremos el cifrado y la firma de la siguiente forma: 

  >	mensajeFirmado:=Firma_RSA(alfabeto,mensaje,publica_A,privada_B);

   

  (3.2.1.6)

   

   

  Este es el mensaje cifrado y firmado por el usuario B, siendo el criptograma: 

  >	criptograma:= mensajeFirmado[1];

   

  (3.2.1.7)

   

   

  y la firma:  

  >	firma:= mensajeFirmado[2];

   

  (3.2.1.8)

   

   

3.2.2 Verificación RSA 

Para verificar la firma de B, el usuario A deberá: 

• Recuperar la rúbrica de B haciendo:

(mod nA) ≡ r 

• Verificar que coincide con el mensaje enviado.

(mod nB) ≡  

Es una función resumen propuesta por Rivest y es de 128 bits. Fue creada para mejorar a su antecesora la función MD4, ya que se encontraron problemas de colisiones. Ha sido muy utilizada, aunque también se han encontrado numerosas debilidades. 

Se han encontrado una tasa de colisiones más alta de lo que se esperaba para su función de compresión.  

Por ello en EEUU no se admite. Pese a ello en este libro hemos decidido utilizarla por su importancia histórica ya que su diseño ha servido como modelo para otras posteriores. 

Ahora usaremos la función Mensaje_firmado contenida en la librería HerramientasRSA  para obtener la firma de un mensaje. Esta función, que utiliza la función resumen MD5 recibe 3 parámetros: 

• mensaje, usaremos el siguiente: "Firma realizada con función resumen MD5".

>	mensaje:= "Firma realizada con función resumen MD5";

 

(3.3.1.1)

 

• alfabeto, como siempre usaremos el castellano

>	alfabeto:=Castellano;

 

(3.3.1.2)

 

• clave pública del destinatario y privada del autor que será el que firme el mensaje:

>	publica_A;

 

(3.3.1.3)

 

>	privada_B;

 

(3.3.1.4)

 

Ahora firmamos el mensaje y obtenemos: 

>	resultado:=Mensaje_firmado(mensaje,alfabeto,publica_A,privada_B);

 

(3.3.1.5)

 

Como resultado obtenemos el par criptograma y firma: 

>	criptograma:=resultado[1];

 

(3.3.1.6)

 

>	firma:=resultado[2];

 

(3.3.1.7)

 

Podemos observar la gran ventaja señalada anteriormente, la firma es mucho más pequeña que el mensaje, lo que agiliza los procesos de cifrado y descifrado posteriores. Ahora veremos cómo la longitud de la firma no aumenta aunque aumentemos la longitud del mensaje, esta es otra gran ventaja de las funciones resumen frente a la firma convencional, que aumentaba el tamaño de la firma al aumentar el del mensaje. 

Usaremos los mismos datos que en el anterior ejemplo aunque modificaremos el mensaje: 

>	mensaje2:="Ahora vamos a realizar una prueba de firma de mensaje con la función resumen MD5, la cual fue propuesta por Rivest.";

 

(3.3.1.8)

 

Ahora procedemos a firmar el mensaje: 

>	resultado:=Mensaje_firmado(mensaje2,alfabeto,publica_A,privada_A);

 

(3.3.1.9)

 

Obtenemos como resultado: 

>	criptograma:=resultado[1];

 

(3.3.1.10)

 

>	firma:=resultado[2];

 

(3.3.1.11)

 

El criptograma, obviamente, aumenta su longitud, por otro lado la firma permanece con una longitud  idéntica a la del ejemplo anterior. En la actualidad las funciones resumen son fundamentales en estos procesos. 

4.2.1 p y q deben ser de la misma longitud 

Ambos deberán tener una longitud aproximadamente igual, para que el número de divisiones necesarias para intentar encontrar un factor de n sea próximo a  Actualmente, la recomendación mínima para la longitud de p y q es de 512 bits, por lo que n  será al menos de 1024 bits. 

4.2.2 p y q no deben estar demasiado cercanos 

Ambos valores no deben ser demasiado cercanos ya que  de ser así y, si por ejemplo p < q, entonces   sería pequeño y se tendría: 

de modo que la diferencia: 

también sería pequeña. Como  el segundo miembro es un cuadrado perfecto, con pocos tanteos se puede encontrar un entero x > , tal que  

Entonces se obtiene que:  

p = x - y      q = x + y 

con lo que n quedaría factorizado. 

Algoritmo de factorización de Fermat.  

4.2.3 El mcd(p-1,q-1) debe ser pequeño 

Si mcd(p-1,q-1) es grande, el mcm(p-1,q-1) va a ser muy pequeño en comparación a  ϕ(n)=, ya que: 

u = mcm(p-1,q-1) =  

Ahora, cualquier inverso de e módulo u, por ejemplo k, sirve como exponente de descifrado y verifica: 

≡1 mod(n) 

para todo mensaje m. Entonces si u es pequeño, esta propiedad se aprovecha para romper el criptosistema realizando los siguientes pasos: 

• Elegir un valor para u y calcular k, el inverso de e módulo u.

• Cifrar varios mensajes sucesivos con el criptosistema y tratar de descifrarlos usando el exponente k.

• Si en alguno de los casos del punto anterior se tiene éxito, el sistema queda roto. En caso contrario se repite el caso 1.

Si u es realmente pequeño en comparación con ϕ(n) el éxito de los pasos anteriores se puede alcanzar con relativa eficiencia computacional. 

4.2.4 p - 1 y q - 1 deben contener factores primos grandes 

4.2.5 p y q deben ser robustos 

Un primo p impar se califica como robusto cuando  verifica las siguientes condiciones: 

• p - 1 tiene un factor primo grande r

• p + 1 tiene un factor primo grande s

• r - 1 tiene un factor primo grande t

En el criptosistema RSA tanto p como q deberían de cumplir estas condiciones para que la factorización de n sea lo más costosa posible. 

4.3.1 Exponente de cifrado pequeño 

Por las razones mencionadas anteriormente, se aconsejan valores de e pequeños y fáciles de escribir en binario.  Los valores más usuales son e=3 ó e= 65537. En efecto: 

• Tanto e=3 como e= 65537 son números primos.

• Si convertimos a binario ambos números, el dígito binario obtenido es elemental lo que facilitará la tarea de calcular

4.3.2 Exponente de cifrado común 

En caso de que varios usuarios de un grupo coincidan en la elección del elemento e (exponente de cifrado) deberán tener distinto n. En otro caso,  tendrían el mismo exponente de descifrado d (o clave privada).  

4.3.3 Exponente pequeño con mensajes iguales 

Si se desea enviar el mismo mensaje a distintos destinatarios, no es recomendable usar valores pequeños de e  ya que un posible criptoanalista podría obtener los siguientes criptogramas: 

x ≡ C1 (mod n1) 

x ≡ C2 (mod n2) 

x ≡ C3 (mod n3) 

En el caso de resolver este sistema, se obtendría el mensaje original. 

Para estar prevenidos de estos ataques, deberemos generar una secuencia aleatoria de bits que añadiremos al comienzo del mensaje previamente al cifrado. Este proceso se denomina "salar" el mensaje. 

Sea n = p · q, p, q primos distintos. Sea a ≡ (mod n), esto es, a es un cuadrado módulo n. Entonces la ecuación ≡ a (mod n), tiene exactamente cuatro soluciones distintas: 

Dichas soluciones se obtienen resolviendo primero las ecuaciones: 

≡ a (mod p) 

≡ a (mod q)  

Si a es un cuadrado módulo n, conocidas las cuatro raíces de a es fácil factorizar n. 

Sean x , y  tales que ≡ a (mod n), ≡ a (mod n) ⇒ ( - ) = (x - y) (x + y) ≡ 0 (mod n) ⇒ n | (x - y) (x + y)  

Por construcción: 

       n ∤ (x - y)             mcd(n, x - y) = p  

⇒ 

       n ∤ (x + y)            mcd(n, x + y) = q 

5.1.3 Ejemplos 

En esta sección veremos cómo actúa este protocolo a través de diferentes funciones de la librería " HerramientasRSA ". Se realizarán dos ejemplos, uno completo para ver cómo se usan las funciones y luego otro en blanco para que el lector introduzca sus propios datos. Antes de esto veremos las funciones que usaremos. 

Ya que los primos que elijamos deben de cumplir el requisito de que ambos sean congruentes con 3 módulo 4,  p,q ≡ 3 (mod 4), usaremos la función Genera_primos que nos dará un par de primos válidos para realizar el protocolo. Esta función recibe como parámetro: 

• longitud, será el entero que indique el tamaño de la pareja de primos.

Ahora veremos cómo actúa: 

>	parejaPrimos:=Genera_primos(3);

 

 

	(5.1.3.1)

 

Como vemos la función genera dos primos de longitud 3, vamos a comprobar si cumplen el requisito p, q ≡ 3 (mod 4) : 

>	p:= parejaPrimos[1]; q:= parejaPrimos[2];

 

 

	(5.1.3.2)

 

>	p mod 4; q mod 4;

 

 

	(5.1.3.3)

 

Vemos que ambos lo cumplen, por lo que son válidos para usarlos en nuestro ejemplo. 

A continuación veremos cómo usar la función Lanza_moneda , la cual no recibe ningún parámetro, pero tiene un comportamiento especial ya que el usuario deberá introducir ciertos datos para simular el lanzamiento de la moneda. La función simulará las acciones realizadas por el usuario B y el lector deberá tomar las decisiones correspondientes al usuario A. 

Cuando ejecutemos la función habrá que seguir los pasos siguientes: 

•  Se pedirá al lector introducir dos números primos, se recomienda utilizar la función Genera_primos . En este ejemplo usaremos los primos 7 y 11.

•  La función mostrará los primos elegidos y también las cuatro raíces obtenidas, dos son correctas y dos no lo son, y se pedirá al usuario que introduzca una de las 4.

•  El lector introducirá la raíz que desee.

•  Por último la función escribirá si el lector ha acertado o no con su decisión.

Veamos un ejemplo de ejecución: 

>	Lanza_moneda();

 

 

 

 

 

 

	(5.1.3.4)

 

5.2 Protocolo SET Comercio Electrónico 

A medida que las tecnologías de la información han ido evolucionando, nuevos modos de comercio han aparecido, aunque esto también provoca que los criptoanalistas busquen métodos para atacar los nuevos sistemas. Es en estos casos cuando la seguridad de la información se convierte en una herramienta necesaria para evitar posibles fraudes como robos de información vital de los usuarios.