Escuela Superior Politécnica del LitoralFacultad de Ingeniería Eléctrica y Computación

Maestría en Seguridad Informática Aplicada

CriptografíaResolución de Ejercicios Hoja5

Por Freddy A. Rojas Vilela.

Ejercicio No. 1Asuma un criptosistema RSA con p = 97 y q = 31. Discuta si todas las llaves públicas propuestas pueden ser usadas en el criptosistema:Para poder determinar si una llave publica puede ser utilizada para el criptosistema es necesaria que sea coprimo con phi(n). Entonces para poder comprobarlo procedamos a calcular dicho valor, así:

n=p∗qn=97∗31n=3007

ϕ (n )= (p−1 ) (q−1 )ϕ (3007 )=96∗30ϕ (3007 )=2880

La prueba para determinar si 2 números son coprimos es que su mcd sea 1:mcd (a ,ϕ (n ) )=1

a. 24mcd (24,2880 )=24

No cumple con la condición por lo tanto se descartab. 33

mcd (33,2880 )=3No cumple con la condición por lo tanto se descarta

c. 45mcd (45,2880 )=45

No cumple con la condición por lo tanto se descarta

d. 49mcd (49,2880 )=1

Cumple con la condición por lo tanto se acepta como clave pública

Ejercicio No. 2Usando números primos con dos dígitos, genere su clave pública y privada RSA. Describa todos los pasos.Primero debemos seleccionar los números primos de dos dígitos, así:

p=31q=89Ahora calculamos n y phi(n):

n=p∗q=31∗89n=2759

ϕ (n )= (p−1 ) (q−1 )ϕ (2759 )=30∗88ϕ (2759 )=2640

Ahora debemos determinar la clave pública, es decir, un número que cumpla con siguiente condición:

1<e<ϕ (n)e=1483

Verificamos que nuestra elección es válida:mcd (e ,ϕ (n ) )=mcd (1483,2640 )=1

Cumple con la condición por lo tanto es apta para ser clave pública.Ahora debemos calcular la clave privada:

d=e−1mod ϕ (n )d= (1483 )−1mod 2640

d=2227Ejercicio No.3Alice y Bob envían mensaje encriptados usando el criptosistema RSA, con los siguientes parámetros:

Alice : p A=223 ;q A=503 ,e A=41Bob : pB=211;qB=509 , eB=73

1. Calcule la clave privada de Alice y BobCalculando la clave privada de Alice

n=p∗q=223∗503n=112169

ϕ (n )= (p−1 ) (q−1 )ϕ (112169)=222∗502ϕ (112169 )=111444

Verificamos la clave pública dada:mcd (e ,ϕ (n ) )=mcd (41,111444 )=1

Cumple con la condición por lo tanto es apta para ser clave pública.Ahora debemos calcular la clave privada:

d=e−1mod ϕ (n )d= (41 )−1mod 111444

d=92417Calculando la clave privada de Bob

n=p∗q=211∗509n=107399

ϕ (n )= (p−1 ) (q−1 )ϕ (107399 )=210∗508ϕ (107399 )=106680

Verificamos la clave pública dada:mcd (e ,ϕ (n ) )=mcd (73,106680 )=1

Cumple con la condición por lo tanto es apta para ser clave pública.

Ahora debemos calcular la clave privada:d=e−1mod ϕ (n )

d= (73 )−1mod 106680d=39457

2. Encripte el mensaje m = 7815, que Bob quiere enviar a AliceComo el mensaje va ser enviado a Alice, debemos utilizar su clave pública para cifrar el mensaje, así:

C=m p A (mod n )C=781541 (mod 112169)

C=51005Ahora comprobaremos el mensaje enviado cuando Alice lo descifre con su clave privada:

m=Cd (mod n )m=5100592417 (mod112169 )

m=7815

Ejercicio No. 4Utilice la clave generada en el Ejercicio No. 2, para firmar digitalmente el mensaje m=7 y valide que el valor del resultado es un firma correcta

Clave públicae=1483

Clave privadad=2227

Módulon = 2759

Mensaje a cifrarm = 7

s=md(modn)s=72227mod 2759=2105Mensaje firmado a enviar

(m, s) = (7, 2105)

Ahora procedemos a validad la firma del mensaje, así:m=semod n

m=21051483mod 2759m=7

Con lo que comprobamos que la firma es completamente válida, ya que hemos obtenido le mensaje enviado.

Ejercicio No. 5

Usando los siguientes parámetros: Zp=Z29 , α=3, cree la llave pública y privada, para los usuarios A y B, y envíe el mensaje m = 15 a B encriptado usando el criptosistema ElGamal. Describa el proceso.Primero con los datos proporcionados calcular el valor de la llave pública y privada, así:Usuario ALlave Privada: Se debe seleccionar un valor aleatorio d de tal manera que cumpla con la condición d ℇ Z29−{0,1 , p−1}

d A=11

Llave Pública: Se calcula elevando el elemento primitivo α , a la llave publica seleccionada.α dmod p=311mod 29=15

e A=15

Usuario BLlave Privada: Se debe seleccionar un valor aleatorio d de tal manera que cumpla con la condición dℇ Z29−{0,1 , p−1 }

d B=25Llave Pública: Se calcula elevando el elemento primitivo α , a la llave publica seleccionada.

α dmod p=325mod 29=14eB=14

Ahora procedemos a encriptar el mensaje destinado para el usuario B, y para poder hacer debemos de seleccionar un valor aleatorio k ℇ Z29−{0,1 , p−1 }. Elegimos k = 7

m=15C=[αk ,m∙ (α d )k ]C=[37 ,15 ∙ (14 )7 ]C=[c1 , c2 ]=[12 ,6 ]

Para verificar vamos a descifrar el mensaje enviado a B, utilizando la llave privada de B, así:C=[12 ,6]m=c1

−d ∙ c2m=12−25 ∙6mod 29

m=15Vemos que coincide con el mensaje original.

Ejercicio No. 6

Alice y Bob utilizan el criptosistema ElGamal (trabajando en un campo finito Z131 , con el elemento primitivo α=37. La correspondiente clave privada de A y B son r A=122 y r B=18.Detalle el proceso de encriptación del mensaje m = 6, que Alice cifra para enviar a Bob (use el valor aleatorio k = 21).También detalle el proceso que debe seguir Bob para descifrar el mensaje.

Para encriptar el mensaje enviado por Alice a Bob, debemos hacerlo con la clave pública de Bob, la cual procederemos a calcular con los datos proporcionados:

α dmod p=3718mod 131=108

eB=108

Con esto Alice, puede ya encriptar el mensaje, así:

m=6C=[αk ,m∙ (α d )k ]C=[3721 ,6 ∙ (108 )21 ]C=[c1 , c2 ]=[95 ,93]

Para descifrar el mensaje enviado a Bob, utilizamos su llave privada r B=18, así:C=[95 ,81]m=c1

−r B ∙ c2m=95−18 ∙93mod 131

m=6Vemos que coincide con el mensaje original.

Ejercicio No. 7

Suponga el criptosistema ElGamal con los parámetros α=3 y Z29, con las siguientes llaves públicas:

USUARIO B 12USUARIO C 5

Usted es el usuario B y ha calculado su clave pública α 7=12mod 29Usted recibe un mensaje cifrado mensaje(α k , c )=(21 ,11), y también recibe la supuesta firma

digital de C para el mensaje, (α k , s )=(21 ,3)1. Encuentre el mensaje Original

Para descifrar el mensaje debemos utilizar la llave privada del Usuario B d B=7, así:C=[21 ,11]m=c1

−dB ∙ c2m=21−7 ∙11mod 29

m=13El mensaje original es m=13

2. Valide la firma(α k , s )=(21,3)α k=21

αm=313mod 29=19(α dc)a

k

∙ (ak )s=521 ∙213mod 29=19

La firma es válida ya que ambos valores coinciden.