Firma de Lamport-Diffie

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

La Firma de Lamport-Diffie es un esquema de firma digital propuesta por L. Lamport y W. Diffie.[1] y que está basada en criptografía simétrica . La firma, en principio, se aplica sobre mensajes sin efectuar ninguna modificación previa de los mismos.

Descripción[editar]

Para firmar un mensaje M de n bits, el firmante elige aleatoriamente un vector K constituido por n parejas de claves secretas dadas por:

K=[(k_{10},k_{11}),....,(k_{n0},k_{n1})]

A continuación el firmante calcula dos secuencias de valores R y S dadas por:

S=[(s_{10},s_{11}),...,(s_{n0},s_{n1})]
R=[(r_{10},r_{11}),...,(r_{n0},r_{n1})]

donde los valores del conjunto S se escogen de forma aleatoria y los del conjunto R son sus respectivos cifrados dados por:

r_{ij}=E_{kij}(s{ij})

siendo E_{kij}(....) un criptosistema simétrico de clave kij. La estructura del criptosistema E utilizado determina el número de bits n y la longitud de las secuencias R y S utilizadas luego para la validación. Por ejemplo, si E es el DES, entonces n=64. En estas condiciones, los conjuntos R y S se hacen públicos en un registro de sólo lectura, que sólo puede ser modificado por el firmante. La firma M_f del mensaje M=(m_1,m_2,...,m_n) con m_i un bit que puede valer 0 ó 1, será:

M_f=(k_{1m1},...,k_{nmn}).

La firma M_f del mensaje M es obtenida de la siguiente forma: la componente i de M_f será r_i0 si m_i es 0, en otro caso será r_i1. La autenticidad de la firma M_f se comprueba verificando las relaciones entre los correspondientes valores de las secuencias de validación R y S en función de las claves conocidas. Sea

S_f=(s_{1m1},...,s_{nmn})

obtenido de la misma forma que se calculaba M_f pero ahora en lugar de R, usamos S. Ahora hallamos R'_f

R'_f=(E_{k1m1}(s_{1m1}),...,E_{knmn}(s_{nmn}))

En estas condiciones, el receptor acepta la validez de la firma si dichos valores son respectivamente iguales a los del subconjunto R_f del registro público R (hallado de forma análoga que M_f y S_f, pero esta vez sobre R)

Ejemplo[editar]

Sea E_k=M \oplus k un criptosistema simétrico de clave secreta k de n=3 bits. Para computar la firma de M=1011, Primero el firmate elige aleatoriamente el vector binario K de claves secretas, por ejemplo:

K=[(000,011),(110,001),(100,111),(010,101)]

A continuación se elige la secuencia binaria aleatorio S, por ejemplo

S=[(011,001),(010,111),(100,110),(101,000)]

y computa el vector R

R=[(011,010),(100,110),(000,001),(111,101)]

haciendo públicos los conjuntos R y S. Por tanto la firma M_f será:

M_f=(011,010,110,000)

Para verificarla hallamos S_f y R_f:

S_f=(001,010,110,000)
R_f=(010,100,001,101)

Para verificar hallamos R'_f quedando

R'_f=(001 \oplus 011,010 \oplus 110, 110 \oplus 111, 000 \oplus 101)

que coincide con R_f y por tanto el receptor acepta la validez de la firma.

Incovenientes[editar]

Es conveniente que el firmate cambie el vector de claves secretas K, así como las correspondientes secuencias de validación contenidas en los registro públicos R y S, cada vez que se aplique la firma. En caso contrario, el secreto podría ser revelado, comprometiendo la seguridad.

Otro inconvenientes es el de la excesiva longitud de la firma, de la clave K y de los vectores R y S implicados. Produciendo un gasto de recursos de almacenamiento y de transmisión. Una forma de paliar un poco este inconveniente es firmar el resultado de aplicar una función hash (realmente un código de detección de manipulaciones).

Referencias[editar]

  • José Pastor Franco, Miguel A. Sarasa López, "Criptografía digital. Fundamentos y aplicaciones", Prensas Universitarias de Zaragoza 1998.
  1. Lamport, L. Diffie W. "Constructing Digital Signatures from a One-Way Function. Technical report CSL-98, SRI International, Palo Alto 1979