cryptography - variable - volumen de un elipsoide por integrales

Cómo calcular la suma de puntos usando el sistema de coordenadas jacobiano sobre curvas elípticas (2)

Estoy escribiendo un pequeño proyecto de criptografía de curva elíptica, y el programa funciona bien cuando uso el sistema de coordenadas afines, lo que significa que cada punto está representado por 2 coordenadas (x '', y'').

Ahora estoy tratando de reemplazar el sistema de coordenadas afines por el sistema de coordenadas jacobiano en el que cada punto está representado por 3 coordenadas (x, y, z), x ''= x / z² y y'' = y / z³.

Me gustaría saber cómo transformar coordenadas afines en coordenadas jacobianas **. En algunos tutoriales, las personas usan la fórmula: (x, y) = (x, y, 1) lo que significa que la coordenada z siempre se establece en uno. Pero no estoy seguro de si es correcto.

Luego, para adiciones de puntos sobre la curva elíptica, para calcular P (x1, y1, z1) + Q (x2, y2, z2) = R (x3, y3, z3). He usado las siguientes fórmulas en mi programa:

u1 = x1.z2² u2 = x2.z1² s1 = y1.z2³ s2 = y2.z1³ h = u2 - u1 r = s2 - s1 x3 = r² - h³ - 2.u1.h² Y3 = r. (U1.h² - x3) - s1.h³ z3 = z1.z2.h

Pero cuando pruebo mi programa, obtengo algunas coordenadas negativas, por ejemplo (-2854978200, -5344897546224,578). Y cuando trato de convertir el resultado a un sistema de coordenadas afines con el formulario (x ''= x / z², y'' = y / z³), obtengo (-8545, -27679), en realidad la coordenada x es -8545.689. ... La coordenada jacobiana x no es divisible por z².

¿Qué debo hacer si las coordenadas no son números enteros? Y si son negativos? Intenté MOD con el tamaño de campo de mi curva, pero el resultado tampoco es correcto.

Entonces, el punto que usa las coordenadas de jacobiano (x,y,1) es correcto, pero no único. Todos los puntos que satisfacen (a^2.x,a^3.y,a) son equivalentes. Y en mi programa, la curva se define en un campo principal, así que cuando calculo u1, u2, s1, s2 ... ¿Debería aplicar MOD p a cada variable?

Y para transformar el resultado final en coordenadas afines, por ejemplo, la coordenada x, de hecho no es una división, ¿ es una inversa modular? Por ejemplo, mi curva se define en un campo finito primordial p=11 , y tengo un punto que usa coordenadas jacobianas (15,3,2) , para transformar la coordenada jacobiana x para afinar x coordenadas, tengo que calcular 2^2 = 4 => x = 4^-1 mod p => x = 3 , y 15.3 mod p = 1 , entonces la coordenada x afín es 1, ¿es así?

El objetivo de las coordenadas jacobianas es evitar la división durante la suma. Pero como dijo Thomas Pornin, cuando calculamos P1 + P2 = P3 , hay algunos casos especiales que manejar.

P1 y P2 son ambos infinitos: P3=infinite .
P1 es infinito: P3=P2 .
P2 es infinito: P3=P1 .
P1 y P2 tienen la misma coordenada x, pero diferentes coordenadas y o ambas coordenadas y son iguales a 0: P3=infinite .
P1 y P2 tienen diferente coordenada x: Addition formula .
P1 y P2 tienen las mismas coordenadas: Doubling formula .

Y aquí hay prototipos de mis funciones C:

jac_addition(jacobian *, point *, jacobian *); jac_doubling(jacobian *, jacobian *);

point es una estructura que representa un punto definido en el sistema de coordenadas afines, y jacobian para el sistema jacobiano.

El problema es que cuando manejo esos casos especiales, especialmente el cuarto, todavía tengo que convertir ambos puntos a coordenadas afines, o no puedo comparar sus coordenadas, lo que significa que todavía tengo que calcular la división.

La forma jacobiana de las coordenadas proyectivas (como cualquier otra forma) no es única: para cada valor de Z (distinto de 0) obtienes otras X e Y sin que cambie el punto real.

Por lo tanto, si tiene un punto en coordenadas afines (X'', Y'') , el par (X'', Y'', 1) es un representante proyectivo de este punto, así como (4·X'', 8·Y'', 2) , (9·X'', 27·Y'', 3) , etc. El que tiene 1 es el más fácil de crear, por lo que normalmente usaría este.

Mientras que uno puede definir (y estudiar) curvas elípticas sobre cualquier campo, y muchos matemáticos estudian curvas definidas sobre los números complejos, para usos criptográficos, las coordenadas son elementos de algún campo finito. En el caso más simple, tenemos un campo principal (es decir, números enteros un número primo), y usted tendrá que hacer suma, resta, multiplicación y división (y probablemente exponenciación) en este campo.

Siempre que Z no sea cero, deberías poder dividir por Z² ; esto es equivalente a multiplicar por el inverso de Z², y ese elemento existe, y puede calcularse de manera eficiente usando el algoritmo euclidiano extendido.

Esto es más fácil si su lenguaje de programación viene con una gran biblioteca numérica que tiene las operaciones necesarias predefinidas, como la clase BigInteger de Java (con sus métodos mod , modPow y modInverse ).

El campo en cuestión (es decir, el módulo) es parte de la definición de la curva elíptica, y las operaciones sobre un campo dan resultados totalmente diferentes a las operaciones en otro. Así que asegúrese de estar usando el campo correcto.

Cuando se trata de curvas elípticas, las coordenadas están en un campo . Para la criptografía, este es un campo finito ; en su caso, el "entero modulo a prime p ". Todas las operaciones se refieren a ese campo, es decir, debe hacer cada módulo de adición, multiplicación o inversión p .

Al agregar puntos, existen algunos casos especiales que debe manejar especialmente:

Hay un "punto especial en el infinito" especial que no tiene coordenadas xey . Es el "cero" de la adición de la curva. En una rutina genérica de adición de puntos, debe tener una forma de codificar un "punto en el infinito" y verificarlo especialmente.
Al agregar (x, y) a (x '', y'') , puede suceder que x = x '' . En ese caso, ya sea y = y '' , y luego es un punto que se duplica, que tiene su fórmula específica (si aplicas la fórmula genérica, terminas dividiendo por cero, lo cual no funcionará); o, y = -y '' , en cuyo caso la suma es el "punto en el infinito".

Por lo tanto, la fórmula genérica se aplicará solo una vez que haya manejado el caso especial. En general, en una curva y ² = x ³ + a · x + b , la suma de (x ₁ , y ₁ ) y (x ₂ , y ₂ ) es (x ₃ , y ₃ ) tal que x ₃ = f ² -x ₁ -x ₂ y y ₃ = f · (x ₁ -x ₃ ) -y ₁ , donde f = (y ₂ -y ₁ ) / (x ₂ -x ₁ ) . Esto implica calcular una división y dos multiplicaciones, y algunas restas (todas las operaciones se realizan en enteros módulo p , como se explicó anteriormente).

La división y el módulo de inversión p son relativamente caros (una división modular tiene típicamente el mismo costo que alrededor de 80 multiplicaciones), por lo que en algunas situaciones usamos sistemas de coordenadas proyectivos o jacobianos . Las coordenadas jacobianas son acerca de representar un punto como tres valores (X, Y, Z) (todos ellos en el campo finito, es decir, enteros módulo p ) tales que x = X / Z ² ey = Y / Z ³ .

Cada punto (x, y) tiene muchas representaciones posibles como (X, Y, Z) . La conversión a coordenadas jacobianas es fácil al establecer X = x , Y = y y Z = 1 : (x, y, 1) es una representación jacobiana perfectamente válida del punto (x, y) . La conversión de coordenadas jacobianas es computacionalmente más difícil: tienes que hacer una inversión modular, y unas pocas multiplicaciones (calcula U = 1 / Z , luego x = X · U ² ey = Y · U ³ ).

Con las coordenadas jacobianas, la suma de dos puntos se realiza en una docena de multiplicaciones de campo, y ninguna división en absoluto. Solo obtiene una representación jacobiana del resultado, por lo que todavía tiene que hacer una inversión o división modular en algún punto; sin embargo (y es por eso que te molestas en usar coordenadas jacobianas), esa división se puede mutualizar. Si tiene que hacer un centenar de adiciones sucesivas de puntos (como es típico en un contexto criptográfico, al "multiplicar" un punto con un entero), entonces puede usar representaciones jacobianas en todas partes, y hacer una única conversión de nuevo a coordenadas cartesianas ( x, y) al final. Entonces en vez de hacer 200 multiplicaciones y 100 divisiones, haces 1000 multiplicaciones y 1 inversión; dado que una inversión cuesta lo mismo que 80 multiplicaciones, la ganancia es apreciable.

Trata de servirte de este libro ; cualquier buena biblioteca universitaria debería tener una. Explica todo eso muy claramente.