El algoritmo RSA

(1) Generación del par de claves

n = p.q

e es primo relativo con (p-1) y con (q-1). Este par de números (e,n) pueden ser conocidos por cualquiera,
y constituyen la llamada clave pública.

e debe tener un inverso módulo (p-1)(q-1), al que llamamos d. La clave privada será el par (d,n). Este
número d debe mantenerse secreto y sólo será conocido por el propietario del par de claves.

(2) Cifrado del mensaje con la clave pública

C= me2 (mod n2)

(3) Descifrado del mensaje con la clave privada

m= Cd (mod n)

EJEMPLO:
Mediante el uso de funciones Hash y del criptosistema RSA, Alberto quiere enviar el mensaje "UNED" a Bárbara de
forma cifrada. Además, desea enviar una firma digital para lo que utilizarán una función resumen H(m) que han
inventado de tal manera que corresponda con la suma de los símbolos que componen el mensaje (módulo 27).
Teniendo en cuenta que el alfabeto español, incluyendo la Ñ, a utilizar es A-Z, codificándose como 0-26, que la clave
pública de Alberto es (n1,e1)=(34121,15775), su clave privada d=26623, tomando p=229 y q=149; y la clave pública
de Bárbara es (n2,e2)=(46927,39423), explicando detalladamente los cálculos y dando los resultados codificados en
el alfabeto indicado:

a) ¿Cuál sería el criptograma?

C= me2 (mod n2)

Datos que ya tengo:

e2=39423

n2=46927

tamAlfabeto=27 (de 0 a 26)

A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

m=?

Necesito el mensaje. Para ello calculo la longitud máxima del mensaje, teniendo en cuenta un alfabeto
de 27 letras y que la longitud del mensaje no puede exceder de n2.

Longitud máxima del mensaje long(m):

tamAlfabetox+1<n2<tamAlfabetox => long(m)=x

n2=46927

274<46927<273 => long(m)=3

Como el mensaje a cifrar tiene 4 letras, hemos de dividir el mensaje en dos partes.

m1=UNE y m2=D
 m1=U*tamAlfabeto2+N*tamAlfabeto1+E*tamAlfabeto0

m1=21*272+13*271+4*270=15309+351+4=15664

C1= m1e2 (mod n2)

C1=1566439423(mod 46927)

Como con una calculadora es imposible realizar la operación 1566439423, hemos de recurrir al algoritmo
de exponenciación rápida.

n2 = 46927

RESUL X Z
1 15664 (m1) 39423 (e2)
si Z-1 es impar = (RESUL-1)*(X-1) mod n2 (X-1)2 mod n2 (Z-1)/2
si Z-1 es par = RESUL-1 Hasta llegar a 0
1*15664 mod 46927 = 15664 156642 mod 46927=26540 19711
… … …
448*34726 mod 46927 = 24411 347262 mod 46927 = 11957 4
24411 119572mod 46927 = 30207 2
24411 302072 mod 46927 = 14261 1
24411*14261 mod 46927 = 20785 (m1e2) --- 0

C1= m1e2 (mod n2)

C1=20785 mod 46927=20785

Ahora convierto C1 a letras. 273=19683 y 274=531441, con lo que 274 < C1 < 273.

Así pues, calculo:

C1/273 = 1*273 + 1102 (resto)

1102/272 = 1*272 + 373 (resto)

373/271 = 13*271 + 22 (resto)

Con lo que C1 = 1*273 + 1*272 + 13*271 + 22*270 = BBNV

A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Y el mismo proceso para m2 = D

C2 = 25180 mod 46927 = 2518 = 1*273 + 7*272 + 14*271 + 16*270 = BHÑP

b) ¿Cuál sería el hash?

En este caso la función resumen H(m) es la suma de los símbolos que componen el mensaje en modulo 27

H(UNED) = (21+13+4+3) mod 27 = 41 mod 27 = 14 mod 27

H(m) = 14

c) ¿Cuál sería la firma digital?

Primero calculamos la rúbrica:

Datos necesarios:
 H(m)=14

d=26623

n1=34121

r = (H(m))d mod n1 (si el ejercicio no tiene función HASH, se ha de sustituir H(m) por m)

r=(14)26623 mod 34121

Recurrimos otra vez al algoritmo de exponenciación rápida.

RESUL X Z
1 14 (H(m)) 26623 (d)
si Z-1 es impar = (RESUL-1)*(X-1) mod n2 (X-1)2 mod n2 (Z-1)/2
si Z-1 es par = RESUL-1 Hasta llegar a 0
….. ….. …..
3424*24175 mod 34121 = 31775 ---- 0

r = 31775 mod 34121

Y ya con la rúbrica, podemos calcular la firma digital:

Datos necesarios:

r = 31775

e2 = 39423

n2 = 46927

s = re2 mod n2

s = 3177539423 mod 46927

RESUL X Z
1 31775 (r) 39423 (e2)
si Z-1 es impar = (RESUL-1)*(X-1) mod n2 (X-1)2 mod n2 (Z-1)/2
si Z-1 es par = RESUL-1 Hasta llegar a 0
… … …
16959 175202 mod 46927 = 893 1
16959*893 mod 46927 = 33893 ---- 0
s = 33893 mod 46927

Ahora convierto s a letras. 273=19683 y 274=531441, con lo que 274 < s < 273.

Así pues, calculo:

s/273 = 1*273 + 14210 (resto)

14210/272 = 19*272 + 359 (resto)

359/271 = 13*271 + 8 (resto)

Con lo que C1 = 1*273 + 19*272 + 13*271 + 8*270 = BSNI

A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 ElGamal
Alberto desea mandar un mensaje a Bárbara y además se quiere asegurarse de que el
mensaje llega tal cual lo envía y de que no sea posible suplantar su identidad, para lo que
deciden utilizar la firma digital de ElGamal. Para ello ambos se ponen de acuerdo en utilizar
un grupo finito Z*15485863 y un elemento de ese grupo, sea el número 7, que hará de generador.
Alberto elige una clave privada, que se le ocurrió fuera 28236, y de la misma manera,
Bárbara elige 21702 como su clave privada. No se olvida de tomar un número aleatorio
v=480 necesario para el algoritmo de cifrado. Por supuesto, ambos utilizarán el alfabeto
español de 27 letras, incluyendo la Ñ, donde A-Z corresponden a los valores 0-26.
Suponiendo que se quiera enviar el mensaje "UNED" y explicando los pasos
detalladamente:
G = Z*p

p = 15485863

α= 7

Clave privada Alberto a = 28236

Clave pública: αa= 728236

Clave privada Bárbara b = 21702

Clave pública: αb= 721702
Número aleatorio v=480
Alfabeto español 27 letras con {A=0, …, Z=26}

m=”UNED”

a) Calcular el criptograma.

El criptograma a enviar es la pareja (αv, m*(αb)v)

m = UNED = U*273 + N*272+E*271+D*270= 21*273 + 13*272 + 4*271 + 3*270= 422931

A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Alberto calcula αv

αv = αv mod p*
αv = 7480 mod 15485863 = 12001315 mod 15485863

Recurrimos otra vez al algoritmo de exponenciación rápida.

RESUL X Z
1 7 (α) 480 (v)
si Z-1 es impar = (RESUL-1)*(X-1) mod p (X-1)2 mod p (Z-1)/2
si Z-1 es par = RESUL-1 Hasta llegar a 0
….. ….. …..
12001315 mod 15485863 = 12001315 ---- 0

Alberto calcula (αb)v y m*(αb)v

Recurrimos otra vez al algoritmo de exponenciación rápida.

αb = 721702 = 8890431 mod 15485863 *

 RESUL X Z
1 7 (α) 21702 (b)
si Z-1 es impar = (RESUL-1)*(X-1) mod p (X-1)2 mod p (Z-1)/2
si Z-1 es par = RESUL-1 Hasta llegar a 0
….. ….. …..
8890431 mod 15485863 = 8890431 ---- 0

Recurrimos otra vez al algoritmo de exponenciación rápida.

(αb)v = 8890431480 = 9846598 mod 15485863 *

RESUL X Z
1 8890431 (αb) 480 (v)
si Z-1 es impar = (RESUL-1)*(X-1) mod p (X-1)2 mod p (Z-1)/2
si Z-1 es par = RESUL-1 Hasta llegar a 0
….. ….. …..
9846598 mod 15485863 = 9846598 ---- 0

m*(αb)v = 422931 * 9846598 mod 15485863 = 4232504 mod 15485863

La pareja a enviar es (αv, m*(αb)v) = ( 12001315, 4232504)
Decodifico la pareja
12001315 = 22*274 + 15*273 + 19*272 + 19*271+ 4*270 = VOSSE
4232504 = 7*274 + 26*273 + 0*272 + 24*271+ 11*270 = HZAXM
El criptograma enviado a Bárbara es (VOSSE, HZAXM)
b) Calcular la firma digital.

Como ya indiqué en el apartado anterior m= 422931

- Alberto genera un número aleatorio h tal que mcd (h, p-1) = 1
Tomo h = 90725 y que es co-primo con 15485863-1 mcd(90725, 15485862) = 1

- Calculo r = αh mod n
r = 790725 mod 15485863 = 7635256 mod 15485863 *

- Resuelvo m= a*r + h*s (mod p-1)

422931 = 28236*7635256 + 90725*s (mod 15485862)

s = (422931-28236*7635256)/90725

Para poder hacer la división en Zp-1, calculo la inversa de 90725 en Z15485862 = 11031191

Con lo que s = (422931-28236*7635256)*11031191

s = 422931-10403514 (28236*7635256 en Z15485862= 10403514 utilizando el algoritmo de exponenciación rápida)*11031191

s = -9980583*11031191 (Ahora 15485862-9980583=5505279)

s = 5505279*11031191

s = 9619815 (que es 5505279*11031191 en Z15485862) mod 15485862

La firma para el mensaje es la pareja (r, s) por lo tanto la firma de Alberto es

(r, s) = (7635256, 9619815)

Realizar la inversa de un numero en Z p

P.E: Realiza el inverso de 3 en Z5

5 dividido entre 3 es 1 con resto 2.

5=3*1+2 2 = 5 – (3*1)

3 = 2*1 + 1 1 = 3 – (2*1)

Sigo hasta llegar a resto = 1

Ahora pongo las expresiones en función del resto

Y empiezo a resolver desde la expresión 1 = 3 – (2*1)

1 = 3 – (2*1), como 2 = 5 – (3*1), lo sustituyo en la expresión.

1 = 3 – (5 – (3*1)*1) = 3 – (5 – 3) = 3 – 5 + 3 = 3 + 3 – 5 = 2*3 – 5
1 = 2*3 – 5

Como en Z5 el 5 es igual a 0 (5 mod 5 = 0) nos queda

1 = 2*3

1
Como estamos buscando 3-1 que es lo mismo que pasamos el 3 multiplicando al otro lado de la
3
función dividiendo

1
=2
3

Con lo que 3-1 en Z5 es igual a 2

−5 mod 3=?
Con un módulo de 3 hacemos un reloj con los números 0, 1, 2.
Empezamos en 0 y nos movemos 5 números en una secuencia en sentido contrario a las manecillas del
reloj (-5 es negativo) de 2, 1, 0, 2, 1.

Terminamos en 1, así que −5 mod 3=1.

7 mod 2=?
Con un módulo de 2 hacemos un reloj con los números 0, 1.
Empezamos en 0 y nos movemos 7 números en una secuencia en sentido de las manecillas del reloj de
1, 0, 1, 0, 1, 0, 1.

Terminamos en 1, así que 7 mod 2=1.