ECDSA (Algoritmo de firma digital de curva elíptica)
ECDSA (Algoritmo de firma digital de curva elíptica)
En el trabajo y en la vida real, utilizamos firmas para expresar nuestra aprobación de un documento, y otros pueden reconocer su firma. Y su firma no puede ser falsificado. La firma digital es una implementación electrónica de una firma mostrada. No sólo puede alcanzar plenamente las características de una firma real, sino que incluso puede hacerlo mejor.
Los algoritmos de firma digital más utilizados incluyen RSA (Rivest-Shamir-Adleman Scheme), DSS (Digital Signature Standard), etc. Bitcoin utiliza ECDSA para generar claves públicas y privadas para cuentas y para verificar transacciones y bloques.
1. Alice (en criptografía, los nombres que comienzan de la A a la Z se usan comúnmente en lugar de A, B, C, D, etc., cuanto más tardías sean las letras, menor será la frecuencia de aparición) genera un par de claves, una es sk (clave de firma), pública sí o no, la otra es vk (clave de verificación), que es pública.
Este par de claves se genera al mismo tiempo y están relacionadas matemáticamente entre sí. Al mismo tiempo, no se puede inferir información sobre sk en función de vk.
2. El algoritmo de firma digital recibe dos salidas: información M y sk, y genera una firma digital Sm
3. La función de verificación recibe información M, Sm y vk como entrada, y devuelve El resultado es sí o no. El propósito de este paso es verificar que la firma digital de la información M que ve esté efectivamente firmada por el sk de Alice, para confirmar si la información coincide con la firma.
A diferencia de las firmas manuscritas, que son básicamente similares, las firmas digitales se ven muy afectadas por la entrada. Pequeños cambios en la entrada producirán una firma digital completamente diferente. Generalmente, la información no se firma digitalmente directamente, pero sí se firma el valor hash de la información. Debido a la naturaleza libre de colisiones de la función hash criptográfica, esto es tan seguro como firmar el mensaje original.
En matemáticas, la curva formada por cualquier punto que satisfaga la siguiente ecuación se llama curva elíptica aleatoria: Y , a y b pueden ser cualquier valor. A continuación se muestran varios ejemplos de funciones elípticas aleatorias:
Antes de comprender cómo generar claves públicas y privadas a través del algoritmo ECDSA basado en la curva elíptica secp256k1, debemos comprender cómo se implementa la suma de puntos en funciones elípticas aleatorias. curvas.
Primero define la suma de puntos en una curva elíptica. Supongamos que hay dos puntos en la curva elíptica, los puntos A y B, luego la línea recta trazada a través de estos dos puntos cruza la curva en el tercer punto (punto C), y luego el punto D se obtiene simétricamente con respecto al eje X, entonces D son estos dos puntos. La suma de se registra como D=A+BD=A+BD=A+B. Obviamente, el punto D también está en la curva. Entonces la suma de dos puntos en una curva elíptica también es un punto en la curva.
Caso especial:
1. Si dos puntos coinciden, haz la recta tangente del punto, y el punto simétrico del punto de intersección con la curva es la suma, es decir, A+A=C
Como se muestra en la figura:
Después de la suma, la implementación de la multiplicación es solo realizar múltiples operaciones de suma. Después de tener un punto de referencia P, podemos multiplicarlo y finalmente obtener otro punto de la curva.
Supongamos que PPP es un punto en la curva elíptica, entonces el resultado de multiplicar el entero positivo kkk por el punto PPP se define mediante la siguiente fórmula. Tenga en cuenta que la suma en la fórmula es el punto en la elíptica. curva mencionada anteriormente Además:
La operación puntual satisface la ley asociativa:
Obviamente, el cálculo mediante acumulación es un método muy estúpido y su complejidad temporal es lineal. Como mencionamos anteriormente, la suma de puntos en una curva elíptica satisface la ley asociativa, es decir, si se expande, hay
Entonces existe una operación tan interesante, como cálculo, podemos calcular primero; luego calcular, luego calcular y finalmente calcular; Aquí hemos reducido las 15 adiciones a 4.
Por supuesto, el valor de k no siempre puede ser una potencia de 2. De hecho, la operación anterior se puede extender al caso en que k sea cualquier número entero positivo. Por ejemplo, para calcular 23P, primero calcule y luego
Porque, entonces. El total *** sólo requiere 7 adiciones.
Analice, para cualquier entero positivo k, podemos usar este método para reducir el número de cálculos de suma necesarios para calcular k?P a
En otras palabras, desde la complejidad del tiempo Desde Desde la perspectiva de, este algoritmo es un algoritmo.
Este método se llama algoritmo de potencia rápida. Originalmente se usaba a menudo para calcular rápidamente la k-ésima potencia de un determinado número. Aquí se extiende al cálculo rápido de la multiplicación de puntos de curva elíptica.
¿Por qué apareció de repente un algoritmo de potencia rápida tras introducir la multiplicación de puntos en curvas elípticas? ¿Cuál es la importancia del algoritmo de potencia rápida para el cifrado de curva elíptica? Porque los matemáticos / criptógrafos han descubierto que la complejidad temporal del uso del algoritmo de potencia rápida para calcular es logarítmica. Sin embargo, si necesita saber y, no existe un algoritmo que sea mucho más rápido que intentar deducir los valores uno por uno. el valor de . Así nació el rompecabezas matemático en el que se basa el cifrado de curva elíptica.
Si cambiamos la notación y registramos la suma de puntos en la curva elíptica como multiplicación, la multiplicación original se convierte en una operación de potencia, entonces la forma del problema anterior debe ser consistente con el problema de logaritmo discreto. Es decir:
Entonces, este difícil problema se llama problema de logaritmos discretos en curvas elípticas.
Aunque los dos tienen la misma forma, no son equivalentes. De hecho, este problema es mucho más difícil que los problemas de factorización de enteros primos grandes (RSA) y de logaritmos discretos (DH). Actualmente no existe ningún algoritmo con complejidad de tiempo subexponencial (los problemas de factorización de enteros primos grandes y de logaritmos discretos son ambos Sí). de modo que bajo el mismo nivel de seguridad, la clave del cifrado de curva elíptica es mucho más corta que la de RSA y DH, lo cual es una gran ventaja del cifrado de curva elíptica.
Supongamos que elige aleatoriamente un valor x entre ~ dígitos y lo calcula, el resultado final definitivamente caerá en un punto de la curva. Suponiendo que el punto es , ¿podemos deducir a la inversa el valor aleatorio inicial de , dado que , y la ecuación de la curva específica?
Prueba: El proceso de búsqueda solo se puede calcular mediante fuerza bruta. El valor posible de es uno de ~. En promedio, se necesitan tiempos de cálculo para encontrar el valor de una vez. Entonces la pregunta es ¿cuánto tiempo se tarda en realizar un cálculo?
Supongamos que estamos usando una supercomputadora con una frecuencia principal de (se pueden realizar un billón de operaciones por segundo). Solo hemos realizado cálculos desde el nacimiento del universo. La probabilidad de encontrar un valor es . Esta probabilidad es cercana a la probabilidad de que la Tierra sea destruida por el impacto de un meteorito gigante en el próximo segundo. Como hemos leído esto, significa que este evento no ha sucedido.
En el caso anterior, es un número aleatorio de ~ bits, que puede usarse como clave privada. es un punto en la curva elíptica aleatoria, que es la clave pública generada por la clave privada, por lo que se puede probar la ventaja.
Sin embargo, en criptografía, la curva elíptica en el campo de números reales presentada anteriormente no se puede utilizar. Porque
necesitamos introducir curvas elípticas en campos finitos.
Para demostrar la ventaja 2, es necesario realizar algunos cambios en la curva elíptica aleatoria: para garantizar que el valor de coordenadas calculado final del punto sume 512 bits, secp256k1 introduce un mecanismo para tomar el módulo números primos.
Específicamente, la curva elíptica aleatoria cambia de
a donde , es el mayor número primo menor que .
El gráfico de la función de curva elíptica aleatoria en este momento es el siguiente:
Específicamente, es para demostrarles a los demás que lo sé, pero no exponer ninguna información al respecto. (Algo similar a la prueba de conocimiento cero)
Prueba: la ley asociativa se introdujo anteriormente: agregando una función hash, se puede obtener una modificación simple: Let, entonces se puede ver que es. En este momento la ecuación es: Para simplificar, escribimos y . En este punto la ecuación se simplifica a: ¿Qué significa la ecuación anterior?
Se puede suponer que: dado que , si podemos proporcionar a y que satisface la ecuación anterior, podemos demostrar que una persona tiene . Esta suposición tiene una premisa. Si una persona no conoce x, entonces no puede proporcionar ni satisfacer la ecuación anterior.
Discute esta premisa en detalle: Si una persona no sabe x y quiere calcular y, ¿se puede hacer? La conclusión es no, en primer lugar no podemos calcular (en un tiempo finito).
Una pregunta más: ¿Se puede calcular alguna información sobre dado que y ?
Según la fórmula: Simplemente resuélvelo.
Para calcular x, es necesario conocer r, pero ¿hay alguna manera de calcular r cuando r no se hace público? Sabemos que R = r * P; pero r no se puede deducir de esta fórmula (el problema matemático que acabamos de presentar), por lo que x también es seguro.
Llegados a este punto, se puede demostrar la segunda ventaja del algoritmo.