cryptography - que - Requisito del generador G de ser un módulo raíz primitivo p en el algoritmo Diffie Hellman

el gamal

Question

Después de buscar, me encontré confundido por el uso de P y G en el algoritmo de Diffie Hellman. Se requiere que P sea primo y G una raíz primitiva de P.

Entiendo que la seguridad se basa en la dificultad de factorizar el resultado de dos números primos muy grandes, así que no tengo ningún problema con eso. Sin embargo, parece que hay poca información disponible sobre el propósito de que G sea una raíz primitiva de P. ¿Puede alguien responder por qué existe este requisito (con referencias si es posible)? ¿Simplemente aumenta la seguridad? Dado que las claves compartidas se pueden crear con aparentemente cualquier combinación de p y g, incluso las que no son primarias, encuentro esto intrigante. Seguramente solo puede ser por seguridad? Si es así, ¿cómo lo aumenta?

Gracias por adelantado

Daniel

Answer 1

La seguridad de Diffie-Hellman no se basa en la dificultad de factorizar. Se basa en la dificultad (asumida) de calcular los logaritmos discretos generales.

g debe ser una raíz primitiva de p para que el algoritmo sea correcto y utilizable. Asegura que para cada número 0 <= x <p , hay un valor distinto de g ^x mod p . Es decir, asegura que g puede "generar" cada valor en el campo finito.

Answer 2

No hay ningún requisito de que el generador g utilizado para Diffie-Hellman sea una raíz primitiva, ni siquiera es una opción común. Mucho más popular es elegir g de manera que genere un subgrupo de orden principal. Es decir, el orden de g es un primo q, que es un gran factor primo de p-1.

Por ejemplo, los grupos Diffie-Hellman propuestos para IKE se han elegido de manera que p es un primo seguro yg genera el subgrupo de orden (p-1) / 2.

Una motivación para elegir g como generador de un gran subgrupo de orden principal es que esto permite tomar la suposición decisional de Diffie-Hellman . Esta suposición no se cumple si g es una raíz primitiva, y eso hace que el análisis de los protocolos implementados sea algo más difícil.

Answer 3

Si g no es una raíz primitiva de p , g solo generará un subgrupo de GF _p . Esto tiene consecuencias para las propiedades de seguridad del sistema: la seguridad del sistema solo será proporcional al orden de g en GF _{p en} lugar de proporcional al orden completo de GF _p .

Para tomar un pequeño ejemplo: seleccione p = 13 yg = 3.

El orden de 3 en GF_13 es 3 (3 ^ 1 = 3, 3 ^ 2 = 9, 3 ^ 3 = 1).

Siguiendo los pasos usuales de Diffie-Hellman, Alice y Bob deberían seleccionar enteros a , b entre 1 y p -1 y calcular resp. A = g ^a y B = g ^b . Para forzar la fuerza bruta, un atacante debe esperar probar todos los valores posibles de a (o b ) entre 1 y p -1 hasta que encuentre un valor que produzca A (o B ). Pero como g no era un módulo de raíz primitivo p , solo tiene que probar los valores 1, 2 y 3 para encontrar una solución a '' para que A = g ^a'' . Y el secreto es s = g ^ab = (g ^a ) ^b = (g ^{a ''} ) ^b = g ^a''b = (g ^b ) ^a'' = B ^{a ''} , que el atacante ahora puede calcular.