Ver el código de «Intercambio de claves de Diffie-Hellman»

El [[protocolo criptográfico]] '''Diffie-Hellman''', debido a [[Whitfield Diffie]] y [[Martin Hellman]] (autores también del ''problema de Diffie-Hellman'' o ''DHP''), es un [[Protocolos de establecimiento de claves|protocolo de establecimiento de claves]] entre partes que no han tenido contacto previo, utilizando un canal inseguro y de manera anónima (no autenticada). 

Se emplea generalmente como medio para acordar claves [[criptografía simétrica|simétricas]] que serán empleadas para el cifrado de una sesión (establecer clave de sesión). Siendo no autenticado, sin embargo, provee las bases para varios protocolos autenticados.<ref name="ccn-stic-401">{{cita CCN-STIC-401|título=Algoritmo Diffie-Hellman|id=38}}</ref> Su seguridad radica en la extrema dificultad (conjeturada, no demostrada) de calcular [[logaritmo discreto|logaritmos discretos]] en un cuerpo finito.<ref name="ccn-stic-401" />

El método lleva el nombre de los [[criptografía|criptógrafos]] [[Whitfield Diffie]] y [[Martin Hellman]], quienes lo desarrollaron y publicaron en 1976<ref name="DH1976">{{Cite journal|last1=Diffie|first1=Whitfield|last2=Hellman|first2=Martin E.|author-link1=Whitfield Diffie|author-link2=Martin Hellman|date=November 1976|title=New Directions in Cryptography|url=http://ee.stanford.edu/%7Ehellman/publications/24.pdf|journal=[[IEEE Transactions on Information Theory]]|volume=22|issue=6|pages=644–654|doi=10.1109/TIT.1976.1055638|archive-url=https://web.archive.org/web/20141129035850/https://ee.stanford.edu/%7Ehellman/publications/24.pdf|archive-date=2014-11-29}}</ref> y recibieron el prestigioso [[Premio Turing|premio A.M. Turing]] de 2015 por este trabajo "que revolucionó la [[seguridad informática]]".<ref>{{cita web |título=Cryptography pioneers receive ACM A.M. Turing Award |url=https://www.acm.org/awards/2015-turing |obra=[[Association for Computing Machinery]] |fecha=1 de marzo de 2016 |fechaacceso=15 de enero de 2024 }}</ref>

== Versión básica ==
El sistema se basa en la idea de que dos interlocutores pueden generar conjuntamente una clave compartida sin que un intruso, que esté escuchando las comunicaciones, pueda llegar a obtenerla.

Para ello se eligen dos números públicos y, cada interlocutor, un número secreto. Usando una fórmula matemática, que incluye la exponenciación, cada interlocutor hace una serie de operaciones con los dos números públicos y su número secreto. A continuación los interlocutores se intercambian los resultados de forma pública. En teoría, revertir esta función es tan difícil como calcular un [[logaritmo discreto]] (un sextillón de veces más costosa que la exponenciación usada para transformar los números). Por tanto, se dice que este número es el resultado de aplicar una [[función unidireccional]] al número secreto.

A continuación, ambos interlocutores utilizan por separado una fórmula matemática que combina los dos números transformados con su número secreto y al final los dos llegan al mismo número resultado, que será la clave compartida.
=== Descripción detallada===
[[Archivo:Diffie-Hellman-Schlüsselaustausch.png|center|thumb|400px|Diffie-Hellman.]]

Para dos partes ''Alice'' y ''Bob'', que intentan establecer una clave secreta, y un adversario ''Mallory'', la versión básica es como sigue:
* Se establecen un primo <math>p</math> y un generador <math>g \in \mathbf{Z}_{p}^{*}</math> (<ref>Aquí <math>\mathbf{Z}_{p}^{*}</math> es el conjunto de los enteros menores que ''p'' que son [[primos relativos]] de ''p'', que es un [[grupo (matemática)|grupo]] bajo la [[multiplicación]] [[Aritmética modular|módulo]] ''p''.</ref>). Estos son públicos, conocidos no solo por las partes. ''Alice'' y ''Bob'' sino también por el adversario ''Mallory''.
* ''Alice'' escoge <math>a \in \mathbf{Z}_{p-1}</math> al azar, calcula <math>A = g^{a} \;\bmod\; p</math>, y envía <math>A</math> a ''Bob.''
* ''Bob'' escoge <math>b \in \mathbf{Z}_{p-1}</math> al azar, calcula <math>B = g^{b} \;\bmod\; p</math>, y envía <math>B</math> a ''Alice.''

Nótese que tanto <math>A</math> como <math>B</math> pueden calcular el valor <math>K=g^{a \cdot b}  \;\bmod\; p</math>. En efecto, lo podemos demostrar usando las [[Aritmética modular#Clases de equivalencia módulo n|propiedades del grupo <math>\mathbf{Z}_{p}^{*}</math>]]:

:Para ''Alice'': <math> B^{a} \;\;\bmod\;\; p = (g^b \;\bmod\; p )^a \;\bmod\; p = ( \overbrace{(g^b \;\bmod\; p ) (g^b \;\bmod\; p ) \cdots (g^b \;\bmod\; p ) }^a ) \;\bmod\; p = g^{b \cdot a} \;\bmod\; p= g^{a \cdot b} \;\bmod\; p = K</math>

:Para ''Bob'': <math>A^{b} \;\bmod\; p = (g^a \;\bmod\; p )^b \;\bmod\; p = ( \overbrace{(g^a \;\bmod\; p ) (g^a \;\bmod\; p ) \cdots (g^a \;\bmod\; p ) }^b ) \;\bmod\; p = g^{a \cdot b} \;\bmod\; p = K</math>

Como ambas partes pueden calcular <math>K</math>, entonces la podemos usar como clave compartida.

=== Ataques ===

==== [[Criptoanálisis#Ataques pasivos|Ataques pasivos]] ====
Un adversario ''Mallory'', que poseyera <math>(p,g,A,B)</math>, podría calcular el [[secreto compartido]] si tuviera también uno de los valores privados (<math>a</math> o <math>b</math>). Obtener <math>a</math> o <math>b</math> a partir de <math>A</math> o <math>B</math> invirtiendo la función ( <math>a=\operatorname{log\;disc}_p(A)</math> y <math>b=\operatorname{log\;disc}_p(B)</math>) es el problema del [[logaritmo discreto]] en <math>\mathbf{Z}_{p}^{*}</math>, un problema que se cree [[NP-completo|intratable computacionalmente]] siempre que <math>p</math> sea un [[número primo]] grande de 200 o más dígitos y que no cumplan ciertas características debilitantes.<ref >Gordon, D. M. Designing and Detecting Trapdoors for Discrete Log. Cryptosystems. Advances in Cryptology-CRYPTO92, Berlin:Springer Verlag pp 66-75</ref>

==== [[Criptoanálisis#Ataques activos|Ataques activos]] ====

El protocolo es sensible a [[Criptoanálisis#Ataques activos|ataques activos]] del tipo ''[[Ataque Man-in-the-middle|Man-in-the-middle]]''. Si la comunicación es interceptada por un tercero, éste se puede hacer pasar por el emisor cara al destinatario y viceversa, ya que no se dispone de ningún mecanismo para validar la identidad de los participantes en la comunicación. Así, el "hombre en el medio" podría acordar una clave con cada participante y retransmitir los datos entre ellos, escuchando la conversación en ambos sentidos. Una vez establecida la comunicación simétrica, el atacante tiene que seguir en medio interceptando y modificando el tráfico para que no se den cuenta. Observar que para que el ataque sea operativo, el atacante tiene que conocer el método de cifrado simétrico que será utilizado. Basarse en la ocultación de algoritmo simétrico de cifrado no cumple con los [[Principio de Kerckhoffs|principios de Kerckhoffs]] (la efectividad del sistema no debe depender de que su diseño permanezca en secreto).

[[Archivo:Man-in-the-middle_attack_of_Diffie-Hellman_key_agreement.svg|center|thumb|300px|Ataque man-in-the-middle en Diffie-Hellman.]]

Para evitar este tipo de ataque, se suele usar una o más de las siguientes técnicas:
* Control de tiempos.
* Autenticación previa de las partes. Por ejemplo, usar en protocolo de capa subyacente [[autenticación]]. Podríamos primero establecer una conexión TLS y sobre esa capa aplicar el algoritmo de Diffie-Hellman.
* Autenticación del contenido. Por ejemplo, podríamos usar [[Message authentication code|MAC]] sobre el contenido de los mensajes.
* Cifrando las claves públicas con un algoritmo de clave pública (asimétrico), evitando el problema de Man-in-the-middle, y a su vez comprobando que la clave pública sea distinta de 0 y 1.
* Usar un tercero (Carol) con el que o bien Alice o bien Bob mantienen un canal seguro. Este tercero puede detectar el man-in-the-middle 
si Alice o Bob están siendo escuchados/modificados, simplemente desafiando a ambos a una prueba implicando en dicha prueba la clave pública del otro.
Si Mallory tergiversa la comunicación Alice-Bob, y también la Alice-Carol, no puede tergiversar el canal seguro Bob-Carol y será detectado.
Y si tergiversa la Alice-Bob y la Bob-Carol, no puede tergiversar la Alice-Carol (por definición debe haber algún canal seguro entre dos de los tres, aunque los otros dos canales sean tergiversados por Mallory). Esto significa que el método Diffie-Hellman puede crear redes de múltiples nodos 100% seguras, a partir de tan solo dos nodos previamente seguros. Este método también sirve para testear canales que se sospecha que puedan ser inseguros.

=== Ejemplo ===
{| border="0" cellspacing="0" cellpadding="2"
|
{| border="1" cellspacing="0" cellpadding="5" style="border: gray solid 1px; border-collapse: collapse;"
| align="center" colspan="3" | '''Alice'''
|-
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;" | Sec 
| align="center" bgcolor="#D0D0D0" | 
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;"  | Calc
|-
| align="center" |
| align="center" | '''p, g'''
| align="center" |
|-
| align="center" | '''a'''
| align="center" | 
| align="center" |
|-
| align="center" | 
| align="center" | 
| align="center" | '''g<sup>a</sup>''' mod p
|-
| align="center" |
| align="center" | …
| align="center" |
|-
| align="center" | 
| align="center" | ('''g<sup>b</sup>''' mod p)'''<sup>a</sup>''' mod p
| align="center" |
|}
| valign="bottom" |
{| border="0" cellspacing= cellpadding=
| align="center" |
|-
| align="center" |
|-
| align="center" |
|-
| align="center" |
|-
| align="center" |
|-
| align="center" | '''<math>\rightarrow</math>'''
|-
| align="center" | '''<math>\leftarrow</math>'''
|-
| align="center" | '''='''
|}
|
{| border="1" cellspacing="0" cellpadding="5" style="border: gray solid 1px; border-collapse: collapse;"
| align="center" colspan="3" | '''Bob'''
|-
| align="center" bgcolor="#D0D0D0" style="font-size: 90%;"  | Calc
| align="center" bgcolor="#D0D0D0" | 
| align="center" bgcolor="#D0D0D0" style="font-size: 100%;"  | Sec
|-
| align="center" |
| align="center" | '''p, g'''
| align="center" |
|-
| align="center" |
| align="center" | 
| align="center" | '''b'''
|-
| align="center" | 
| align="center" | …
| align="center" |
|-
| align="center" | '''g<sup>b'''</sup> mod p
| align="center" | 
| align="center" |
|-
| align="center" | 
| align="center" | ('''g<sup>a</sup>''' mod p)'''<sup>b</sup>''' mod p
| align="center" |
|}
|
# Alice y Bob acuerdan usar el número primo ''p''=23 y la base ''g''=5.
# Alice elige un número secreto ''a''=6, luego envía a Bob (''g<sup>a</sup>'' mod ''p'')
#* 5<sup>6</sup> mod 23 = 8.
# Bob elige un número secreto ''b''=15, luego envía a Alice (''g<sup>b</sup>'' mod p)
#* 5<sup>15</sup> mod 23 = 19.
# Alice calcula (''g<sup>b</sup>'' mod ''p'')''<sup>a</sup>'' mod ''p''
#* 19<sup>6</sup> mod 23 = 2.
# Bob calcula (''g<sup>a</sup>'' mod ''p'')''<sup>b</sup>'' mod ''p''
#* 8<sup>15</sup> mod 23 = 2.
|}

=== Ejemplo con implementación de cifrado ===
La necesidad para este ejemplo es: Bob necesita enviarle un [[texto cifrado]] a Alice pero sin compartir la clave de cifrado. ¿Cómo lo hace?
# Alice elige un número secreto ''a''=6, el número primo ''p''=23 y la base ''g''=5. Luego envía a Bob la llave pública de Alice (''g<sup>a</sup>'' mod ''p''), ''p'' y ''g'':
#* 5<sup>6</sup> mod 23 = 8.
#* 23
#* 5
# Bob elige un número secreto ''b''=15, luego Bob calcula la llave de cifrado común (''g<sup>a</sup>'' mod ''p'')''<sup>b</sup>'' mod ''p''
#* 8<sup>15</sup> mod 23 = 2.
# Bob cifra, con un cifrador simétrico como AES, el texto claro usando la llave de cifrado generada.
# ''TextoCifrado'' = '''CifradorSimetrico (''' TextoClaro, ''2'' ''')'''
# Bob envía a Alice el texto cifrado y la llave pública de Bob (''g<sup>b</sup>'' mod p)
#* 5<sup>15</sup> mod 23 = 19.
#* ''TextoCifrado''
# Alice calcula (''g<sup>b</sup>'' mod ''p'')''<sup>a</sup>'' mod ''p''
#* 19<sup>6</sup> mod 23 = 2.
# Alice usa esa clave de cifrado generada para descifrar los datos enviados por Bob
# TextoClaro = '''DescifradorSimetrico (''' TextoCifrado, ''2'' ''')'''

Valores mucho más grandes de ''a'',''b'' y ''p'' se necesitarían para hacer este ejemplo seguro. Dado que es muy sencillo probar todos los valores posibles de ''g<sup>ab</sup>'' mod 23 (habrá, como máximo, 22 valores, inclusive si ''a'' y ''b'' son números grandes).

Obviamente la necesidad de Alice de enviarle a Bob la información cifrada también la cubre la implementación.

== Generalizaciones ==

=== Aumentando el número de partes ===
La idea del algoritmo podemos generalizarla a la negociación de claves entre más de dos entidades. Veamos un ejemplo para tres entidades y a partir de ahí podemos aumentar el número de partes de forma fácil:

# Las partes (Alice, Bob y Carol) se ponen de acuerdo en los parámetros del algoritmo <math>p</math> y <math>g</math>.
# Las partes generan sus propias claves privadas llamadas <math>a</math>, <math>b</math>, y <math>c</math> respectivamente.
# Alice calcula <math>g^a  \;\bmod\; p</math> y lo envía a Bob.
# Bob calcula <math>(g^a)^b \;\bmod\; p= g^{ab} \;\bmod\; p</math> y lo envía a Carol.
# Carol calcula <math>(g^{ab})^c \;\bmod\; p = g^{abc} \;\bmod\; p</math> y la usa como su clave secreta.
# Bob calcula <math>g^b \;\bmod\; p</math> y lo envía a Carol.
# Carol calcula <math>(g^b)^c \;\bmod\; p= g^{bc} \;\bmod\; p</math> y lo envía a Alice.
# Alice calcula <math>(g^{bc})^a \;\bmod\; p= g^{bca} \;\bmod\; p= g^{abc} \;\bmod\; p</math> y lo usa como su clave secreta.
# Carol calcula <math>g^c \;\bmod\; p</math> y lo envía a Alice.
# Alice calcula <math>(g^c)^a \;\bmod\; p= g^{ca} \;\bmod\; p</math> y lo envía a Bob.
# Bob calcula <math>(g^{ca})^b \;\bmod\; p= g^{cab} \;\bmod\; p= g^{abc} \;\bmod\; p</math> y lo usa como su clave secreta.

=== Cambiando de grupo ===
Podemos generalizar el protocolo y sus derivados si en lugar de basarnos en el grupo <math>\mathbf{Z}_{p}^{*}</math> nos basamos en otros grupos que cumplan las condiciones necesarias para poder aplicar el algoritmo (GDHP<-Generalized Diffie-Hellman Problem)

==== Formalización ====
# Los usuarios A y B seleccionan públicamente un grupo multiplicativo finito G de orden n y generador <math>g \in G</math> cuya operación multiplicación es una operación de una vía (no tiene inversa o difícilmente invertible)
# El usuario A genera un [[número aleatorio]] a,<math>1 \le a \le n-1</math>, calcula <math>g^a \in G</math> y transmite este elemento a B, manteniendo secreto a
# El usuario B genera un número aleatorio b,<math>1 \le b \le n-1</math>, calcula <math>g^b \in G</math> y transmite este elemento a A, manteniendo secreto b
# El usuario A recibe <math>g^b</math> y calcula <math>(g^b)^a \in G</math>
# El usuario B recibe <math>g^a</math> y calcula <math>(g^a)^b \in G</math>
# A y B poseen un elemento común secreto del grupo <math>g^{a \cdot b}</math>

==== Ejemplos ====
Ejemplos de grupos que podríamos usar: El grupo multiplicativo análogo de los [[Cuerpo finito|campos de Galois]] <math>\mathbb{F}_{2^{n}}</math>, el grupo de puntos definidos por una [[curvas elípticas|curva elíptica]] sobre un cuerpo finito.

== Usos prácticos del protocolo ==

* La red para anonimato [[Tor (red de anonimato)|Tor]] usa el protocolo Diffie Hellman, sobre una conexión [[Transport Layer Security|TLS]] de una capa inferior previamente establecida, para procurarse claves de sesión entre el cliente y los nodos de enrutamiento de la red. Esas claves son usadas para cifrar las capas de cebolla de los paquetes que transitan por la red.
*El protocolo [[Off the record messaging|Off-the-Record Messaging (OTR)]] para comunicación de [[mensajería instantánea]] se apoya<ref>N. Borisov,"Off-the-Record Communication or, Why Not To Use PGP"</ref> en el protocolo Diffie-Hellman para ir cambiando de clave de cifrado según se van intercambiando los mensajes.

== Referencias ==
{{listaref}}

== Bibliografía adicional ==
* Menezes, A.J., P.C. van Oorschot y S.A. Vanstone. ''Handbook of Applied Cryptography''. Boca Raton, Fl.: [[CRC Press]], 1997.
* {{cita IETF |rfc=2631 |first1=E. |last1=Rescorla |title=Diffie-Hellman Key Agreement Method |date=junio de 1999 }}

{{Control de autoridades}}
[[Categoría:Protocolos de establecimiento de claves]]
[[Categoría:Algoritmos epónimos|Diffie-Hellman]]
[[Categoría:Algoritmos criptográficos]]