PDF de programación - Capítulo 19 Protocolos y Esquemas Criptográficos

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 19

Protocolos y Esquemas Criptográficos

Seguridad Informática y Criptografía

Ultima actualización del archivo: 01/03/06
Este archivo tiene: 73 diapositivas

v 4.1

Material Docente de
Libre Distribución

Dr. Jorge Ramió Aguirre
Universidad Politécnica de Madrid

Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza el uso,
reproducción en computador y su impresión en papel, sólo con fines docentes y/o personales, respetando los
créditos del autor. Queda prohibida su comercialización, excepto la edición en venta en el Departamento de
Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España.

Curso de Seguridad Informática y Criptografía © JRA

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 926

Definición de protocolo criptográfico

• Protocolo: es el conjunto de acciones

coordinadas que realizan dos o más partes o
entidades con el objeto de llevar a cabo un
intercambio de datos o información.

¿Qué es un
protocolo?

• Protocolos criptográficos serán aquellos que

cumplen esta función usando para ello
algoritmos y métodos criptográficos.
• Permiten dar una solución a distintos

problemas de la vida real, especialmente en
aquellos en donde puede existir un grado de
desconfianza entre las partes.

Veamos 10 ejemplos

http://www.criptored.upm.es/guiateoria/gt_m023c.htm



© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 927

Ejemplos de protocolos criptográficos (1)

1.- El problema de la identificación del usuario

¿Cómo permitir que un usuario se identifique y autentique
ante una máquina -y viceversa- con una clave, password o
passphrase y no pueda ser suplantado por un tercero?

2.- El problema del lanzamiento de la moneda

¿Cómo permitir que dos usuarios realicen una prueba con
probabilidad ½ -como es el lanzamiento de una moneda-
si éstos no se encuentran físicamente frente a frente y,
a la vez, asegurar que ninguno de los dos hace trampa?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 928

Ejemplos de protocolos criptográficos (2)

3.- El problema de la firma de contratos
¿Cómo permitir que dos o más usuarios que se encuentran
físicamente alejados puedan realizar la firma de un contrato,
asegurando que ninguno de los firmantes va a modificar las
condiciones ni negarse a última hora a dicha firma?

4.- El problema del descubrimiento mínimo de un secreto
¿Cómo poder demostrar y convencer a otra persona o a un
sistema que uno está en posesión de un secreto, sin por ello
tener que desvelarlo ni a ella ni a un tercero?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 929

Ejemplos de protocolos criptográficos (3)

5.- El problema del juego de póker mental o por teléfono
¿Cómo permitir que dos o más usuarios puedan jugar a través
de la red un juego de póker -o cualquier otro- si no están
físicamente en una misma mesa de juego y asegurando, al
mismo tiempo, que ninguno de ellos va a hacer trampa?

6.- El problema de la división de un secreto o del umbral
Si tenemos un secreto único y por tanto muy vulnerable,
¿cómo permitir que ese secreto se divida en n partes, de
forma que juntando k < n partes sea posible reconstruirlo y,
en cambio, con k-1 partes imposible su reconstrucción?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 930

Ejemplos de protocolos criptográficos (4)

7.- El problema del esquema electoral o voto electrónico
¿Cómo realizar unas elecciones a través de una red, de forma
que pueda asegurarse que el voto es único y secreto, que los
votantes y mesas estén autenticados, y se pueda comprobar
que el voto se contabiliza de adecuadamente en el cómputo?

8.- El problema de la transmisión por canales subliminales
Dos usuarios desean intercambiar información a través de un
tercero del cual desconfían. ¿Cómo pueden hacerlo sin cifrar
la información de forma que este tercero sólo vea un mensaje
con texto en claro aparentemente inocente?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 931

Ejemplos de protocolos criptográficos (5)

9.- El problema del millonario
Dos usuarios desean conocer cuál de los dos tiene más
dinero en su cuenta corriente. ¿Cómo pueden hacerlo de
forma que, una vez terminado el protocolo, ambos sepan
quién de los dos es más rico sin por ello desvelar el dinero
que tiene el otro?

10.- El problema del correo electrónico con acuse de recibo
¿Cómo hacer que una vez recibido un correo electrónico,
éste sólo pueda ser leído (abierto) si el receptor envía, con
anterioridad al emisor, un acuse de recibo como sucede de
forma similar con el correo ordinario certificado?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 932

El protocolo de firma ciega

Supongamos que Adela desea que Benito le firme algo pero sin que
Benito se entere de qué es lo que está firmando. En este caso Benito
actúa como un ministro de fe, autenticando a Adela.
Protocolo:
Adela pone un documento dentro de un sobre.
Adela cierra el sobre y se lo envía a Benito.
Benito firma el sobre autenticando a Adela y se lo devuelve.
Adela abre el sobre y demuestra que Benito al firmar en el sobre

cerrado también ha firmado el documento que estaba en su interior.

En el anterior algoritmo, si Benito necesita una comprobación de la
identidad de Adela, ésta sencillamente incluye una firma digital suya en
el sobre que le permita a Benito comprobar su autenticidad.

http://www.di.ens.fr/~pointche/Documents/Papers/2003_joc.pdf



© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 933

Algoritmo de firma ciega RSA (Chaum)

Adela desea que Benito le firme un documento M

Adela (A) conoce las claves públicas de Benito (B: nB, eB)
A elige un coeficiente de ceguera k de forma que se
cumpla mcd (k, nB) = 1, calcula k-1 = inv (k, nB) y luego
enmascara su mensaje mediante la siguiente operación:
tA = M ∗ keB mod nB
→ y lo envía a B
B firma el valor: tB = tA
dB mod nB → y lo envía a A
A quita la máscara haciendo s = tB ∗ inv (k, nB) mod nB
El resultado es que A tiene MdB mod nB, es decir la firma

de B del documento M, una firma ciega sobre M.
tB = (M ∗ keB)dB mod nB = MdB ∗ k mod nB
[MdB ∗ k ∗ inv (k, nB)] mod nB = MdB mod nB

Comprobación:
Luego:

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 934

Ejemplo de algoritmo de firma ciega

Adela (A) desea que Benito (B) le firme el mensaje M = 65
Claves públicas de B: nB = 299, eB = 7
Clave privada y datos de B: pB = 13; qB = 23; φ(nB) = 264, dB = 151
A elige k / mcd (k, nB), por ejemplo k = 60. Luego inv (k, nB) = 5
A enmascara el mensaje: tA = M ∗ keB mod nB = 65 ∗ 607 mod 299
A envía a B: tA = 65∗226 mod 299 = 39
B firma tA con clave privada: tB = tA
A quita la máscara: s = tB ∗ inv (k, nB) = 104 ∗ 5 mod 299 = 221
Este valor (221) es el mismo que se obtendría si B firmase su con

eB mod nB = 39151 mod 299 = 104

clave privada el mensaje M, es decir 65151 mod 299 = 221

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 935

Transferencia inconsciente o trascordada

Algoritmo de TI propuesto por Michael Rabin en 1981:
• Un usuario A transfiere a un usuario B un dato o

secreto con un cifrado probabilístico del 50%.

• El usuario B recibe el dato y tiene una probabilidad

del 50% de descubrir el secreto. Una vez que ha
recibido el dato, B sabe si éste es el secreto o no.

• No obstante, el usuario A no tiene forma de saber si el

usuario B ha recibido el secreto o no.
Esta incertidumbre mutua forzará a
los protagonistas a que terminen el
protocolo sin hacer trampas.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 936

Algoritmo de TI de Rabin (1)

Paso 1º

Paso 2º

Paso 3º

Paso 4º

A elige dos primos (p y q), calcula n = p∗q y
envía el valor n a B.
B elige un número aleatorio x del CCR(n) de
forma que que mcd (x,n) = 1, y devuelve a A
el valor K = x2 mod n.
A calcula las cuatro raíces de x2 mod n y
envía a B una de ellas. Las raíces de x2 mod n
serán: x, n-x, y, n-y. Sólo A puede hacerlo
porque conoce los valores de p y q.
B intenta descubrir el valor de p o q.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 19: Protocolos y Esquemas Criptográficos

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 19: Protocolos y Esquemas Criptográficos

Página 937

Conclusión del algoritmo de TI de Rabin

Si B recibe x o n-x no será capaz de encontrar p o q.

No tiene más información que la que tenía porque:
x y n-x son valores que conoce (B ha elegido x).



☺

Si B recibe y o n-y, podrá encontrar p o q.

En este caso, como x2 mod n = y2 mod n,