Cómo entienden los estudiantes de secundaria el algoritmo de cifrado de Bitcoin

La criptografía tiene una larga historia y casi todo el mundo puede construir métodos de cifrado y descifrado, como simples desplazamientos circulares. Los métodos antiguos o simples requieren claves y algoritmos de cifrado secretos. Sin embargo, a juzgar por las batallas ofensivas y defensivas a largo plazo de la historia, la confidencialidad basada en el cifrado no es confiable. Al mismo tiempo, la transmisión de claves siempre ha sido un gran problema y a menudo se enfrenta al riesgo de fugas de claves o ataques de intermediarios.

En la década de 1970, la criptografía marcó el comienzo de un gran avance. Ralph C. Merkle propuso por primera vez la idea del cifrado asimétrico en 1974. Dos años más tarde, dos académicos, Whitfield Diffie y Whitfield Diffie, propusieron ideas específicas basadas en funciones unidireccionales y funciones de trampilla unidireccionales. Posteriormente, surgieron una gran cantidad de investigaciones y algoritmos, los más famosos son el algoritmo RSA y una serie de algoritmos de curva elíptica.

No importa qué algoritmo se utilice, se basa en los hombros de sus predecesores y se basa principalmente en el desarrollo de la teoría de números, la teoría de grupos y la teoría de campos finitos con los números primos como objeto de investigación. La clave para el cifrado de contenidos ya no es necesario transmitirla, sino que se genera mediante cálculo, de modo que la comunicación sea segura incluso en redes inseguras. El descifrado de texto cifrado se basa en el descifrado de la clave, pero el descifrado de la clave enfrenta un problema difícil. Para el algoritmo RSA, este problema es la factorización de números grandes, y para el algoritmo de curva elíptica, este problema es la solución logarítmica cuasi discreta. Ninguno de los dos tiene actualmente una solución en tiempo polinómico, lo que significa que la dificultad aumenta exponencialmente a medida que aumenta el número de dígitos.

Entonces, ¿cómo funcionan el cifrado y descifrado en sistemas de claves públicas y privadas? En resumen, se realiza mediante cálculos en un área limitada, porque el cifrado y descifrado deben ser precisos. Un cuerpo finito es un conjunto formado por un número finito de elementos. El cifrado asigna un elemento a otro, mientras que el descifrado se asigna nuevamente. La composición de los cuerpos finitos está relacionada con las propiedades de los números primos.

Hace algún tiempo, cuando la Hipótesis de Riemann (estrechamente relacionada con el Teorema de los Números Primos) era un tema candente, un director técnico del proyecto blockchain dijo que el algoritmo de la curva elíptica no tiene nada que ver con los números primos y no se ve afectado por la Hipótesis de Riemann, lo cual es una completa tontería. Se puede ver que el proyecto blockchain tiene ventajas mixtas y necesita una buena limpieza.

El sistema de clave pública utilizado por Bitcoin y la mayoría de los proyectos blockchain es el algoritmo de curva elíptica, no RSA. Antes de presentar el algoritmo de curva elíptica, es útil comprender primero el problema del logaritmo discreto por su seguridad.

Echemos un vistazo primero al último teorema de Fermat:

Definición de raíz primitiva:

Supongamos (a, p)=1 (a y p son primos relativos ), el entero positivo más bajo L que satisface

se llama orden de A módulo P, y el entero A cuyo orden módulo P es (máximo) p-1 se llama raíz primitiva de módulo P.

Dos teoremas:

Basado en esto, podemos ver que {1, 2, 3,... p-1} es un cuerpo finito, y la operación gi (mod p) se define dentro de este dominio finito. Al mismo tiempo, cuando tomo números diferentes del 0 al p-2, los resultados de la operación también son diferentes. Esto es básicamente lo mismo que el funcionamiento eléctrico que aprendimos en la escuela secundaria, pero con una capa adicional de funcionamiento modular.

Otra cosa a tener en cuenta es que el exponente de g no se limita a 0 ~ p-2. De hecho, pueden ser todos números naturales, sino porque

por lo tanto, todos funcionan. Los valores están dentro de un dominio finito y son continuamente cíclicos.

Definición de logaritmos discretos:

Supongamos que g es una raíz primitiva módulo p, (a, p) = 1,

Llamamos a I la primitiva de a El índice (para una raíz primitiva g módulo p) se expresa como:

Donde ind son las tres primeras letras del índice.

¿Es esta definición muy similar a la definición de registro? De hecho, esta es una extensión de la definición de logaritmos que aprendimos en la escuela secundaria, pero ahora se aplica a cuerpos finitos.

Pero esto es diferente del cálculo logarítmico en el campo de números reales. El campo de números reales es un espacio continuo. Hay fórmulas y reglas a seguir para el cálculo logarítmico, pero a menudo es difícil ser preciso. Nuestros sistemas criptográficos requieren precisión, pero operar en dominios finitos es extremadamente difícil.

Cuando se conoce el valor de potencia A y la base logarítmica G, es difícil encontrar su valor logarítmico discreto I.

Cuando el número primo elegido p es lo suficientemente grande, resulta imposible, tanto en tiempo como en cálculo, encontrar I. Por tanto, podemos decir que no se puede calcular, es decir, es seguro y no se puede descifrar.

El algoritmo de curva elíptica de Bitcoin utiliza específicamente el algoritmo secp256k1. Hay muchas introducciones al algoritmo de curva elíptica en Internet, por lo que no entraré en detalles aquí. Solo sepa que en realidad es una curva cúbica (no una función elíptica), definida de la siguiente manera:

Entonces hay parámetros a y b; diferentes curvas elípticas tienen valores diferentes. Por supuesto, X e Y se definen en el dominio de los números reales, lo que no es factible en criptografía. Cuando realmente se usan, X e Y deben definirse en un campo finito, ambos son números naturales, menores que un número primo p. Luego, cuando se define esta curva elíptica, su respuesta son solo algunos puntos discretos en el sistema de coordenadas, lo cual no es nada. como curva. Sin embargo, en el campo finito de conjuntos, sus diversas operaciones son completas. En otras palabras, los puntos correspondientes se pueden encontrar mediante operaciones de cifrado y los puntos antes del cifrado se pueden obtener mediante operaciones de descifrado.

Al mismo tiempo, al igual que el problema de logaritmos discretos mencionado anteriormente, esperamos encontrar un subgrupo finito en la red discreta de esta curva elíptica, que tenga la ergodicidad y ciclicidad mencionadas anteriormente. Todos nuestros cálculos utilizarán este subgrupo. Esto crea un dominio finito que necesitamos. Entonces aquí necesitamos el orden del subgrupo (un número primo n) y el punto base g en el subgrupo (una coordenada que puede atravesar el subgrupo de orden n mediante la suma).

Según la descripción anterior, sabemos que la definición de curva elíptica incluye un ancestro de cinco elementos (P, A, B, G, N, H); las definiciones y conceptos específicos son los siguientes:

p: Número primo grande, utilizado para definir el campo finito (grupo) de una curva elíptica.

a, b: parámetros de la curva elíptica, que definen la función de la curva elíptica.

g: El punto base en el subgrupo cíclico, la base de operaciones.

n: El orden del subgrupo cíclico (otro número primo grande,

h: El factor de correlación del subgrupo, es decir, la parte entera del orden de un grupo dividido por el orden del subgrupo.

Bien, es hora de ver qué tipo de curva elíptica es el algoritmo de curva elíptica de Bitcoin. En pocas palabras, es una curva elíptica y los parámetros anteriores tienen los siguientes valores:<. /p>

La curva elíptica define la suma, lo que significa que dos puntos están conectados. El punto de simetría donde el eje X se cruza con el tercer punto de la imagen es la suma de los dos puntos, por lo que no entraré en detalles. aquí

Sin embargo, los estudiantes cuidadosos pueden tener una pregunta. El problema con los logaritmos discretos es que es fácil encontrar el exponente, pero es difícil encontrar su exponente. no hay potencia, solo producto. ¿Problema de logaritmo discreto?

De hecho, este es un problema de definición. Inicialmente, el algoritmo de curva elíptica definió esta operación como una suma, pero siempre que la definas como. un producto, todo el sistema estará bien. Y si define el producto, encontrará que todas las operaciones son formalmente consistentes con el principio del problema de logaritmo discreto y la selección de campo finito. Por lo tanto, este es esencialmente un problema de logaritmo discreto, pero. no es un simple problema de logaritmo discreto. Es más difícil que el problema de logaritmo discreto general porque no simplemente encuentra el logaritmo discreto de un número, sino que encuentra un valor similar al logaritmo discreto en un cálculo personalizado. El algoritmo de curva es muy útil porque utiliza muchos menos bits de clave privada (256 bits) de los que requiere RSA (normalmente 2048 bits).