Curva elíptica Diffie-Hellman

Protocolo de acuerdo clave

El protocolo Diffie–Hellman de curva elíptica ( ECDH ) es un protocolo de acuerdo de claves que permite a dos partes, cada una con un par de claves pública-privada de curva elíptica , establecer un secreto compartido a través de un canal inseguro . ^{[1] [2] [3]} Este secreto compartido puede usarse directamente como clave o para derivar otra clave . La clave, o la clave derivada, puede usarse luego para cifrar comunicaciones posteriores utilizando un cifrado de clave simétrica . Es una variante del protocolo Diffie–Hellman que utiliza criptografía de curva elíptica .

Protocolo de establecimiento de claves

El siguiente ejemplo ilustra cómo se establece una clave compartida. Supongamos que Alice quiere establecer una clave compartida con Bob , pero el único canal disponible para ellos puede ser interceptado por un tercero. Inicialmente, se deben acordar los parámetros del dominio (es decir, en el caso principal o en el caso binario). Además, cada parte debe tener un par de claves adecuado para la criptografía de curva elíptica, que consiste en una clave privada (un entero seleccionado aleatoriamente en el intervalo ) y una clave pública representada por un punto (donde , es decir, el resultado de sumarse a sí mismo veces). Sea el par de claves de Alice y el par de claves de Bob . Cada parte debe conocer la clave pública de la otra parte antes de la ejecución del protocolo. ${\displaystyle (p,a,b,G,n,h)}$ ${\displaystyle (m,f(x),a,b,G,n,h)}$ ${\displaystyle d}$ ${\displaystyle [1,n-1]}$ ${\displaystyle Q}$ ${\displaystyle Q=d\cdot G}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle (d_{\text{A}},Q_{\text{A}})}$ ${\displaystyle (d_{\text{B}},Q_{\text{B}})}$

Alice calcula el punto . Bob calcula el punto . El secreto compartido es (la coordenada x del punto). La mayoría de los protocolos estandarizados basados ​​en ECDH derivan una clave simétrica mediante el uso de alguna función de derivación de clave basada en hash. ${\displaystyle (x_{k},y_{k})=d_{\text{A}}\cdot Q_{\text{B}}}$ ${\displaystyle (x_{k},y_{k})=d_{\text{B}}\cdot Q_{\text{A}}}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k}}$

El secreto compartido calculado por ambas partes es igual, porque . ${\displaystyle d_{\text{A}}\cdot Q_{\text{B}}=d_{\text{A}}\cdot d_{\text{B}}\cdot G=d_{\text{B}}\cdot d_{\text{A}}\cdot G=d_{\text{B}}\cdot Q_{\text{A}}}$

La única información sobre su clave que Alice expone inicialmente es su clave pública. Por lo tanto, ninguna parte excepto Alice puede determinar la clave privada de Alice (Alice, por supuesto, la conoce porque la ha seleccionado), a menos que esa parte pueda resolver el problema del logaritmo discreto de la curva elíptica . La clave privada de Bob es igualmente segura. Ninguna parte que no sea Alice o Bob puede calcular el secreto compartido, a menos que esa parte pueda resolver el problema de Diffie-Hellman de la curva elíptica .

Las claves públicas son estáticas (y confiables, por ejemplo, a través de un certificado) o efímeras (también conocidas como ECDHE , donde la "E" final significa "efímera"). Las claves efímeras son temporales y no necesariamente autenticadas, por lo que si se desea autenticación, se deben obtener garantías de autenticidad por otros medios. La autenticación es necesaria para evitar ataques de intermediarios . Si una de las claves públicas de Alice o Bob es estática, entonces se frustran los ataques de intermediarios. Las claves públicas estáticas no proporcionan ni confidencialidad hacia adelante ni resiliencia a la suplantación de identidad por compromiso de clave, entre otras propiedades de seguridad avanzadas. Los poseedores de claves privadas estáticas deben validar la otra clave pública y deben aplicar una función de derivación de clave segura al secreto compartido Diffie–Hellman sin procesar para evitar filtrar información sobre la clave privada estática. Para esquemas con otras propiedades de seguridad, consulte MQV .

Si Alice elige maliciosamente puntos de curva no válidos para su clave y Bob no valida que los puntos de Alice sean parte del grupo seleccionado, ella puede recolectar suficientes residuos de la clave de Bob para derivar su clave privada. Se descubrió que varias bibliotecas TLS eran vulnerables a este ataque. ^[4]

El secreto compartido se distribuye uniformemente en un subconjunto de tamaño . Por este motivo, el secreto no se debe utilizar directamente como clave simétrica, sino que se puede utilizar como entropía para una función de derivación de claves. ${\displaystyle [0,p)}$ ${\displaystyle (n+1)/2}$

Acuerdo clave Diffie-Hellman sobre las curvas de Montgomery

Sea tal que . La curva elíptica de la forma Montgomery es el conjunto de todos los que satisfacen la ecuación junto con el punto en el infinito denotado como . Esto se llama la forma afín de la curva. El conjunto de todos los puntos -racionales de , denotado como es el conjunto de todos los que satisfacen junto con . Bajo una operación de adición adecuadamente definida, es un grupo con como elemento identidad. Se sabe que el orden de este grupo es un múltiplo de 4. De hecho, normalmente es posible obtener y tales que el orden de es para un primo . Para discusiones más extensas de las curvas de Montgomery y su aritmética, se puede seguir. ^{[5] [6] [7]} ${\displaystyle A,B\in F_{p}}$ ${\displaystyle B(A^{2}-4)\neq 0}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle (x,y)\in F_{p}\times F_{p}}$ ${\displaystyle By^{2}=x(x^{2}+Ax+1)}$ ${\displaystyle \infty }$ ${\displaystyle F_{p}}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle E_{M,A,B}(F_{p})}$ ${\displaystyle (x,y)\in F_{p}\times F_{p}}$ ${\displaystyle By^{2}=x(x^{2}+Ax+1)}$ ${\displaystyle \infty }$ ${\displaystyle E_{M,A,B}(F_{p})}$ ${\displaystyle \infty }$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle 4q}$ ${\displaystyle q}$

Para eficiencia computacional, es preferible trabajar con coordenadas proyectivas. La forma proyectiva de la curva de Montgomery es . Para un punto en , el mapa de coordenadas es el siguiente: ^[7] si y si . Bernstein ^{[8] [9]} introdujo el mapa de la siguiente manera: que se define para todos los valores de y en . Siguiendo a Miller, ^[10] Montgomery ^[5] y Bernstein, ^[9] el acuerdo de claves de Diffie-Hellman se puede llevar a cabo en una curva de Montgomery de la siguiente manera. Sea un generador de un subgrupo de orden primo de . Alice elige una clave secreta y tiene clave pública ; Bob elige una clave secreta y tiene clave pública . La clave secreta compartida de Alice y Bob es . Usando computadoras clásicas, el método más conocido para obtener de y requiere aproximadamente tiempo usando el algoritmo rho de Pollards . ^[11] ${\displaystyle E_{M,A,B}}$ ${\displaystyle BY^{2}Z=X(X^{2}+AXZ+Z^{2})}$ ${\displaystyle P=[X:Y:Z]}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x(P)=[X:Z]}$ ${\displaystyle Z\neq 0}$ ${\displaystyle x(P)=[1:0]}$ ${\displaystyle P=[0:1:0]}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{0}(X:Z)=XZ^{p-2}}$ ${\displaystyle X}$ ${\displaystyle Z}$ ${\displaystyle F_{p}}$ ${\displaystyle Q}$ ${\displaystyle E_{M,A,B}(F_{p})}$ ${\displaystyle s}$ ${\displaystyle x_{0}(sQ)}$ ${\displaystyle t}$ ${\displaystyle x_{0}(tQ)}$ ${\displaystyle x_{0}(stQ)}$ ${\displaystyle x_{0}(stQ)}$ ${\displaystyle Q,x_{0}(sQ)}$ ${\displaystyle x_{0}(tQ)}$ ${\displaystyle O(p^{1/2})}$

El ejemplo más famoso de curva de Montgomery es Curve25519 que fue introducida por Bernstein. ^[9] Para Curve25519, y . La otra curva de Montgomery que forma parte de TLS 1.3 es Curve448 que fue introducida por Hamburg. ^[12] Para Curve448, y . Se han propuesto un par de curvas de Montgomery denominadas M[4698] y M[4058] competitivas con Curve25519 y Curve448 respectivamente en. ^[13] Para M[4698], y para M[4058], . En el nivel de seguridad de 256 bits, se han propuesto tres curvas de Montgomery denominadas M[996558], M[952902] y M[1504058] en. ^[14] Para M[996558], , para M[952902], y para M[1504058], respectivamente. Aparte de estas dos, se pueden encontrar otras propuestas de curvas de Montgomery en. ^[15] ${\displaystyle p=2^{255}-19,A=486662}$ ${\displaystyle B=1}$ ${\displaystyle p=2^{448}-2^{224}-1,A=156326}$ ${\displaystyle B=1}$ ${\displaystyle p=2^{251}-9,A=4698,B=1}$ ${\displaystyle p=2^{444}-17,A=4058,B=1}$ ${\displaystyle p=2^{506}-45,A=996558,B=1}$ ${\displaystyle p=2^{510}-75,A=952902,B=1}$ ${\displaystyle p=2^{521}-1,A=1504058,B=1}$

Software

• Curve25519 es un conjunto popular de parámetros de curva elíptica y una implementación de referencia de Daniel J. Bernstein en C. También están disponibles enlaces e implementaciones alternativas.
• Curve448 , una curva elíptica que potencialmente ofrece 224 bits de seguridad, desarrollada por Mike Hamburg de Rambus Cryptography Research.
• La aplicación de mensajería LINE ha utilizado el protocolo ECDH para su cifrado de extremo a extremo "Letter Sealing" de todos los mensajes enviados a través de dicha aplicación desde octubre de 2015. ^[16]
• El protocolo Signal utiliza ECDH para obtener seguridad posterior a la vulneración. Existen implementaciones de este protocolo en Signal , WhatsApp , Facebook Messenger y Skype .

Véase también

• Criptografía de curva elíptica
• Intercambio de claves Diffie-Hellman
• Secreto de reenvío

Referencias

1. NIST, Publicación especial 800-56A, Recomendación para esquemas de establecimiento de claves por pares utilizando criptografía de logaritmo discreto, marzo de 2006.
2. Certicom Research, Estándares para criptografía eficiente, SEC 1: Criptografía de curva elíptica, versión 2.0, 21 de mayo de 2009.
3. Criptografía Suite B de la NSA, Guía para implementadores de Suite B de NIST SP 800-56A Archivado el 6 de marzo de 2016 en Wayback Machine , 28 de julio de 2009.
4. Tibor Jager; Jorg Schwenk; Juraj Somorovsky (4 de septiembre de 2015). "Ataques prácticos de curvas no válidas en TLS-ECDH" (PDF) . Simposio Europeo sobre Investigación en Seguridad Informática (ESORICS'15) .
5. Montgomery, Peter L. "Aceleración de los métodos de factorización de Pollard y de curva elíptica" (PDF) . Matemáticas de la computación, 48(177):243–264, 1987.
6. Bernstein, Daniel J.; Lange, Tanja. "Curvas de Montgomery y la escalera de Montgomery". En Joppe W. Bos y Arjen K. Lenstra, editores, Temas de teoría de números computacionales inspirados por Peter L. Montgomery, páginas 82-115. Cambridge University Press, 2017.
7. Costello, Craig; Smith, Benjamin. "Curvas de Montgomery y su aritmética: el caso de grandes campos característicos". J. Cryptographic Engineering, 8(3):227–240, 2018.
8. Bernstein, Daniel J. "¿Podemos evitar las pruebas de cero en aritmética rápida de curvas elípticas?" (PDF) .
9. Bernstein, Daniel J. "Curve25519: Nuevos récords de velocidad de Diffie-Hellman". En: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlín, Heidelberg.
10. Miller, Victor S. "Uso de curvas elípticas en criptografía". En Advances in Cryptology - CRYPTO'85, Santa Barbara, California, EE. UU., 18-22 de agosto de 1985, Actas, páginas 417-426. Springer Berlin Heidelberg, 1985.
11. Pollard, John M. "Métodos de Monte Carlo para el cálculo de índices mod p" (PDF) . Matemáticas de la computación, 32:918–924, 1978.
12. Hamburg, Mike. "Ed448-goldilocks, una nueva curva elíptica". Archivo de publicaciones electrónicas de criptología de la ACR, 2015:625, 2015.
13. Nath, Kaushik; Sarkar, Palash. "Compensaciones entre seguridad y eficiencia para el algoritmo Diffie-Hellman de curva elíptica en los niveles de seguridad de 128 y 224 bits". J Cryptogr Eng 12, 107–121 (2022).Código disponible en https://github.com/kn-cs/x25519
14. Nath, Kaushik; Sarkar, Palash. "Cálculo Diffie-Hellman de curva elíptica eficiente en el nivel de seguridad de 256 bits". IET Information Security, 14(6):633640, 2020.Código disponible en https://github.com/kn-cs/mont256-dh y https://github.com/kn-cs/mont256-vec
15. Bernstein, Daniel J.; Lange, Tanja. "Safecurves: elección de curvas seguras para la criptografía de curva elíptica" . Consultado el 15 de abril de 2024 .
16. JI (13 de octubre de 2015). «Nueva generación de mensajería segura: «Sellado de cartas»». Blog de ingenieros de LINE . LINE Corporation. Archivado desde el original el 1 de febrero de 2019. Consultado el 5 de febrero de 2018 .