Firma de Schnorr

Esquema de firma digital

En criptografía , una firma Schnorr es una firma digital producida por el algoritmo de firma Schnorr que fue descrito por Claus Schnorr . Es un esquema de firma digital conocido por su simplicidad, entre los primeros cuya seguridad se basa en la intratabilidad de ciertos problemas de logaritmos discretos . Es eficiente y genera firmas cortas. ^[1] Estaba amparado por la patente estadounidense 4.995.082 que expiró en febrero de 2010.

Algoritmo

Elección de parámetros

• Todos los usuarios del esquema de firmas coinciden en un grupo , , de orden primo, , con generador, , en el que se supone que el problema de logaritmo discreto es difícil. Normalmente se utiliza un grupo de Schnorr . ${\displaystyle G}$ ${\displaystyle q}$ ${\displaystyle g}$
• Todos los usuarios están de acuerdo con una función hash criptográfica . ${\displaystyle H:\{0,1\}^{*}\rightarrow \mathbb {Z} /q\mathbb {Z} }$

Notación

A continuación,

• La exponenciación representa la aplicación repetida de la operación de grupo.
• La yuxtaposición significa multiplicación en el conjunto de clases de congruencia o aplicación de la operación de grupo (según corresponda)
• La resta significa restar en el conjunto de clases de congruencia.
• ${\displaystyle M\in \{0,1\}^{*}}$, el conjunto de cadenas de bits finitos
• ${\displaystyle s,e,e_{v},x,k\in \mathbb {Z} /q\mathbb {Z} }$, el conjunto de clases de congruencia módulo ${\displaystyle q}$
• ${\displaystyle y,r,r_{v}\in G}$.

Generación de claves

• Elija una clave de firma privada, , del conjunto permitido. ${\displaystyle x}$
• La clave de verificación pública es . ${\displaystyle y=g^{-x}}$

Firma

Para firmar un mensaje, : ${\displaystyle M}$

• Elija un número aleatorio del conjunto permitido. ${\displaystyle k}$
• Dejar . ${\displaystyle r=g^{k}}$
• Sea , donde denota concatenación y se representa como una cadena de bits. ${\displaystyle e=H(r\parallel M)}$ ${\displaystyle \parallel }$ ${\displaystyle r}$
• Dejar . ${\displaystyle s=k+xe}$

La firma es el par, . ${\displaystyle (s,e)}$

Tenga en cuenta que ; si , entonces la representación de la firma puede caber en 64 bytes. ${\displaystyle s,e\in \mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle q<2^{256}}$

Verificando

• Dejar ${\displaystyle r_{v}=g^{s}y^{e}}$
• Dejar ${\displaystyle e_{v}=H(r_{v}\parallel M)}$

Si entonces se verifica la firma. ${\displaystyle e_{v}=e}$

Prueba de corrección

Es relativamente fácil ver que si el mensaje firmado es igual al mensaje verificado: ${\displaystyle e_{v}=e}$

${\displaystyle r_{v}=g^{s}y^{e}=g^{k+xe}g^{-xe}=g^{k}=r}$, y por lo tanto . ${\displaystyle e_{v}=H(r_{v}\parallel M)=H(r\parallel M)=e}$

Elementos públicos : , , , , , . Elementos privados: , . ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle q}$ ${\displaystyle y}$ ${\displaystyle s}$ ${\displaystyle e}$ ${\displaystyle r}$ ${\displaystyle k}$ ${\displaystyle x}$

Esto sólo demuestra que un mensaje firmado correctamente se verificará correctamente; se requieren muchas otras propiedades para un algoritmo de firma seguro.

Fuga de claves debido a la reutilización de valores nonce

Al igual que con los algoritmos de firma estrechamente relacionados DSA , ECDSA y ElGamal , la reutilización del valor nonce secreto en dos firmas Schnorr de mensajes diferentes permitirá a los observadores recuperar la clave privada. ^[2] En el caso de las firmas Schnorr, esto simplemente requiere restar valores: ${\displaystyle k}$ ${\displaystyle s}$

${\displaystyle s'-s=(k'-k)-x(e'-e)}$.

Si, pero entonces, se puede aislar de forma sencilla. De hecho, incluso pequeños sesgos en el valor o una fuga parcial de pueden revelar la clave privada, después de recopilar suficientes firmas y resolver el problema del número oculto. ^[2] ${\displaystyle k'=k}$ ${\displaystyle e'\neq e}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle k}$

Argumento de seguridad

El esquema de firma se construyó aplicando la transformación Fiat-Shamir ^[3] al protocolo de identificación de Schnorr. ^{[4] [5]} Por lo tanto, (según los argumentos de Fiat y Shamir), es seguro si se modela como un oráculo aleatorio . ${\displaystyle H}$

Su seguridad también se puede argumentar en el modelo de grupo genérico , bajo el supuesto de que es "resistente a la preimagen de prefijo aleatorio" y "resistente a la segunda preimagen de prefijo aleatorio". ^[6] En particular, no necesita ser resistente a colisiones . ${\displaystyle H}$ ${\displaystyle H}$

En 2012, Seurin ^[1] proporcionó una prueba exacta del esquema de firma de Schnorr. En particular, Seurin muestra que la prueba de seguridad que utiliza el lema de bifurcación es el mejor resultado posible para cualquier esquema de firma basado en homomorfismos de grupo unidireccionales, incluidas las firmas de tipo Schnorr y los esquemas de firma de Guillou-Quisquater. Es decir, bajo el supuesto ROMDL, cualquier reducción algebraica debe perder un factor en su razón de tiempo hasta el éxito, donde es una función que permanece cercana a 1 siempre que " sea notablemente menor que 1", donde es la probabilidad de falsificar un error al realizar como máximo consultas al oráculo aleatorio. ${\displaystyle f({\epsilon }_{F})q_{h}}$ ${\displaystyle f\leq 1}$ ${\displaystyle {\epsilon }_{F}}$ ${\displaystyle {\epsilon }_{F}}$ ${\displaystyle q_{h}}$

Firmas cortas de Schnorr

El proceso mencionado anteriormente logra un nivel de seguridad de t bits con 4 firmas de t bits. Por ejemplo, un nivel de seguridad de 128 bits requeriría firmas de 512 bits (64 bytes). La seguridad está limitada por ataques logarítmicos discretos en el grupo, que tienen una complejidad de la raíz cuadrada del tamaño del grupo.

En el artículo original de Schnorr de 1991, se sugirió que, dado que no se requiere resistencia a colisiones en el hash, las funciones hash más cortas pueden ser igual de seguras y, de hecho, desarrollos recientes sugieren que se puede lograr un nivel de seguridad de t bits con firmas de 3 t bits. ^[6] Entonces, un nivel de seguridad de 128 bits requeriría solo firmas de 384 bits (48 bytes), y esto podría lograrse truncando el tamaño de e hasta que sea la mitad de la longitud del campo de bits s .

Véase también

• DSA
• Educación DSA
• Esquema de firma ElGamal

Referencias

1. Seurin, Yannick (12 de enero de 2012). "Sobre la seguridad exacta de las firmas de tipo Schnorr en el modelo de Oracle aleatorio". Archivo de ePrints de criptología . Asociación Internacional de Investigación Criptológica . Consultado el 6 de febrero de 2023 .
2. Tibouchi, Mehdi (13 de noviembre de 2017). "Ataques a las firmas Schnorr con nonces sesgados" (PDF) . Taller ECC . Consultado el 6 de febrero de 2023 .
3. Fiat, Amos ; Shamir, Adi (1987). "Cómo demostrar su valía: soluciones prácticas a los problemas de identificación y firma". En Andrew M. Odlyzko (ed.). Avances en criptología . Conferencia sobre la teoría y aplicación de técnicas criptográficas. Actas de CRYPTO '86. Apuntes de clase en informática. Vol. 263. págs. 186–194. doi : 10.1007/3-540-47721-7_12 . ISBN 978-3-540-18047-0.S2CID 4838652  .
4. Schnorr, CP (1990). "Identificación y firmas eficientes para tarjetas inteligentes". En Gilles Brassard (ed.). Avances en criptología . Conferencia sobre la teoría y aplicación de técnicas criptográficas. Actas de CRYPTO '89. Apuntes de conferencias sobre informática. Vol. 435. págs. 239–252. doi : 10.1007/0-387-34805-0_22 . ISBN 978-0-387-97317-3.S2CID 5526090  .
5. Schnorr, CP (1991). "Generación eficiente de firmas mediante tarjetas inteligentes". Revista de criptología . 4 (3): 161–174. doi :10.1007/BF00196725. S2CID  10976365.
6. Neven, Gregory; Smart, Nigel ; Warinschi, Bogdan. "Requisitos de la función hash para las firmas Schnorr". IBM Research . Consultado el 19 de julio de 2012 .

Enlaces externos

• RFC 8235
• BIP 340: Firmas Schnorr para secp256k1