protocolo diffie - hellman

Protocolo Diffie - Hellman

T I C r i p t o 2 0 2 1

Tomás CaramSantiago Curi

Santiago FreireBruno Hernández

Juan Pablo MartínezJimena Mignaco

Alfredo Viola

Formalización matemática del acuerdo de claves

Recapitulación

En base a lo que aprendimos anteriormente con las

sustancias de colores, vamos a ver su analogía con el

protocolo real.

BugsAbuelita

Ambos emplearán en común un númeroprimo 𝒑 y un número 𝒈 entre 1 y 𝑝 − 1

con la propiedad especial de que∀𝑥 ∈ {1,… , 𝑝 − 1} ∶ ∃𝑒 ∈ ℕ / 𝑔𝑒 ≡ 𝑥 (𝑚𝑜𝑑 𝑝)

“𝑔𝑒 es congruente con 𝑥 módulo 𝑝”

“𝑥 es el resto de dividir 𝑔𝑒 entre 𝑝”

20 ≡ 1 (𝑚𝑜𝑑 11)

Por ejemplo, con 𝒑 = 𝟏𝟏 y 𝒈 = 𝟐 :

g

21 ≡ 2 𝑚𝑜𝑑 11

22 ≡ 4 𝑚𝑜𝑑 1123 ≡ 8 (𝑚𝑜𝑑 11)

24 ≡ 5 (𝑚𝑜𝑑 11)

25 ≡ 10 (𝑚𝑜𝑑 11)

26 ≡ 9 𝑚𝑜𝑑 11

27 ≡ 7 𝑚𝑜𝑑 11

28 ≡ 3 (𝑚𝑜𝑑 11)

29 ≡ 6 (𝑚𝑜𝑑 11)

28 = 256 = 𝟏𝟏 × 23 + 3 ≡ 3 (𝑚𝑜𝑑 𝟏𝟏)

BugsAbuelita

Ambos emplearán en común un númeroprimo 𝒑 y un número 𝒈 entre 1 y 𝑝 − 1

con la propiedad especial de que∀𝑥 ∈ {1,… , 𝑝 − 1} ∶ ∃𝑒 ∈ ℕ / 𝑔𝑒 ≡ 𝑥 (𝑚𝑜𝑑 𝑝)

20 ≡ 1 (𝑚𝑜𝑑 11)

Por ejemplo, con 𝒑 = 𝟏𝟏 y 𝒈 = 𝟐 :

g

21 ≡ 2 𝑚𝑜𝑑 11

22 ≡ 4 𝑚𝑜𝑑 1123 ≡ 8 (𝑚𝑜𝑑 11)

24 ≡ 5 (𝑚𝑜𝑑 11)

25 ≡ 10 (𝑚𝑜𝑑 11)

26 ≡ 9 𝑚𝑜𝑑 11

27 ≡ 7 𝑚𝑜𝑑 11

28 ≡ 3 (𝑚𝑜𝑑 11)

29 ≡ 6 (𝑚𝑜𝑑 11)

Observar que con los exponentes de 0,… , 𝑝 − 2 se obtienen todos

los números requeridos

La Abuelita elige unexponente secreto

(por ejemplo, 𝑎 = 5)

Abuelita Bugs

a

𝒑 = 𝟏𝟏

Generadorcomún(𝑔 = 2)

g

b

Bugs elige unexponente secreto

(por ejemplo, 𝑏 = 9)

Abuelita Bugs

Secreto dela Abuelita

(𝑎 = 5)

a

𝒑 = 𝟏𝟏

Generadorcomún(𝑔 = 2)

g

Secreto deBugs

(𝑏 = 9)

Secreto dela Abuelita

(𝑎 = 5)

Ambos elevan a su exponente secretoel elemento g en común y reducen

módulo 𝑝 el resultado

Abuelita Bugs

g

a

g

b

𝒈𝒂 (𝒎𝒐𝒅 𝒑) 𝒈𝒃 (𝒎𝒐𝒅 𝒑)

𝟐𝟓 ≡ 𝟏𝟎 (𝒎𝒐𝒅 𝟏𝟏) 𝟐𝟗 ≡ 𝟔 (𝒎𝒐𝒅 𝟏𝟏)

𝒑 = 𝟏𝟏𝒈 = 𝟐

Luego ponen su resultadoreducido módulo 𝒑

a disposición en el canal público

Abuelita Bugs

Secreto dela Abuelita

(𝑎 = 5)

a

Secreto deBugs

(𝑏 = 9)

b

Resultado dela Abuelita

𝟏𝟎

Resultado deBugs

𝟔

𝒑 = 𝟏𝟏

Generadorcomún(𝑔 = 2)

g

𝟕

Supongamos que además de ellos alguien más

calculó una exponenciación módulo 𝑝 con base g

Abuelita Bugs

Secreto dela Abuelita

(𝑎 = 5)

a

Secreto deBugs

(𝑏 = 9)

b

Resultado dela Abuelita

𝟏𝟎

Resultado deBugs

𝟔

𝒑 = 𝟏𝟏

Generadorcomún(𝑔 = 2)

g

CoyoteSecreto del

Coyote(𝑐 = ?)

Sin embargo, tuvo laprecaución de correrla cortina y no pudimosver su exponente𝑐 secreto

Abuelita Bugs

Secreto dela Abuelita

(𝑎 = 5)

a

Secreto deBugs

(𝑏 = 9)

b

Generadorcomún(𝑔 = 2)

g

Resultado dela Abuelita

𝟏𝟎

Resultado deBugs

𝟔

𝟕

Resultado delCoyote

𝒑 = 𝟏𝟏

La Abuelita tomael resultado módulo 𝑝

entregado por Bugs

Abuelita Bugs

Secreto dela Abuelita

(𝑎 = 5)

a

Secreto deBugs

(𝑏 = 9)

b

Resultado dela Abuelita

𝟏𝟎

Resultado deBugs

𝟔

𝒑 = 𝟏𝟏

Abuelita Bugs

Secreto dela Abuelita

(𝑎 = 5)

a

Secreto deBugs

(𝑏 = 9)

b

Resultado dela Abuelita

𝟏𝟎

Resultado deBugs

𝟔

Resultado deBugs

𝟔

Bugs se copia elresultado módulo 𝑝

de la Abuelita

𝒑 = 𝟏𝟏

Entonces cuando cada uno tenga el resultado de la exponenciación

módulo 𝑝 que hizo el otro . . .

Abuelita Bugs

Secreto dela Abuelita

(𝑎 = 5)

a

Secreto deBugs

(𝑏 = 9)

b

Resultado dela Abuelita

𝟏𝟎

Resultado deBugs

𝟔

𝟕

Resultado delCoyote

𝒑 = 𝟏𝟏

Resultado deBugs

𝟔

Resultado dela Abuelita

𝟏𝟎

Generadorcomún(𝑔 = 2)

g

Abuelita BugsSecreto de

Bugs(𝑏 = 9)

Secreto dela Abuelita

(𝑎 = 5)a b

Resultadode Bugs

(6)

Resultado dela Abuelita

(10)

𝒈𝒃

(𝒎𝒐𝒅 𝒑)

𝒈𝒃𝒂≡ 𝒈𝒃𝒂 (𝒎𝒐𝒅 𝒑)

𝟔𝟓 ≡ 𝟏𝟎 (𝒎𝒐𝒅 𝟏𝟏)

𝒈𝒂

(𝒎𝒐𝒅 𝒑)

𝟏𝟎𝟗 ≡ 𝟏𝟎 (𝒎𝒐𝒅 𝟏𝟏)

𝒈𝒂 𝒃 ≡ 𝒈𝒂𝒃 (𝒎𝒐𝒅 𝒑)

Ambos elevan a su exponente secretoel resultado del otro y reducen

el cálculo módulo 𝑝

𝒑 = 𝟏𝟏𝒈 = 𝟐

𝟏𝟎𝟏𝟎

Sin conocer cuál era el exponente secreto del otro,obtuvieron el MISMO valor módulo 𝑝

Abuelita Bugs

𝟏𝟎

Abuelita Bugs

Este valor 𝑲 entre 1 y 𝑝 − 1es la clave secreta

de la Abuelita y Bugs

𝟏𝟎

𝑲 ≡ 𝒈𝒃𝒂(𝒎𝒐𝒅 𝒑) 𝑲 ≡ 𝒈𝒂 𝒃(𝒎𝒐𝒅 𝒑)

𝑲 ≡ 𝒈𝒂𝒃(𝒎𝒐𝒅 𝒑)

¿Cuál es el exponente secreto del Coyote?

Resultado delCoyote

Primera “garantía de seguridad”

𝟕

¿Qué hizo el Coyote?Secreto del

Coyote(𝑐 = ?)

g

𝟐𝒄 ≡ 𝟕 (𝒎𝒐𝒅 𝟏𝟏)

{0, … , 𝑝 − 2}

¿Podemos probar cada número 𝑐 ∈ {0,… , 𝑝 − 2},

uno por uno, hasta dar con el que 2𝑐 ≡ 7 (𝑚𝑜𝑑 𝑝)?

Sí, si buscamos secuencialmente vemos que 𝑐 = 7.

Entonces precisamos que 𝑝 sea un número muy grande (mayor que la cantidad estimada de átomos en el Universo).

Pero queremos resistir ataques de fuerza bruta.

En general, calcular las exponenciaciones módulo 𝑝es una operación fácil de hacer, aún con números inmensos.

Sin embargo, dado 𝑔𝑐 (𝑚𝑜𝑑 𝑝) hallar el exponente𝑐 es muy difícil si se elige 𝑝 lo suficientemente grande.

Este es el problema llamado logaritmo discreto.

Se conjetura que no existe ningún algoritmo eficiente para resolver todas las instancias del logaritmo discreto.

Dicha conjetura es la base de la seguridad de este protocolo, que fue presentado por Diffiey Hellman en 1976.

Supongamos que ahora Bugs quiere

descubrir la clave secreta de

la Abuelita y el Coyote . . .

Segunda “garantía de seguridad”

Generadorcomún(𝑔 = 2)

g 𝟕

Resultado delCoyote

Resultado dela Abuelita

𝟏𝟎

¿A qué información tuvo acceso Bugs?

Recordar lo que nosotros vimos… o no tanto

2

5

2

?

La clave secreta de la Abuelita y el Coyote es el resultado de:

Generadorcomún(𝑔 = 2)

Secreto dela Abuelita

(𝑎 = 5)

𝑲 ≡ 𝒈𝒂𝒄(𝒎𝒐𝒅 𝒑)

Secreto delCoyote(𝑐 = ?)

Si Bugs multiplicara los resultados entregados por cada participante:

Bugs precisa despejar el secreto de la Abuelita o el Coyote (𝒂 o 𝒄, resp.)

𝒈𝒂𝒈𝒄 ≡ 𝒈𝒂+𝒄(𝒎𝒐𝒅 𝒑)

Los exponentes quedan sumando!

Problema de Diffie - Hellman

Se conoce:

• un primo 𝒑,

• un generador 𝒈 de los números {1,… , 𝑝 − 1},

• 𝑨 ≡ 𝒈𝒂 (𝑚𝑜𝑑 𝑝) y

• 𝑩 ≡ 𝒈𝒃(𝑚𝑜𝑑 𝑝)

Se debe hallar:

𝑲 ≡ 𝒈𝒂𝒃(𝑚𝑜𝑑 𝑝)

gb

𝒈𝒃 (𝒎𝒐𝒅 𝒑)

ga

𝒈𝒂 (𝒎𝒐𝒅 𝒑)

𝟔𝟏𝟎

a

Terminología del paradigma asimétrico

• Al exponente secreto de cada participante se le conoce como clave secreta (o clave privada), y sólo es conocido por su propietario.

• El valor de 𝑔𝑎(𝑚𝑜𝑑 𝑝) y 𝑔𝑏(𝑚𝑜𝑑 𝑝) es la clave pública de cada participante. Está asociada con el dueño de la clave privada y es conocida por todos.

• Hay una función exponenciación modular que toma como entradas un exponente secreto y una base 𝑔, y permite obtener los valores módulo 𝑝 anteriores.

• Hay una función logaritmo discreto que a partir de un valor público 𝑥 ∈ {1,… , 𝑝 − 1}, devuelve el exponente secreto 𝑒 tal que 𝑔𝑒 ≡ 𝑥 (𝑚𝑜𝑑 𝑝). En otras palabras, es la inversa de exponenciar.

b

𝒈𝒂

(𝒎𝒐𝒅 𝒑)

b

𝒈𝒂𝒃(𝒎𝒐𝒅 𝒑)

• La función exponenciar es fácil de realizar si se tiene el exponente.

• No se conoce una forma eficiente de realizar la función logaritmo discreto, a menos que se tenga el exponente secreto, se eleve la base 𝑔 y luego se observe que al reducir módulo 𝑝 da el valor público.

• Funciones que son fáciles de implementar pero para las cuales no se conoce una forma eficiente de implementar la función inversa, se las conoce como funciones “unidireccionales” (one way, en inglés).

• No se conocen maneras eficientes de lograr el secreto compartido de dos participantes usando sólo su información pública.

• Para generar la clave compartida entre A y B, cada uno debe usar su clave secreta y la clave pública del otro.

𝒈𝒃

(𝒎𝒐𝒅 𝒑)

a

𝒈𝒃𝒂(𝒎𝒐𝒅 𝒑)

Secreto dela Abuelita

(𝑎 = 5)

a

Secreto deBugs

(𝑏 = 9)

b

Resultado delCoyote

Secreto delCorrecaminos

Abuelita Bugs

Problema del tercero en el medio

Resultado dela Abuelita

𝟏𝟎

Resultado deBugs

𝟔

𝒑 = 𝟏𝟏

Generadorcomún(𝑔 = 2)

g

𝟑

Correcaminos ¿Qué pasa si Correcaminos se hace pasar por

Coyote?

Abuelita La Abuelita piensa que acuerda una clave con el Coyote, pero en realidad lo está haciendo con el

Correcaminos

𝑲 ≡ 𝒈𝒄 𝒂

(𝑚𝑜𝑑 𝑝)

𝑲 ≡ 𝒈𝒂 𝒄

(𝑚𝑜𝑑 𝑝)

Hay que certificar la identidad de los participantes!

Correcaminos

Tenemos el problema deltercero en el medio.

Coyote no se enterade nada!