Firma del anillo

En criptografía , una firma en anillo es un tipo de firma digital que puede realizar cualquier miembro de un conjunto de usuarios, cada uno de los cuales tiene claves . Por lo tanto, un mensaje firmado con una firma en anillo está respaldado por alguien de un grupo 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 se puede utilizar como conjunto de firma sin configuración adicional.

Las firmas de anillo fueron inventadas por Ron Rivest , Adi Shamir y Yael Tauman Kalai , y se introdujeron 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 , Si _, P ₁ , ..., P _n ). Cualquiera puede verificar la validez de una firma de anillo dadas σ, m y las claves públicas involucradas, P ₁ , ..., P _n . 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 en cualquier mensaje para cualquier conjunto sin conocer ninguna de las claves privadas de ese conjunto. ^[2]

Aplicaciones y modificaciones

Comportamiento del esquema de firma de anillos de Rivest, Shamir, Tauman

En el artículo original, Rivest, Shamir y Tauman describieron las firmas de anillos como una forma de filtrar un secreto. Por ejemplo, se podría utilizar un anillo de firma 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 en anillo son adecuadas para esta aplicación porque el anonimato de una firma en anillo no se puede revocar y porque el grupo de una firma en anillo se puede improvisar.

Otra aplicación, también descrita en el documento original, es la de firmas negables. Aquí el remitente y el destinatario de un mensaje forman un grupo para la firma en anillo, luego la firma es válida para el destinatario, pero cualquier otra persona no estará segura de si el destinatario o el remitente fue el firmante real. Por tanto, una firma de este tipo es convincente, pero no puede transferirse más allá de su destinatario previsto.

Fueron diversos trabajos, introduciendo novedades y partiendo de diferentes supuestos:

Firmas de anillos de umbral

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

Firmas de anillo 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 efectivo 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 emite más de una firma bajo la misma clave privada). Se puede implementar un sistema de votación electrónica utilizando este protocolo.

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 mediano relativamente pequeño , dicha estimación puede ser aceptable. CryptoNote implementa un 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 tamaño sublineal de la firma, ^[6] así como con 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 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 trampilla (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 llama ecuación de anillo y se define a continuación. La ecuación se basa en una función de cifrado simétrica : ${\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 )))}$

Genera un valor único que se fuerza a ser igual a . La ecuación se puede resolver siempre que al menos uno , y por extensión , pueda elegirse libremente. Según los supuestos de RSA, esto implica el conocimiento de al menos una de las funciones 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 firma

Generar una firma de anillo implica seis pasos. El texto plano se indica con , las claves públicas del anillo con . ${\displaystyle m}$ ${\displaystyle P_{1},P_{2},\dots ,P_{n}}$

1. Calcule 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 aleatoriamente para todos los miembros del anillo menos usted ( se calculará utilizando la clave privada del firmante ) y calcule la correspondiente . ${\displaystyle x_{i}}$ ${\displaystyle x_{s}}$ ${\displaystyle y_{i}=g_{i}(x_{i})}$
4. Resuelve la ecuación del anillo para ${\displaystyle y_{s}}$
5. Calcule usando 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 firma implica tres pasos.

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

Implementación de Python

Aquí hay una implementación de Python del artículo original usando RSA . Requiere el módulo PyCryptodome de terceros.

importar  sistema operativo importar  hashlib importar  aleatoriamente importar  Crypto.PublicKey.RSAimportar  funciones Anillo de clase : """Implementación RSA."""  def  __init__ ( self ,  k ,  L :  int  =  1024 )  ->  Ninguno :  self . k  =  k  yo . l  =  L  yo . n  =  len ( k )  uno mismo . q  =  1  <<  ( L  -  1 ) def  sign_message ( self ,  m :  str ,  z :  int ):  self . _permut ( m )  s  =  [ Ninguno ]  *  self . norte  tu  =  aleatorio . randint ( 0 ,  self . q )  c  =  v  =  self . _UE )​​ 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 ]  =  aleatorio . 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 )  %  propio . norte  ==  0 :  c  =  v s [ z ]  =  yo . _g ( v  ^  u ,  self . k [ z ] . d ,  self . k [ z ] . n )  return  [ c ]  +  s def  verificar_mensaje ( self ,  m :  str ,  X )  ->  bool :  self . _permutar ( m ) def  _f ( i ):  devuelve  uno mismo . _g ( X [ i  +  1 ],  yo . k [ i ] . e ,  yo . k [ i ] . n ) y  =  mapa ( _f ,  rango ( len ( X )  -  1 ))  y  =  lista ( y ) def  _g ( x ,  i ):  devuelve  self . _E ( x  ^  y [ i ]) r  =  herramientas funcionales . reducir ( _g ,  rango ( self . n ),  X [ 0 ])  devolver  r  ==  X [ 0 ] def  _permut ( self ,  m ):  mensaje  =  m . codificar ( "utf-8" )  auto . p  =  int ( hashlib . sha1 ( msg ) . hexdigest (),  16 ) def  _E ( self ,  x )  : msg  =  f " { x } { self.p } " . codificar ( "utf-8" ) devolver 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 )  más :  resultado  =  x  devolver  resultado

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

tamaño  =  4 msg1 ,  msg2  =  "hola" ,  "¡mundo!"def  _rn ( _ ):  devuelve  Cripto . Llave pública . RSA . generar ( 1024 ,  os . urandom )clave  =  mapa ( _rn ,  rango ( tamaño )) clave  =  lista ( clave )r  =  Anillo ( llave )para  i  en  rango ( tamaño ):  firma_1  =  r . sign_message ( msg1 ,  i )  firma_2  =  r . sign_message ( msg2 ,  i )  afirmar  r . verificar_mensaje ( msg1 ,  firma_1 )  y  r . verificar_message ( msg2 ,  firma_2 )  y  no  r . verificar_mensaje ( msg1 ,  firma_2 )

CRIPTOMONEDAS

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

Ver también

• Pruebas testimoniales indistinguibles

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 conferencias sobre 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. popa; M. Szyd·lo (2002). "Firmas de anillo umbral y aplicaciones a grupos ad-hoc" (PDF) . Avances en criptología - CRYPTO 2002 . Apuntes de conferencias sobre informática. vol. 2442, págs. 465–480. doi : 10.1007/3-540-45708-9_30 . ISBN 978-3-540-44050-5.
4. Liu, José K.; Wong, Duncan S. (2005). "Firmas de anillo enlazables: modelos de seguridad y nuevos esquemas". Ciencia Computacional y sus Aplicaciones – ICCSA 2005 . Apuntes de conferencias sobre 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, Koutaro (2007). "Firma de anillo rastreable". Criptografía de clave pública : 181–200.
6. Fujisaki, Eiichiro (2011). "Firmas de anillos rastreables de tamaño sublineal sin oráculos aleatorios". Transacciones IEICE sobre Fundamentos de Electrónica, Comunicaciones e Informática . 95 (1): 393–415. Código Bib : 2012IEITF..95..151F. doi :10.1587/transfun.E95.A.151.
7. Au, Man Ho; Liu, José K.; Susilo, Willy; Yuen, Tsz Hon (2006). "Firma de anillo vinculada revocable y vinculable basada en ID de tamaño constante". Progreso en criptología - INDOCRYPT 2006. Apuntes de conferencias sobre informática. vol. 4329, págs. 364–378. doi :10.1007/11941378_26. ISBN 978-3-540-49767-7.