Conceptos básicos de criptografía 2: análisis de los principios de la criptografía de curva elíptica
Lo primero que hay que tener en cuenta es que las curvas elípticas no son elipses. La ecuación elíptica es la siguiente:
La ecuación de la curva elíptica que generalmente discutimos es una ecuación cúbica binaria, que tiene muchas formas en el sistema de criptografía de curva elíptica. La más comúnmente utilizada es la siguiente fórmula general de Weierstrass (la curva25519 y otros tipos de curvas elípticas no se analizan en este artículo):
La razón por la que se llama curva elíptica es porque la ecuación de curva Es similar a la fórmula integral para encontrar la longitud del arco de una elipse. Es fácil ver en la ecuación de la curva y en la imagen que la curva elíptica es simétrica con respecto al eje X. La razón por la que el predicado no es igual a cero es que la curva elíptica no tiene puntos singulares, es decir, es suave y diferenciable en todas partes, por lo que se pueden realizar operaciones de suma en la curva elíptica. A continuación se muestran algunas curvas elípticas adecuadas para el cifrado, entre las que se encuentran.
El algoritmo de cifrado de curva elíptica involucra teoría de grupos, campos finitos, etc. en matemáticas. Esta sección presenta brevemente las teorías matemáticas relevantes. También puede omitir e ir directamente a la Sección 3 y luego buscarla cuando encuentre términos relacionados.
Antes de hablar de grupos, hablemos de colecciones. Un conjunto simplemente significa juntar un montón de cosas, como un conjunto de números naturales. Por supuesto, no basta con tener un montón de cosas. La interacción entre las cosas puede describir mejor el mundo. Por lo tanto, el conjunto de números naturales se puede derivar del conjunto de números enteros mediante operaciones de suma y resta, y el conjunto de números enteros se puede derivar del conjunto de números racionales mediante multiplicación y división. Luego, el conjunto de números reales se puede derivar mediante. la suma de números irracionales y la raíz cuadrada de números negativos se pueden derivar del conjunto de números complejos. Un grupo es un conjunto y una operación binaria.
Si se cumple la ley conmutativa, el grupo se denomina grupo abeliano.
Según la definición de grupo, la operación de suma de números enteros es un grupo, y también es un grupo abeliano. La operación de suma de números naturales no es un grupo. La operación de suma de enteros forma un grupo porque satisface la definición de grupo: la propiedad de cierre, la ley asociativa y la ley conmutativa de la suma de enteros son todas verdaderas. El elemento de identidad en las operaciones de suma de enteros es 0. Todos los números enteros n tienen inversos aditivos -n.
En criptografía, generalmente se requiere un grupo finito, que se define de la siguiente manera:
Para que una estructura admita cuatro aritméticas básicas (es decir, suma, resta, multiplicación y división) al mismo tiempo, necesitamos una estructura que contenga el conjunto de grupos aditivos y multiplicativos, este es el campo. Cuando un conjunto es un dominio, podemos realizar operaciones aritméticas básicas sobre él.
Por lo tanto, los elementos en el campo solo necesitan formar un grupo aditivo y un grupo multiplicativo y satisfacer la ley distributiva. Debido a que los elementos del grupo tienen elementos inversos, la resta/división se puede convertir en inverso. Implementación de elementos de los elementos de suma/multiplicación. El conjunto de números reales es un campo. El elemento identidad en el grupo aditivo es 0, y cada número real tiene un elemento inverso aditivo. El elemento identidad en el grupo multiplicativo es , y cada número real distinto de cero tiene un elemento inverso multiplicativo. . El conjunto de números enteros no es un campo, porque la mayoría de los elementos no tienen inversos multiplicativos y no pueden formar un grupo multiplicativo.
En criptografía normalmente sólo nos interesan los campos con elementos finitos, que se denominan campos finitos. Lo que usamos a menudo en campos finitos es el campo de números primos. El llamado campo de números primos es un campo finito con un número primo. Por ejemplo, cuando p es un número primo, el anillo de enteros es un campo de número primo, que se puede escribir como. Para realizar operaciones aritméticas en el campo de los números primos, es necesario obedecer las reglas del anillo de enteros, es decir, la suma es la suma módulo p y la multiplicación es la multiplicación módulo p.
Por ejemplo, existen:
Después de que los puntos de la curva elíptica se someten a una operación de suma específica, la curva elíptica puede formar un grupo en el dominio de los números reales.
Punto infinito: Define un punto infinito, es decir, cualquier recta perpendicular al eje X que pase por cualquier punto de la elipse pasa por este punto.
Algunas personas pueden preguntarse si las líneas rectas perpendiculares al eje X son líneas paralelas. ¿Por qué se pueden definir como que pasan por el punto? Porque en geometría no euclidiana, se puede considerar que las líneas paralelas se cruzan en un punto en el infinito.
Suma de puntos de curva elíptica: el punto de intersección de la línea recta en la curva elíptica que pasa por los dos puntos y la curva elíptica se registra como , según la definición hay y . Luego defina la suma de puntos de curva elíptica:, es decir, el resultado de la suma es otro punto de intersección de la línea recta que pasa por el punto y es perpendicular al eje X y la curva elíptica. En pocas palabras, es el punto de simetría de la. punto de intersección con respecto al eje X.
Grupo de curva elíptica: definido como el conjunto de puntos y la suma de puntos de la curva elíptica en el campo de números reales.
Se puede ver que los puntos de la curva elíptica forman un grupo en el Operación de suma de curvas elípticas. grupo abeliano. Después de agregar el elemento unitario, la ecuación de la curva elíptica cambia a:
Se puede saber por la definición que, por lo que la suma final solo necesita calcular el elemento inverso de la intersección. punto . Notas sobre varios casos especiales:
La sección anterior definió la suma de puntos en el sentido geométrico de las curvas elípticas, que deben convertirse en suma algebraica para facilitar el cálculo. Cabe señalar que esta no es una simple suma de las coordenadas de dos puntos.
Asumiendo la pendiente de la recta PQ y luego sustituyendo la ecuación de la recta en la curva, podemos obtener: , convertida a una fórmula estándar, según el teorema védico, se puede obtener si. Si desea conocer el proceso de derivación específico, consulte [ecuaciones cúbicas].
El cálculo de la pendiente debe distinguir entre dos situaciones. Cuando P = Q, simplemente encuentre la pendiente tangente (derivada) de la curva elíptica en el punto P:
Para casos especiales donde uno de ellos es un punto tangente, como por ejemplo, el método de cálculo se mantiene sin cambios y es fácil de obtener. Para casos especiales, la exactitud de la fórmula también se puede verificar utilizando la pendiente tangente.
En los algoritmos de cifrado reales, normalmente necesitamos realizar la suma de curvas elípticas varias veces para lograr un cifrado, como se muestra en la siguiente figura:
El proceso de punteado en la figura es:
En los algoritmos de cifrado reales, a menudo usamos un punto para superponerse, es decir, la línea recta inicial se convierte en la tangente de la curva elíptica, como la siguiente:
Definimos n sumas a un punto P para obtener nP, lo que se llama multiplicación escalar. Como en el ejemplo anterior.
Sin embargo, cuando n es muy grande, se necesita tiempo para realizar n sumas y existe un problema de eficiencia. Debido a que la suma de puntos de la curva elíptica forma un grupo abeliano en el dominio de los números reales y satisface la ley conmutativa y la ley asociativa, se puede optimizar mediante el algoritmo [Doblar y sumar]. Por ejemplo, su representación binaria es. Mediante optimización, solo necesita 7 multiplicaciones y 4 sumas, y la complejidad del tiempo se reduce a.
Esta es una buena función unidireccional, la dirección de avance es fácil de calcular, pero los cálculos de fuerza bruta y inversa son complejos.
Sea , entonces Q es la clave pública y n es la clave privada. Si desea descifrar la clave, el problema es "Q = nP, si se conocen P y Q, ¿cómo resolver n"? Este problema es relativamente difícil. Sin embargo, dado que la curva es continua en el dominio de los números reales, puede ser más fácil encontrar algunas reglas que descifrar. Además, no hay límite en el tamaño de los valores en el campo de números reales, y problemas como los números de punto flotante conducen a problemas de eficiencia computacional. En aplicaciones prácticas, las curvas elípticas a menudo se limitan a un dominio finito y las curvas se giran. en puntos discretos. Esto no solo facilita los cálculos sino que también aumenta la dificultad de descifrado.
Como se mencionó anteriormente, por seguridad y facilidad de implementación, la curva elíptica debe limitarse a un dominio finito, generalmente el dominio primo (es decir, el punto es un número primo). Entonces la solución se convierte en un problema de logaritmos discretos, que es mucho más difícil que el problema de logaritmos en una curva continua. La curva elíptica en el campo principal se define de la siguiente manera:
La siguiente es la imagen de la curva y . Se puede encontrar que la curva elíptica se convierte en un punto discreto y es simétrica con respecto a .
La definición de suma de puntos en curvas elípticas es la siguiente. En comparación con la fórmula en el campo de números reales, solo tiene más operaciones modulares.
El cálculo de la pendiente m también se divide en dos situaciones:
La suma de puntos de curvas elípticas en el campo principal todavía constituye un grupo abeliano. El elemento identidad sigue siendo el punto en el infinito, y el elemento inverso del elemento se convierte en . La ley conmutativa, la ley asociativa y la clausura se pueden demostrar mediante la suma modular y la multiplicación modular en el campo primo. La definición de suma de puntos de curva elíptica en el campo de números reales tiene un significado geométrico claro y es fácil de probar geométricamente. La curva elíptica no tiene un significado geométrico obvio en . La observación muestra que los tres puntos satisfacen. La prueba de la ley del grupo es demasiado engorrosa y se omite (de hecho, no se encontró una prueba simple).
Tomando la curva anterior como ejemplo, entonces están , y y están ambos en la curva elíptica. Gráficamente, en línea recta.
En un campo finito, los elementos del grupo aditivo de curva elíptica son finitos y el número de elementos es el orden del grupo.
Por ejemplo, una curva elíptica tiene elementos en el campo primo y el orden es 24 (23 puntos en el campo primo y 1 punto infinito si p es muy grande, el orden calculado mediante fuerza bruta es). Es difícil, pero afortunadamente usando [el algoritmo de Schoof] puedes calcular el orden del grupo en tiempo polinómico. Para calcular el número de puntos en una curva elíptica en un campo finito, consulte [Contar puntos en curvas elípticas].
El algoritmo de Schoof utiliza el teorema de Hasses. El teorema de Hasses da el rango del orden de la curva elíptica en. Se puede ver que cuando p es grande, el orden es relativamente cercano al valor de p.
Al igual que en el campo de números reales, se selecciona un punto P en el campo de números primos y luego la multiplicación nP se calcula como clave pública. Aún tomando como ejemplo, usamos la nueva fórmula de cálculo en el campo de números primos para calcular.
Se puede encontrar que el conjunto de puntos obtenido por la multiplicación escalar de P es un subconjunto del grupo de curva elíptica original, entonces es un subgrupo del grupo de curva elíptica original , y es un subgrupo cíclico. El número de elementos en un subgrupo se llama orden del subgrupo (el orden del subgrupo de ejemplo es 8) y el punto P se llama punto base o generador del subgrupo.
El subgrupo cíclico es la base del criptosistema de curva elíptica. Esperamos que cuantos más elementos haya en el subgrupo, mejor es particularmente importante cómo encontrar un subgrupo adecuado.
En primer lugar, necesitamos resolver un problema, es decir, dado el punto P en la curva elíptica, ¿cómo encontrar el orden del subgrupo generado después de la operación de multiplicación de P según el grupo de Lagrange? Teorema de la teoría, el orden del subgrupo es un divisor del orden del grupo principal. Se puede utilizar el siguiente método para resolver el orden del subgrupo generado por el punto P en la curva:
Tomando la curva de ejemplo como ejemplo, el orden del grupo principal es, luego el orden del subgrupo generado por el punto de la curva sólo puede ser . Para el punto, el orden del subgrupo generado por él es 8, y el orden del subgrupo generado por el punto es exactamente igual al orden del grupo principal 24.
En los algoritmos de cifrado, esperamos encontrar un subgrupo de orden superior. Sin embargo, normalmente no es posible encontrar primero un punto base y luego calcular el orden del subgrupo, porque esto es demasiado incierto y difícil de implementar algorítmicamente. Por el contrario, es mucho más fácil elegir primero un orden de subgrupo grande y luego encontrar un punto base que genere el subgrupo.
Como se mencionó anteriormente, el orden n del subgrupo es un divisor del orden N del grupo principal, es decir, h es un número entero, al que llamamos cofactor del subgrupo. Porque, existe:
Generalmente se elige un número primo como orden del subgrupo, es decir, n es un número primo. Se puede encontrar que el punto genera un subgrupo de orden n (excepto , porque el orden de este subgrupo es 1), y el punto que no es igual a es el punto base que buscamos. Los pasos específicos son los siguientes:
Cabe señalar que n en el algoritmo anterior debe ser un número primo; de lo contrario, el orden del subgrupo generado por el punto base calculado G puede ser un divisor de n. de n, que no cumple los requisitos. Tomando la curva como ejemplo, elegimos, luego seleccionamos aleatoriamente un punto y calculamos que cumple exactamente con los requisitos.
Como se mencionó anteriormente, el algoritmo de cifrado de curva elíptica funciona en el subgrupo cíclico de curva elíptica bajo el dominio principal. Los parámetros de dominio requeridos (parámetro de dominio) incluyen:
Por ejemplo, Bitcoin usa. Los parámetros de dominio de la curva elíptica [secp256k1] utilizados en las firmas digitales son los siguientes: