[T3P1] - Generación de llaves en ElGamal

[VicenteVicente]

Hola, tengo una duda sobre la cota superior de la generación:

¿x e y se extraen de {1,...,q}, o bien, de {1,...,q-1}? (La primera es la que vimos en clases, pero la segunda la he visto en internet)

Adjunto la captura de la versión vista en clases

Saludos y gracias!

[marceloarenassaavedra]

Hola!

Ambas opciones son correctas, pero para la tarea vamos a sacar estos elementos desde el conjunto {1, ..., q-1}. Nótese que en la práctica esto no hace una diferencia porque la probabilidad de sacar q es muy baja.

Saludos!

[VicenteVicente]

Genial, muchas gracias!

[Christian-Klempau]

Una duda sólo por curiosidad, por qué entonces en la tarea debemos sacar números del conjunto {1, ..., q-1} pero la definición en clases es hasta q?

[marceloarenassaavedra]

Todo funciona bien si x = q, pero no es una buena idea seleccionar x = q ya que g ** x es igual al neutro del grupo, por lo que es fácil en este caso calcular el valor de x dado g ** x (calcular el logaritmo discreto). Por esto nos pareció mejor que al momento de construir la clave privada, x sea sacado desde el conjunto {1, ..., q - 1}. De todas formas, esto es un detalle ya que la probabilidad de que x = q en un caso real es muy baja. Por ejemplo, el segundo caso para la clase ZpStar en pregunta1.ipynb incluye valores usados en la práctica, y ahí se tiene que la probabilidad de que x = q es menor que 1/(10 ** 76).

Saludos!

[Christian-Klempau]

Me quedó muy claro, gracias profesor!