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.