Firma de Lamport-Diffie

La Firma de Lamport es un esquema de firma digital de un solo uso, inventada por Leslie Lamport en 1979.^[1] La firma se aplica sobre mensajes sin efectuar ninguna modificación previa de los mismos.

La esquema de firma de Lamport utiliza un juego de claves, compuesto por una clave privada y una clave pública. La clave privada es un conjunto de ${\displaystyle 2*n}$ elementos privados. La clave pública es otro conjunto de ${\displaystyle 2*n}$ elementos, formados, generalmente, por la aplicación de una función hash a cada elemento privado. Para firmar un documento, se aplica una función hash al documento del que se obtienen ${\displaystyle n}$ bits, y se utilizan para seleccionar ${\displaystyle n}$ elementos de la clave pública.

Representación de la secuencia para firmar un documento con una firma de Lamport.

La firma de Lamport se debe utilizar una sola vez por cada juego de claves. Sin embargo, combinado el esquema de firma de Lamport con un Árbol de Merkle, un solo juego de claves podría usarse para firmar varios mensajes, lo que la convierte en un esquema de firma digital bastante eficiente.

El desarrollo potencial de la computación cuántica amenaza la seguridad de muchas formas comunes de criptografía como RSA, pero se cree que las firmas de Lamport estarían seguras si se usan, como componentes de las claves, valores de tamaño adecuado.

Descripción formal

A continuación se muestra una descripción de cómo funciona una firma Lamport, en notación matemática. Notar que el "mensaje" en esta descripción es un bloque de ${\displaystyle n}$ datos siendo posiblemente (pero no necesariamente) el resultado de aplicar una función hash al mensaje que realmente se quiere firmar.

Claves

Sea ${\displaystyle n}$ un entero positivo y sea ${\displaystyle f:\,Y\rightarrow Z}$ una función unidireccional.

Para ${\displaystyle 1\leq i\leq n}$ y ${\displaystyle j\in \{0,1\}}$ el firmante elige aleatoriamente ${\displaystyle y_{i,j}\in Y}$ y luego calcula ${\displaystyle z_{i,j}=f(y_{i,j})}$.

La clave privada, ${\displaystyle Y}$, consiste en ${\displaystyle 2n}$ valores ${\displaystyle y_{i,j}}$. La clave pública,${\displaystyle Z}$, consiste en otros ${\displaystyle 2n}$ valores ${\displaystyle z_{i,j}}$.

Firma de un mensaje

Sea ${\displaystyle M}$ el bloque descriptor del mensaje: ${\displaystyle M=f({mensaje})\in \{0,1\}^{n}}$

${\displaystyle M=m_{1}\ldots m_{n}}$

La firma del mensaje es:

${\displaystyle \operatorname {S} (m_{1}\ldots m_{n})=(y_{1,m_{1}},\ldots ,y_{n,m_{n}})=(s_{1},\ldots ,s_{n})}$.

Verificación de la firma

Quien necesite validar la firma debe verificar que:

${\displaystyle f(s_{i})=z_{i,m_{i}}}$ para todo  ${\displaystyle 1\leq i\leq n}$.

Se debe conservar los elementos privados que forman la firma, la clave pública y el mensaje original para futuras validaciones.

Para que Eva pueda falsificar una firma, debe poder invertir los valores de la clave pública. Y esto se asume como un problema computacionalmente inviable si se usan valores de tamaño adecuado.

Inconvenientes

El primer inconveniente es que se debe utilizar cada juego de claves una sola vez. La razón es que al firmar se hacen visibles los ${\displaystyle n}$ elementos privados que generaron los ${\displaystyle n}$ elementos públicos. Es decir, se exponen el 50% de los elementos que forman la clave privada, por lo tanto una vez que se firma un documento no se debe reutilizar el juego de clave pública y privada. Además se debe destruir el 50% remanente de elementos privados que forman la clave privada y no que fueron expuestos.

Otro inconvenientes es el de la excesiva longitud de las claves y la firma.

Referencias

1. Lamport, L. "Constructing Digital Signatures from a One-Way Function. Technical report CSL-98, SRI International, Palo Alto 1979

• Datos: Q603296