stringtranslate.com

Criptosistema Niederreiter

En criptografía , el criptosistema Niederreiter es una variación del criptosistema McEliece desarrollado en 1986 por Harald Niederreiter . [1] Se aplica la misma idea a la matriz de verificación de paridad , H , de un código lineal. Niederreiter equivale a McEliece desde el punto de vista de la seguridad. Utiliza un síndrome como texto cifrado y el mensaje es un patrón de error. El cifrado de Niederreiter es aproximadamente diez veces más rápido que el cifrado de McEliece. Niederreiter se puede utilizar para construir un esquema de firma digital .

Definición del esquema

Un caso especial de la propuesta original de Niederreiter se rompió [2] pero el sistema es seguro cuando se usa con un código binario Goppa .

Generación de claves

  1. Alice selecciona un código Goppa binario ( n , k ) lineal, G , capaz de corregir t errores. Este código posee un algoritmo de decodificación eficiente.
  2. Alice genera una matriz de verificación de paridad ( n − k ) × n , H , para el código , G.
  3. Alice selecciona una matriz binaria no singular aleatoria ( n − k ) × ( n − k ) , S.
  4. Alice selecciona una matriz de permutación aleatoria de n × n , P.
  5. Alice calcula la matriz ( n − k ) × n , H pub = SHP .
  6. La clave pública de Alice es ( H pub , t ); su clave privada es ( S , H , P ).

Cifrado de mensajes

Supongamos que Bob desea enviar un mensaje, m , a Alice cuya clave pública es ( H pub , t ):

  1. Bob codifica el mensaje, m , como una cadena binaria e m' de longitud n y peso como máximo t .
  2. Bob calcula el texto cifrado como c = H pub e T .

Descifrado de mensajes

Al recibir c = H pub m T de Bob, Alice hace lo siguiente para recuperar el mensaje, m .

  1. Alice calcula S −1 c = HPm T .
  2. Alice aplica un algoritmo de decodificación de síndrome para que G recupere Pm T.
  3. Alice calcula el mensaje, m , mediante m T = P −1 Pm T .

Esquema de firma

Courtois, Finiasz y Sendrier mostraron cómo se puede utilizar el criptosistema Niederreiter para derivar un esquema de firma. [3]

  1. Hash el documento, d , que se va a firmar (con un algoritmo hash público).
  2. Descifre este valor hash como si fuera una instancia de texto cifrado.
  3. Agregue el mensaje descifrado al documento como firma.

Luego, la verificación aplica la función de cifrado público a la firma y verifica si es igual o no al valor hash del documento. Cuando se utiliza Niederreiter, o cualquier criptosistema basado en códigos de corrección de errores, el segundo paso en el esquema de firma casi siempre falla. Esto se debe a que un síndrome aleatorio normalmente corresponde a un patrón de error de peso mayor que t . Luego, el sistema especifica una forma determinista de ajustar d hasta que se encuentre uno que pueda descifrarse.

La elección de los parámetros del código está relacionada con la probabilidad de que un síndrome aleatorio sea decodificable. Courtois, Finiaz y Sendrier sugieren los valores de los parámetros n = 2 16 yt = 9. Entonces la probabilidad de decodificar un síndrome aleatorio es . Por lo tanto, ¡se encuentra un síndrome decodificable después de un número esperado de 9! intentos. Agregue un contador, i , al documento original d , para producir un documento ligeramente modificado, d i . Hashing d i da un síndrome que depende de i . Sea i desde 0 hasta i 0 , siendo i 0 el primer valor de i para el cual d i es decodificable. En este caso , el mensaje descifrado es una palabra, z , de longitud n y peso 9, tal que Hz T es igual al valor hash de di 0 . La firma se combinará con el valor i 0 para su verificación. Esta firma se adjunta al documento original, d .

Referencias

  1. ^ H. Niederreiter (1986). "Criptosistemas tipo mochila y teoría de la codificación algebraica". Problemas de Control y Teoría de la Información. Problema Upravlenija I Teorii Informacii . 15 : 159-166.
  2. ^ VM Sidel'nikov y SO Shestakov (1992). "Sobre la inseguridad de los criptosistemas basados ​​en códigos Reed-Solomon generalizados". Matemáticas Discretas y Aplicaciones . 2 (4): 439–444. doi :10.1515/dma.1992.2.4.439. S2CID  120779674.
  3. ^ N. Courtois; M. Finiaz; N. Sendrier (2001). "Cómo lograr un esquema de firma digital basado en McEliece". Avances en criptología - ASIACRYPT 2001 . Apuntes de conferencias sobre informática. vol. LNCS 2248. págs. 157-174. doi : 10.1007/3-540-45682-1_10 . ISBN 978-3-540-42987-6.

enlaces externos