Tamaño de la clave privada Diffie-Hellman
Actualmente estoy escribiendo mi propia implementación de Diffie-Hellma n (esto no es para uso real. Esto es estrictamente para mí para comprender mejor el DH al hacerlo yo mismo).
Para el principal y el generador, estoy usando RFC 3526 , más específicamente el principal de 4096 bits.
Mi pregunta es, ¿existe una generación de enteros secretos estándar específica para Diffie-Hellman? Dado que la seguridad de los números enteros secretos (normalmente dos, pero DH admite más de una comunicación 1-1) es bastante crucial para la seguridad del intercambio de claves.
Respuestas
DHKE
En un Diffie-Hellman exponencial , denotado por DHKE, uno toma un grupo$G$ con un generador $g$ con su orden $n$.
Alice y Bob, durante el intercambio de claves, generan un número aleatorio $a$ y $b$ en el rango $a,b\in (1,n)$ y transmite $g^a$ y $g^b$ y finalmente, establecen la clave como $g^{ab}$ luego use un KDF para derivar una clave simétrica y un IV / nonce.
También existe la versión de curva elíptica de DHKE y se denota por ECDH y es más utilizada que la versión exponencial clásica.
principal
En DHKE, elegimos prime para ser un prime seguro, es decir $p = 2 \cdot q + 1$ con $q$también es un primo. los$q$se llama Sophie Germain prime .
Esta es una contramedida contra el algoritmo de Pohlig-Hellman que se beneficia del pequeño factor de$p-1$. Si se usa un cebado seguro, entonces los factores son$2$ y $q$. Tener un factor grande es una contramedida contra Pohlig-Hellman.
También está el grupo Schnorr con$p = r\,q + 1$. Esto puede considerarse como una generalización de los números primos de la salvia. La salvia prima es óptima.
Generación Prime
El enfoque ingenuo genera una prima $q$ luego compruebe la primordialidad de $2 \, q +1$( Menezes: Algoritmo 4.86 ). En pseudocódigo;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
Hay métodos más rápidos
Safe Prime Generation de doble velocidad de David Naccache, 2003
como sugiere el título, esto acelera el proceso en aproximadamente un factor de dos al probar ambos $2q + 1$ y $(q − 1)/2$ por lo primordial.
La idea es usar el primo aleatorio $p$ como prima segura o prima Sophie Germain;
do p = randomPrime(k-bit integer) while ((p − 1)/2 and 2p + 1 are composite)Safe Prime Generation con un tamiz combinado por Michael J. Wiener, 2003.
Propusieron tamizar pequeños primos hasta $2^{16}$. Esto proporciona$15x$ acelerar que el algoritmo ingenuo.
La idea comienza con esta observación; ambos$q$ y $q=2p+1$ debe ser congruente con $2$ modulo $3$. Por tanto, se pueden eliminar los candidatos con los que se$0$ modulo $3$ y $1$ modulo $3$.
Esto se puede generalizar a cualquier primo impar $r$. Eliminar$q$son conguruentes a $(r-1)/2$ modulo $r$ ya que en este caso $p$ es divisible $r$.
Tomar un juego $S$ todo primo impar $<B$. Luego$\prod_{r\in S}(r-2)/r$ de los candidatos sobrevivirán al tamiz.
Si $B=2^{16}$ se estima que puede producir $\approx \times 15$ acelerar.
Colisión
Ahora veremos la probabilidad de obtener el mismo número aleatorio si hay $k$personas que utilizan el mismo módulo DHKE. Estamos asumiendo que el$k$personas que utilizan el mismo generador de números aleatorios seguro (impredecible) para generar sus claves aleatorias. Para simplificar esto, podemos asumir que hay una persona que genera números aleatorios. En este caso, esto es completamente la paradoja del cumpleaños y en Criptografía vemos que este es el ataque de cumpleaños para encontrar una colisión con el 50%. Esta es una forma común de ver la colisión de las funciones hash.
Dejar $H$ ser el rango del generador de números aleatorios, y el $p$ representa la probabilidad que queremos, entonces $n(p; H)$ ser el menor número de valores que tenemos que elegir;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
En el caso clásico de colisión de hash, establecemos $p=1/2$ y esto se acerca
$$n(0.5;H) \approx 1.1774 \sqrt H$$ y generalmente representamos como $\mathcal{O}(\sqrt{H})$
Ahora, veamos algunos números reales.
Primo de 2048 bits
Asumir que $n$ es un número de 2048 bits, recuerda $n$ fue la orden del generador $g$. Luego
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
Con 50% de probabilidad $$n(0.5;2^{2048})\approx 2^{1204}$$
Como resultado, necesita generar $2^{1204}$números aleatorios para volver a acertar uno con el 50%. No factible.
4096 bits primos
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
Con 50% de probabilidad $$n(0.5;2^{4096})\approx 2^{2048}$$
Como resultado, necesita generar $2^{2048}$números aleatorios para volver a acertar uno con el 50%. No factible. Calcule previamente la tabla dlog.
Dado que los módulos están predeterminados por los estándares, se puede argumentar que algunas organizaciones con superpoderes construyeron alguna tabla DLog para el módulo.
Esto tampoco es un peligro. Supongamos que pueden construir una mesa hasta$2^{64}$ entonces la probabilidad de tu acierto aleatorio es $$\frac{\ell \, 2^{64}}{2^{2048}}$$ con $\ell$tratar. Ponga el posible número de generación de claves de su grupo en$\ell$. Entonces, 2048 bits es un número realmente grande con el que lidiar.