Cryptography Reference
In-Depth Information
Adversary
Message
m
Signature
Extraction
σ
e
σ
mod
N
m
d
mod
N
Public key
Secret key
e
,
N
e
,
N
d
,
N
AUTHENTICATED
Generator
Figure 10.4.
Plain RSA signature scheme.
10.2.3
ISO/IEC 9796
The ISO/IEC 9796 (Ref. [10]) was the first international norm which specified a mes-
sage formatting scheme to be used in order to feed a given signature scheme.
1
The
original norm does not specify the signature scheme, but it is RSA in most applications
(it can also be the
Rabin scheme
).
The signature of a
d
-bit message
m
into a
k
-bit signature proceeds as follows. (Let
us consider that
d
≤
512 and
k
=
1024 for instance.)
1. We pad
m
with leading zero bits (at most seven) so that the total length can be
cut into a sequence of
z
bytes
m
z
,
m
1
.
2. We extend the message by taking the
t
rightmost bytes of the infinite sequence
...,
m
z
−
1
,...,
m
z
,
m
z
−
1
,...,
m
1
,
m
z
,
m
z
−
1
,...,
m
1
,...,
m
z
,
m
z
−
1
,...,
m
1
64 bytes.)
3. We add redundancy by inserting a byte
S
(
x
) to the left of each of the
t
bytes
x
of
the string, and XOR
r
onto the
z
-th rightmost redundancy byte
S
(
m
z
). We thus
obtain a string of 2
t
bytes, which consists of at least
k
where
t
is the smallest size such that 16
t
≥
k
−
1. (Hence
t
=
−
1 bits. Here
r
is one plus
the number of zero bits which have been padded at the beginning (hence between
1 and 8), and
S
is the
shadow function
defined by
S
(
x
H
x
L
)
=
π
(
x
H
)
π
(
x
L
) where
x
H
x
L
represents the two hexadecimal digits of
x
, and
π
is a permutation defined
by
0 123456 7 8 9
ABCDEF
E
358942
F
0
DB
67
AC
1
π
=
.
4. We take the
k
−
1 rightmost bits and we pad a one bit to the left and replace the
rightmost byte
x
=
x
H
x
L
by
x
L
6 in hexadecimal. We thus obtain a formatted
string of
k
bits.
5. We sign the formatted string, for instance by using the plain RSA.
1
Note that it was originally published in 1991.
Search WWH ::
Custom Search