Firma del anillo

En criptografía , una firma en anillo es un tipo de firma digital que puede ser realizada por cualquier miembro de un conjunto de usuarios que tengan claves . Por lo tanto, un mensaje firmado con una firma en anillo está respaldado por alguien de un conjunto particular de personas. Una de las propiedades de seguridad de una firma en anillo es que debería ser computacionalmente inviable determinar cuál de las claves de los miembros del conjunto se utilizó para producir la firma. Las firmas en anillo son similares a las firmas de grupo , pero difieren en dos aspectos clave: primero, no hay forma de revocar el anonimato de una firma individual; y segundo, cualquier conjunto de usuarios puede usarse como un conjunto de firma 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 similar a un anillo del algoritmo de firma .

Definición

Supongamos que un conjunto de entidades tiene pares de claves pública/privada, ( P ₁ , S ₁ ), ( P ₂ , S ₂ ), ..., ( P _n , S _n ). La parte i puede calcular una firma de anillo σ en un mensaje m , en la entrada ( m , S _i , P ₁ , ..., P _n ). Cualquiera puede comprobar la validez de una firma de anillo dados σ, m , y las claves públicas involucradas, P ₁ , ..., P _n . Si una firma de anillo se calcula correctamente, debería pasar la comprobación. Por otro lado, debería ser difícil para cualquiera crear una firma de anillo válida en cualquier mensaje para cualquier conjunto sin conocer ninguna de las claves privadas para ese conjunto. ^[2]

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 de anillo como una forma de filtrar un secreto. Por ejemplo, una firma de anillo podría usarse para proporcionar una firma anónima de "un funcionario de alto rango de la Casa Blanca ", sin revelar qué funcionario firmó el mensaje. Las firmas de anillo son adecuadas para esta aplicación porque el anonimato de una firma de anillo no se puede revocar y porque el grupo para una firma de anillo se puede improvisar.

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 en anillo; la firma es válida para el destinatario, pero nadie más estará seguro de si el destinatario o el remitente fue el firmante real. Por lo tanto, una firma de este tipo es convincente, pero no puede transferirse más allá de su destinatario previsto.

Se realizaron diversos trabajos, introduciendo novedades y partiendo de diferentes supuestos:

Firmas de anillo de umbral

^{[3] A diferencia de} la firma de umbral estándar " t -de -n " , donde t de n usuarios deben colaborar para firmar un mensaje, esta variante de una firma de anillo requiere que t usuarios cooperen en el protocolo de firma de anillo . Es decir, t partes S ₁ , ..., S _t ∈ { P ₁ , ..., P _n } pueden calcular una ( t , n )-firma de anillo, σ, en un mensaje, m , en la entrada ( m , S ₁ , ..., S _t , P ₁ , ..., P _n ).

Firmas de anillos enlazables

^[4] La propiedad de vinculabilidad permite determinar si dos firmas 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 un sistema de dinero electrónico fuera de línea .

Firma de anillo rastreable

^[5] Además del esquema anterior se revela la clave pública del firmante (si se emiten más de una firma bajo la misma clave privada). Mediante este protocolo se puede implementar un sistema de votación electrónica .

Eficiencia

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

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

Implementación

Esquema original

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

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

${\displaystyle 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 )))}$

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

Generación de firmas

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

1. Calcular la clave , utilizando una función hash criptográfica . Este paso supone un oráculo aleatorio para , ya que se utilizará como clave para . ${\displaystyle k={\mathcal {H}}(m)}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle k}$ ${\displaystyle E_{k}}$
2. Elija un valor de pegamento aleatorio . ${\displaystyle v}$
3. Elija un número aleatorio para todos los miembros del anillo excepto usted mismo ( se calculará utilizando la clave privada del firmante ) y calcule el correspondiente . ${\displaystyle x_{i}}$ ${\displaystyle x_{s}}$ ${\displaystyle y_{i}=g_{i}(x_{i})}$
4. Resolver la ecuación del anillo para ${\displaystyle y_{s}}$
5. Calcular utilizando la clave privada del firmante: ${\displaystyle x_{s}}$ ${\displaystyle x_{s}=g_{s}^{-1}(y_{s})}$
6. La firma del anillo ahora es la -tupla ${\displaystyle (2n+1)}$ ${\displaystyle (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 implica tres pasos.

1. Aplicar la trampa de clave pública a todos los : . ${\displaystyle x_{i}}$ ${\displaystyle y_{i}=g_{i}(x_{i})}$
2. Calcular la clave simétrica . ${\displaystyle k={\mathcal {H}}(m)}$
3. Verifique que la ecuación del anillo se cumple . ${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v}$

Implementación de Python

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

importar  sistema operativo importar  hashlib importar  aleatorio importar  Crypto.PublicKey.RSAImportar  herramientas de funciónclase  Ring : "Implementación RSA."  def  __init__ ( self ,  k ,  L :  int  =  1024 )  ->  Ninguno :  self . k  =  k  self . l  =  L  self . n  =  len ( k )  self . q  =  1  <<  ( L  -  1 ) def  sign_message ( self ,  m :  str ,  z :  int ) :  self._permut ( m ) s = [ Ninguno ] * 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_rango para  i  en  todo el rango :  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 ) si ( i + 1 ) % self.n == 0 : c = v​​​​​​​​​​​​​                       s [ z ]  =  self._g ( v ^ u , self.k [ z ] .d , self.k [ z ] .n ) devuelve [ c ] + s​​​​​​​​         def  verificar_mensaje ( self ,  m :  str ,  X )  - >  bool :  self._permut ( m )​ def  _f ( i ):  devuelve  self . _g ( X [ i  +  1 ],  self . k [ i ] . e ,  self . k [ i ] . n ) y  =  mapa ( _f ,  rango ( len ( X )  -  1 ))  y  =  lista ( y ) def  _g ( x ,  i ):  devuelve  self . _E ( x  ^  y [ i ]) r  =  functools . reduce ( _g ,  range ( self . n ),  X [ 0 ])  devuelve  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 ):  resultado  =  q  *  n  +  pow ( r ,  e ,  n )  else :  resultado  =  x  return  resultado

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

tamaño  =  4 msg1 ,  msg2  =  "hola" ,  "¡mundo!"def  _rn ( _ ):  devuelve  Crypto . PublicKey . RSA . generate ( 1024 ,  os . urandom )clave  =  mapa ( _rn ,  rango ( tamaño )) clave  =  lista ( clave )r  =  Anillo ( llave )para  i  en  rango ( tamaño ):  firma_1  =  r . signo_mensaje ( msg1 ,  i )  firma_2  =  r . signo_mensaje ( msg2 ,  i )  afirmar  r . verificar_mensaje ( msg1 ,  firma_1 )  y  r . verificar_mensaje ( msg2 ,  firma_2 )  y  no  r . verificar_mensaje ( msg1 ,  firma_2 )

Criptomonedas

Monero y otras criptomonedas utilizan esta tecnología. ^{[ cita requerida ]}

Véase también

• Pruebas indistinguibles de los testigos

Referencias

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

1. Rivest, Ronald L .; Shamir, Adi ; Tauman, Yael (2001). "Cómo filtrar un secreto". Avances en criptología — ASIACRYPT 2001. Apuntes de clase en informática. Vol. 2248. págs. 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. Apuntes de clase en informática. 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". Ciencias de la computación y sus aplicaciones – ICCSA 2005 . Apuntes de clase en informática. Vol. 2. págs. 614–623. doi :10.1007/11424826_65. ISBN 978-3-540-25861-2. {{cite book}}: |journal=ignorado ( ayuda )
5. Fujisaki, Eiichiro; Suzuki, Koutarou (2007). "Firma de anillo rastreable". Criptografía de clave pública : 181–200.
6. Fujisaki, Eiichiro (2011). "Firmas de anillos trazables por 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 con si/solo si basada en ID de tamaño constante". Progreso en criptología - INDOCRYPT 2006. Apuntes de clase en informática. Vol. 4329. págs. 364–378. doi :10.1007/11941378_26. ISBN 978-3-540-49767-7.