Protocolo de Diffie-Hellman

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de julio de 2022; las comprobaciones requieren 2 ediciones .

El protocolo Diffie -Hellman ( Ing. Diffie-Hellman key exchange protocol, DH ) es un protocolo criptográfico que permite que dos o más partes obtengan una clave secreta compartida utilizando un canal de comunicación que no está protegido contra la escucha. La clave resultante se utiliza para cifrar más intercambios utilizando algoritmos de cifrado simétricos .

El esquema de distribución de claves públicas propuesto por Diffie y Hellman hizo una verdadera revolución en el mundo del cifrado, ya que eliminó el principal problema de la criptografía clásica: el problema de la distribución de claves.

En su forma pura, el algoritmo Diffie-Hellman es vulnerable a la modificación de datos en el canal de comunicación, incluido el ataque " Man-in-the-middle (hombre en el medio) ", por lo que los esquemas que lo utilizan utilizan una o dos vías adicionales. Métodos de autenticación de vías .

Historia

La transmisión de la clave a través de canales abiertos fue un gran problema en la criptografía del siglo XX. Pero este problema se resolvió después del advenimiento del algoritmo Diffie-Hellman. Este algoritmo permitió responder a la pregunta principal: "¿Cómo, al intercambiar mensajes cifrados, evitar la necesidad de transmitir un código de descifrado secreto que, por regla general, no es menos que el mensaje mismo?" La distribución pública de claves Diffie-Hellman permite que un par de usuarios del sistema desarrollen una clave secreta compartida sin intercambiar datos secretos.

Los fundamentos de la criptografía de clave pública fueron avanzados por Whitfield Diffie y Martin Hellman , e independientemente por Ralph Merkle .

Su contribución a la criptografía fue la afirmación de que las claves se pueden usar en pares, una clave de cifrado y una clave de descifrado, siempre que sea imposible determinar el contenido de la clave de descifrado a partir del contenido de la clave de cifrado transmitida públicamente. Diffie y Hellman presentaron esta idea por primera vez en la Conferencia Nacional de Informática en 1976, y unos meses más tarde se publicó su artículo seminal New Directions in Cryptography [1] .

Un año después, se inventó el primer algoritmo de encriptación asimétrica RSA , que resolvió el problema de comunicarse por un canal inseguro.

En 2002, Martin Hellman escribió :

Este sistema ... desde entonces se conoce como el algoritmo Diffie-Hellman. Sin embargo, cuando el sistema fue descrito por primera vez en papel por Diffie y yo, era un sistema de distribución de clave pública conceptualizado por Merkle y, por lo tanto, debería llamarse "algoritmo Diffie-Hellman-Merkle" si está asociado con nombres. Espero que este pequeño cambio ayude a reconocer la contribución equitativa de Merkle a la invención de la criptografía de clave pública.

En la patente estadounidense 4.200.770, ahora vencida, se enumeran tres autores como los creadores de este algoritmo: Hellman, Diffie y Merkle.

Recién en diciembre de 1997 apareció información actualizada de que Malcolm Williamson ya en 1974 inventó un algoritmo matemático basado en la conmutatividad de los exponentes cuando se exponen sucesivamente ( ). Este método puede llamarse un análogo del algoritmo Diffie-Hellman. $(b^{x})^{y} = (b^{y})^{x} = b^{xy}$

Descripción del algoritmo [2]

Supongamos que hay dos suscriptores: Alice y Bob. Ambos suscriptores conocen unos dos números y , que no son secretos y también pueden ser conocidos por otros interesados. Para crear una clave secreta desconocida para los demás, ambos suscriptores generan grandes números aleatorios: Alice - número , Bob - número . Alicia luego calcula el resto de la división [3] (1): $gramo$ $pags$ $a$ $b$

A=g^a \bmod p

(una)

y se lo envía a Bob, y Bob calcula el resto de la división (2):

B=g^b \bmod p

(2)

y se lo da a Alicia. Se supone que un atacante puede obtener ambos valores, pero no modificarlos (es decir, no tiene forma de interferir con el proceso de transferencia).

En la segunda etapa, Alice, basándose en lo que tiene y recibió a través de la red , calcula el valor (3): $a$ $B$

B^a\bmod p=g^{ab}\bmod p

(3)

Bob, basándose en lo que tiene y recibió a través de la red , calcula el valor (4): $b$ $A$

A^b\bmod p=g^{ab}\bmod p

(cuatro)

Como puede ver, Alice y Bob obtuvieron el mismo número (5):

K=g^{ab}\bmod p

(5)

Pueden usarlo como clave secreta, ya que aquí el atacante se enfrentará a un problema prácticamente irresoluble (en un tiempo razonable) de calcular (3) o (4) de interceptado y , si los números , se eligen lo suficientemente grandes. El funcionamiento del algoritmo se muestra en la Figura [4] . $g^a \bmod p$ $g^b \bmod p$ $pags$ $a$ $b$

Cuando el algoritmo se está ejecutando, cada lado:

genera un número natural aleatorio a - la clave privada
junto con el lado remoto establece los parámetros públicos p y g (generalmente los valores p y g se generan en un lado y se pasan al otro), donde p es un número primo aleatorio (p-1)/2 también debe ser un número primo aleatorio (para mayor seguridad) [5] g es una raíz primitiva módulo p (también un número primo)
calcula la clave pública de A usando la transformación en la clave privada A = g a mod p
intercambia claves públicas con una parte remota
calcula la clave secreta compartida K , utilizando la clave pública de la parte remota B y su clave privada a K = B un mod p K es igual en ambos lados porque: B un mod p = (g b mod p) un mod p = g ab mod p = (g un mod p) b mod p = A b mod p

En implementaciones prácticas , se utilizan para a y b números del orden de 10100 y p del orden de 10300 . El número g no tiene que ser grande y por lo general tiene un valor dentro de los diez primeros.

Ejemplo

Eva es criptoanalista. Lee el reenvío de Bob y Alice, pero no cambia el contenido de sus mensajes [6] .

s = clave secreta. s = 2
g = raíz primitiva mod p. gramo = 5
p = número primo público. pag=23
a = Clave privada de Alice. un = 6
A = clave pública de Alice. A = g una mod p = 8
b = clave privada de Bob. b = 15
B = clave pública de Bob. segundo = gramo segundo mod pag = 19

Alicia
sabe	No sabe
pag = 23	b = ?
gramo = 5
un = 6
A = 5 6 módulo 23 = 8
B = 5 b mod 23 = 19
s = 19 6 módulo 23 = 2
s = 8 b mod 23 = 2
s = 19 6 mod 23 = 8 b mod 23
s = 2

Beto
sabe	No sabe
pag = 23	un = ?
gramo = 5
b = 15
B = 5 15 módulo 23 = 19
A = 5 a mod 23 = 8
s = 8 15 módulo 23 = 2
s = 19 a mod 23 = 2
s = 8 15 mod 23 = 19 a mod 23
s = 2

Alguna vez
sabe	No sabe
pag = 23	un = ?
gramo = 5	b = ?
	s = ?
A = 5 a mod 23 = 8
B = 5 b mod 23 = 19
s = 19 a mod 23
s = 8 b mod 23
s = 19 a mod 23 = 8 b mod 23

Algoritmo de Diffie-Hellman con tres o más participantes

El uso del algoritmo Diffie-Hellman no se limita a dos participantes. Se puede aplicar a un número ilimitado de usuarios. Considere una situación en la que Alice, Bob y Carol generan juntos una clave inicial. En este caso, la secuencia de acciones será la siguiente [7] :

Todos los cálculos se realizan módulo p

Las partes acuerdan los parámetros del algoritmo p y g
Las partes, Alice, Bob y Carol generan sus claves: a , b y c respectivamente.
Alice calcula g a mod p y se lo envía a Bob
Bob calcula (g a ) b mod p = g ab mod p y se lo envía a Carol
Carol calcula (g ab ) c mod p = g abc mod p y así obtiene la clave secreta compartida
Bob calcula g b mod p y se lo envía a Carol
Carol calcula (g b ) c mod p = g bc mod p y se lo envía a Alice
Alice calcula (g bc ) a mod p = g bca mod p = g abc mod p es el secreto compartido
Carol calcula g c mod p y se lo envía a Alice
Alice calcula (g c ) un mod p = g ca mod p y se lo envía a Bob
Bob calcula (g ca ) b mod p = g cab mod p = g abc mod p y también obtiene el secreto compartido

Si alguien escucha el canal de comunicación, podrá ver g a mod p , g b mod p , g c mod p , g ab mod p , g ac mod p y g bc mod p , pero no lo hará. ser capaz de reproducir g abc mod p usando cualquier combinación de estos números.

Para que este algoritmo se aplique de manera efectiva a un gran grupo de personas, se deben observar dos principios básicos:

La transferencia de clave debe comenzar con una clave "en blanco" g. Todo el secreto es aumentar una vez el valor actual del indicador de cada participante;
Cualquier valor intermedio puede divulgarse públicamente, pero el valor final es una clave secreta que nunca debe divulgarse públicamente. Así, cada usuario recibe su propia copia de la clave secreta.

Cifrado de clave pública

El algoritmo Diffie-Hellman también se puede utilizar en el cifrado de clave pública. En este caso, el esquema general sigue siendo similar al anterior, pero con ligeras diferencias. Alice no pasa los valores de p, g y A directamente a Bob, sino que los publica por adelantado como su clave pública. Bob hace su parte del cálculo, luego cifra el mensaje con un algoritmo simétrico utilizando K como clave y envía el texto cifrado a Alice junto con el valor de B.

En la práctica, el algoritmo de Diffie-Hellman no se usa de esta manera. En esta área, el algoritmo de clave pública dominante es RSA. Esto se debe más a consideraciones comerciales, ya que fue RSA Data Security quien creó la autoridad de certificación. Además, el algoritmo Diffie-Hellman no se puede utilizar al firmar certificados [4] .

Obtener una clave sin transmitir una clave

Si existe una comunidad de usuarios, cada uno de los usuarios puede publicar la clave pública X= mod n en una base de datos común. Si Alice quiere comunicarse con Bob, necesita obtener la clave pública de Bob y generar su secreto compartido. Alice puede cifrar el mensaje con la clave privada generada y enviárselo a Bob. Bob extraerá la clave pública de Alice y encontrará el secreto compartido. $g^{x}$

Cada par de usuarios puede usar su propia clave secreta única sin requerir ningún intercambio de datos entre usuarios. En este caso, todas las claves públicas deben autenticarse para excluir al "hombre en el medio" [4] .

Fuerza criptográfica

La fuerza criptográfica del algoritmo Diffie-Hellman (es decir, la complejidad de calcular p, g y ) se basa en la complejidad esperada del problema del logaritmo discreto. $K = g^{ab} \bmod p$ $A = g^a \bmod p$ $B = g^b \bmod p$

El Protocolo Diffie-Hellman es excelente para resistir un ataque pasivo, pero si se implementa un ataque de intermediario, no resistirá. De hecho, en el protocolo, ni Alice ni Bob pueden determinar de forma fiable quién es su interlocutor, por lo que es muy posible imaginar un caso en el que Bob y Alice establecieran una relación con Mallory, que finge ser Bob para Alice, y Alice se presenta. a Bob Y luego, en lugar del protocolo Diffie-Hellman, obtenemos algo similar a lo siguiente:

Paso	Alicia	Mallory	Frijol
una	g un →	g un
2	g norte ←	gn_ _
	g un	g un
3		gramo metro →	g m
cuatro		g b ←	gb_ _
		gmb _	gmb _

Es decir, Mallory obtiene una clave compartida con Alice (que cree que es Bob) y una clave compartida con Bob (que cree que es Alice). Y, por lo tanto, puede recibir de Alice cualquier mensaje para Bob, descifrarlo con una clave, leerlo, cifrarlo con una clave y enviárselo a Bob. Por lo tanto, la falsificación puede pasar desapercibida durante mucho tiempo [3] .

El problema de Diffie-Hellman y el problema del logaritmo discreto

La fuerza de la clave compartida en el protocolo Diffie-Hellman se asegura calculando el valor de los números dados y . Este problema se denomina problema computacional de Diffie-Hellman [8] . $g^{ab}{\bmod {p))$ $g^a$ $g ^ b$

Problema computacional de Diffie-Hellman (en un campo finito)

DATOS INICIALES: desq : descripción del campo objetivo

F_q

F_q

; g∈ es un elemento generador del grupo

F_q^*

F_q^*

; , ∈ , donde 0 < a, b < q.

Georgia

g_b

F_q^*

RESULTADO:

g^{ab}

Tal formulación es una formulación general del problema en un campo finito ; representa el caso general; para Diffie-Hellman, se usa un caso especial. Si el problema de Diffie-Hellman fuera fácil de resolver, entonces el valor se podría encontrar conociendo los números , y , que son parte del protocolo. Suponiendo que el enemigo tiene la capacidad de interceptar información, se debe suponer que estos números no son un secreto para él. El problema de Diffie-Hellman se basa en la complejidad de calcular el logaritmo discreto [1] . $F_q$ $g^{ab}{\bmod {p))$ $pags$ $gramo$ $g^a$ $g ^ b$

El problema del logaritmo discreto (en un campo finito)

DATOS INICIALES: desq : descripción del campo objetivo

F_q

F_q

; g∈ es un elemento generador del grupo

F_q^*

F_q^*

; h ∈

{}_T

F_q^*

RESULTADO: Un número único a < q que satisface la condición h = .

g^a

Un número entero a se denota como h.

log_g

El logaritmo discreto es similar al logaritmo habitual en el campo de los números reales. Sin embargo, a diferencia del último problema, en el que la solución es aproximada, el problema de cálculo del logaritmo discreto tiene solución exacta.

Como ya ha quedado claro, la teoría de la complejidad computacional está en el corazón de la criptografía moderna. Esto significa que la fortaleza de los criptosistemas de clave pública es condicional y depende de la complejidad de resolver ciertos problemas. Todo esto lleva al hecho de que el problema de Diffie-Hellman y el problema del logaritmo discreto se consideran intratables.

Es intuitivamente claro que la complejidad de resolver estos problemas depende tanto del tamaño del campo Fq como de la elección de los parámetros (parámetro público g y números secretos a y b). Obviamente, las versiones pequeñas de estos problemas tienen solución. La información obtenida nos permite formular supuestos exactos sobre la insolubilidad del problema de Diffie-Hellman y el problema del logaritmo discreto.

Supuesto 1 - Condiciones para la insolubilidad del problema de Diffie-Hellman

Un algoritmo para resolver el problema de Diffie-Hellman es un algoritmo polinomial probabilístico A con ventaja ε > 0:

ε = Prob[ A(desc( ), g, , )].

g^{ab}

\flecha izquierda larga

F_q

g^a

g ^ b

donde los datos de entrada A se especifican en la definición (problema computacional de Diffie-Hellman) (en el campo final).

Sea IG un generador de variantes que recibe como entrada un número , cuyo tiempo de ejecución es un polinomio en el parámetro k, y el resultado es 1) desq( ), donde |q| = k, y 2) el elemento generador g ∈ . $1 ^ k$ $F_q$ $F_q^*$

Diremos que el generador IG cumple las condiciones de insolubilidad del problema de Diffie-Hellman si, para variantes de IG( ), no existe un algoritmo de solución con ventaja ε > 0 que no sea despreciable frente a todos los números suficientemente grandes k. $1 ^ k$

Supuesto 2 - Condiciones para la insolubilidad del problema del logaritmo discreto

Un algoritmo para resolver el problema del logaritmo discreto es un algoritmo polinomial probabilístico A con ventaja ε > 0:

ε = Prob[ A(desc( ), g, h)]

registro

\flecha izquierda larga

F_q

donde los datos de entrada A se especifican en la definición (problema computacional de Diffie-Hellman) (en el campo final).

En otras palabras, aquí se asume que casi todas las variantes suficientemente grandes de estos problemas en campos finitos no tienen un algoritmo de solución eficiente. La proporción de variantes débiles de estos problemas que pueden resolverse es insignificante.

Crítica

La elección de los parámetros es importante para la seguridad del protocolo. Muchas implementaciones usan una pequeña cantidad de conjuntos de parámetros de algoritmos populares. En 2016 se presentó un trabajo que mostraba la posibilidad de preparar campos finitos especiales para el algoritmo Diffie-Hellman (DH). El número primo p de una forma especial elegida por los investigadores (1024 bits de tamaño) parece normal para los usuarios, pero simplifica la complejidad de los cálculos utilizando el método SNFS para resolver el problema del logaritmo discreto en varios órdenes de magnitud. Para combatir el ataque, se propone aumentar el tamaño del módulo a 2048 bits [9] [10] .

Véase también

Notas

↑ 1 2 Diffie W. , Hellman M. E. Nuevas direcciones en criptografía // IEEE Trans . inf. Teoría / F. Kschischang - IEEE , 1976. - Vol. 22, edición. 6.- Pág. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
↑ Intelecto. Cómo funciona el cifrado asimétrico en lenguaje sencillo Archivado el 4 de febrero de 2018 en Wayback Machine . 20 de mayo de 2012.
↑ 1 2 Bruce Schneier "Criptografía aplicada"
↑ 1 2 3 Métodos asimétricos de cifrado Capítulo 8 ("Cifrado de clave pública", "Intercambio de claves sin intercambio de claves", "Seguridad criptográfica", "Problema de Diffie-Hellman y problema del logaritmo discreto")
↑ Bruce Schneier "Criptografía aplicada" Capítulo 22 párrafo 22.1
↑ Aparato y método criptográfico Martin E. Hellman, Bailey W. Diffie y Ralph C. Merkle, Patente de EE. UU. n.º 4.200.770, 29 de abril de 1980)
↑ Resumen de ANSI X9.42: Acuerdo de claves simétricas usando criptografía de logaritmos discretos[enlace muerto] (archivo PDF de 64K) (Descripción de los estándares ANSI 9)
↑ Intercambio de claves Diffie-Hellman - La explicación de un no matemático por Keith Palmgren
↑ La NSA podría poner "trampillas" indetectables en millones de claves criptográficas. La técnica permite a los atacantes descifrar pasivamente los datos protegidos por Diffie-Hellman. (inglés) , ARS Technica (11 de octubre de 2016). Archivado desde el original el 13 de octubre de 2016. Consultado el 13 de octubre de 2016.
↑ Josué frito; Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. Cálculo de logaritmos discretos SNFS ocultos en kilobits . Eprint IACR (2016). Consultado el 13 de octubre de 2016. Archivado desde el original el 13 de octubre de 2016.

Fuentes

Bruce Schneier. Criptografía aplicada
Mao, V. Criptografía moderna: teoría y práctica. : Por. De inglés. M.: Editorial Williams, 2005. - 768 p. : enfermo. — Paralelo. teta. inglés Cifrado - métodos asimétricos. Capítulo 8 ("Cifrado de clave pública", "Intercambio de clave sin intercambio de clave", "Seguridad criptográfica", "Problema de Diffie-Hellman y problema de logaritmo discreto")
Dieter Gollmann (2006). Seguridad informática Segunda edición West Sussex, Inglaterra: John Wiley & Sons, Ltd.
T. Kivinen; M. Kojo, Seguridad de Comunicaciones SSH. Más grupos modulares exponenciales (MODP) Diffie-Hellman para intercambio de claves de Internet (IKE) ( TXT). Pista de Normas . Consejo de Ingeniería de Internet (mayo de 2003). — Los grupos de números abiertos estándar p y g recomendados por el Grupo de trabajo de ingeniería de Internet (IETF). Fecha de acceso: 15 de febrero de 2016.
La posibilidad del cifrado digital no secreto JH Ellis, enero de 1970.
Cifrado no secreto usando un campo finito MJ Williamson, 21 de enero de 1974.
Reflexiones sobre el cifrado no secreto más barato MJ Williamson, 10 de agosto de 1976.
Nuevas direcciones en criptografía W. Diffie y ME Hellman, IEEE Transactions on Information Theory, vol. IT-22, nov. 1976, págs.: 644-654.
Aparato y método criptográfico Martin E. Hellman, Bailey W. Diffie y Ralph C. Merkle, patente de EE. UU. n.º 4.200.770, 29 de abril de 1980
La historia del cifrado no secreto [enlace muerto] JH Ellis 1987 (archivo PDF de 28K) (versión HTML [enlace muerto])
Los primeros diez años de criptografía de clave pública Whitfield Diffie, Proceedings of the IEEE, vol. 76, núm. 5, mayo de 1988, págs.: 560-577 (archivo PDF de 1,9 MB)
Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Manual de Criptografía Aplicada Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7 . (Disponible en linea)
Singh, Simon (1999) The Code Book: la evolución del secreto de Mary Queen of Scots a la criptografía cuántica Nueva York: Doubleday ISBN 0-385-49531-5
Una descripción general de la criptografía de clave pública Martin E. Hellman, IEEE Communications Magazine, mayo de 2002, pp: 42-49. (archivo PDF de 123kB)
Intercambio de claves Diffie-Hellman explicado en 5 minutos
Entrevista de historia oral con Martin Hellman, Instituto Charles Babbage, Universidad de Minnesota. El destacado erudito en criptografía *Martin Hellman analiza las circunstancias y los conocimientos fundamentales de su invención de la criptografía de clave pública con los colaboradores Whitfield Diffie y Ralph Merkle en la Universidad de Stanford a mediados de la década de 1970.
RFC 2631 - Método de Acuerdo Clave Diffie-Hellman E. Rescorla Junio 1999.
Resumen de ANSI X9.42: Acuerdo de claves simétricas mediante criptografía de logaritmo discreto [enlace muerto] (archivo PDF de 64K) (Descripción de los estándares ANSI 9)
Intercambio de claves Diffie-Hellman: la explicación de un no matemático por Keith Palmgren
Módulo Crypt::DH Perl de CPAN
Demostración práctica de Diffie-Hellman
Implementación de C usando GNU Multiple Precision Arithmetic Library [enlace muerto]
Diffie Hellman en 2 lineas de Perl (usando dc)
Smart Account Management (SAcct) (usando el intercambio de claves DH para obtener la clave de sesión)
Charla de Martin Hellman en 2007, video de Google

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP