NOTA SEGUNDA PARTE.

EJERCICIO 2 (3,0 puntos)

APELLIDOS Y NOMBRE: INICIAL

EJERCICIO 2. CADA UNO DE LOS SEIS APARTADOS VALE 0,5 PUNTOS

CONTESTA SOLAMENTE EN ESTE FOLIO Y EN SU ANVERSO
Clave RSA de Alicia: pA = 31, qA = 41, eA = 13.
Clave RSA de Bernardo: pB = 23, qB = 43, eB = 17.
ES OBLIGATORIO usar en este segundo ejercicio el Algoritmo Extendido de Euclides AEE para encontrar los
inversos y el Algoritmo de Exponenciación Rápida AER para las operaciones de exponenciación modular. La
resolución de los apartados 2.1 y 2.2 sin usar AEE y de los apartados 2.3 y 2.4 sin usar AER, significa
obtener 0 puntos aunque el resultado sea el correcto.
2.1. Con el AEE encuentra la clave privada dA de Alicia.
2.2. Con el AEE encuentra la clave privada dB de Bernardo.
2.3. Muestra la ecuación (con letras) a usar si Alicia desea enviar a Bernardo confidencialmente el
número secreto K = 10. Aplicando el AER, encuentra después resultado de esa cifra.
2.4. Alicia firmará ahora el valor 15 y se lo enviará a Bernardo, a quien le llega el criptograma F = 798
como firma digital de Alicia. Muestra la ecuación (con letras) a usar por Bernardo para comprobar la
firma de Alicia. Aplicando el AER, encuentra después el resultado de esa comprobación de firma por
parte de Bernardo.
2.5. La clave de Alicia muestra 10 claves privada parejas, todas separadas por una diferencia igual a 120.
La primera de ellas es 37 y la última es 1.237, a la que se suma la clave privada d. ¿Podría alguien
firmar por Alicia usando como clave el número 637 y por qué sí o no? ¿Podría alguien recuperar un
secreto cifrado para Alicia usando como clave el número 937 y por qué sí o no?
2.6. La clave de Alicia muestra 10 claves privadas parejas CPP y 35 números no cifrables NNC. Sin
embargo, la clave de Bernardo muestra el valor mínimo de ambos, es decir 1 CPP y 9 NNC. ¿Por qué
sucede esto?
RESPUESTA
2.1. La clave privada de Alicia será eA = inv (dA, nA) = inv (13, nA)
nA = (pA – 1)(qA – 1) = (31-1)( 41-1) = 30*40 = 1.200
i yi gi ui vi
0 - 1.200 1 0
1 - 13 0 1
2 92 4 1 -92
3 3 1 -3 277
4 4 0 13 -1.200
La clave privada de Alicia es dA = 277
2.2. La clave privada de Bernardo será eB = inv (dB, nB) = inv (17, nB)
nB = (pB – 1)(qB – 1) = (23-1)( 43-1) = 22*42 = 924

Examen Parcial SI - Curso 2019-2020. Evaluación Continua - Fecha: 9 de marzo de 2020 Página 4
 i yi gi ui vi
0 - 924 1 0
1 - 17 0 1
2 54 6 1 -54
3 2 5 -2 109
4 1 1 3 -163
5 5 0 -17 924
La clave privada de Bernardo es dB = -163 + 924 = 761
2.3. La cifra de Alicia a Bernardo para enviarle de forma confidencial el secreto K = 10
será: KeB mod nB
Como nB = pB x qB = 23 x 43 = 989 entonces KeB mod nB = 1017 mod 989, con 17 =
10001
17 = 10001 = b4b3b2b1b0 x = 1
i = 4 b4 = 1 x = 12 * 10 mod 989 = 10
i = 3 b3 = 0 x = 102 mod 989 = 100 mod 989 = 100
i = 2 b2 = 0 x = 1002 mod 989 = 10.000 mod 989 = 110
i = 1 b1 = 0 x = 1102 mod 989 = 12.100 mod 989 = 232
i = 0 b0 = 1 x = 2322 * 10 mod 989 = 538.240 mod 989 = 224
C = 224
2.4. La comprobación de la firma F de Alicia por parte de Bernardo será FeA mod nA
Como nA = pA x qA = 31 x 41 = 1.271 entonces FeA mod nA = 79813 mod 1.271, con 13 =
1101
12 = 1101 = b3b2b1b0 x=1
i = 3 b3 = 1 x = 12 * 798 mod 1.271 = 798
i = 2 b2 = 1 x = 7982 * 798 mod 1.271 = 508.169.592 mod 1.271 = 914
i = 1 b1 = 0 x = 9142 mod 1.271 = 835.396 mod 1.271 = 349
i = 0 b0 = 1 x = 3492 *798 mod 1.271 = 97.197.198 mod 1.271 = 15
Bernardo recupera y comprueba el número firmado por Alicia
2.5. Como las claves privadas parejas de Alicia comienzan por 37 y están separadas entre
ellas 120 espacios, dichas claves serán: 37, 157, 277 (la clave privada d), 397, 517, 637,
757, 877, 997, 1.117 y 1.273 la última. Por lo tanto, dado que 637 es una CPP sí se podrá
firmar digitalmente con ese número. Sin embargo, como 937 no se encuentra entre estas
CPP, no se podrá usar para descifrar algo enviado confidencialmente a Alicia.
2.6. Porque Bernardo usa el primo 23 que es un primo seguro (23 = 11x2 +1), en cambio
los primos de Alicia son 31 y 41, que no son primos seguros porque 31 = 15x2 +1 y 41 =
20x2 +1, y no son primos ni el 15 ni el 20. El uso de primos seguros minimiza la cantidad
de CPP y la cantidad de NNC en RSA, alcanzando 1 CPP y 9 NNC, los valores mínimos.

Examen Parcial SI - Curso 2019-2020. Evaluación Continua - Fecha: 9 de marzo de 2020 Página 5
 que tardaría unas 2 * 10282 veces más que la existencia del Universo).
Ejercicio 2. Cifrado con RSA (3 puntos)
En un sistema RSA, el usuario A genera sus claves utilizando: pA = 173; qA = 241 y eA
= 29.
a) Comprueba que el valor elegido para eA es adecuado. (0,5 puntos)
b) Utilizando el Algoritmo Extendido de Euclides (AEE) encuentra el valor de la
clave privada asociada (dA). (0,5 punto)
c) Construye una [pareja de] clave[s] para el usuario B, de 16 bits. Deberás indicar
qué valor(es) eliges, cómo se obtienen los derivados de ellos (0,5 puntos) y que
se cumplen las condiciones requeridas en la técnica RSA (0,5 puntos). En este
apartado no se requiere utilizar el AEE ni el AER.
d) El usuario A cifra el valor ‘123’ para el usuario B ¿Qué valor recibe este último?
Justifica los resultados. (0,5 puntos)
e) ¿Cómo procedería el Usuario B para descifrar el valor recibido por parte de A?
Justifica los resultados. En este apartado no se requiere utilizar el AEE ni el
AER. (0,5 puntos)
Solución
En un sistema RSA, el usuario A genera sus claves utilizando: pA = 173; qA = 241 y eA
= 29.
a) Comprueba que el valor elegido para eA es adecuado. (0,5 puntos)
• nA = pA * qA = 173 * 241 = 41693
• φA(n) = (pA – 1) * (qA – 1) = 172 * 240 = 41280
Se comprueba que mcd ((eA, φA(n)) = mcd (29, 41280) = 1
b) Utilizando el Algoritmo Extendido de Euclides (AEE) encuentra el valor de la
clave privada asociada (dA). (0,5 puntos)
i yi gi ui vi
Ent(gi-1/gi) gi-1 - yi+1∗ gi ui-1 - yi+1∗ ui vi-1 - yi+1∗ vi
0 - 41280 1 0
1 - 29 0 1
2 1423 13 1 -1423
3 2 3 -2 2847
4 4 1 8 -12811 mod 41280 = 28469
3 0
dA = 28469
c) Construye una [pareja de] clave[s] para el usuario B, de 16 bits. Deberás indicar
qué valor(es) eliges, cómo se obtienen los derivados de ellos (0,5 puntos) y que
se cumplen las condiciones requeridas en la técnica RSA (0,5 puntos). En este
apartado no se requiere utilizar el AEE ni el AER.
Elegimos
• pB = 163, qB = 277. Deben ser primos.
 • eB = 13. Debe cumplir que 1 < eB < φB(n) y mcd [eB, φB(n)] = 1. Se comprueba
posteriormente
Calculamos
• nB = pB * qB = 163 * 277 = 45151. Se comprueba que su tamaño es 16 bits
• φB(n) = (pB – 1) * (qB – 1) = 162 * 276 = 44712
 Se comprueba que eB cumple los requerimientos: 1 < eB < φB(n) y mcd [eB,
φB(n)] = 1
• dB = (inv(eB, φB(n)) = inv(13, 44712) = 17197. (Realizado con SAMCript)
[pareja de] clave[s] para el usuario B
• Clave pública: {13, 45151}
• Clave privada: {17197, 45151}
d) El usuario A cifra el valor ‘123’ para el usuario B ¿Qué valor recibe este último?
Justifica los resultados. (0,5 puntos)
El usuario A utiliza la clave pública del usuario B:
C = MeB mod nB = 12313 mod 45151 = 4479 (Con la calculadora de Windows)
e) ¿Cómo procedería el Usuario B para descifrar el valor recibido por parte de A?
Justifica los resultados. En este apartado no se requiere utilizar el AEE ni el
AER. (0,5 puntos)
El usuario B utiliza su clave privada.
C = MdB mod nB = 447917197 mod 45151 = 123 (Con SAMCript)
Ejercicio 3. Seguridad en integridad y autenticidad. [2 puntos]
Tomando en consideración el supuesto anterior y sabiendo que el usuario A va a enviar
al usuario B el mensaje de texto ‘123’
a) Describe (0,25 puntos) y explica (0,25 puntos) la estructura del (único) bloque
MD5 correspondiente a dicho mensaje. Solo la parte significativa, no hace
falta poner los 0’s de relleno.
 grandes como es este caso se vuelve intratable. Tampoco podrá hacer fuerza bruta en
búsqueda de los valores secretos a de Alicia y b de Bernardo porque ambos serán
números de 256 bits y, por tanto, existen 2256 números posibles, imposible de calcular
hoy en día.

e) Carlos le envía a ambos el mismo valor αc mod p = 36 mod 17 = 729 mod 17 = 15.

f) Alicia calcula 153 mod 17 = 3.375 mod 17 = 9 y Carlos calcula 106 mod 17 = 1.000.000
mod 17 = 9. Es decir, Alicia y Carlos intercambian el valor secreto αac mod p = 33*6 mod
17 = 387.420.489 mod 17 = 9.
Bernardo calcula 155 mod 17 = 759.375 mod 17 = 2 y Carlos calcula 56 mod 17 = 15.625
mod 17 = 2. Es decir, Bernardo y Carlos intercambian el valor secreto αbc mod p = 35*6
mod 17 = [Link].649 mod 17 = 2.
EJERCICIO 2
Clave RSA de Alicia: pA = 47, qA = 61, dA = 1.183. Clave RSA de Bernardo: pB = 43, qB = 53, eB = 5.
Aquí es obligatorio usar el Algoritmo Extendido de Euclides AEE y el Algoritmo de
Exponenciación Rápida AER.
a) [0,5 puntos] Encontrar la clave pública eA de Alicia.
b) [0.5 puntos] Ecuación y resultado si Alicia envía cifrado el número secreto N = 51 a
Bernardo.
c) [0.5 puntos] Ecuación y resultado si Bernardo comprueba que Alicia ha firmado
digitalmente el valor 123 porque ha recibido de ella la firma FA = 916.
d) [0.5 puntos] ¿Pueden enviarse Alicia a Bernardo y Bernardo a Alicia mediante sus
claves RSA el valor secreto 2.500? Justifica la respuesta.
e) [0.5 puntos] ¿Qué significa que la clave privada de Alicia tenga la clave privada pareja
d’ = 2.563?
f) [0.5 puntos] Se sabe que la clave de Alicia tiene 21 números no cifrables. ¿Qué significa
esto?. Si algunos de los NNC son los siguientes [0, 1, 47, 48, 563, 610, 611, 657, 658,
……, 2.256, 2.257, 2.304, 2.819, 2.820, 2.866]. ¿Podrías indicar dos NNC más?
RESPUESTA:
a) La clave pública de Alicia será e = inv (dA, φnA) = inv (1.183, φnA)
φnA = (pA – 1)(qA – 1) = (47-1)( 61-1) = 46*60 = 2.760
I yi gi ui vi
0 - 2.760 1 0
1 - 1.183 0 1
2 2 394 1 -2
3 3 1 -3 7
4 394 0 1.183 -2.760
La clave pública de Alicia es eA = 7.
b) Como nB = pBxqB = 43x53 = 2.279, el cifrado debe ser NeB mod nB = 515 mod 2.279
5 = 101 = b2b1b0 x=1
i = 2 b2 = 1 x = 12*51 mod 2.279 = 51
i = 1 b2 = 0 x = 512 mod 2.279 = 2.601 mod 2.279 = 322
i = 0 b2 = 1 x = 3222*51 mod 2.279 = 5.287.884 mod 2.279 = 604

Examen Parcial SI - Curso 2018-2019. Evaluación Continua - Fecha: 8 de abril de 2019 Página 3
 C = 604
c) Como nA = pA*qA = 47*61 = 2.867, Bernardo comprueba la firma de Alicia con la clave
pública de ella calculando: FAeA mod nA = 9167 mod 2.867
7 = 111 = b2b1b0 x=1
2
i = 2 b2 = 1 x = 1 *916 mod 2.867 = 916
i = 1 b2 = 1 x = 9162*916 mod 2.867 = 768.575.296 mod 2.867 = 1.404
i = 0 b2 = 1 x = 1.4042*916 mod 2.867 = [Link] mod 2.867 = 123
Valor firmado por Alicia = 123
d) Como el módulo de Alicia es nA = 2.867, Bernardo puede enviarle a Alicia el número
secreto 2.500 porque es un elemento de ese cuerpo de cifra. Sin embargo, Alicia no
puede enviarle el número 2.500 a Bernardo porque en este caso cuerpo de cifra de es
nB = 2.279 y si cifra el valor 2.500 en realidad le estaría enviando el valor 2.500 – 2.279
= 221.
e) Significa que cualquier número N cifrado con la clave pública de Alicia, además de
poderse descifrar con su clave privada, también podrá descifrarse con el número
2.563.
Fuera del examen: Si N = 10 y ciframos con la clave pública de Alicia que es 7 entonces
C = 107 mod 2.867 = 10.000.000mod 2.867 = 2.771. Para descifrar C podemos realizar
estas dos operaciones:
2.7711.183 mod 2.867 = 10 o bien 2.7712.563 mod 2.867 = 10.
f) Significa que si N es un NNC entonces dicho NeA mod nA = N. Dada las características de
los NNC que la suma de los extremos (excepto el 0) es igual al módiulo n, también
serán NNC el 2.209 y el 2.210, ya que se cumple 2.209 + 658 = 2.867 = n y 2.210 + 657
= 2.867 = n.

Examen Parcial SI - Curso 2018-2019. Evaluación Continua - Fecha: 8 de abril de 2019 Página 4
claves secretas de Amparo y Bartolo que entregan el mismo valor de clave pública. Es decir, para Amparo tendríamos
que αa1 mod 661 = αa2 mod 661 = αa3 mod 661, etc. = valor constante de clave pública.

EJERCICIO 2 (2,0 PUNTOS)

Andrés (A) y Carlos (C) enviarán a Benjamín (B) un número N secreto (distinto en cada caso) mediante un
intercambio de clave con el algoritmo RSA. Pero Eva interceptará esos dos criptogramas y realizará un ataque con el
único fin de encontrar, en cada caso, el secreto que le han transmitido a Benjamín, cuya clave pública es:
• Clave pública de Benjamín: n = 667, e = 3.
• Se sabe que Benjamín recibe de Andrés el criptograma C = 320 (que captura Eva)
• Se sabe que Benjamín recibe de Carlos el criptograma C = 231 (que captura Eva)
Se pide:
a. [0.4 puntos] ¿Qué ataque debe realizar Eva para encontrar el secreto de los criptogramas interceptados, sin
que ello lleve a la necesidad de descubrir antes la clave privada de Benjamín? Explica cómo lo hace.
b. [0.4 puntos] Termina el ataque que corresponde según la tabla entregada al criptograma C = 320, enviado
por Andrés a Benjamín. ¿En qué vuelta se encuentra el secreto?
1 3203 mod 667 = 291
2 2913 mod 667 = 523
3 5233 mod 667 = 175
4 1753 mod 667 = 30
5 …
c. [0.4 puntos] Realiza el mismo tipo de ataque al criptograma C = 231 enviado por Carlos a Benjamín. ¿En qué
vuelta se encuentra el secreto?
d. [0.4 puntos] Justifica por qué han sido diferentes el número de operaciones realizadas en casa caso. ¿Qué ha
sucedido con el secreto enviado por Carlos?
e. [0.4 puntos] Eva ha logrado factorizar el módulo de Benjamín (n = 667 = 29*23). Encuentra la clave privada d
de Benjamín usando obligatoriamente el Algoritmo Extendido de Euclides.
SOLUCIÓN:
Apartado a. Se trata de un ataque por cifrado cíclico, usando para ello solamente la clave pública de la víctima y el
criptograma interceptado. Realiza una cifra RSA del criptograma con la clave pública de Benjamín, y lo mismo a los
resultados que va obteniendo, hasta que se encuentra otra vez con el valor inicial del ataque. En ese momento sabe
que el número de la cifra anterior era el secreto que buscaba.
Apartado b. Datos conocidos C= 320,n = 667, e = 3.

5 303 mod 667 = 320

Como ha vuelto a encontrar C = 320 tras 5 vueltas o cifrados, el valor N = 30 anterior era el secreto.
Apartado c. Datos conocidos C= 231, n = 667, e = 3.

1 2313 mod 667 = 231

Como ha vuelto a encontrar C = 231 tras 1 vueltas o cifrado, el valor N = 231 anterior era el secreto.
Apartado d. En el primer caso, Eva ha tenido que realizar 5 operaciones. En el segundo caso, Eva ha tenido que
realizar una única operación. Esto se debe a que el primer criptograma C y su secreto asociado N de Andrés se
encontraba en un anillo de longitud 5, el segundo criptograma C y su secreto asociado N de Carlos se encontraba en
un anillo de longitud 1. El número secreto enviado por Carlos se trataba de un número no cifrable de la clave de
Benjamín.
Apartado e. Sí puede hacerlo. Se trata de un ataque basado en la factorización del módulo n.

Datos: e = 3; n = 667. Como ha logrado factorizar P = 23 y q = 29, por tanto φ(n) = 22 * 28 = 616. Estamos en
condiciones de calcular la clave privada de Benjamín

Asignatura SI - Curso 2018-2019 - Examen Convocatoria Extraordinaria - 2 de julio de 2019 Página 4

d = inv (3, 616) = 411
Y descifrar el criptograma recibido N = 320411 mod 667 = 30
Cálculo de d

i yi gi ui vi
0 -- 616 1 0
1 -- 3 0 1
2 205 1 1 -205
3 3 0 -3 616
Por tanto d = -205+616 = 411

EJERCICIO 3 (1,0 PUNTO)

Según la siguiente figura de un SGSI, pon en cada uno de los 14 recuadros con dominios, a qué área de aplicación
pertenece cada apartado: ORG, LOG, FIS y LEG.
Indica de mayor a menor cuántos son ORG, LOG, FIS y LEG

Política de seguridad ORG

Organización de la seguridad de la información ORG
Relaciones con proveedores ORG
Gestión de activos ORG
Control de accesos LOG
Cumplimiento LEG
Seguridad relativa a los recursos humanos ORG
Seguridad física y del entorno FIS
Aspectos de la seguridad de la información en la gestión de la continuidad del negocio ORG
Criptografía LOG
Adquisición, desarrollo y mantenimiento de sistemas de información LOG
Seguridad de las operaciones LOG
Seguridad de las comunicaciones LOG
Gestión de incidentes de seguridad de la información LOG

De los 14 dominios, 6 son ORG, 6 son LOG, 1 es LEG y 1 es FIS.

Asignatura SI - Curso 2018-2019 - Examen Convocatoria Extraordinaria - 2 de julio de 2019 Página 5

 c) [0,25]¿¿Cuántos bits relleno se observan? ¿Cómo comienza ese relleno? Marca en la figura todo el relleno.

2 bytes en la palabra 4 más 4 bytes en las palabras 5, 6, 7, 8, 9, 10, 11, 12, 13 y 14. Es decir: 16 + 10x32 = 336 bits.
El relleno comienza por el byte 1000 0000, el valor 80 en hexadecimal que se observa en la palabra 4.

d) [0,25]¿¿Qué tamaño tiene el archivo en bits? Marca en la figura dónde lo indica y cuántos bits reserva para
ello.

El archivo tiene un tamaño de 14 bytes = 14x8 = 112 bits, que en hexadecimal es igual al valor 70 que se muestra
en la palabra 15. MD5 reserva las dos últimas palabras del hash indicar para el relleno, es decir 64 bits.

PREGUNTA ABIERTA 2 (CONTESTA EN ESTE FOLIO, 1 punto)

Sin resolver las ecuaciones, pero sí indicándolas con sus números, muestra cómo se desarrolla un Man In The Middle
en un intercambio de clave de Diffie y Hellman con p = 197, α = 2. Los datos privados de los participantes son Alicia a
= 5, Bernardo b = 7, Atacante Carlos c = 10. El valor que Alicia le envía a Bernardo es C1, el que Bernardo le envía a
Alicia es C2 y el valor que usa el atacante Carlos para el MITM es C3.

Alicia calcula 25 mod 197 = C1 y se lo desea enviar a Bernardo pero lo intercepta Carlos
Carlos calcula 210 mod 197 = C3 y se lo envía a Bernardo.
Bernardo calcula 27 mod 197 = C2 y se lo desea enviar a Alicia pero lo intercepta Carlos
Carlos calcula 210 mod 197 = C3 y se lo envía a Alicia.
Alicia calcula C35 mod 197 y obtiene la clave con la que conversa con Carlos
Carlos calcula C110 mod 197 y obtiene la clave con la que conversa con Alicia
Bernardo calcula C37 mod 197 y obtiene la clave con la que conversa con Carlos
Carlos calcula C210 mod 197 y obtiene la clave con la que conversa con Bernardo
Ha prosperado el ataque Man In The Middle

TERCERA PARTE CON 2 EJERCICIOS (5 puntos)

Ejercicio 1 (CONTESTA EN ESTE FOLIO, 2 puntos)

En un sistema de cifra RSA, Alicia tierne como datos públicos nA = 209 y eA = 7. Se pide:

a) [1,00]¿Encontrar la clave privada dA. Obligatorio usar Algoritmo Extendido de Euclides.

b) [1,00]¿Bernardo con clave nB = 377, eB = 5 y dB = 269, desea enviar a Alicia confidencialmente la clave K = 85.
Cifra ese valor y encuentra el criptograma. Obligatorio usar Algoritmo de Exponenciación Rápida.

Examen Parcial asignatura Seguridad de la Información curso 2017/2018 3

Si nA = 209, entonces es fácil encontrar que p = 11 y q = 19. Por lo tanto, (n) = (11-1)(19-1) = 10x18 = 180.

a) dA = inv (eA, (n)) = inv (7, 180)

i yi gi ui vi

0 - 180 1 0

1 - 7 0 1

2 25 5 1 -25

3 1 2 -1 26

4 2 1 3 -77

5 2 0 -7 180

dA = -77 + 180 = 103

b) C = 857 mod 209
Como e = 7 = 111 = b2b1b0
x=1
b2 = 1 x = 12*85 mod 209 = 85
b1 = 1 x = 852*85 mod 209 = 83
b0 = 1 x = 832*85 mod 209 = 156
El secreto 85 se cifra como 156

Ejercicio 2 (CONTESTA EN ESTE FOLIO, 3 puntos)

Mortadelo y Filemón deben descifrar la hora aproximada en la que se ha producido un crimen. El formato es HH,
entre las 00 y las 23 horas, sin minutos. Un compañero de la TIA les ha dejado como criptograma el número 65
resultado de estas operaciones de cifra:

a) Primero se cifra esa hora con la clave de Mortadelo (nM = 77, eM = 13, dM = 37)

b) Segundo se firma ese resultado con la clave de la TIA (nT = 119, eT = 5, dT= 77)

Se pide:

a) [1,50]¿Encontrar la hora del suceso. Es obligatorio usar el Algoritmo de Exponenciación Rápida. Ayuda,
valores en binario: 5 = 101, 13 = 1101, 37 = 100101, 77 = 1001101 (2 puntos)

b) [1,50]¿¿Qué debe tenerse en cuenta al hacer esta operación doble (cifra y firma o firma y cifra) para que
todo salga bien? Justifica tu respuesta. (1 punto)

Examen Parcial asignatura Seguridad de la Información curso 2017/2018 4

 TERCERA PARTE. 2 EJERCICIOS (5,0 puntos en total)

EJERCICIO 1 (2,5 puntos)

Para la generación de una clave RSA contamos con estos datos: p = 23, q = 59, e = 3. Se pide:
1. Encontrar la clave privada d, usando obligatoriamente el Algoritmo Extendido de Euclides AEE.
2. Firmar con esta clave RSA el número 33, usando obligatoriamente el Algoritmo de Exponenciación Rápida AER y
terminando las operaciones del AER que se indican.
b9 = 1 x = 12 *33 mod 1.357 = 33
b8 = 1 x = 332 *33 mod 1.357 = 655
b7 = 0 x = 6552 mod 1.357 = 213
b6 = 1 x = 2132 *33 mod 1.357 = 406
b5 = 0 x = 4062 mod 1.357 = 639
b4 = 1 x = 6392 *33 mod 1.357 = 940
…
(Nota: todas las operaciones pueden hacerse con una calculadora básica).
3. Comprobar que la firma es correcta, usando obligatoriamente el Algoritmo de Exponenciación Rápida AER.
4. ¿Podríamos esperar una única clave privada pareja y nueve números no cifrables? ¿Por qué sí o por qué no?
5. Si con esa clave queremos cifrar un texto en ASCII, ¿qué tamaño de bloque de texto en claro en bytes elegiríamos
y por qué?
Ayuda: 850 en binario es 1101010010 y 1.357 = 10101001101.
SOLUCIÓN:
1. Tenemos que n = pxq = 23x59 = 1.357 y φ(n) = (p-1)(q-1) = 22x58 = 1.276. Por lo tanto:
d = inv (e, (φ(n)) = inv (3, 1.276)
i yi gi ui vi
0 - 1.276 1 0
1 - 3 0 1
2 425 1 1 -425
3 3 0 -3 1.276
d = -425 + 1.276 = 851
Se comprueba que son inversos porque 851*3 mod 1.276 = 2.553 mod 1.276 = 1
2. Firma: NUMd mod n. Conocido el valor binario de 850, es obvio que 851 = 1101010011 = b9b8b7b6b5b4b3b2b1b0
x=1
b9 = 1 x = 12 *33 mod 1.357 = 33
b8 = 1 x = 332 *33 mod 1.357 = 655
b7 = 0 x = 6552 mod 1.357 = 213
b6 = 1 x = 2132 *33 mod 1.357 = 406
b5 = 0 x = 4062 mod 1.357 = 639
b4 = 1 x = 6392 *33 mod 1.357 = 940
** Hasta aquí entregado en el examen **
b3 = 0 x = 9402 mod 1.357 = 193
b2 = 0 x = 1932 mod 1.357 = 610
b1 = 1 x = 6102 *33 mod 1.357 = 1.164
b0 = 1 x = 1.1642 *33 mod 1.357 = 1.132
33851 mod 1.357 = 1.132
3. Comprobación firma: NUMe mod n. Como e = 3 = 11 en binario, entonces 1.1323 mod 1.357 será:
x=1
b1 = 1 x = 12 *1.132 mod 1.357 = 1.132

Asignatura SI - Curso 2017-2018 - Examen Convocatoria Extraordinaria - 13 de julio de 2018 Página 5

 b0 = 1 x = 1.1322 *1.132 mod 1.357 = 33
4. Los primos p y q son primos seguros porque 23 = 11x2 + 1 (con 11 primo) y 59 = 29x2 + 1 (con 29 primo). Como la
clave e es la menor posible que cumple con mcd (e, (φ(n)) = 1, entonces obtendremos una clave RSA óptima con
una única clave privada pareja y nueve números no cifrables.
Comprobación (Nota: esto no se pide ni puntúa):
La cantidad de números no cifrables será:
σn= [1 + mcd (e-1, p-1)] [1 + mcd (e-1, q-1)]
Como e = 3, p = 23, q = 59
σn= [1 + mcd (3-1, 23-1)] [1 + mcd (3-1, 59-1)]
σn= [1 + mcd (2, 22)] [1 + mcd (2, 58)]
σn= [1 + 2] [1 + 3)] = 3x3 = 9
Y las claves privadas parejas son:
λ = (n - dγ)/γ
γ = mcm [(p-1), (q-1)] = mcm [(23 - 1), (59 - 1)] = mcm [22, 58] = 638
dγ = inv (e, γ) = inv (3, 638) = 213
i yi gi ui vi
0 - 638 1 0
1 - 3 0 1
2 212 2 1 -212
3 1 1 -1 213
4 2 0 3 -638
Entonces:
λ = (n - dγ)/γ = (1.357 - 213)/638
Como (1.357 - 213)/638) = 1,79, entonces λ = 1,79 = 1
De hecho las claves son:
di = dγ + i γ, con i = 0, 1
d1 = dγ = 213 (CPP)
d1 = dγ + γ = 213 + 638 = 851 (clave privada)
5. Como el módulo 1.357 = 10101001101 (11 bits) y cada carácter ASCII tendrá 8 bits, podemos sólo formar bloques
de 8 bits (un carácter) por lo que se cifrará en bloques de un byte, es decir cifra carácter a carácter.

EJERCICIO 2 (2,5 puntos)

Generamos una clave RSA de 10 bits con p = 23, q = 31 y e = 7. Observamos que tiene más de 9 números no cifrables
NNC. Si las ecuaciones para encontrar esos números son las que se indican más abajo, se pide:
1. Encontrar el mcd (e-1, p-1), el mcd (e-1, q-1) y hecho esto la cantidad de números no cifrables σn.
2. Encontrar los resultados de inv (q, p) y de inv (p, q). Aquí NO es obligatorio usar el AEE.
3. Encuentra los valores que faltan en la búsqueda del resultado Ne mod q = N. Aquí NO es obligatorio usar el AER.
4. Al aplicar la ecuación de NNC, se obtiene la siguiente cadena de números antes de reducir al módulo n:
{0, 621, 3105, 3726, 15525, 16146, 18630, 93, 714, 3198, 3819, 15618, 16239, 18723, 2046, 2667, 5151, 5772,
17571, 18192, 20676} mod 713
Reduciendo módulo 713 y sin ordenar aún la cadena de menor a mayor, se obtiene:
{x1, 621, 253, 161, 552, 460, 92, 93, x2, 346, 254, 645, 553, 185, 620, 528, 160, 68, 459, 367, x3}
¿Qué números deben ser x1, x2 y x3?
5. ¿Qué cosa no deseable podría suceder con los NNC si aceptamos que se introduzca como clave pública cualquier
número e válido, por ejemplo e = 331 = [(22x30)/2] + 1?
Datos:

Asignatura SI - Curso 2017-2018 - Examen Convocatoria Extraordinaria - 13 de julio de 2018 Página 6

σn= [1 + mcd (e-1, p-1)] [1 + mcd (e-1, q-1)] (Cantidad de números no cifrables)
NNC = [q{inv (q, p)}Np + p{inv (p, q)}Nq] mod n (Listado de los números no cifrables)
Np: Buscar si Ne mod p = N (con 1 ≤ N ≤ p-1)
Cálculos para N7 mod 23 = N para N = {0, 1, 22} (Completo)
Nq: Buscar si N7 mod q = N (con 1 ≤ N ≤ q-1)
Cálculos iniciales: N7 mod 31 = N para N = 0, 1, 5, 6, … (Cálculos hechos hasta N = 24)
SOLUCIÓN:
1. mcd (e-1, p-1) = mcd (6, 22) = 2
mcd (e-1, q-1) = mcd (6, 30) = 6
σn = [1 + mcd (e-1, p-1)] [1 + mcd (e-1, q-1)] = [1 + 2] [1 + 6] = 3 x 7 = 21
2. inv (q, p) = inv (31, 23) = inv (8, 23) = 3 (es obvio porque 3x8 = 24)
inv (p, q) = inv (23, 31) = 27
Aplicando el AEE: inv (23, 31) [no es obligatorio aquí el AEE]
i yi gi ui vi
0 - 31 1 0
1 - 23 0 1
2 1 8 1 -1
3 2 7 -2 3
4 1 1 3 -4
5 7 0 -23 31
-4 + 31 = 27
3. Faltan los cálculos en q = 31 para N = 25, 26, 27, 28, 29 y 30
N = 25 257 mod 31 = 25 N = 26 267 mod 31 = 26 N = 27 277 mod 31 = 15
N = 28 287 mod 31 = 14 N = 29 297 mod 31 = 27 N = 30 307 mod 31 = 30
Este último valor no es necesario calcularlo porque sabemos que (n-1)e mod n = n.
Por lo tanto, para q se tienen estos seis números {0, 1, 5, 6, 25, 26, 30}
4. NNC = [q{inv (q, p)}Np + p{inv (p, q)}Nq] mod 713
Las siguientes operaciones no se piden en el examen.
[31{3}(0, 1, 22) + 23{27}(0, 1, 5, 6, 25, 26, 30)]
{31x3x0, 31x3x1, 31x3x22} + {23x27x0, 23x27x1, 23x27x5, 23x27x6, 23x27x25, 23x27x26, 23x27x30 }
{0, 93, 2046} + {0, 621, 3105, 3726, 15525, 16146, 18630}
{0, 621, 3105, 3726, 15525, 16146, 18630, 93, 714, 3198, 3819, 15618, 16239, 18723, 2046, 2667, 5151, 5772,
17571, 18192, 20676} mod 713
{0, 621, 253, 161, 552, 460, 92, 93, 1, 346, 254, 645, 553, 185, 620, 528, 160, 68, 459, 367, 712}
En el enunciado se entrega esto:
{x1, 621, 253, 161, 552, 460, 92, 93, x2, 346, 254, 645, 553, 185, 620, 528, 160, 68, 459, 367, x3}
Obviamente x1, x2 y x3 son los tres valores que se sabe son no cifrables: el 0, el 1 y el n-1.
Ordenando de menor a mayor(no se pide esto):
NNC = {0, 1, 68, 92, 93, 160, 161, 185, 253, 254, 346, 367, 459, 460, 528, 552, 553, 620, 621, 645, 712}
5. Si no prestamos atención al valor de clave pública e que se elija, podriamos llegar a tener todo el cuerpo n no
cifrable. Esto se da cuando e = φ(n)/2 + 1 es un valor válido de clave pública en φ(n). Por ejemplo, en este ejercicio
se da este caso de NNC = n si e = φ(n)/2 + 1 = [(p-1)(q-1)/2]+1 = [(22x30)/2] + 1 = 331, el valor dado como clave
pública en el enunciado.
Comprobación (nota: esto no se pide ni puntúa):
σn= [1 + mcd (e-1, p-1)] [1 + mcd (e-1, q-1)]
σn= [1 + mcd (331-1, 23-1)] [1 + mcd (331-1, 31-1)]
σn= [1 + mcd (330, 22)] [1 + mcd (330, 30)]
σn= [1 + 22] [1 + 30] = 23 x 31 = 713 (el valor de n)

Asignatura SI - Curso 2017-2018 - Examen Convocatoria Extraordinaria - 13 de julio de 2018 Página 7

 CALIFICACION –
PROBLEMAS
Seguridad de la Información
Curso 2016 – 17. Primer Parcial
24 de Abril. (1 h. 45 min)
(Publicación Notas 5/05/17) (Revisión 8/05/17. 13 h. y 15 h. D 1129)
P1 P2
APELLIDOS Y NOMBRE ____________________________________
___________________________________________________________

Problema 2 [2.5 Ptos] RSA

Una versión apócrifa1 de Juego de Tronos, la familia Stark utiliza el sistema de cifrado simétrico para cifrar los mensajes
que se envían por medio de los cuervos negros y que afectan a Invernalia. En esta ocasión Arya envía a Bran una clave
secreta de cifrado simétrico K = 53 firmada y cifrada utilizando RSA.
1
Apócrifa: obra escrita que no es auténtica o no es obra de la persona a la que se atribuye

Se conocen los siguientes datos públicos del sistema RSA:

Nombre p Nombre q Nombre eNombre

Arya 7 11 17
Bran 17 23 15

a) (0,5 puntos) Realiza todas las operaciones necesarias para calcular la clave privada de Arya y de Bran.
b) (0,5 puntos) Utilizando el Algoritmo de Exponenciación Rápida, realiza los cálculos que ha tenido que realizar Arya para
enviarle a Bran la clave secreta K firmada y cifrada.
c) (0,5 puntos) Utilizando el Algoritmo de Exponenciación Rápida, realiza las operaciones que tiene que realizar Bran para
poder recuperar la clave K enviada por Arya y comprobar que es su firma.
d) (0,5 puntos) ¿Daría lo mismo el orden de las operaciones de firma y cifrado para recuperar esta clave K? Realiza las
operaciones oportunas y justifica tu respuesta.
e) (0,5 puntos) ¿Podría darse el caso de existir alguna clave no recuperable al alterar el orden de las operaciones? Justifica
tu respuesta.
NOTA 1: Es obligatorio utilizar el Algoritmo Extendido de Euclides para el cálculo de los inversos en cuerpo.
NOTA 2: Utilizar la tabla de conversión de decimal a binario adjunta cuando se estime necesario.

4
 CALIFICACION –
PROBLEMAS
Seguridad de la Información
Curso 2016 – 17. Primer Parcial
24 de Abril. (1 h. 45 min)
(Publicación Notas 5/05/17) (Revisión 8/05/17. 13 h. y 15 h. D 1129)
P1 P2
APELLIDOS Y NOMBRE ____________________________________
___________________________________________________________

a) Solución:

Nombre p Nombre q Nombre eNombre n Nombre= p*q Ф(n) = (p-1)(q-1) dNombre= inv(eNombre, Ф(n))
Arya 7 11 17 77 60 53
Bran 17 23 15 391 352 47

Cálculos Arya:

n=7 *11 = 77; Ф(n) = 6*10 =60; d= inv(17, 60) =53

Operaciones inv (A,B): partiendo de (g0, g1, u0, u1, v0, v1, i) = (B, A, 1, 0, 0, 1, 1), las operaciones a realizar son:

i yi gi ui vi

0 - 60 1 0

1 - 17 0 1

2 3 9 1 -3

3 1 8 -1 4

4 1 1 2 -7

5 8 0 -17 60

Mientras gi <> 0
Hacer yi+1 = parte entera (gi-1/gi)
Hacer gi+1 = gi-1 – yi + 1* gi
Hacer ui+1 = ui-1 – yi + 1* ui
Hacer vi+1 = vi-1 – yi + 1* vi
Hacer i = i+1
Si (vi-1 < 0)
Hacer vi-1 = vi-1 + B
Hacer x = vi-1
El resultado es negativo (-7) por lo que se le suma el módulo. inv (17,60) = -7 + 60 = 53

Cálculos Bran:

n=17 *23 = 391; Ф(n) = 16*22 =352; d= inv(15, 352) = 47

Operaciones inv (A,B): partiendo de (g0, g1, u0, u1, v0, v1, i) = (B, A, 1, 0, 0, 1, 1), las operaciones a realizar son:

5
 i yi gi ui vi

0 - 352 1 0

1 - 15 0 1

2 23 7 1 -23

3 2 1 -2 47

4 7 0 15 -352

Con las mismas operaciones: inv (15,352) = 47

b) Solución:

Arya:
1. Firma el mensaje K= 53 con su clave privada y su módulo K Firmado = 53 53 mod 77 = 58
5310 = 001101012
x=1
i=5 b5= 1 x = 12 53 mod 77 = 53 x = 53
i=4 b4= 1 x = 532 *53 mod 77 = 36 x = 36
i=3 b3= 0 x = 362 mod 77 = 64 x =64
i=2 b2= 1 x = 642 53 mod 77 = 25 x = 25
i=1 b1= 0 x = 252 mod 77 = 9 x = 9
i=0 b0= 1 x = 92 53 mod 77 = 58 x = 58

2. Cifra el mensaje cifrado (58), con la clave pública y módulo de Bran

Kfirmada y cifrada para Bran= 5815 mod 391= 243

1510 = 11112
x=1
i=3 b3= 1 x = 12 *58 mod 391 = 58 x =58
i=2 b2= 1 x = 582 58 mod 391 = 3 x = 3
i=1 b1= 1 x = 32 *58 mod 391 = 131 x = 131
i=0 b0= 1 x = 1312 58 mod 391 = 243 x = 243

Arya envía a Bran 243

c) Solución:

Bran:

1. Descifra el mensaje recibido 243 con su clave privada y su módulo

M1 = 243 47 mod 391 = 58

4710 = 1011112
x=1
i=5 b5= 1 x = 12 243 mod 391 = 243 x = 243
i=4 b4= 0 x = 2432 mod 391 = 8 x=8
i=3 b3= 1 x = 82 * 243 mod 391 = 303 x =303
i=2 b2= 1 x = 3032 243 mod 391 = 300 x = 300
i=1 b1= 1 x = 3002 * 243 mod 391 = 197 x = 197
i=0 b0= 1 x = 1972 243 mod 391 = 58 x = 58

2. Comprueba la firma de Arya con la clave pública y módulo de Arya recuperando así el mensaje con la clave secreta K.
M2= 5817 mod 77 = 53

6
 1710 = 100012
x=1
i=4 b3= 1 x = 12 *58 mod 77 = 58 x =58
i=3 b3= 0 x = 582 mod 77 = 53 x =53
i=2 b2= 0 x = 532 mod 77 = 37 x = 37
i=1 b1= 0 x = 372 mod 77 = 60 x = 60
i=0 b0= 1 x = 602 58 mod 77 = 53 x = 53

d) Solución:

Arya:
1. Cifra el mensaje K= 53 para Bran con la clave pública y módulo de Bran
K cifrada para Bran= 5315 mod 391= 60

1510 = 11112
x=1
i=3 b3= 1 x = 12 *53 mod 391 = 53 x =53
i=2 b2= 1 x = 532 53 mod 391 = 3 x = 297
i=1 b1= 1 x = 2972 *53 mod 391 = 281 x = 281
i=0 b0= 1 x = 2812 53 mod 391 = 60 x = 60

2. Firma el mensaje cifrado con su clave privada y su módulo

K Cifrado y Firmado = 60 53 mod 77 = 37

5310 = 001101012
x=1
i=5 b5= 1 x = 12 60 mod 77 = 60 x = 60
i=4 b4= 1 x = 602 *60 mod 77 = 15 x = 15
i=3 b3= 0 x = 152 mod 77 = 71 x =71
i=2 b2= 1 x = 712 60 mod 77 = 4 x = 4
i=1 b1= 0 x = 42 mod 77 = 16 x = 16
i=0 b0= 1 x = 162 60 mod 77 = 37 x = 37

Envía a Bran 37

Bran:
1. Comprueba la firma de Arya con la clave pública y módulo de Arya recuperando así el mensaje con la clave
secreta K cifrada.
M1= 3717 mod 77= 60

1710 = 100012
x=1
i=4 b3= 1 x = 12 *37 mod 77 = 37 x =37
i=3 b3= 0 x = 372 mod 77 = 60 x =60
i=2 b2= 0 x = 602 mod 77 = 58 x = 58
i=1 b1= 0 x = 582 mod 77 = 53 x = 53
i=0 b0= 1 x = 532 37 mod 77 = 60 x = 60

2. Descifra 60 con su clave privada y su módulo para encontrar la clave

K = 60 47 mod 391 = 53

4710 = 1011112
x=1
i=5 b5= 1 x = 12 60 mod 391 = 60 x = 60
i=4 b4= 0 x = 602 mod 391 = 81 x = 81
i=3 b3= 1 x = 812 * 60 mod 391 = 314 x =314
i=2 b2= 1 x = 3142 60 mod 391 = 321 x = 321
i=1 b1= 1 x = 3212 * 60 mod 391 = 359 x = 359
i=0 b0= 1 x = 3592 60 mod 391 = 53 x = 53

En este caso la clave K=53 se recupera sin problemas utilizando cualquier orden Cifra y firma o Firma y Cifra.

7
e) Solución:

SI, podría ocurrir que una de las operaciones para comprobar la firma o descifrado la base de la potencia (el número que se
vaya a elevar a una u otra clave) no esté dentro del cuerpo de cifra. En este caso, podría ocurrir que el orden alterase el resultado
recuperado.

8
 P1 P2
Seguridad de la Información
Curso 2016 – 17. CONVOCATORIA EXTRAORDINARIA
14 de Julio. 12:00 h (Duración 2 h. 45 min)
(Publicación Notas 18/07/17) (Revisión 19/07/17. A las 12 h. Laboratorio 1101)
PRACTICA
APELLIDOS
Y NOMBRE:

PROBLEMA 1. [1.0 punto] (contesta en esta misma hoja)

Se dispone del hash MD5 para un texto M de 134 bytes. Ambos se indican a continuación.

M = Una función hash toma cada carácter de texto y lo convierte en numérico, los agrupa de 3 en 3 y realiza las
operaciones (1º - 2º) * 3º

MD5 (M) = CE6FA7A370C71CB29F258CB8DD8DA77D

a) ¿Sobre cuántos bloques debe operar MD5 para obtener el hash de M? Justifica tu respuesta. (0,2 pts)
b) Describe y representa la estructura y la distribución de los bits generados en cada bloque. (0,5 pts)
c) Si al texto anterior le añadimos 50 caracteres, el mensaje M’ y su hash son los que se muestran más abajo. ¿Qué
sucederá ahora con la estructura y la distribución de los bits generados en cada bloque? (0,3 pts)

M’ = Una función hash toma cada carácter de texto y lo convierte en numérico, los agrupa de 3 en 3 y realiza las
operaciones (1º - 2º) * 3º. Los resultados son acumulados en un número final

MD5 (M’) = 227D106DB289D9CF12FD86A658DDF354

SOLUCIÓN

a) M tiene 134 caracteres => 134 x 8 = 1.072 bits. Como 1.072/512 = 2,09375, se procesarán 3 bloques.

b) MD5 procesa bloques de 512 bit y reserva los últimos 64 bits para indicar el tamaño del archivo.
El primer y el segundo bloque tendrán 512 bits correspondientes al texto.
El tercer bloque tendrá 1.072 - 1.024 = 48 bits correspondientes al texto y los 64 últimos bits para el tamaño del
texto, En medio habrá 512 – (48 + 64) = 400 bits de relleno constituido por un 1 seguido de 399 ceros.

c) Al añadir 50 bytes, el mensaje queda en 134 + 50 = 184 bytes, que significa 1.472 bits. Si a esta cantidad le
sumamos los 64 bits de relleno el resultado es 1.536 bits, que es justo 512x3. Pero como el hash siempre deberá
llevar al menos un byte de relleno, ahora serán 4 bloques a procesar y el último bloque serán todos rellenos (512 –
64 = 448 bits) y los últimos 64 bits indicarán el tamaño del archivo.

P1 P2
Seguridad de la Información
Curso 2016 – 17. CONVOCATORIA EXTRAORDINARIA
14 de Julio. 12:00 h (Duración 2 h. 45 min)
(Publicación Notas 18/07/17) (Revisión 19/07/17. A las 12 h. Laboratorio 1101)
PRACTICA
APELLIDOS
Y NOMBRE:

PROBLEMA 2. [1.0 punto] (contesta en esta misma hoja)

Sabiendo los siguientes datos:

γ = mcm [(p-1), (q-1)] dγ = e-1 mod γ = inv (e, γ) di = dγ + i γ con 1 < di < n i = 0, 1,... λ λ = (n - dγ)/γ

σn = [1 + mcd (e-1, p-1)]*[1 + mcd (e-1, q-1)] Ne mod p = N con 1 < N < p-1 y Ne mod q = N con 1 < N < q-1

SOLUCION Examen extraordinario Seguridad de la Información, julio de 2017 3

Alicia tiene una clave RSA con los siguientes datos: p = 11, q = 17, e = 7.
Bernardo tiene una clave RSA con los siguientes datos: p = 5, q = 23, e = 7.
Se pide lo siguiente.
a) Utilizando el Algoritmo Extendido de Euclides encuentra la clave privada de Bernardo (0,2 pts)
b) Utilizando el Algoritmo de Exponenciación Rápida, realiza las operaciones de cifra que Bernardo
tendría que realizar para enviar a Alicia el valor secreto M = 100, cifrado. (0,2 pts)
c) ¿Puede Bernardo enviarle a Alicia el secreto 250? ¿Por qué sí o no? (0,2 pts)
d) Encuentra cuántas claves privadas parejas tiene la clave de Bernardo. [mcm (4, 22) = 44] (0,15 pts)
e) Encuentra los valores de todas las claves privadas parejas de Bernardo. (0,1 pts)
f) ¿Cuántas operaciones en p y en q habrá que realizar para encontrar todos los números no cifrables de
Bernardo? ¿Y cuántas operaciones serían si p y q tuviesen 1.024 bits cada uno? (0,15 pts)

SOLUCIÓN
a) Tenemos n = p*q = 115 y que φ(n) = (p-1)(q-1) = 4*22 = 88. Buscaremos el inv (7, 88)
i yi gi ui vi
0 - 88 1 0
1 - 7 0 1
2 12 4 1 -12
3 1 3 -1 13
4 1 1 2 -25
5 3 0 -7 88
La clave privada de Bernardo es inv (7, 88) = -25+88 = 63

b) Como nA = pA x qA = 11 x 17 = 187, Bernardo cifrará el secreto con la clave pública de Alicia

mediante la operación 1007 mod 187.
Como e = 7 = 111 = b2b1b0
x=1
b2 = 1 x = 12*100 mod 187 = 100
b1 = 1 x = 1002*100 mod 187 = 111
b0 = 1 x = 1112*100 mod 187 = 144
El secreto 100 se cifra como 144

c) Bernardo no puede enviar el secreto 250 a Alicia porque el cuerpo de cifra de ésta es 187 y 250 queda
fuera del cuerpo. En realidad le estaría enviado otro secreto, el número 250 – 187 = 63.

d) El número de claves privadas parejas de la clave de Bernardo es λ = (n - dγ)/γ = 2

Porque n = p*q = 5*23 = 115
γ = mcm [(p-1), (q-1)] = mcm (4, 22) = 44
dγ = inv (e, γ) = inv (7, 44) = 19

i yi gi ui vi
0 - 44 1 0
1 - 7 0 1
2 6 2 1 -6
3 3 1 -3 19
4 2 0 7 -44

Entonces λ = (n - dγ)/γ = (115 - 19)/44 = 2,18 = 2.

e) di = dγ + i γ con i = 0, 1, 2
d0 = 19 + 0*44 = 19; d1 = 19 + 1*44 = 63; d2 = 19 + 2*44 = 107
Como 63 es la clave privada, las claves privadas parejas CPP son 19 y 107.

f) Como p = 5 (3 bits) y q = 23 (5 bits), entonces realizaremos en Ne mod 5 un total de 23 - 3 = 8 – 3 = 5

operaciones en p y en Ne mod 23 un total de 25 - 3 = 32 – 3 = 29 operaciones en q. Se les quita 3

SOLUCION Examen extraordinario Seguridad de la Información, julio de 2017 4

 operaciones porque es obvio que se cifran en claro 0, 1 y p-1 en el primer caso y 0, 1 y q-1 en el
segundo caso. Si p y q tuviesen ahora 1.204 bits cada uno, habría que realizar 21.024 operaciones en p y
otras 21.024 operaciones en q. Por el tamaño de la clave, aquí podríamos despreciar esos 6 cálculos de
números obvios en claro para p y q.

Seguridad de la Información PRACTICA

Curso 2016 – 17. CONVOCATORIA EXTRAORDINARIA
14 de Julio. 12:00 h (Duración 2 h. 45 min)
(Publicación Notas 18/07/17) (Revisión 19/07/17. A las 12 h. Laboratorio 1101)
P1 P2 P3
APELLIDOS
Y NOMBRE:

PREGUNTA 1 [0.4 puntos] (contesta en esta misma hoja)

Dadas las claves
• Clave1: p = 967; q = 991; e = 13 (n = 958.297, clave de 20 bits)
• Clave2: p = 3.491; q = 2.927; e = 3 (n = 10.218.157, clave de 24 bits)
• Clave3: p = 12.343; q = 13.679; e = 5 (n = 168.839.897, clave de 28 bits)
Y el informe de los anillos de dichas claves, generado con RingRSA y que se muestra en la Figura 1

Clave1 de 20 bits Clave 2 de 24 bits Clave 3 de 28 bits

Longitud Nº Prob. Longitud Nº Prob. Longitud Nº Prob.

660 672 46,28% 5.220 1.344 68,66% 161.040 816 77,83%
330 336 11,57% 2.610 672 17,16% 53.680 408 12,97%
220 1.008 23,14% 1.740 224 3,81% 14.640 816 7,08%
132 336 4,63% 1.044 672 6,87% 4.880 408 1,18%
110 504 5,79% 870 112 0,95% 2.928 412 0,71%
66 144 0,99% 522 336 1,72% 2.640 48 0,08%
60 344 2,15% 348 120 0,41% 976 206 0,12%
44 504 2,31% 180 112 0,2% 880 36 0,02%
33 48 0,17% 174 60 0,1% 330 24 0,0047%
30 172 0,54% 90 84 0,07% 240 48 0,0068%
22 252 0,58% 60 16 0,0094% 110 12 0,0008%
20 516 1,08% 36 56 0,02% 80 36 0,0017%
12 172 0,22% 30 12 0,0035% 55 12 0,0004%
11 84 0,1% 20 8 0,0016% 48 24 0,0007%
10 258 0,27% 18 42 0,0074% 30 24 0,0004%
6 72 0,05% 12 8 0,0009% 16 18 0,0002%
4 258 0,11% 6 6 0,0004% 10 12 0,00007107%
3 28 0,0088% 5 12 0,0006% 6 14 0,00004975%
2 126 0,03% 4 6 0,0002% 5 12 0,00003554%
1 49 0,0051% 1 9 0,000088% 2 6 0,00000711%
1 9 0,00000533%
Progreso: 100% Progreso 100% Progreso 100%
Tiempo 1 segundos Tiempo 13 segundos Tiempo 4 minutos, 1segundo
Nº Longitudes 20 Nº Longitudes 20 Nº Longitudes 21
Nº Total Anillos 5.883 Nº Total Anillos 3.911 Nº Total Anillos 3.401

Figura 1

SOLUCION Examen extraordinario Seguridad de la Información, julio de 2017 5

 Se pide:

1. Comenta al menos tres características que veas en los anillos encontrados acerca de las claves, sus anillos
y números. (0,2 pts)
2. ¿Qué son los anillos de longitud 1? (0,2 pts)

SOLUCIÓN:

1) a) Las tres claves tienen varios anillos, la primera y la segunda 20 anillos y la tercera 21 anillos.

b) Hay algunos anillos que concentran una gran cantidad de números. En la clave1 los 672 anillos de
longitud 660 significan el 46% de los números del módulo. En la Clave2 los 1.344 anillos de longitud 5.220
significan el 68% de los números del módulo. En la Clave3 los 816 anillos de longitud 161.040 significan el
77% de los números del módulo.

c) A medida que la clave tiene más bits, tarda más tiempo en encontrar todos sus anillos.

2) Los anillos de longitud 1 son los números no cifrables de la clave, en la Clave1 hay 49, en la Clave2 y en la
Clave3 hay 9.

Seguridad de la Información PRACTICA

Curso 2016 – 17. CONVOCATORIA EXTRAORDINARIA
14 de Julio. 12:00 h (Duración 2 h. 45 min)
(Publicación Notas 18/07/17) Revisión 19/07/17. A las 12 h. Laboratorio 1101
P1 P2 P3
APELLIDOS
Y NOMBRE:

PREGUNTA 2 [0.3 puntos]

A una clave RSA de 40 bits con p = 950.993; q = 675.823; e = 5; n= [Link] y d= [Link], se
le ha realizado un ataque por cifrado cíclico para los dos mensajes secretos originales siguientes:
a) Mensaje original: 10
b) Mensaje original: 20

A la vista de la Figura 2 y sabiendo que los resultados obtenidos han sido:

a) Partiendo del mensaje original 10, se rompe el secreto en la vuelta 68.253.780 tras 1 minuto y 7
segundos a una tasa media de 1.000.000 cifras por segundo.
b) Partiendo del mensaje original 20, se rompe el secreto en la vuelta 9.750.540 tras 9 segundos a
una tasa media de 1.000.000 cifras por segundo.

SOLUCION Examen extraordinario Seguridad de la Información, julio de 2017 6

 Figura 2

SE PIDE:
a) Justifica las diferencias de tiempo entre ambos ataques.

SOLUCIÓN

El segundo ataque ha prosperado mucho antes simplemente porque el mensaje original 20 se encuentra en uno
de los anillos de longitud 9.750.540 y el mensaje original 10 se encuentra en uno de los anillos de longitud
68.253.780, exactamente 7 veces mayor.

Seguridad de la Información PRACTICA

Curso 2016 – 17. CONVOCATORIA EXTRAORDINARIA
14 de Julio. 12:00 h (Duración 2 h. 45 min)
(Publicación Notas 18/07/17) Revisión 19/07/17. A las 12 h. Laboratorio 1101
P1 P2 P3
APELLIDOS
Y NOMBRE:

PREGUNTA 3 [0.3 puntos]

SOLUCION Examen extraordinario Seguridad de la Información, julio de 2017 7

 Seguridad de la Información
Curso 2015– 16. Evaluación Continua.
2ª Parte. Ejercicio (4 puntos)

Resolviendo problemas de Seguridad de la Información, Carlos y Sara trabajan con el algoritmo RSA utilizando un
módulo de 10 bits. Uno de los problemas que estudian trata del intercambio de una clave de sesión KS de 8 bits para una
comunicación. Los datos de trabajo de Carlos y Sara son los siguientes:
Carlos: p Carlos = 7; q Carlos = 17; e Carlos = 11; d Carlos = 35
Sara: p Sara = 11; q Sara = 7; e Sara = 7
Nota: Todos los cálculos de inversos y de exponenciación deben hacerse obligatoriamente con el Algoritmo Extendido
de Euclides y el Algoritmo de Exponenciación Rápida respectivamente.
Se pide:
a) (0,5 puntos) Calcule detalladamente todas las operaciones necesarias para encontrar la clave privada de Sara.
b) (0,5 puntos) Los datos de trabajo de Carlos generan una única Clave Privada Pareja = 83. Calcule y encuentre las
claves privadas parejas de Sara. ¿Qué datos elegiría, los de Carlos o los de Sara? Justifique su respuesta.
c) (1,25 puntos) Carlos genera una clave de sesión K=43 y se la envía cifrada de forma confidencial a Sara. Cuando
Sara recibe el criptograma lo descifra. Realice detalladamente las operaciones de cifrado y descifrado de la clave
K generada por Carlos (0,5). Analice y justifique los resultados obtenidos en las operaciones realizadas (0,75).
d) (1,25 puntos) ¿Calcule y describa detalladamente qué ocurre cuando es Sara la encargada de generar y transmitir a
Carlos esta misma clave K=43 cifrada? (0,5) ¿Sería mejor o igual este nuevo escenario de intercambio de clave que
el propuesto en el apartado c)? Justifique su respuesta (0,75).
e) (0,5 puntos) Indique las operaciones (sin realizarlas) que tendrían que realizar Carlos y Sara para verificar la
confidencialidad y la integridad del intercambio de la clave de sesión K=43.
Información y datos de interés que se conocen en cada una de las operaciones realizadas:

i)  = mcm[(p-1),(q-1)]; d = inv (e, );  = (n - d)/  ; di = d + i

ii) 4310 = 1010112 y 3510 = 1000112

iii) NNC (n=77 y e=7) = {0, 1, 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76}
NNC (n=119 y e=11) = {0, 1, 34, 35, 50, 69, 84, 85, 118}

Solución:
Apartado a)
Sara: p Sara = 11; q Sara = 7; e Sara = 7
n Sara =77; (n) Sara = 60
d Sara = inv [eS, (n) Sara)] = inv (7,60) =43
i yi gi ui vi
0 -- 60 1 0
1 -- 7 0 1
2 Int(60/7)=8 60-8*7=4 1-8*0=-7 0-8*1=-8
3 Int(7/4)=1 7-1*4=3 0-1*-7=7 1-1*(-8)=9
4 Int(4/3)=1 4-1*3=1 -7-1*7= -14 -8-1*9=-17
5 Int(3/1)=3 3-3*1=0
La clave privada de Sara es dSara = -17+60=43
Apartado b)
Sara: p Sara = 11; q Sara = 7; e Sara = 7 n Sara =77; (n) Sara = 60 d Sara =inv (7,60) =43
 = mcm[(p-1),(q-1)] = mcm (10, 6) = 30
d = inv (e, ) = inv (7, 30) =13
 Seguridad de la Información
Curso 2015– 16. Evaluación Continua.
2ª Parte. Ejercicio (4 puntos)

La primera clave d =13

i yi gi ui vi
0 -- 30 1 0
1 -- 7 0 1
2 Int(30/7)=4 30-4*7=2 1-4*0=1 0-4*1=-4
3 Int(7/2)=3 7-3*2=1 0-3*1=-3 1-3*(-4)=13
4 Int(2,1)=2 2-2*1=0 -- --

El número de claves privadas parejas serán.  = (n - d)/  = (77- 13)/ 30 = 2
Las claves privadas parejas se calculan aplicando: di = d + i
i=0; d0 = 13 + 0*30 =13;
i=1; d1 = 13+1*30=43, (Esta es la clave privada y NO es clave pareja)
i=2, d2 = 13+2*30=73
Las claves parejas son {13,73}
Apartado c)
KSesion = 43.
Cifra para Sara
C = KeSara mod nSara = 437 mod 77
710 = 1112 (b2b1b0); x = 1

i=2 b2 = 1 x = 12 x 43 mod 77 x = 43

i=1 b1 = 1 x = 432 *43 mod 77 x = 43

i=0 b1 = 1 x = 432 x 43 mod 77 x = 43

C = 43
43 es un Número No Cifrable en el cuerpo n =77 de Sara de acuerdo a los datos proporcionados
en el enunciado (iii). Por lo tanto Sara no necesitaría descifrar porque sabe que el mensaje
recibido viene en claro y NO cifrado.
Apartado d)
Si es Sara la encargada de generar y transmitir de forma confidencial la clave K=43 a Carlos,
la cifra se haría en el cuerpo de Carlos, con la clave pública de Carlos.
KSesion = 43.
Cifrado para Carlos
Carlos: p Carlos = 7; q Carlos = 17; e Carlos = 11; n=p*q = 119; d Carlos = 35
C= KSesioneCarlos 11
mod nCarlos = 43 mod 119;
1110=10112 (b3b2b1b0); (entregado como dato, ii) x = 1

i=3 b3 = 1 x = 12 x 43 mod 119 x = 43

i=2 b2 = 0 x = 432 mod 119 x = 64

 Seguridad de la Información
Curso 2015– 16. Evaluación Continua.
2ª Parte. Ejercicio (4 puntos)

i=1 b1 = 1 x = 642 * 43 mod 119 x=8

i=0 b1 = 1 x = 82 *43 mod 119 x = 15

C = 15 y este criptograma NO está incluido entre los Números No Cifrables en el cuerpo n de

Carlos. Por lo que tendrá que descifrarlo.
Descifrado que realiza Carlos:
KSesion = CdCarlos mod nCarlos = 1535 mod 119
35 = 1000112 (b5b4b3b2b1b0); x = 1 (entregado como dato (ii))

i=8 B5 = 1 x = 12 x 15 mod 119 x = 15

i=7 B4 = 0 x = 152 mod 119 x = 106

i=6 B3 = 0 x = 1062 mod 119 x = 50

i=5 B2 = 0 x = 502 mod 119 x=1

i=4 B1 = 1 x = 12 x 15 mod 119 x = 15

i=3 B0 = 1 x = 152 x 15 mod 119 x = 43

Se comprueba que la clave de sesión enviada llega cifrada. Por lo tanto, este nuevo escenario
es mejor que el presentado en el apartado c) (donde la clave de sesión es transmitida en claro
al tratarse de un Número No Cifrable en el cuerpo de Sara). En este nuevo escenario la clave
de sesión es transmitida de Sara a Carlos de forma cifrada porque NO está entre los NNC en
el cuerpo de Carlos.
Apartado e)
1º) Cifrado con confidencial e íntegridad de Sara para Carlos:
Sara cifra KSesión para Carlos (para confidencialidad a Carlos) con la clave pública de Carlos
obteniendo C1 = (KSesión)eCarlos mod nCarlos
Sara además, aplica el hash de (KSesión) y lo firma con su clave privada:
Firma= hash(KSesión)dSara mod nSara
Sara envía a Carlos las dos cosas (C1 y la Firma)
2º) Autenticación de la Firma y verificación de la integridad:
Carlos descifra C1 con su clave privada y obtiene la supuesta clave de sesion K´Sesión:
K´Sesión = C1dCarlos mod nCarlos
Además autentica la Firma de Sara descifrando el h(KSesión) con la clave pública de Sara
obteniendo el hash(KSesión) que le envió Sara.
hash(KSesión) =FirmaeSara mod nSara
Carlos aplica la función hash(K´Sesión) y comprueba que hash (KSesión)= hash(K´Sesión)
verificando así la integridad de la clave.
 Seguridad de la Información
Curso 2015 – 16. Evaluación SOLO PRUEBA FINAL
6 de JUNIO. (2 h. 45 min)
APELLIDOS
Y NOMBRE _______________________________________________________________
Problema 2 [2 Ptos]

Carmen ha interceptado un mensaje cifrado que Alicia ha enviado a Beatriz de forma confidencial. Se sospecha que
para cifrar el mensaje interceptado se ha utilizado el algoritmo de cifrado de clave pública RSA. Además, Carmen
sabe que Alicia firma utilizando RSA todos los documentos enviados. El criptograma interceptado es C=317.

Se conocen los siguientes datos públicos:

Nombre eNombre nNombre

Carmen eCarmen = 13 nCarmen = 345
Beatriz eBeatriz= 77= nBeatrizs= 527
Alicia eAlicia= 7 =1112 nAlicia= 527

a) ¿Es posible que Carmen conozca el mensaje M asociado al criptograma interceptado sin conocer la
clave privada de receptor? Justifica detalladamente tu respuesta.
Solución

SÍ, es posible. Realizando cualquiera de los ataques que puede sufrir el algoritmo RSA.

 El ataque basado en la factorización del módulo n encontrando p y q, posteriormente (n)=(p-1)(*(q-1)

y por lo tanto la clave privada
 El ataque por cifrado cíclico con la clave pública donde se consigue romper el secreto que se intercepta

 El ataque basado en la paradoja del cumpleaños en la que se encuentra la clave privada d o una clave
privada pareja

b) Detalla y realiza las operaciones que haría Carmen para realizar un ataque cíclico.
El secreto interceptado es C=175
Solución

C=175 (se captura)

C1 = 1757 mod 527 = 452
C2 = 452 7 mod 527 = 226
C3 = 226 7 mod 527 = 10 - > M
C4 = 10 7 mod 527 = 175

Luego el texto en claro secreto que ha sido cifrado es M = 10

c) ¿Cuáles son los valores de p y q utilizados por Ana y Boris? ¿Son primos seguros? ¿Qué ocurriría si el
ataque cíclico se realiza sobre un cifrado en el que Ana y Boris han utilizado un n= 517?

Solución

 n de Boris y Ana es =. 527; 527 =17 * 31 -> p=17 y q = 31

 Para que sean primos seguros se tiene que cumplir que p= 2* r + 1, siendo r primo -> 17 = 2*8+1 y 8 no es
primo. Lo mismo ocurre con q = 2* r’ +1 -> 31= 2* 15 + 1 y 15 tampoco es primo. Por lo tanto, p y q NO son
primos seguros.
 Si n=517 -> n= 11*47 por lo que p=11 y q= 47; p= 2* r + 1; 11= 2*5 +1 r=5 que es primo; q= 2* r’ + 1;
47= 2*23 +1 r’=23 que también es primo. Por lo tanto en este caso Boris y Ana estarán usando primos seguros
y el ataque tendría que realizarse con más pasos.