search

UC-IIC3253 / 2021

Repositorio del curso Criptografı́a y Seguridad Computacional - IIC3253
21 stars 3 forks source link

[Tarea 3] Pregunta 2 - OverflowError #54

Open Pipelao opened 3 years ago

Pipelao commented 3 years ago

Hola @mugartec y @marceloarenassaavedra,

Lo que pasa es que en la función de firma_Schnorr al calcular el s = k - x*e este queda negativo, por lo que al pasarlo a la función de exp_mod no se puede porque es negativo, y al invertir el número para pasarle el exponente positivo, se obtiene un OverflowError, ¿qué deberíamos hacer en este caso? Porque cuando lo ejecuto con el número negativo la función verificar_firma_Schnorr retorna False.

Dunkan1 commented 3 years ago

Hola, no soy profe ni ayudante pero creo que en realidad deberia ser s = (k - (x*e)) mod (p-1) el -1 en p-1 si no me equivoco es por el teorema pequeño de fermat.

marceloarenassaavedra commented 3 years ago

Como fue comentado en clases, s = k - x*e puede ser un número negativo. Si esto sucede no es un problema ya que la función de exponenciación modular sigue estando bien definida. De hecho, con las herramientas vistas en clases ustedes pueden deducir cómo se debe calcular (a**b) mod n si b es un número negativo.

Saludos!

Pipelao commented 3 years ago

Perfecto, gracias @Dunkan1 y @marceloarenassaavedra