Lamport-Einmal-Signaturverfahren

In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:

Geschichte, Entstehung, Sicherheit

Hilf der Wikipedia, indem du sie recherchierst und einfügst.

Das Lamport-Einmal-Signaturverfahren (englisch Lamport One-Time Signature Scheme, kurz OTS) ist ein Signaturverfahren, das 1979 von Leslie Lamport entwickelt wurde^[1]. Normalerweise wird eine kollisionresistente Hashfunktion ${\displaystyle 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 ${\displaystyle x}$ und einen Verifikationsschlüssel ${\displaystyle y}$. Um später ein Dokument mit ${\displaystyle y}$ zu verifizieren, muss außerdem die verwendete Einwegfunktion ${\displaystyle H}$ bekannt sein.

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

${\displaystyle 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 ${\displaystyle k}$ auf die Hashlänge begrenzt.

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

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

${\displaystyle {\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}}}$

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

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

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

Wenn

${\displaystyle {\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.

• 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.

• Digitale Signaturen – Lamport’s Einmalsignaturverfahren

1. ↑ Leslie Lamport: Constructing Digital Signatures from a One Way Function. 18. Oktober 1979 (microsoft.com [abgerufen am 2. Januar 2022]).