elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Seguridad Informática
| |-+  Seguridad
| | |-+  Criptografía (Moderador: kub0x)
| | | |-+  Paridad de un punto en Curvas Elipticas Criptograficas
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Paridad de un punto en Curvas Elipticas Criptograficas  (Leído 3,261 veces)
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.614


🏴 Libertad!!!!!


Ver Perfil WWW
Paridad de un punto en Curvas Elipticas Criptograficas
« en: 27 Febrero 2021, 09:08 am »

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!


« Última modificación: 8 Marzo 2021, 17:00 pm por AlbertoBSD » En línea

Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW
kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.449


S3C M4NI4C


Ver Perfil
Re: Paridad de un punto en Curvas Elipticas Criptograficas
« Respuesta #1 en: 27 Febrero 2021, 16:59 pm »

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

El orden del grupo es p+1=115792089237316195423570985008687907853269984665640564039457584007908834675928.

Sus factores son =2^3 \cdot 3 \cdot 31\cdot 1332800710337519 \cdot 159396839868569837 \cdot 264924657894446267 \cdot 2765277052581038646431687

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

Sea este punto aleatorio Q=(11149953761093268019683972221017297159551054455242720599347854800672619132861, 37518241730050014222306371200771084611880803990503119353253790030802953771498)

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

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

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  G=(G_x,G_y)=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

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

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.


En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.614


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Paridad de un punto en Curvas Elipticas Criptograficas
« Respuesta #2 en: 6 Marzo 2021, 05:58 am »

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 (Q_{x})^2 %2B 7 = (Q_y)^2 = h entonces como P es primo, podemos hacer h^{\frac{p-1}{2}} \equiv (Q_y)^{p-1} \equiv 1 \pmod P.

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

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

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!
« Última modificación: 6 Marzo 2021, 07:17 am por AlbertoBSD » En línea

Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW
kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.449


S3C M4NI4C


Ver Perfil
Re: Paridad de un punto en Curvas Elipticas Criptograficas
« Respuesta #3 en: 6 Marzo 2021, 16:16 pm »

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 P=d\cdot G 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 h^{\frac{p-1}{2}} \equiv (Q_y)^{p-1} \equiv 1 \pmod P

Con esa demostración me refería al lemma general en el que dado un field de dimensión 1 y prime characteristic, F_p, su grupo multiplicativo F_p^* tiene orden p-1. 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:
g^x \equiv h \pmod{p} entonces, si x es par, tendríamos:
g^{2k} \equiv \h \pmod{p} y si exponenciamos con \frac{p-1}{2} y reducimos:
g^{2k\frac{p-1}{2}} \equiv g^{k \cdot p-1} \equiv (g^{p-1})^k \equiv 1^k \equiv 1

Por lo tanto, queda demostrado que si el exponente x es par, la equación g^{x \frac{p-1}{2}} 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 y^2 = x^3 %2B 7 \pmod{P}, tenemos que el exponente de la variable "y" es par (es 2 en este caso). Por lo tanto aplicando la exponciación con \frac{p-1}{2} tendría que dar 1 si el punto (x,y) fuera válido, ya que f(x)=y^2, 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 P = d \cdot G 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.
En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.614


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Paridad de un punto en Curvas Elipticas Criptograficas
« Respuesta #4 en: 8 Marzo 2021, 17:00 pm »

Gracias, ya quedo mas claro.

Saludos!
En línea

Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW
kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.449


S3C M4NI4C


Ver Perfil
Re: Paridad de un punto en Curvas Elipticas Criptograficas
« Respuesta #5 en: 11 Marzo 2021, 23:53 pm »

Gracias, ya quedo mas claro.

Saludos!

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

Saludos.
En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
curvas?
Diseño Gráfico
3k1n0x 4 2,289 Último mensaje 30 Noviembre 2007, 15:42 pm
por _loko_
Alguien sabe de algun algoritmo escrito en php para cifrar con curvas elipticas?
PHP
whiteshocket 0 882 Último mensaje 15 Mayo 2013, 15:27 pm
por whiteshocket
Duda acerca de tarjetas criptográficas (DNIe)
Hardware
Daklon 0 773 Último mensaje 8 Octubre 2013, 21:10 pm
por Daklon
matriz con propiedad de paridad
Programación C/C++
xxxaxi 0 797 Último mensaje 16 Diciembre 2016, 00:30 am
por xxxaxi
Encabezados de criptografía en bibliotecas criptográficas
Criptografía
retr02332 7 1,452 Último mensaje 24 Febrero 2020, 04:11 am
por engel lex
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines