The following important information is missing from this article or section:
History, creation, security
Help Wikipedia by
researching and
pasting it .
The Lamport-Diffie One-Time Signature Scheme ( English Lamport-Diffie One-Time Signature Scheme , LD-OTS for short ) is a signature method that was developed in 1979 by Leslie Lamport and Whitfield Diffie . Usually a collision-resistant hash function is used as a one-way function .
H
:
{
0
,
1
}
k
→
{
0
,
1
}
k
,
k
∈
N
{\ displaystyle H: \ left \ {0.1 \ right \} ^ {k} \ rightarrow \ left \ {0.1 \ right \} ^ {k}, k \ in \ mathbb {N}}
LD-OTS uses two keys, a signature key and a verification key . In order to later verify a document , the one-way function used must also be known.
x
{\ displaystyle x}
y
{\ displaystyle y}
y
{\ displaystyle y}
H
{\ displaystyle H}
Key generation
The private key consists of -bit number pairs that are generated randomly. Where is the length of the document to be signed and any natural number.
x
{\ displaystyle x}
k
{\ displaystyle k}
n
{\ displaystyle n}
k
{\ textstyle k}
n
{\ displaystyle n}
x
=
(
x
(
0
,
1
)
,
x
(
1
,
1
)
,
x
(
0
,
2
)
,
x
(
1
,
2
)
,
...
,
x
(
0
,
n
)
,
x
(
1
,
n
)
)
∈
(
{
0
,
1
}
k
)
2
n
,
n
∈
N
{\ 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}}
In the case of longer documents or if the length of the document is not yet known when the key is generated, it is advisable to first apply a collision-resistant hash function to the document and to sign the resulting hash value, which is limited to the hash length.
k
{\ displaystyle k}
Assuming a 256-bit hash function is used, it is best to choose 256. This results in a key length of 2 × 256 × 256 = 128 kibits.
n
{\ displaystyle n}
The public key is obtained by hashing all the pairs of numbers in the private key.
y
{\ displaystyle y}
k
{\ displaystyle k}
y
=
(
H
(
x
(
0
,
1
)
)
,
H
(
x
(
1
,
1
)
)
,
H
(
x
(
0
,
2
)
)
,
H
(
x
(
1
,
2
)
)
,
...
,
H
(
x
(
0
,
n
)
)
,
H
(
x
(
1
,
n
)
)
)
=
(
y
(
0
,
1
)
,
y
(
1
,
1
)
,
y
(
0
,
2
)
,
y
(
1
,
2
)
,
...
,
y
(
0
,
n
)
,
y
(
1
,
n
)
)
{\ 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}}}
Generation of the signature
The signature of a document is
d
=
(
d
1
,
...
,
d
n
)
∈
{
0
,
1
}
n
{\ displaystyle d = (d _ {\ text {1}}, \ ldots, d _ {\ text {n}}) \ in {\ begin {Bmatrix} 0,1 \ end {Bmatrix}} ^ {n}}
s
=
(
s
1
,
...
,
s
n
)
=
(
x
(
d
1
,
1
)
,
...
,
x
(
d
n
,
n
)
)
{\ displaystyle s = (s_ {1}, \ ldots, s_ {n}) = {\ Bigl (} x (d_ {1}, 1), \ ldots, x (d_ {n}, n) {\ Bigr )}}
verification
The verifier knows the one-way function , the verification key , the document and the signature .
H
{\ displaystyle H}
y
{\ displaystyle y}
d
=
(
d
1
,
...
,
d
n
)
{\ displaystyle d = (d_ {1}, \ ldots, d_ {n})}
s
=
(
s
1
,
...
,
s
n
)
{\ displaystyle s = (s_ {1}, \ ldots, s_ {n})}
If
(
H
(
s
1
)
,
...
,
H
(
s
n
)
)
=
(
y
(
d
1
,
1
)
,
...
,
y
(
d
n
,
n
)
)
{\ displaystyle {\ Bigl (} H (s_ {1}), \ ldots, H (s_ {n}) {\ Bigr)} = {\ Bigl (} y (d_ {1}, 1), \ ldots, y (d_ {n}, n) {\ Bigr)}}
applies, then the signature is correct.
literature
Johannes Buchmann : Introduction to Cryptography . 5th edition. Springer Verlag, 2010, ISBN 978-3-642-11185-3 , pp. 220 ff .
Leslie Lamport : Constructing digital signatures from a one-way function , Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Oct. 1979.
Web links
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">