[Lab4] Ejericicio 5

[Lab4] Ejericicio 5

de Gerardo Agustin Lerena Amilivia -
Número de respuestas: 10

Buenas! No me queda claro que es lo que hay que hacer en el ultimo punto de las especificaciones, alguna ayuda?

Muchas gracias!

En respuesta a Gerardo Agustin Lerena Amilivia

Re: [Lab4] Ejericicio 5

de Nathan Ryan -

Si estás hablando de como calcular el punto de base es hace así:

 

1. al azar se elige un x en el cuerpo GF(p):

 

 

 


sage: p = 101; F = GF(p)

sage: E = EllipticCurve(F, [1,1,0,0,1])

sage: x = randint(0,101)

sage: xx = F(x)

 

2.  Se trata de construir un punto en E con primera cordenada xx (sage tira un error si no puede)

sage: P = E.lift_x(xx)

 

3.  Se compara el orden del punto con el order del grupo

sage: P.order()
105

sage: E.order()
105


sage: P.xy()
(45, 84)

 

 

En respuesta a Nathan Ryan

Re: [Lab4] Ejericicio 5

de Cristina Belen Techera Cedres -

Me parece que la pregunta se referia a la parte del apendice donde dice:

Check that the elliptic curve E over GF(p) given by  y2 = = x3 + ax+ b has suitable order. If not, go to Step 1. 

Por lo menos a mi no me quedo claro a que se refiere precisamente con eso. 

En respuesta a Cristina Belen Techera Cedres

Re: [Lab4] Ejericicio 5

de Nathan Ryan -

Si es eso, en el primer párrafo de las especificaciones, dice que el orden del grupo E(GF(p)) debería ser f x r donde f es 1,2, o 4 y r es un primo grande (por Hasse-Weil va a ser más o menos equal a p).

 

N

En respuesta a Nathan Ryan

Re: [Lab4] Ejericicio 5

de Javier Agustin Farias Gonzalez -

r debería ser un número primo? En las especificaciones r es un número primo. El punto base debería tener el mismo orden que la curva si f = 1, pero siempre se puede encontrar un punto así? Gracias.

En respuesta a Javier Agustin Farias Gonzalez

Re: [Lab4] Ejericicio 5

de Nathan Ryan -

El grupo E(GF(q)) o es cíclico (o sea tiene orden r y hay un punto de orden r) o es el producto de dos grupos cíclico (o sea tiene orden r y hay un punto de orden n que divide r donde r/n es "pequeño").  Es un teorema de Deuring, creo. 

En respuesta a Nathan Ryan

Re: [Lab4] Ejericicio 5

de Javier Agustin Farias Gonzalez -

Impecable, muchas gracias. Entonces tendríamos que elegir un grupo cíclico de orden r primo? Pregunto porque en las especificaciones es así en todos los casos creo, y además según leí es lo recomendado para poder usar la curva y el punto como parámetros públicos en Menezes-Vanstone, puede ser?

En respuesta a Gerardo Agustin Lerena Amilivia

Re: [Lab4] Ejericicio 5

de Sebastian Federico Fiamene Antelo -

En nuestra implementación tomamos como que debemos pasarle el primo p, como parámetro, por lo que me surje la duda de si es necesario devolverlo al final de la función.

Está bien la suposición que hicimos? o debemos crear un primo aleatorio de 192 bits dentro del algoritmo?

Otra duda, al elegir un punto aleatorio de la curva y verificar si tiene el orden adecuado...supongamos que tomo un punto y no me verifica el orden de la curva, tengo que seguir tomando puntos hasta chequear todos los puntos y alguno verifique y si no verifica ninguno volver al paso 1 o vuelvo al paso 1 al no verificarse el primer punto de la curva como dice en el punto 10?
Porque capaz que la curva me sirve y yo me tome un punto que no, y en ese caso estaría descartando la curva cuando puede haber otro punto de la curva que si me diga que la curva tiene el orden adecuado.

 

La salida c de sha-1 la retornamos en formato entero o hexadecimal?
El punto, lo retornamos con cada coordenada por separado o todo junto?

 

Saludos.

En respuesta a Sebastian Federico Fiamene Antelo

Re: [Lab4] Ejericicio 5

de Nathan Ryan -

En nuestra implementación tomamos como que debemos pasarle el primo p, como parámetro, por lo que me surje la duda de si es necesario devolverlo al final de la función.

Está bien la suposición que hicimos? o debemos crear un primo aleatorio de 192 bits dentro del algoritmo?

>>> Me parece que son equivalentes.  En algún momento, vas a tener que generar un primo aleatorio de 192 bits.  Si me acuerdo bien, mi función era algo tipo def generar_curva(nbits,...) donde nbits era el tamaño del primo.

 

Otra duda, al elegir un punto aleatorio de la curva y verificar si tiene el orden adecuado...supongamos que tomo un punto y no me verifica el orden de la curva, tengo que seguir tomando puntos hasta chequear todos los puntos y alguno verifique y si no verifica ninguno volver al paso 1 o vuelvo al paso 1 al no verificarse el primer punto de la curva como dice en el punto 10?
Porque capaz que la curva me sirve y yo me tome un punto que no, y en ese caso estaría descartando la curva cuando puede haber otro punto de la curva que si me diga que la curva tiene el orden adecuado.

 >>> Para mí sería mejor probar con otro punto antes de descartar la curva.  En una pregunta anterior, mencioné que E(GF(p)) o es cíclico o el producto de dos grupos cíclicos.  Además, en todos los ejemplos en las especificiaciones, E(GF(p)) tiene orden primo (así que tiene que ser cíclico).  Por ahora, si querés, podés elegir solamente curvas de orden primo para facilitar las cosas (o sea, elegí una curva, calculá su orden, y ver si es primo, repetir hasta que encontrás una curva de orden primo)

La salida c de sha-1 la retornamos en formato entero o hexadecimal?
El punto, lo retornamos con cada coordenada por separado o todo junto?

 >>> Eso no es tan importante para mi. Siguiendo las especificaciones, todo excepto el primo y el orden debería ser en hexadecimal, y el punto debería estar separado por coordenadas.