Paridad de un punto en Curvas Elipticas Criptograficas

[AlbertoBSD]

Quisiera abrir el siguiente hilo para saber si es posible determinar la paridad de un punto en una curva Eliptica utilizada en criptografía.

Encontré un video en youtube donde un programador de C# afirma tener la formula para determinar si un punto dado es par o impar para una curva en especifico.

Tiene una pagina

:http://remon78eg.tk/curve/mod2/

Utiliza un valor P custom: 115792089237316195423570985008687907853269984665640564039457584007908834675927

El cual afirma que es un valor débil o vulnerable.

El usuario no revela mucho de su método o test de paridad de un punto o publickey.

Las preguntas aquí son las siguientes:
¿Qué tiene de débil o vulnerable su orden de la curva?
¿Cuál seria el test de paridad que se pueda implementar para determinar si un punto (X,Y) pertenece a una privatekey par o impar?

Saludos!

[kub0x]

Voy a aportar un par de cosillas, pero hay que hilarlas.

El orden del grupo es p+1=115792089237316195423570985008687907853269984665640564039457584007908834675928.

Sus factores son [latex]=2^3 \cdot 3 \cdot 31\cdot 1332800710337519 \cdot 159396839868569837 \cdot 264924657894446267 \cdot 2765277052581038646431687[/latex]

Por lo tanto, con álgebra modular podemos comprobar un par de cosillas. Parametrizamos en sage y generamos un elemento aleatorio en la curva [latex]y^2 = x^{3} %2B 7 \quad \pmod{P}[/latex]

Sea este punto aleatorio [latex]Q=(11149953761093268019683972221017297159551054455242720599347854800672619132861, 37518241730050014222306371200771084611880803990503119353253790030802953771498)[/latex]

Por lo tanto sabemos que [latex](Q_{x})^2 %2B 7 = (Q_y)^2 = h[/latex] entonces como P es primo, podemos hacer [latex]h^{\frac{p-1}{2}} \equiv (Q_y)^{p-1} \equiv 1 \pmod P[/latex].

Es decir, si sustituimos [latex]Q_x[/latex] en la ecuación de la curva mod P, tendremos que tener un residuo cuadrático [latex]h[/latex] tal que [latex](Q_y)^2 \equiv h \pmod P[/latex].

Lo gracioso del tema, es que los valores que presenta para el punto de la clave pública no definen un punto válido en la curva  [latex]G=(G_x,G_y)=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)[/latex]

ya que [latex]((55066263022277343669578718895168534326250603453777594175500187360389116729240)^3 %2B 7)^{\frac{p-1}{2}} \equiv 103385459387519877611629604899025418984197736413864609339481624319167415399987^{\frac{p-1}{2}} \equiv 115792089237316195423570985008687907853269984665640564039457584007908834675926 \neq 1 \pmod P[/latex]

Creo que tu primera pregunta queda respondida por la simplicidad de la factorización, ya que el factor más grande aporta 82 bits.

La segunda pregunta, quitando que su valor público, G, no constituye un punto en la curva, no da mucha info saber que la privkey tiene paridad, que parece ser siempre 0 en esa web. Por ejemplo mod P con P primo ya te he demostrado que recuperar la paridad del exponente privado es sencillo, ¿trae complicaciones? bueno descartas la mitad de los valores, ya que si es par no buscaras impares verdad.

Saludos.

[AlbertoBSD]

Gracias por la respuesta tan elaborada

Aclarado:

¿Qué tiene de débil o vulnerable su orden de la curva?

El tamaño de los factores primos del ordel del grupo P+1 es debil ya que el primo mas grande solo aporta 80 bits y se puede resolver mediante Pohlig hellman

La segunda pregunta, quitando que su valor público, G, no constituye un punto en la curva, no da mucha info saber que la privkey tiene paridad, que parece ser siempre 0 en esa web.

Tines razón si el valor P cambio también debe de cambiar el valor de alguno de los componentes x o y del generado orginal es decir se tienen  que recalcular alguno de los 2, efectivamente su punto generador es invalido con el nuevo valor de P utilizado. Acabo de comprobar puntos validos en la curva con tu valor aleatorio como generado y en su pagina WEB todos los valores son 0.
Curiosamente con puntos fuera de la curva (inválidos) su pagina web si acierta.. ni idea de que operación interna este realizando el usuario, pero si los puntos son inválidos, no vale la pena perder el tiempo con ellos.

Por ejemplo mod P con P primo ya te he demostrado que recuperar la paridad del exponente privado es sencillo

Cuando dices que ya lo has demostrado ¿te refieres a las formulas descritas en el siguiente parrafo?

Por lo tanto sabemos que [latex](Q_{x})^2 %2B 7 = (Q_y)^2 = h[/latex] entonces como P es primo, podemos hacer [latex]h^{\frac{p-1}{2}} \equiv (Q_y)^{p-1} \equiv 1 \pmod P[/latex].

Es decir, si sustituimos [latex]Q_x[/latex] en la ecuación de la curva mod P, tendremos que tener un residuo cuadrático [latex]h[/latex] tal que [latex](Q_y)^2 \equiv h \pmod P[/latex].

Ya comprobe que para los puntos validos en la curve esto siempre se cumple [latex]h^{\frac{p-1}{2}} \equiv (Q_y)^{p-1} \equiv 1 \pmod P [/latex]

Y da como resultado uno, ahora la pregunta es, ¿esto ayuda a determinar la paridad del punto?, es decir ¿esto ayuda a determinar si el privkey es par o impar?
¿O de plano no se puede saber? persona que lo pregunte de nuevo, solo que esa parte no me quedo clara

Nuevamente gracias por tu respuesta.

Saludos!

[kub0x]

El tamaño de los factores primos del ordel del grupo P+1 es debil ya que el primo mas grande solo aporta 80 bits y se puede resolver mediante Pohlig hellman

Tomando en cuenta la cota computacional como la raíz cuadrada del tamaño del mayor primo en bits, tendriamos aproximadamente 40 bits de seguridad.

Por lo tanto, dado un punto P computado como [latex]P=d\cdot G[/latex] podríamos recuperar el exponente privado resolviendo el logaritmo discreto, una curva facilita. Con Pohlig Hellman podríamos incluso factorizar el orden del primo más grande y separarlo en más instancias de CRT, al final si tenemos la habilidad de factorizar, Pohlig-Hellman se puede separar en forma de árbol, para paralelizar o distribuir el trabajo de la recomputación de manera eficiente.

Ya comprobe que para los puntos validos en la curve esto siempre se cumple [latex]h^{\frac{p-1}{2}} \equiv (Q_y)^{p-1} \equiv 1 \pmod P [/latex]

Con esa demostración me refería al lemma general en el que dado un field de dimensión 1 y prime characteristic, [latex]F_p[/latex], su grupo multiplicativo [latex]F_p^*[/latex] tiene orden [latex]p-1[/latex]. Por lo tanto, podemos inferir la paridad del exponente privado por ejemplo en Diffie-Hellman ya que, la clave pública general es dada por:
[latex]g^x \equiv h \pmod{p}[/latex] entonces, si x es par, tendríamos:
[latex]g^{2k} \equiv \h \pmod{p}[/latex] y si exponenciamos con [latex]\frac{p-1}{2}[/latex] y reducimos:
[latex]g^{2k\frac{p-1}{2}} \equiv g^{k \cdot p-1} \equiv (g^{p-1})^k \equiv 1^k \equiv 1[/latex]

Por lo tanto, queda demostrado que si el exponente x es par, la equación [latex]g^{x \frac{p-1}{2}}[/latex] es 1, y si es impar, es distinto de 1. Vemos como en Diffie-Hellman habríamos reducido la "fuerza bruta" a la mitad, pues descartamos exponentes pares o impares según el valor de la congruencia (1 o distinto de 1).

Como esta curva es [latex]y^2 = x^3 %2B 7 \pmod{P}[/latex], tenemos que el exponente de la variable "y" es par (es 2 en este caso). Por lo tanto aplicando la exponciación con [latex]\frac{p-1}{2}[/latex] tendría que dar 1 si el punto (x,y) fuera válido, ya que [latex]f(x)=y^2[/latex], introduces el X y obtienes Y^2, aplicando el lemma, obtendrás 1 si es válido.

Como ves, esto no arroja información sobre la privkey. De todas formas, como [latex]P = d \cdot G[/latex] si G tiene las coordenadas x,y pares el punto P será par, y de la privkey poco podremos saber, podría ser par o impar. Creo que este razonamiento excluye la posibilidad de la existencia de dicho método. Puede que exista literatura sobre éstas comprobaciones, pero como ya te expliqué sobre el brute force en Diffie-Hellman, como mucho descartas la mitad de los valores posibles para la privkey.

Saludos.

[AlbertoBSD]

Gracias, ya quedo mas claro.

Saludos!

[kub0x]

Gracias, ya quedo mas claro.

Saludos!

A ti por postear buenas preguntas y traer contenido

Saludos.