Foro de elhacker.net

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!

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

El orden del grupo es p+1=115792089237316195423570985008687907853269984665640564039457584007908834675928.

Sus factores son

Por lo tanto, con álgebra modular podemos comprobar un par de cosillas. Parametrizamos en sage y generamos un elemento aleatorio en la curva

Sea este punto aleatorio

Por lo tanto sabemos que entonces como P es primo, podemos hacer .

Es decir, si sustituimos en la ecuación de la curva mod P, tendremos que tener un residuo cuadrático tal que .

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  

ya que

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.

Gracias por la respuesta tan elaborada

Aclarado:


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



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.


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


Ya comprobe que para los puntos validos en la curve esto siempre se cumple

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!

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 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.


Con esa demostración me refería al lemma general en el que dado un field de dimensión 1 y prime characteristic, , su grupo multiplicativo tiene orden . 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:
entonces, si x es par, tendríamos:
y si exponenciamos con y reducimos:


Por lo tanto, queda demostrado que si el exponente x es par, la equación 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 , tenemos que el exponente de la variable "y" es par (es 2 en este caso). Por lo tanto aplicando la exponciación con tendría que dar 1 si el punto (x,y) fuera válido, ya que , 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 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.

Gracias, ya quedo mas claro.

Saludos!

A ti por postear buenas preguntas y traer contenido :) :)

Saludos.