Esquema de Schnorr

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de septiembre de 2021; las comprobaciones requieren 3 ediciones .

El esquema de Schnorr es uno de los esquemas de autenticación más efectivos y basados en la teoría . La seguridad del circuito se basa en la dificultad de calcular logaritmos discretos . El esquema propuesto por Klaus Schnorr es una modificación de los esquemas ElGamal (1985) y Fiat-Shamir (1986) , pero tiene un tamaño de firma más pequeño. El esquema Schnorr es la base del estándar de la República de Bielorrusia STB 1176.2-99 y los estándares de Corea del Sur KCDSA y EC-KCDSA. Estaba cubierto por la patente estadounidense 4.999.082 , que expiró en febrero de 2008.

Introducción

Los esquemas de autenticación y firma electrónica son uno de los tipos de protocolos criptográficos más importantes y comunes que aseguran la integridad de la información.

El propósito de los protocolos de autenticación se puede entender fácilmente con el siguiente ejemplo. Supongamos que tenemos un sistema de información en el que es necesario diferenciar el acceso a varios datos. También en este sistema hay un administrador que almacena todos los identificadores de usuario con un conjunto de derechos asociados, con la ayuda de los cuales se diferencia el acceso a los recursos. A un usuario se le puede permitir leer un archivo, cambiar el segundo y al mismo tiempo denegar el acceso al tercero. En este ejemplo, asegurar la integridad de la información significa impedir el acceso al sistema a personas que no sean sus usuarios, así como impedir que los usuarios accedan a aquellos recursos para los que no tienen autorización. El método más común de control de acceso, la protección con contraseña , tiene muchos inconvenientes, así que pasemos a la formulación criptográfica del problema.

Hay dos participantes en el protocolo: Alice, que quiere confirmar su identidad, y Bob, que debe verificar esta confirmación. Alice tiene dos claves , una clave pública (pública) y una clave privada (privada) que solo conoce Alice. De hecho, Bob debe verificar que Alice conoce su clave privada usando solo . ${\ estilo de visualización \ mathrm {K} _ {1}}$ ${\ estilo de visualización \ mathrm {K} _ {2}}$ ${\ estilo de visualización \ mathrm {K} _ {2}}$ ${\ estilo de visualización \ mathrm {K} _ {1}}$

El esquema de Schnorr es uno de los más efectivos entre los protocolos de autenticación prácticos que implementa esta tarea. Minimiza la dependencia del cálculo requerido para crear una firma en el mensaje. En este esquema, los cálculos principales se pueden realizar mientras el procesador está inactivo, lo que le permite aumentar la velocidad de firma. Al igual que DSA , el esquema de Schnorr utiliza un subgrupo de orden en . Este método también utiliza una función hash . $q$ ${\ estilo de visualización \ mathbb {Z} _ {p}^{*}}$ ${\displaystyle h:\{0,1\}^{*}\to \mathbb {Z} _{p))$

Generación de claves

La generación de claves para el esquema de firma Schnorr es la misma que la generación de claves para DSA , excepto que no hay restricciones de tamaño. Tenga en cuenta también que el módulo se puede calcular de forma autónoma. $pags$

Se elige un número primo , que suele tener la misma longitud que los bits. $pags$ $1024$
Se elige otro número primo tal que sea divisor de . O en otras palabras, debe hacerse . Es costumbre elegir el tamaño para un número igual a bits. $q$ $p-1$ $p-1\equiv 0{\pmod {q))$ $q$ ${\ estilo de visualización 160}$
Elija un número diferente de , tal que . $gramo$ $una$ $g^{q}\equiv 1{\pmod {p))$
Peggy elige un número entero al azar menor que . $w$ $q$
Peggy calcula . $y=g^{qw}{\pmod {p))$
La clave pública de Peggy es , la clave privada de Peggy es . ${\ estilo de visualización (p, q, g, y)}$ $w$

Protocolo de autenticación

Algoritmo de operación de protocolo

Preprocesamiento . Alice elige un número aleatorio menor que y calcula . Estos cálculos son preliminares y se pueden hacer mucho antes de que llegue Bob. $r$ $q$ $x=g^{r}{\pmod {p}}$
Iniciación. Alice le envía a Bob. $X$
Bob elige un número aleatorio de a y se lo envía a Alice. $mi$ ${\ estilo de visualización 0}$ ${\ estilo de visualización 2^{t}-1}$
Alice calcula y envía a Bob. $s=r+nosotros{\pmod {q))$ $s$
Confirmación. Bob comprueba que $x=g^{s}y^{e}{\pmod {p}}$

La seguridad del algoritmo depende del parámetro t . La complejidad de abrir el algoritmo es aproximadamente igual a . Schnorr aconseja usar t alrededor de 72 bits, para y . Para resolver el problema del logaritmo discreto, en este caso, se requieren al menos los pasos de algoritmos conocidos. $2^{t}$ $p\geq 2^{512}$ $q\geq 2^{140}$ $2^{{72}}$

Ejemplo

Generación de claves:

Seleccionar primo y primo ( ) ${\ estilo de visualización p = 48731}$ ${\ estilo de visualización q = 443}$ ${\ estilo de visualización q|p-1}$
Calculado a partir de la condición , en este caso $gramo$ $g^{q}=1{\pmod {p}}$ ${\ estilo de visualización g = 11444}$
Alice elige una clave privada y calcula una clave pública ${\ estilo de visualización w = 357}$ $y=g^{qw}{\pmod {p}}=7355$
Alice envía la clave pública , respectivamente, igual a , la clave privada se mantiene - ${\ estilo de visualización (p, q, g, y)}$ ${\ estilo de visualización (48731,443,11444,7355)}$ ${\ estilo de visualización w = 357}$

Autenticación:

Alice elige un número al azar y se lo envía a Bob. ${\ estilo de visualización r = 274}$ $x=g^{r}{\pmod {p}}=37123$
Bob le envía un número a Alice ${\ estilo de visualización e = 129}$
Alice cuenta y envía a Bob. $s=(r+w*e){\pmod {q}}=255$ $s$
Bob calcula e identifica a Alice porque . $z=g^{s}*y^{e}{\pmod {p}}=37123$ ${\ estilo de visualización z = x}$

Ataques al Esquema

Enemigo pasivo

Si asumimos en el esquema de Schnorr que Alice es un adversario, entonces en el paso 1 puede elegir de manera aleatoria pero eficiente. Sea el número pasado por Alice. Supongamos que es posible encontrar dos números aleatorios y que para cada uno de ellos Alice puede encontrar el correspondiente y cuya confirmación dará un resultado positivo. Obtenemos: $X$ $X$ $e_{1}$ $e_{2}$ ${\displaystyle e_{1}\neq e_{2))$ $s_{1}$ $s_{2}$

x=g^{s_{1}}y^{e_{1}}{\bmod {p}}

x=g^{s_{2}}y^{e_{2}}{\bmod {p}}

Desde aquí o . Como , entonces existe y, por lo tanto, , es decir, el logaritmo discreto de . Por lo tanto, es raro que Alice pueda responder adecuadamente a ambos (dado el mismo ) en el paso 3 del protocolo, lo que significa que el ataque de Alice tiene éxito solo con una probabilidad insignificante. O tales valores se encuentran a menudo, y luego el algoritmo que usa Alice se puede usar para calcular logaritmos discretos. $g^{s_{1}}y^{e_{1}}=g^{s_{2}}y^{e_{2}}{\pmod {p}}$ $y^{e_{1}-e_{2}}=g^{s_{2}-s_{1}}{\pmod {p}}$ ${\displaystyle e_{1}\neq e_{2))$ $(e_{2}-e_{1})^{-1}{\bmod {q))$ $(s_{1}-s_{2})(e_{2}-e_{1})^{-1}=w{\bmod {q))$ $y$ ${\displaystyle e_{1},e_{2},e_{1}\neq e_{2))$ $X$

En otras palabras, se demuestra que, bajo el supuesto de que el problema del logaritmo discreto es difícil, el esquema de autenticación de Schnorr es resistente frente a un adversario pasivo, es decir, correcto.

Enemigo activo

Un adversario activo puede realizar una serie de sesiones de ejecución de protocolo como verificador con un probador honesto (o escuchar a escondidas dichas ejecuciones) y luego intentar atacar el esquema de autenticación. Para la resistencia frente a un adversario activo, es suficiente que el protocolo de autenticación sea una prueba de conocimiento cero . Sin embargo, nadie ha podido aún probar la propiedad de conocimiento cero para el esquema de Schnorr.

Protocolo de firma digital

El algoritmo de Schnorr también se puede utilizar como protocolo para firmar digitalmente un mensaje . El par de claves es el mismo, pero se agrega una función hash unidireccional . $METRO$ ${\ estilo de visualización H (M)}$

Generación de firmas

Tramitación preliminar. Peggy elige un número aleatorio menor que y calcula . Esta es la etapa de precálculo. Vale la pena señalar que las mismas claves públicas y privadas se pueden usar para firmar diferentes mensajes, mientras que el número se elige de nuevo para cada mensaje. $r$ $q$ $x=g^{r}{\pmod {p}}$ $r$
Peggy concatena el mensaje y procesa el resultado para obtener la primera firma: $METRO$ $X$ $S_{1}=H(M|g^{r}{\bmod {p)))$
Peggy calcula la segunda firma. Cabe señalar que la segunda firma se calcula módulo . $q$ $S_{2}=r+wS_{1}{\bmod {q))$ .
Peggy le envía un mensaje a Víctor y subtítulos , . $METRO$ $S_{1}$ $S_{2}$

Verificación de firma

Víctor calcula (o , si se calcula como ). $X=g^{S_{2}}y^{S_{1}}{\bmod {p}}$ $X=g^{S_{2}}y^{-S_{1}}{\bmod {p}}$ $y$ $y=g^{w}{\pmod {p}}$
Víctor comprueba eso . Si es así, considera que la firma es válida. $H(M|X)=S_{1}$

Eficiencia

Los principales cálculos para generar una firma se realizan en la etapa de preprocesamiento y en la etapa de cálculo , donde los números y tienen el orden de bits, y el parámetro es un bit. La última multiplicación es insignificante en comparación con la multiplicación modular en el esquema RSA . $wS_{1}{\bmod {q))$ $w$ $S_{1}$ ${\ estilo de visualización 140}$ $r$ ${\ estilo de visualización 72}$

La verificación de firma consiste principalmente en un cálculo que se puede hacer en el promedio de cálculos de módulo donde hay una longitud en bits. $X=g^{S_{2}}y^{S_{1}}$ ${\ estilo de visualización 1,5 l + 0,25 t}$ $pags$ $l=[log_{2}q]$ $q$

Una firma más corta reduce el número de operaciones para la generación y verificación de la firma: en el esquema Schnorr y en el esquema ElGamal . $O(\log _{2}q\log _{2}^{2}p)$ $O(\log ^{3}p)$

Ejemplo

Generación de claves:

${\ estilo de visualización q = 103}$ y . y . ${\ estilo de visualización p = 2267}$ ${\ estilo de visualización p = 22q + 1}$
Se selecciona el , que es el elemento del campo . Entonces y ${\ estilo de visualización f = 2}$ $Z_{2267*}$ ${\frac{p-1}{q}}=22$ $g=2^{22}{\bmod {2}}267=354$
Peggy elige la llave entonces ${\ estilo de visualización w = 30}$ ${\ estilo de visualización y = 1206}$
La clave privada de Peggy es , la clave pública es . ${\ estilo de visualización 30}$ ${\ estilo de visualización (103,2267,354,1206)}$

Firma del mensaje:

Peggy necesita firmar el mensaje . $M=1000$
Peggy elige y calcula . ${\ estilo de visualización r = 11}$ ${\ estilo de visualización g^{r}=354^{11}=630mod2267}$
Supongamos que el mensaje es , y la conexión en serie significa . Suponga también que el hash de este valor produce un resumen . Esto significa ${\ estilo de visualización 1000}$ ${\ estilo de visualización 1000630}$ ${\ estilo de visualización H (1000630) = 200}$ ${\ estilo de visualización S_ {1} = 200}$
Peggy calcula . $S_{2}=r+wS_{1}modq=11+30*200mod103=11+26=37$
Peggy envía a Víctor y . $M=1000$ ${\ estilo de visualización S_ {1} = 200}$ ${\ estilo de visualización S_ {2} = 37}$

Patentes

El esquema de Schnorr tiene patentes en varios países. Por ejemplo, US #4,995,082 con fecha del 19 de febrero de 1991 (caducó el 19 de febrero de 2008). En 1993, Public Key Partners (PKP) de Sunnyvale adquirió los derechos mundiales de esta patente. Además de los Estados Unidos, este esquema también está patentado en varios otros países.

Modificaciones esquemáticas

Una modificación del circuito realizada por Ernie Brickell y Kevin McCurley en 1992 mejoró enormemente la seguridad del circuito. Su método utiliza el número , que, al igual que , es difícil de descomponer, un divisor simple del número y un elemento exponente en , que posteriormente se utilizan en la firma. A diferencia del esquema de Schnorr, la firma en su método se calcula mediante la ecuación $pags$ $p-1$ $q$ $p-1$ $\alfa$ $q$ ${\ estilo de visualización \ mathbb {Z} _ {p}^{*}}$

s=e\alpha +k{\bmod {(}}p-1)

Beneficios

Si bien la modificación de Brickell y McCarley es computacionalmente menos eficiente que el esquema de Schnorr, este método tiene la ventaja de basarse en la dificultad de dos problemas complejos:

cálculo del logaritmo en el subgrupo cíclico de orden en ; $q$ ${\ estilo de visualización \ mathbb {Z} _ {p}^{*}}$
factorización _ $p-1$

Véase también

Notas

Literatura

Schnorr CP Generación Eficiente de Firma por Tarjetas Inteligentes. - J. Criptología, 1991. - S. 161-174.
Schnorr CP Identificación y Firma Eficiente para Tarjetas Inteligentes. Avances en Criptología - CRYPTO'89. Lecture Notes in Computer Science 435. - 1990. - S. 239 - 252.
A. Menezes, P. van Oorschot, S. Vanstone. Manual de Criptografía Aplicada. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7 .
Schneier B. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .
Varnovsky N. P. Protocolos criptográficos // Introducción a la criptografía / Editado por V. V. Yashchenko. - Pedro, 2001. - 288 p. - ISBN 5-318-00443-1 . Archivado el 25 de febrero de 2008 en Wayback Machine .

Enlaces

RFC 8235

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP