La criptografía de curva elíptica es una forma popular de cifrado de clave pública que se basa en la teoría matemática de las curvas elípticas . Los puntos en una curva elíptica se pueden agregar y formar un grupo bajo esta operación de adición. Este artículo describe los costos computacionales para la adición de este grupo y ciertas operaciones relacionadas que se utilizan en algoritmos de criptografía de curva elíptica.
Abreviaturas de las operaciones
La siguiente sección presenta una tabla de todos los costos de tiempo de algunas de las posibles operaciones en curvas elípticas. Las columnas de la tabla están etiquetadas por varias operaciones computacionales. Las filas de la tabla son para diferentes modelos de curvas elípticas. Estas son las operaciones consideradas:
DBL - Duplicación
ADD - Adición
mADD - Adición mixta: adición de una entrada que ha sido escalada para tener la coordenada Z 1.
mDBL - Duplicación mixta: duplicación de una entrada que ha sido escalada para tener la coordenada Z 1.
TPL - Triplicación.
DBL + ADD - Combinado doble y paso adicional
Para ver cómo se definen la suma (ADD) y la duplicación (DBL) de puntos en curvas elípticas, consulte La ley de grupos . La importancia de duplicar para acelerar la multiplicación del escalador se discute después de la tabla. Para obtener información sobre otras posibles operaciones en curvas elípticas, consulte http://hyperelliptic.org/EFD/g1p/index.html .
Tabulación
Bajo diferentes supuestos sobre la multiplicación, suma, inversión de los elementos en algún campo fijo , el costo de tiempo de estas operaciones varía. En esta tabla se asume que:
- I = 100M, S = 1M, * param = 0M, sumar = 0M, * const = 0M
Esto significa que se requieren 100 multiplicaciones (M) para invertir (I) un elemento; se requiere una multiplicación para calcular el cuadrado (S) de un elemento; no se necesita multiplicación para multiplicar un elemento por un parámetro (* param), por una constante (* const) o para sumar dos elementos.
Para obtener más información sobre otros resultados obtenidos con diferentes supuestos, consulte http://hyperelliptic.org/EFD/g1p/index.html
Importancia de duplicar
En algunas aplicaciones de criptografía de curva elíptica y el método de curva elíptica de factorización ( ECM ) es necesario considerar la multiplicación escalar [ n ] P . Una forma de hacer esto es calcular sucesivamente:
Pero es más rápido usar método de doble-and-add , por ejemplo, [5] P = [2] ([2] P) + P . En general, para calcular [ k ] P , escriba
con k i en {0,1} y, k l = 1, entonces:
.
Tenga en cuenta que este algoritmo simple toma como máximo 2l pasos y cada paso consiste en duplicar y (si k i ≠ 0) agregar dos puntos. Entonces, esta es una de las razones por las que se definen fórmulas de suma y duplicación. Además, este método es aplicable a cualquier grupo y si la ley de grupo se escribe multiplicativamente, el algoritmo de doble y suma se llama algoritmo de cuadrado y multiplicación .
Referencias
- ↑ Fay, Björn (20 de diciembre de 2014). "Doble y sumar con coordenadas jacobianas relativas" . Archivo ePrint de criptología .