Firma de anillo

Firma en anillo ( ring signature en inglés  ) - una opción de implementación para una firma electrónica , en la que se sabe que el mensaje fue firmado por uno de los miembros de la lista de firmantes potenciales, pero no se revela quién. El firmante forma independientemente una lista de un número arbitrario de personas diferentes, incluyéndose a sí mismo en ella. Para aplicar una firma, el firmante no requiere permiso, asistencia o asistencia de las personas incluidas en la lista; solo se utilizan las claves públicas de todos los miembros de la lista y la clave privada solo del propio firmante.

El algoritmo matemático de la firma del anillo fue desarrollado por Ronald Rivest , Adi Shamir y Yael Tauman , presentándolo  en 2001 en la conferencia internacional Asiacrypt [1] . Según los autores, en el título intentaron enfatizar la ausencia de una estructura central o coordinada en la formación de tal firma: "... los anillos son figuras geométricas con una periferia uniforme y sin centro".

Historia

La idea de una firma grupal bajo peticiones o denuncias, que confirme que todos los firmantes apoyan el recurso, pero que no permita identificar a su autor o iniciador, tiene su origen en el pasado. Así, el término inglés “ round-robin ” se conoce desde el siglo XVII y denota una petición que se firmaba en círculo sin respetar la jerarquía para evitar el castigo del firmante primero [2] - una especie de garantía mutua . En 1898, luego del sitio de la ciudad de Santiago de Cuba durante la Guerra Hispano-Estadounidense, oficiales de alto rango del V Cuerpo de Ejército firmaron una carta en círculo al cuartel general del ejército en Washington exigiendo que el cuerpo fuera devuelto a los Estados Unidos . Estados para el tratamiento y el descanso. La carta llegó a la prensa y se hizo ampliamente conocida , y también causó resonancia en el gobierno del presidente McKinley [3] .

La firma múltiple se ha convertido en el análogo electrónico de la firma en papel en un círculo. En 1991, David Chaum y Eugene Van Heyst propusieron un esquema de firma grupal  [1] , donde el firmante es uno de los miembros del grupo formado por el administrador . El verificador puede verificar que el firmante es miembro del grupo, pero no puede averiguar quién. En este caso, el administrador tiene la capacidad de identificar al firmante [4] .  

Las firmas de anillo son esencialmente similares a las firmas de grupo, pero, a diferencia de estas últimas, no hay forma de identificar al firmante, no hay administrador ni coordinador. Es posible que todos los miembros de la lista, con la excepción del propio firmante, no conozcan el contenido del mensaje, o incluso el hecho de que alguien utilizó su clave pública para formar una firma de anillo [1] .

Descripción general del mecanismo para crear y verificar una firma de anillo

Se supone que existe una lista determinada que indica la relación inequívoca de una persona con su clave pública (pública) (por ejemplo, un servidor de claves criptográficas ). El motivo de la aparición de la clave pública en esta lista no importa. Por ejemplo, una persona puede haber creado claves RSA solo para compras por Internet y puede no saber que sus claves públicas están siendo utilizadas por alguien para crear una firma de anillo en un mensaje que nunca ha visto y no desea firmar [1] . El algoritmo general de firma de anillo permite el uso simultáneo de claves públicas generadas por diferentes sistemas (algoritmos), incluidos aquellos con diferentes tamaños tanto de claves como de firmas [1] .

Al crear una firma de anillo para un mensaje m , el firmante, a su discreción, forma una lista de claves públicas ( P 1 , P 2 , …, P n ), en la que también incluye su número i (su número de serie en la lista no importa). Todo ello, junto con la clave secreta del firmante Si , se alimenta como parámetros a la entrada de la función de superposición de firma ( m , Si , P1 , … , Pn ) , obteniendo el resultado σ en la salida . Aunque cada clave pública de la lista tiene su propia clave privada única y solo se utiliza una de ellas (la que pertenece al firmante), es imposible saber a partir de la firma resultante cuál de las claves privadas se utilizó para crearla. Incluso con un número ilimitado de firmas de anillo realizadas por el mismo firmante, no hay forma de identificarlo o al menos establecer con certeza que algunas firmas se aplicaron utilizando la misma clave privada [1] .

La autenticidad de la firma del anillo se puede verificar utilizando σ , m y solo las claves públicas P 1 , …, P n [5] .

Opciones de implementación

En su artículo, Rivest, Shamir y Tauman describieron la firma del anillo como una forma de filtrar información secreta sin perder su credibilidad. Por ejemplo, la firma en el anillo de un "funcionario de alto rango de la Casa Blanca " no revelará su identidad, pero garantiza que el mensaje fue firmado por alguien de la lista especificada de funcionarios, lo que confirma el nivel de competencia. Al mismo tiempo, la lista de personas para la firma del anillo se puede compilar fácilmente tomando claves públicas de fuentes abiertas [1] .

Otra aplicación, también descrita por los autores de la idea, es para crear firmas ambiguas (controvertidas) . En el caso más simple, para este uso, la firma del anillo se forma en base a las claves del remitente y el destinatario del mensaje. Entonces la firma es significativa para el destinatario, está seguro de que el remitente creó el mensaje. Sin embargo, para un extraño, tal firma pierde credibilidad y falta de ambigüedad: no habrá certeza de quién formó y firmó exactamente el mensaje, porque podría ser el destinatario mismo. Esa firma, por ejemplo, no puede utilizarse en los tribunales para identificar al remitente [1] .

Posteriormente, aparecieron trabajos en los que se proponían nuevas áreas de aplicación de las firmas anulares y algoritmos alternativos para su formación [6] [7] .

Firmas de anillo de umbral

A diferencia de la firma de umbral estándar "t-out-of-n" , donde t de n usuarios deben cooperar para descifrar un mensaje, esta variante de firma de anillo requiere que t usuarios cooperen en el proceso de firma. Para hacer esto, t participantes ( i 1 , i 2 , …, i t ) deben calcular la firma σ para el mensaje m proporcionando t claves privadas y n públicas a la entrada ( m , S i 1 , S i 2 , … , Sentarse , PAGS 1 , ..., PAGS norte ) [ 8 ] .

Firmas de anillo enlazables

La propiedad de conectividad le permite determinar si dos firmas de anillo fueron creadas por la misma persona (si se utilizó la misma clave privada), pero sin especificar quién. Una posible aplicación podría ser un sistema de dinero electrónico fuera de línea [9] .

Firma de anillo rastreable

Además de la firma asociada, la clave pública del firmante puede quedar expuesta cuando se reutilice. Tal protocolo permite la implementación de sistemas secretos de votación electrónica que permiten que solo una firma sea anónima, pero revelan al participante que votó dos veces [10] .

Criptomonedas

El sistema CryptoNote permite firmas circulares [11] . Esto se usó por primera vez en julio de 2012 en la criptomoneda Bytecoin [12] [13] ( que no debe confundirse con Bitcoin ).

La criptomoneda ShadowCash utiliza una firma de anillo rastreable para anonimizar al remitente de una transacción [14] . Sin embargo, la implementación inicial fue defectuosa, lo que llevó a la desanonimización parcial de ShadowCash desde la primera implementación hasta febrero de 2016 [15] .

Eficiencia

La mayoría de los algoritmos propuestos tienen un tamaño de resultado asintótico , es decir, el tamaño de la firma resultante es directamente proporcional al número de claves públicas utilizadas. Cada clave pública utilizada al imponer o verificar una firma de anillo requiere una cantidad fija de cálculos, que es mucho mejor que los análogos disponibles en el momento en que se creó el protocolo [1] . Por ejemplo, la tecnología CryptoNote implementa firmas en anillo en los pagos p2p para garantizar el anonimato del remitente [10] .

Recientemente, han aparecido algoritmos más eficientes. Hay esquemas con un tamaño sublineal de la firma [16] , así como con un tamaño constante [17] .

Algoritmo

La esencia del algoritmo de firma de anillo propuesto por Rivest, Shamir y Tauman es la siguiente [1] (ver diagrama).

La firma de timbre para algún mensaje se generará en base a la lista de claves públicas (indicadas en el diagrama como ), entre las cuales la clave del firmante tiene un número de serie . Las claves públicas le permiten encriptar información arbitraria (el bloque de información , encriptado con la clave , se indica en el diagrama como ). Los " bloques de información " en adelante no forman parte ni son el resultado del procesamiento del mensaje firmado y no tienen un significado independiente, son datos generados aleatoriamente que se convierten en componentes de la firma.

Existe una función de combinación de un número arbitrario de argumentos , por el valor de los cuales y los valores de todos los argumentos, excepto uno, uno puede restaurar de forma única un argumento faltante. Un ejemplo de tal función es la suma secuencial: si se conocen la suma total y todos los términos excepto uno, entonces se puede calcular el término faltante (reduciendo la suma total por el valor de todos los términos conocidos).

Como función de combinación, los autores del algoritmo propusieron la siguiente secuencia de acciones: se toma un determinado valor de partida (indicado en el diagrama , se genera aleatoriamente), sobre el cual y el primer argumento se realiza un “o” exclusivo bit a bit ( indicado en el diagrama por el símbolo ). Luego, se aplica cierta transformación reversible al resultado (indicado en el diagrama como ), uno a uno asociado con la suma hash del mensaje que se firma. El resultado se somete a XOR bit a bit con el segundo argumento, la conversión se aplica de nuevo, y así sucesivamente. Los bloques de información correspondientes encriptados con claves públicas se utilizan como argumentos .

El valor aleatorio seleccionado es tanto el valor inicial como el objetivo (final) de la función de combinación: el resultado de todas las transformaciones debe "dar la vuelta al círculo" y volverse igual al valor inicial. Los bloques de información para cada una de las claves, excepto el bloque correspondiente a la propia clave del firmante, se dan como valores aleatorios. El firmante encripta los bloques de información con las claves públicas correspondientes. El firmante ahora tiene el valor de destino de la función combinatoria y todos menos uno de los argumentos, el correspondiente a su propia clave. Gracias a las propiedades de la función combinacional, el firmante puede averiguar el argumento faltante y, utilizando su propia clave privada ( ), “descifrar” este argumento ( ), obteniendo el bloque de información faltante .

Componentes de la firma del anillo terminado [1] :

• mensaje firmado;
• lista de todas las claves públicas utilizadas;
• valores de todos los bloques de información ;
• el valor de la función de combinación .

Para verificar la firma necesitas [1] :

• usar claves públicas para cifrar bloques de información;
• usando la suma hash del mensaje a firmar, calcule el valor de la función de combinación, usando como argumentos (estableciendo el valor inicial) y bloques de información encriptados (resultados del paso anterior);
• asegúrese de que el valor recibido coincida con el .

Ejemplo de implementación

Como ejemplo, se proporciona una implementación en Python de un algoritmo básico utilizando claves RSA .

import os import hashlib import random import Crypto.PublicKey.RSA Anillo de clase : def __init__ ( self , k , L = 1024 ): self . k = k uno mismo . l = L mismo . n = len ( k ) uno mismo . q = 1 << ( L - 1 ) signo def ( self , m , z ): self . permut ( m ) s = [ Ninguno ] * self . tu = aleatorio ._ _ randint ( 0 , uno mismo . q ) c = v = uno mismo . E ( u ) para i en ( rango ( z + 1 , self . n ) + rango ( z )): s [ i ] = aleatorio . randint ( 0 , self . q ) e = self . g ( s [ yo ], yo . k [ yo ] . mi , yo . k [ yo ] . norte ) v = yo . E ( v ^ e ) si ( i + 1 ) % yo mismo . norte == 0 : do = v s [ z ] = yo . g ( v ^ u , self . k [ z ] . d , self . k [ z ] . n ) return [ c ] + s def verificar ( self , m , X ): self . permut ( m ) def _f ( i ): return self . g ( X [ i + 1 ], self . k [ i ] . e , self . k [ i ] . n ) y = map ( _f , range ( len ( X ) - 1 )) def _g ( x , i ) : volver a sí mismo . E ( x ^ y [ i ]) r = reducir ( _g , rango ( self . n ), X [ 0 ]) volver r == X [ 0 ] def permut ( self , m ): self . p = int ( hashlib . sha1 ( ' %s ' % m ) . hexdigest (), 16 ) def E ( self , x ): mensaje = ' %s%s ' % ( x , self . p ) return int ( hashlib . sha1 ( msg ) . hexdigest (), 16 ) def g ( self , x , e , n ): q , r = divmod ( x , n ) if (( q + 1 ) * n ) <= (( 1 << self . l ) - 1 ): rslt = q * n + pow ( r , e , n ) else : rslt = x return rslt

Firmando y verificando 2 mensajes con un anillo de 4 usuarios:

tamaño = 4 msg1 = 'hola' msg2 = '¡mundo!' def _rn ( _ ): devuelve Cripto . clave pública . R.S.A._ _ generar ( 1024 , os . urandom ) clave = mapa ( _rn , rango ( tamaño )) r = anillo ( clave ) para i en rango ( tamaño ): s1 = r . signo ( msg1 , yo ) s2 = r . firmar ( msg2 , i ) afirmar r . verificar ( msg1 , s1 ) y r . verificar ( msg2 , s2 ) y no r . verificar ( msg1 , s2 )

Notas

1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Ronald L. Rivest , Adi Shamir , Yael Tauman. Cómo filtrar un secreto  // Avances en criptología - ASIACRYPT 2001 / C. Boyd (ed.). - Berlín, Heidelberg: Springer-Verlag , 2001. - P. 552-565. - ( Lecture Notes in Computer Science . Vol. 2248).
2. ↑ I. Yu. Pavlovskaya . Análisis fonosemántico del habla. - San Petersburgo. : Editorial de la Universidad de San Petersburgo, 2001. - 290 p.
3. ↑ Diccionario histórico de la guerra hispanoamericana / Donald H. Dyal, Brian B. Carpenter y Mark A. Thomas, eds. — Westport, Connecticut: Greenwood Press , 1996.
4. ↑ B. Schneier . Criptografía  aplicada . - Nueva York: John Wiley & Sons , 1996. - Pág. 98.
5. ↑ Debnath A., Singaravelu P., Verma, S. Esquema de protección de privacidad espacial eficiente para la red de sensores // Central European Journal of Engineering . - 2013. - Vol. 3, núm. 1.- Pág. 1-10. -doi : 10.2478 / s13531-012-0048-7 .
6. ↑ Lingling Wang, Guoyin Zhang, Chunguang Ma. Una encuesta de la firma del anillo // Fronteras de la ingeniería eléctrica y electrónica en China. - 2008. - Vol. 3, núm. 1.- Pág. 10-19. -doi : 10.1007/ s11460-008-0012-8 .
7. ↑ Hu Xiong, Zhiguang Qin, Fagen Li. Una taxonomía de esquemas de firma de anillo: teoría y aplicaciones // IETE Journal of Research. - 2013. - Vol. 59, núm. 4.- Págs. 376-382. -doi : 10.4103/ 03772063.2013.10876518 .
8. ↑ Bresson E., Stern J., Szydlo M. Firmas de anillo de umbral y aplicaciones para grupos ad-hoc // Avances en criptología: CRYPTO 2002 / Moti Yung. - Berlín, Heidelberg, Ney York, Barcelona, ​​Hong Kong, Londres, Milán, París, Tokio: Springer, 2002. - Pág. 465-480. - ( Lecture Notes in Computer Science . Vol. 2442). -doi : 10.1007/ 3-540-45708-9_30 .
9. ↑ Liu JK, Wong DS Firmas de anillos enlazables: modelos de seguridad y nuevos esquemas // Ciencia computacional y sus aplicaciones - ICCSA 2005. - Berlín; Nueva York: Springer, 2005. vol. 2.- Pág. 614-623. - ( Lecture Notes in Computer Science . Vol. 3481). -doi : 10.1007/ 11424826_65 .
10. ↑ 1 2 Fujisaki E., Suzuki K. Firma de anillo trazable // Criptografía de clave pública - PKC 2007. - Berlín; Heidelberg; Nueva York: Springer, 2007. - P. 181-200. - ( Lecture Notes in Computer Science . Vol. 4450).
11. ↑ Filosofía de CryptoNote . CryptoNoteTech. Consultado el 24 de noviembre de 2017. Archivado desde el original el 24 de noviembre de 2017. (indefinido)
12. ↑ CryptoNote Currencies  (inglés) (2015). Consultado el 29 de noviembre de 2017. Archivado desde el original el 13 de julio de 2017.
13. ↑ ¿CryptoNote es un asesino de Bitcoin? (23 de junio de 2014). Consultado el 29 de noviembre de 2017. Archivado desde el original el 1 de diciembre de 2017. (indefinido)
14. ↑ Rynomster, Tecnovert. ShadowCash: Zeroknowledge Anonymous Distributed ECash via Traceable Ring Signatures  (inglés) (pdf)  (enlace no disponible) . www.shadow.cash (2015). Archivado desde el original el 1 de diciembre de 2017.
15. ↑ Criptodiversión. Cripto roto en Shadowcash  (inglés)  (enlace no disponible) (13/02/2016). Consultado el 29 de noviembre de 2017. Archivado desde el original el 27 de septiembre de 2016.
16. ↑ Fujisaki E. Firmas de anillo trazables de tamaño sublineal sin oráculos aleatorios // Temas de criptología - CT-RSA 2011. - Heidelberg; Dordrecht; Londres; Nueva York: Springer, 2011. - P. 393-415. - ( Lecture Notes in Computer Science . Vol. 6558).
17. ↑ Au, Man Ho; Liu JK; Susilo W.; Yuen, TszHong. Firma de anillo enlazable y revocable basada en ID de tamaño constante // Progreso en criptología - INDOCRYPT 2006. - Heidelberg; Dordrecht; Londres; Nueva York: Springer, 2006.—Pág. 364-378. - ( Lecture Notes in Computer Science . Vol. 4329).

Literatura

• Chikishev G. O. Firma de anillo único y su aplicación en efectivo electrónico // Matemáticas discretas aplicadas. - 2012. - Nº 5. - S. 56-58. - Solicitud.
• Zapechnikov SV y otros . Ring signatures y sus aplicaciones en la Enciclopedia de Criptografía Teórica y Aplicada, MEPhI

diccionarios y enciclopedias	gran chino

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