Lamport-Einmal-Signaturverfahren

Das Lamport-Einmal-Signaturverfahren (englisch Lamport One-Time Signature Scheme, kurz OTS) ist ein Signaturverfahren, das 1979 von Leslie Lamport entwickelt wurde. Normalerweise wird eine kollisionresistente Hashfunktion $H:\left\{0,1\right\}^{k}\rightarrow \left\{0,1\right\}^{k},k\in \mathbb {N}$ als Einwegfunktion verwendet.

OTS verwendet zwei Schlüssel, einen Signaturschlüssel $x$ und einen Verifikationsschlüssel $y$. Um später ein Dokument mit $y$ zu verifizieren, muss außerdem die verwendete Einwegfunktion $H$ bekannt sein.

Schlüsselerzeugung

Der private Schlüssel $x$ besteht aus $n$ $k$-bit Zahlenpaaren, die zufällig generiert werden, wobei ${\textstyle n}$ die Länge des zu signierenden Dokuments ist.

$x={\Bigl (}x(0,1),x(1,1),x(0,2),x(1,2),\ldots ,x(0,n),x(1,n){\Bigr )}\in ({\begin{Bmatrix}0,1\end{Bmatrix}}^{k})^{2n},n\in \mathbb {N}$

Bei längeren Dokumenten oder wenn die Länge des Dokuments bei der Schlüsselerzeugung noch nicht bekannt ist, empfiehlt es sich, erst eine kollisionsresistente Hashfunktion auf das Dokument anzuwenden und den resultierenden Hashwert zu signieren, was $k$ auf die Hashlänge begrenzt.

Angenommen, es wird eine 256-bit-Hashfunktion verwendet, empfiehlt es sich, für $n$ 256 zu wählen. Daraus ergibt sich eine Schlüssellänge von 2×256×256 = 128 Kibit.

Den öffentlichen Schlüssel $y$ erhält man, wenn man alle $k$ Zahlenpaare des privaten Schlüssels hasht.

${\begin{aligned}y&={\Bigl (}H(x(0,1)),H(x(1,1)),H(x(0,2)),H(x(1,2)),\ldots ,H(x(0,n)),H(x(1,n)){\Bigr )}\\&={\Bigl (}y(0,1),y(1,1),y(0,2),y(1,2),\ldots ,y(0,n),y(1,n){\Bigr )}\end{aligned}}$

Erzeugung der Signatur

Die Signatur eines Dokuments $d=(d_{\text{1}},\ldots ,d_{\text{n}})\in {\begin{Bmatrix}0,1\end{Bmatrix}}^{n}$ ist

$s=(s_{1},\ldots ,s_{n})={\Bigl (}x(d_{1},1),\ldots ,x(d_{n},n){\Bigr )}$

Verifikation

Der Verifizierer kennt die Einwegfunktion $H$, den Verifikationsschlüssel $y$, das Dokument $d=(d_{1},\ldots ,d_{n})$ und die Signatur $s=(s_{1},\ldots ,s_{n})$.

Wenn

${\Bigl (}H(s_{1}),\ldots ,H(s_{n}){\Bigr )}={\Bigl (}y(d_{1},1),\ldots ,y(d_{n},n){\Bigr )}$

gilt, dann ist die Signatur korrekt.

Literatur

• Johannes Buchmann: Einführung in die Kryptographie. 5. Auflage. Springer Verlag, 2010, ISBN 978-3-642-11185-3, S. 220 ff. 
• Leslie Lamport: Constructing digital signatures from a one-way function, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Okt. 1979.

Weblinks

• Digitale Signaturen – Lamport’s Einmalsignaturverfahren