signature – ¿Cómo funciona el proceso de verificación asociado a este esquema de firma?

Pregunta:

Mi profesor de criptología nos pidió que demostráramos que, si bien el siguiente esquema de firma es conceptualmente válido, es intrínsecamente inseguro; sin embargo, no estoy seguro de cómo demostrar que el proceso de verificación asociado produce una igualdad si la firma es válida.

El protocolo funciona de la siguiente manera dado:

  • Un primo $p$ compartido públicamente;
  • Una raíz primitiva de $p$, $a|a<q$
  • Una clave privada: $x|x<q$; y
  • Una clave pública: $y=a^x\bmod{q}$
  • Una función hash criptográfica $H=\texttt{SHA1}$

Se puede generar una firma $s$ para $m$ de la siguiente manera: primero, calcule $h = H(m)$; if $\texttt{gcd}(h, q-1) \neq 1$ agrega $h$ a $m$ y calcula un nuevo hash, y continúa el proceso hasta que $h$ y $q-1$ sean primos relativos.

Luego, calcule $z|z\cdot h\equiv x\bmod{q-1}$ y devuelva la firma $s = a^{z}$.

Para verificar $s$, un usuario verifica que $Y=(a^z)^{h}=a^{x}\bmod{q}$.


Por ejemplo, para firmar un mensaje $m$, donde:

  • $q=6043$
  • $a=5$
  • $x=1098$
  • $y=485$
  • $h\flecha izquierda H(m)=612515367434372930600221767499032307523881412051$
  • $z\leftarrow z\cdot h\equiv x\bmod{q-1}=8513$
  • $s\flecha izquierda a^{z} = 5845$

Dada la firma $s$, un usuario puede verificar que la firma es correcta verificando que $y=(a^{z})^{h}=a^{x}\bmod{q}$, sin embargo, soy no estoy seguro de cómo evaluar

$$(a^{z})^{h}= a^{x}\bmod{q}$$

ya que $h$ es (relativamente) grande. Yo (creo) que necesito evaluar la siguiente expresión, sin embargo, no estoy seguro si es computacionalmente factible ya que:

$$(a^{z})^{h}\rightarrow s^{h}\rightarrow 5845^{612515367434372930600221767499032307523881412051}$$

Es decir, para verificar la firma, tendría que realizar el siguiente cálculo:

$$(5^{8513})^{612515367434372930600221767499032307523881412051} = 5^{1098}\bmod{6043}$$

Normalmente, usaría exponenciación modular rápida aquí, pero $h$ es absolutamente enorme. Por un tiempo, pensé que tal vez no entendí bien el protocolo y que $h$ debería reducirse al módulo $q$, pero, de nuevo, ¿tal vez solo tengo una comprensión vergonzosamente defectuosa del protocolo?

¿Cómo crees que debo verificar la firma?

Respuesta:

Lo siento, no puedo comentar todavía. Así que voy a ser más detallado ya que es una respuesta;)

Obtengo otros valores para $z$ y $s$: $$h^{-1} = 2441\mod q-1 $$ y $$z = x \cdot h^{-1} = 3612\mod q- 1\\ \Rightarrow s = a^z = 1039\mod q$$

El valor hash $h$ se puede reducir ya que estamos trabajando en el módulo $q$. Con $q$ primo tenemos $\phi(q) = q-1$ y podemos reducir el exponente módulo $q-1$.

Esto da $$y' = s^h = s^{h\mod q-1} \mod q\\$$ Así que con $h \equiv 2297 \mod q-1$ verificamos: $$y' = 1039 ^{2297}\mod 6043 = 485 = y$$ como se desee.

Deja un comentario

Tu dirección de correo electrónico no será publicada.

Ir arriba