No es imposible. El número de puntos en una curva elíptica E sobre un campo finito es un número finito N. Dado un punto base P en E y un punto Q que es un múltiplo escalar de P, podría calcular n * P para cada entero n desde 1 a N y vea qué valor de n produce Q. Pero para fines criptográficos, N normalmente será del orden de 2 ^ 256 (o mayor), y este cálculo tomará demasiado tiempo para ser factible.
Sin embargo, uno puede hacerlo mejor que este enfoque de fuerza bruta.
Primero, si el entero N es el producto de muchos números primos pequeños, se puede usar un algoritmo debido a Pohlig y Hellman (también acreditado a Silver) para calcular el logaritmo discreto de manera bastante eficiente. De hecho, si N fuera igual a 2 ^ 256, podría calcular logaritmos discretos de menos de un milisegundo en una computadora típica. Por esta razón, las curvas elípticas utilizadas en la criptografía no son realmente aleatorias, se eligen de manera que N tenga un factor primo grande (a menudo N es en sí mismo un número primo). Pero aparte de esta restricción, uno quiere que E sea lo más “aleatorio” posible, porque para ciertas elecciones muy raras de E, los logaritmos discretos se pueden calcular rápidamente incluso cuando N no es un producto de números primos pequeños.
- ¿Cuál es la prueba lógica del teorema de la multiplicación con respecto a la probabilidad?
- ¿Qué cursos de matemática pura (p. Ej., Topología, análisis, álgebra moderna, geometría diferencial / algebraica) debería un estudio importante de física?
- ¿Qué es 0 + 0 + 0 + 0 + 0 + 0 + 0 + 11 + 11 + 22 + 22 + 22 + 22 + 22 + 22 + 22 + 22 + 22-100?
- ¿Qué es una explicación intuitiva de un ideal fraccional?
- Soy lo suficientemente bueno para resolver funciones, integral, derivada, etc. Pero soy tan lento en matemáticas simples de pruebas psicológicas, pruebas de coeficiente intelectual, pruebas de candidatos para el trabajo, etc. ¿Por qué?
En segundo lugar, incluso si N tiene un factor primo grande, uno puede usar el algoritmo rho de Pollard para calcular logaritmos discretos más rápidamente que el enfoque de fuerza bruta (hay variantes más sofisticadas que involucran lambdas y canguros, pero no entraré en ellos aquí) . La idea básica de Pollard rho es iterar una función “aleatoria” que implique múltiplos de P y Q hasta que se encuentre una colisión (en realidad, la función no es aleatoria en absoluto, pero se espera que se comporte como una función aleatoria). Si se supone que la función que se está iterando en realidad * es * aleatoria, entonces el tiempo esperado para encontrar una colisión es proporcional a la raíz cuadrada de N. Pero si N es del orden de 2 ^ 256, entonces la raíz cuadrada de N es del orden de 2 ^ 128, que todavía es demasiado grande para hacer práctico este enfoque.
Entonces, ¿cómo sabemos que no hay una mejor manera de calcular logaritmos discretos en una curva elíptica? Bueno, no lo hacemos, y podría haberlo. Existen algoritmos de logaritmos discretos para otros grupos (por ejemplo, el grupo multiplicativo de un campo finito) cuyos tiempos de ejecución son mucho más rápidos que la raíz cuadrada del orden de grupo. Pero ninguno de estos algoritmos parece aplicable a las curvas elípticas, y esto no es por falta de intentos: los investigadores han estado tratando de encontrar un algoritmo más rápido para calcular logaritmos discretos en curvas elípticas durante al menos dos décadas sin ningún éxito, ni siquiera un poco ( al menos sobre los campos principales).
Sabemos que cualquier algoritmo de logaritmo discreto que tome pasos significativamente menores que sqrt (N) tendrá que aprovechar de alguna manera algo especial sobre el grupo de puntos en una curva elíptica, no puede simplemente tratar la operación del grupo de curvas elípticas como un caja negra. Hay un límite inferior debido a Victor Shoup que demuestra que no existe un algoritmo de logaritmo discreto “genérico” que funcione en cualquier grupo y utilice significativamente menos operaciones de grupo sqrt (N).
En resumen, existen dos razones para pensar que el problema del logaritmo discreto en una curva elíptica es difícil: (1) nadie ha podido encontrar un algoritmo más rápido, incluso después de muchos años de esfuerzo, y (2) allí son límites inferiores teóricos que al menos descartan un enfoque genérico.
Habiendo dicho todo eso, debo señalar que si alguien logra construir una computadora cuántica viable con un número decente de q-bits, todas las apuestas están canceladas. Hay algoritmos rápidos para resolver el problema del logaritmo discreto en una computadora cuántica que se conoce desde hace un tiempo, pero hasta ahora nadie tiene una computadora cuántica en la que ejecutarlos (la máquina de D-Wave, incluso si realmente hace todo lo que reclamo, no es capaz de ejecutar este algoritmo).
