Firma del anillo

En criptografía , una firma de anillo es un tipo de firma digital que puede ser realizada por cualquier miembro de un conjunto de usuarios, cada uno con su propia clave . Por lo tanto, un mensaje firmado con una firma de anillo está avalado por alguien de un grupo específico de personas. Una de las propiedades de seguridad de una firma de anillo es que debería ser computacionalmente inviable determinar cuál de las claves de los miembros del conjunto se utilizó para generar la firma. Las firmas de anillo son similares a las firmas de grupo , pero se diferencian en dos aspectos clave: primero, no hay forma de revocar el anonimato de una firma individual; y segundo, cualquier conjunto de usuarios puede utilizarse como conjunto firmante sin configuración adicional.

Las firmas de anillo fueron inventadas por Ron Rivest , Adi Shamir y Yael Tauman Kalai , y presentadas en ASIACRYPT en 2001. ^{[ 1 ]} El nombre, firma de anillo , proviene de la estructura en forma de anillo del algoritmo de firma .

Definición

Supongamos que un conjunto de entidades tiene pares de claves públicas/privadas, ( _P₁ , S₁ ₎, (P₂, S₂), ..., (Pₙ, Sₙ ) _.La parte i _puede calcular _una firma de anillo σ sobre un mensaje m, con la entrada (m, Si, P₁ , ... , _Pₙ ) . Cualquiera puede verificar _la validez de _una firma de anillo dados σ, _m_y las claves públicas involucradas, P₁ , ..., Pₙ _. Si una firma de anillo se calcula correctamente, debería pasar la verificación. Por otro lado, debería ser difícil para cualquiera crear una firma de anillo válida sobre cualquier mensaje para cualquier conjunto sin conocer ninguna de las claves privadas de ese conjunto. ^[²^]

Aplicaciones y modificaciones

Comportamiento del esquema de firmas de anillos de Rivest, Shamir y Tauman

En el artículo original, Rivest, Shamir y Tauman describieron las firmas en anillo como una forma de filtrar información secreta. Por ejemplo, una firma en anillo podría usarse para proporcionar una firma anónima de "un alto funcionario de la Casa Blanca ", sin revelar quién firmó el mensaje. Las firmas en anillo son adecuadas para esta aplicación porque su anonimato es irrevocable y porque el grupo que las firma puede improvisarse.

Otra aplicación, también descrita en el artículo original, es la de las firmas negables . En este caso, el remitente y el destinatario de un mensaje forman un grupo para la firma circular; entonces, la firma es válida para el destinatario, pero cualquier otra persona no podrá estar segura de si el remitente o el destinatario fue quien realmente firmó. Por lo tanto, dicha firma es convincente, pero no puede transferirse más allá de su destinatario previsto.

Hubo varios trabajos que introdujeron nuevas características y se basaron en diferentes supuestos:

Firmas de anillos de umbral: ^{[ 3 ]} A diferencia de la firma umbralestándar "tden", dondetdenusuarios deben colaborar para firmar un mensaje, esta variante de una firma de anillo requieretusuarios cooperen en elprotocolo. Es decir,tpartesS₁, ...,S_t∈ {P₁, ...,P_n} pueden calcular unafirma de anillot,nm, en la entrada (m,S₁, ...,S_t,P₁, ...,P_n).
Firmas de anillos enlazables: ^{[ 4 ]} La propiedad de vinculabilidad permite determinar si dos firmas cualesquiera han sido producidas por el mismo miembro (bajo la misma clave privada). No obstante, se conserva la identidad del firmante. Una de las posibles aplicaciones puede ser unsistema de dinero electrónico.
Firma de anillo rastreable: ^{[ 5 ]} Además del esquema anterior, se revela la clave pública del firmante (si emite más de una firma con la misma clave privada).Se puede implementarsistema de votación electrónica

Eficiencia

La mayoría de los algoritmos propuestos tienen un tamaño de salida asintótico. $O(n)$ ; es decir, el tamaño de la firma resultante aumenta linealmente con el tamaño de la entrada (número de claves públicas). Esto significa que tales esquemas son impracticables para casos de uso reales con suficientemente grandes $n$ (por ejemplo, una votación electrónica con millones de participantes). Pero para alguna aplicación con un tamaño de entrada medio relativamente pequeño , dicha estimación puede ser aceptable. CryptoNote implementa $O(n)$ Esquema de firma de anillo de Fujisaki y Suzuki ^{[ 5 ]} en pagos P2P para lograr la imposibilidad de rastrear al remitente.

Recientemente han aparecido algoritmos más eficientes. Existen esquemas con tamaño sublineal de la firma, ^{[ 6 ]} así como con tamaño constante. ^{[ 7 ]}

Implementación

Plan original

El artículo original describe un esquema de firma de anillo basado en RSA , así como uno basado en Rabin . Definen una "función de combinación" con clave . ${\ Displaystyle C_ {k, v} (y_ {1}, y_ {2}, \ dots, y_ {n})}$ que requiere una llave $k$ , un valor de inicialización $v$ y una lista de valores arbitrarios ${\ Displaystyle y_ {1}, \ puntos y_ {n}}$ . $y_{i}$ se define como $g_{i}(x_{i})$ , dónde $g_{i}$ es una función de puerta trasera (es decir, una clave pública RSA en el caso de firmas de anillo basadas en RSA).

La función ${\ Displaystyle C_ {k, v} (y_ {1}, y_ {2}, \ dots, y_ {n})}$ Se denomina ecuación del anillo y se define a continuación. La ecuación se basa en una función de cifrado simétrico. $E_{k}$ :

C_{k,v}(y_{1},y_{2},\dots ,y_{n})=E_{k}(y_{n}\oplus E_{k}(y_{n-1}\oplus E_{k}(\dots \oplus E_{k}(y_{1}\oplus v)\dots )))

Genera un único valor. $z$ que se ve obligado a ser igual a $v$ La ecuación $v=C_{k,v}(y_{1},y_{2},\dots,y_{n})$ se puede resolver siempre que al menos uno $y_{i}$ y por extensión $x_{i}$ , puede elegirse libremente. Bajo los supuestos de RSA, esto implica el conocimiento de al menos una de las inversas de las funciones de la puerta trasera. $g_{i}^{-1}$ (es decir, una clave privada), ya que $g_{i}^{-1}(y_{i})=x_{i}$ .

Generación de firmas

La generación de una firma de anillo implica seis pasos. El texto plano se indica mediante $m$ , las claves públicas del anillo por $P_{1},P_{2},\dots ,P_{n}$ .

Calcular la clave $k={\mathcal {H}}(m)$ , utilizando una función hash criptográfica . Este paso supone un oráculo aleatorio para ${\mathcal {H}}$ , desde $k$ se utilizará como clave para $E_{k}$ .
Elige un valor de pegamento al azar $v$ .
Elige al azar $x_{i}$ para todos los miembros del anillo excepto para ti ( $x_{s}$ se calculará utilizando la clave privada del firmante ), y calculará el correspondiente $y_{i}=g_{i}(x_{i})$ .
Resuelve la ecuación del anillo para $y_{s}$
Calcular $x_{s}$ utilizando la clave privada del firmante: $x_{s}=g_{s}^{-1}(y_{s})$
La firma del anillo ahora es la $(2n+1)$ -tupla $(P_{1},P_{2},\dots ,P_{n};v;x_{1},x_{2},\dots ,x_{n})$

Verificación de firma

La verificación de la firma consta de tres pasos.

Aplique la puerta trasera de llave pública en todos $x_{i}$ : $y_{i}=g_{i}(x_{i})$ .
Calcular la clave simétrica $k={\mathcal {H}}(m)$ .
Verifica que se cumple la ecuación del anillo. $C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v$ .

Implementación en Python

Aquí se presenta una implementación en Python del artículo original utilizando RSA . Requiere el módulo de terceros PyCryptodome.

import os import hashlib import random import Crypto.PublicKey.RSAimportar functoolsClase Ring : """Implementación RSA."""def __init__ ( self , k , L : int = 1024 ) -> None : self . k = k self . l = L self . n = len ( k ) self . q = 1 << ( L - 1 )def sign_message ( self , m : str , z : int ) : " " " Firma un mensaje . " " " self._permut ( m ) s = [ None ] * self.n u = random.randint ( 0 , self.q ) c = v = self._E ( u )primer_rango = lista ( rango ( z + 1 , self.n ) ) segundo_rango = lista ( rango ( z ) ) rango_completo = primer_rango + segundo_rangofor i in whole_range : s [ i ] = random.randint ( 0 , self.q ) e = self._g ( s [ i ] , self.k [ i ] .e , self.k [ i ] .n ) v = self._E ( v ^ e ) if ( i + 1 ) % self.n == 0 : c = vs [ z ] = self._g ( v ^ u , self.k [ z ] .d , self.k [ z ] .n ) return [ c ] + sdef verify_message ( self , m : str , X ) -> bool : """Verifica un mensaje.""" 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 )) y = list ( y )def _g ( x , i ): return self . _E ( x ^ y [ i ])r = functools.reduce ( _g , range ( self.n ) , X [ 0 ] ) return r == X [ 0 ]def _permut ( self , m ): msg = m . encode ( "utf-8" ) self . p = int ( hashlib . sha1 ( msg ) . hexdigest (), 16 )def _E ( self , x ): msg = f " { x }{ self . p } " . encode ( "utf-8" ) 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 ) : result = q * n + pow ( r , e , n ) else : result = x return result

Para firmar y verificar 2 mensajes en un anillo de 4 usuarios:

tamaño = 4 msg1 , msg2 = "hola" , "¡mundo!"def _rn ( _ ): return Crypto . PublicKey . RSA . generate ( 1024 , os . urandom )clave = mapa ( _rn , rango ( tamaño )) clave = lista ( clave )r = Anillo ( llave )for i in range ( size ) : signature_1 = r.sign_message ( msg1 , i ) signature_2 = r.sign_message ( msg2 , i ) assert r.verify_message ( msg1 , signature_1 ) and r.verify_message ( msg2 , signature_2 ) and not r.verify_message ( msg1 , signature_2 )

Criptomonedas

Monero ^{[ 8 ]} y varias otras criptomonedas utilizan esta tecnología.

Véase también

Referencias

Este artículo incorpora texto disponible bajo la licencia CC BY-SA 4.0 .

↑ Rivest, Ronald L. ; Shamir, Adi ; Tauman, Yael (2001). "Cómo filtrar un secreto" . Avances en criptología — ASIACRYPT 2001. Notas de clase en ciencias de la computación. Vol. 2248. pp. 552–565 . doi : 10.1007/3-540-45682-1_32 . ISBN 978-3-540-42987-6.
^ Debnath, Ashmita; Singaravelu, Pradheepkumar; Verma, Shekhar (19 de diciembre de 2012). "Esquema eficiente de preservación de la privacidad espacial para la red de sensores" . Revista Centroeuropea de Ingeniería . 3 (1): 1– 10. doi : 10.2478/s13531-012-0048-7 . S2CID 137248994 .
↑ E. Bresson; J. Stern; M. Szyd lo (2002). "Firmas de anillo de umbral y aplicaciones a grupos ad hoc" (PDF) . Avances en criptología — CRYPTO 2002. Notas de clase en ciencias de la computación. Vol. 2442. págs. 465–480 . doi : 10.1007/3-540-45708-9_30 . ISBN 978-3-540-44050-5.
↑ Liu, Joseph K.; Wong, Duncan S. (2005). «Firmas de anillo enlazables: modelos de seguridad y nuevos esquemas». Ciencia computacional y sus aplicaciones – ICCSA 2005. Notas de clase en ciencias de la computación. Vol. 2. págs. 614–623 . doi : 10.1007/11424826_65 . ISBN 978-3-540-25861-2.{{cite book}}: |journal=ignorado ( ayuda )
1 2 Fujisaki, Eiichiro; Suzuki, Koutarou (2007). "Firma de anillo rastreable". Criptografía de clave pública : 181–200 .
↑ Fujisaki, Eiichiro (2011). "Firmas de anillo trazables de tamaño sublineal sin oráculos aleatorios". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences . 95 (1): 393– 415. Bibcode : 2012IEITF..95..151F . doi : 10.1587/transfun.E95.A.151 .
↑ Au, Man Ho; Liu, Joseph K.; Susilo, Willy; Yuen, Tsz Hon (2006). "Firma de anillo enlazable y revocable si y solo si ID de tamaño constante". Avances en criptología - INDOCRYPT 2006. Notas de clase en ciencias de la computación. Vol. 4329. págs. 364–378 . doi : 10.1007/11941378_26 . ISBN 978-3-540-49767-7.
↑ "Evaluación de la implementación a prueba de balas" (PDF) . Quarkslab.

[1] Rivest, Ronald L. ; Shamir, Adi ; Tauman, Yael (2001). "Cómo filtrar un secreto" . Avances en criptología — ASIACRYPT 2001. Notas de clase en ciencias de la computación. Vol. 2248. pp. 552–565 . doi : 10.1007/3-540-45682-1_32 . ISBN 978-3-540-42987-6.

[2] Debnath, Ashmita; Singaravelu, Pradheepkumar; Verma, Shekhar (19 de diciembre de 2012). "Esquema eficiente de preservación de la privacidad espacial para la red de sensores" . Revista Centroeuropea de Ingeniería . 3 (1): 1– 10. doi : 10.2478/s13531-012-0048-7 . S2CID 137248994 .

[3] E. Bresson; J. Stern; M. Szyd lo (2002). "Firmas de anillo de umbral y aplicaciones a grupos ad hoc" (PDF) . Avances en criptología — CRYPTO 2002. Notas de clase en ciencias de la computación. Vol. 2442. págs. 465–480 . doi : 10.1007/3-540-45708-9_30 . ISBN 978-3-540-44050-5.

[4] Liu, Joseph K.; Wong, Duncan S. (2005). «Firmas de anillo enlazables: modelos de seguridad y nuevos esquemas». Ciencia computacional y sus aplicaciones – ICCSA 2005. Notas de clase en ciencias de la computación. Vol. 2. págs. 614–623 . doi : 10.1007/11424826_65 . ISBN 978-3-540-25861-2.{{cite book}}: |journal=ignorado ( ayuda )

[FS07-5] 1 2 Fujisaki, Eiichiro; Suzuki, Koutarou (2007). "Firma de anillo rastreable". Criptografía de clave pública : 181–200 .

[6] Fujisaki, Eiichiro (2011). "Firmas de anillo trazables de tamaño sublineal sin oráculos aleatorios". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences . 95 (1): 393– 415. Bibcode : 2012IEITF..95..151F . doi : 10.1587/transfun.E95.A.151 .

[7] Au, Man Ho; Liu, Joseph K.; Susilo, Willy; Yuen, Tsz Hon (2006). "Firma de anillo enlazable y revocable si y solo si ID de tamaño constante". Avances en criptología - INDOCRYPT 2006. Notas de clase en ciencias de la computación. Vol. 4329. págs. 364–378 . doi : 10.1007/11941378_26 . ISBN 978-3-540-49767-7.

[8] "Evaluación de la implementación a prueba de balas" (PDF) . Quarkslab.

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]