Teoría de números en criptografía

Dado un entero positivo x, y, n, encuentre un entero positivo k (si existe) tal que y≡xk (mod n). En la actualidad, la gente no ha encontrado un algoritmo rápido para calcular logaritmos discretos (el llamado algoritmo rápido se refiere a un algoritmo cuya complejidad computacional está dentro del rango polinómico, es decir, O (logn) k, donde k es una constante). Aunque existe un algoritmo cuántico para calcular rápidamente logaritmos discretos, ¿su complejidad computacional es O(logn)2+? Mire, todavía no hay computadoras cuánticas (es posible que nunca se construya una computadora cuántica práctica).

Ahora explique el proceso de operación de DHM (suponiendo que A y B quieran formar una clave en un canal inseguro como Internet para futuros cifrados y descifrados).

Primero, A y B deberían acordar públicamente un número primo Q y un generador G en el campo finito Fq;

a elige un número aleatorio a∈{1, 2, . ., q-1} (a puede considerarse como la clave privada de A) envía g a (modq) a B;

B elige un número aleatorio B ∈ {1, 2,..., q- 1}(b puede considerarse como la clave privada de B) y envía gb(modq) a A;

En este momento, A puede calcular (g b)a(modq), y B también puede calcular (g a )b(modq). Dado que (GB)A(MODQ)=(GA)B(MODQ)= g ab(MODQ), A y B forman una clave pública g ab(modq). A continuación se ofrece un ejemplo de cálculo de un logaritmo discreto.

A y B coinciden en que Q = 2739(7149-1)/6+1, g=7.

A elige un número aleatorio A, calcula 7a (modq) y lo envía a B (nota: A no se puede filtrar

(Ver lectura adicional)

En este momento, tanto A como B pueden calcular la clave 7ab(modq), pero no es fácil para otros calcular porque no conocen A y B. Los lectores interesados ​​tal vez quieran usar esto como ejercicio e intentarlo. para calcular el valor 7ab(modq). En 1978, sólo dos años después de que DHM inventara el criptosistema de clave pública, tres científicos del Instituto Tecnológico de Massachusetts, R.L. Rivest, A. Shamir y Leonard Adleman (RSA para abreviar) propusieron un método basado en la dificultad de la descomposición de números enteros. Un práctico sistema de criptografía de clave pública.