Firma de Schnorr

Esquema de firma digital

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

Algoritmo

Elección de parámetros

• Todos los usuarios del esquema de firma de acuerdo en un grupo , de primer orden, con generador, en la que el logaritmo discreto problema se supone que es duro. 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}}$

Notación

En el siguiente,

• La exponenciación significa 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)
• Resta significa resta en un conjunto de grupos de equivalencia
• ${\displaystyle M\in \{0,1\}^{*}}$, el conjunto de cadenas de bits finitas
• ${\displaystyle s,e,e_{v}\in \mathbb {Z} _{q}}$, el conjunto de clases de congruencia módulo${\displaystyle q}$
• ${\displaystyle x,k\in \mathbb {Z} _{q}^{\times }}$, el grupo multiplicativo de números enteros módulo${\displaystyle q}$ (para primos , )${\displaystyle q}$${\displaystyle \mathbb {Z} _{q}^{\times }=\mathbb {Z} _{q}\setminus {\overline {0}}_{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}}$

Firmando

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

• Elija un aleatorio del conjunto permitido.${\displaystyle k}$
• Deja .${\displaystyle r=g^{k}}$
• Let , donde denota concatenación y se representa como una cadena de bits.${\displaystyle e=H(r\parallel M)}$${\displaystyle \parallel }$${\displaystyle r}$
• Deja .${\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 40 bytes.${\displaystyle s,e\in \mathbb {Z} _{q}}$${\displaystyle q<2^{160}}$

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 tanto .${\displaystyle e_{v}=H(r_{v}\parallel M)=H(r\parallel M)=e}$

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

Esto muestra solo que un mensaje correctamente firmado se verificará correctamente; se requieren muchas otras propiedades para un algoritmo de firma seguro.

Fuga de claves por reutilización de 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 diferentes mensajes permitirá a los observadores recuperar la clave privada. ^[2] En el caso de las firmas de Schnorr, esto simplemente requiere restar valores:${\displaystyle k}$${\displaystyle s}$

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

Si, pero entonces puede simplemente aislarse. De hecho, incluso un ligero sesgo en el valor o una fuga parcial de puede revelar la clave privada, después de recopilar suficientes firmas y resolver el problema de los números ocultos . ^[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] 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". ^[5] En particular, no no tiene que ser resistente al choque .${\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 Guillou-Quisquater . Es decir, bajo la suposición de ROMDL, cualquier reducción algebraica debe perder un factor en su relación de tiempo-éxito, donde es una función que permanece cerca de 1 siempre que " sea ​​notablemente menor que 1", donde es la probabilidad de forjar un error al realizar en la mayoría de las 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 t nivel de seguridad bits con 4 t firmas -bit. Por ejemplo, un nivel de seguridad de 128 bits requeriría firmas de 512 bits (64 bytes). La seguridad está limitada por ataques de logaritmos 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, los desarrollos recientes sugieren que se puede lograr un nivel de seguridad de t -bit con 3 t - firmas de bits. ^[5] 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 .

Ver también

• DSA
• EdDSA
• Esquema de la firma ElGamal

Notas

1. Seurin, Yannick (12 de enero de 2012). "Sobre la seguridad exacta de las firmas de tipo Schnorr en el modelo aleatorio de Oracle" (PDF) . Archivo ePrint de criptología . Asociación Internacional para la Investigación Criptológica . Consultado el 11 de agosto de 2014 .
2. https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf
3. Fiat; Shamir (1986). "Cómo demostrar su valía: soluciones prácticas para problemas de identificación y firma" (PDF) . Actas de CRYPTO '86 . Apuntes de conferencias en informática. 263 : 186-194. doi : 10.1007 / 3-540-47721-7_12 . ISBN  978-3-540-18047-0. S2CID  4838652 .
4. Schnorr (1989). "Identificación y firma eficientes para tarjetas inteligentes" (PDF) . Actas de CRYPTO '89 . Apuntes de conferencias en informática. 435 : 239-252. doi : 10.1007 / 0-387-34805-0_22 . ISBN  978-0-387-97317-3. S2CID  5526090 .
5. Neven, inteligente, Warinschi. "Requisitos de la función hash para firmas Schnorr" . IBM Research . Consultado el 19 de julio de 2012 .

Referencias

• Menezes, Alfred J. et al. (1996), Manual de criptografía aplicada , CRC Press.
• CP Schnorr (1990), "Identificación y firmas eficientes para tarjetas inteligentes", en G. Brassard, ed. Avances en criptología — Crypto '89 , 239-252, Springer-Verlag. Notas de la clase en Ciencias de la Computación , nr 435
• Claus-Peter Schnorr (1991), "Generación eficiente de firmas mediante tarjetas inteligentes", Journal of Cryptology 4 (3), 161-174 (PS) (PDF) .

Enlaces externos

• RFC 8235