ISO/IEC 9796 formatting
ISO/IEC 9796 was published in 1991 by the International Standards Organization as the first international standard for digital signatures. It specifies a digital signature process which uses a digital signature mechanism providing message recovery.
The main features of ISO/IEC 9796 are: (i) it is based on public-key cryptography; (ii) the particular signature algorithm is not specified but it must map k bits to к bits; (iii) it is used to sign messages of limited length and does not require a cryptographic hash function; (iv) it provides message recovery (see Note 11.14); and (v) it specifies the message padding, where required. Examples of mechanisms suitable for the standard are RSA (Algorithm 11.19) and modified-Rabin (Algorithm 11.30). The specific methods used for padding, redundancy, and truncation in ISO/IEC 9796 prevent various means to forge signatures. Table 11.3 provides notation for this subsection.
Symbol |
Meaning |
к |
the bitlength of the signature. |
d |
the bitlength of the message m to be signed; it is required that d < 8 [(к + 3)/16j. |
z |
the number of bytes in the padded message; г = [d/8]. |
r |
one more than the number of padding bits; r = Sz — d + 1. |
t |
the least integer such that a string of 21 bytes includes at least к - 1 bits; f = {k- 1)/16], |
Table 11.3: ISO/IEC 9796 notation.
11.35 Example (sample parameter values for ISO/IEC 9796) The following table lists sample values of parameters in the signing process for a 150-bit message and a 1024-bit signature.
Parameter |
к (bits) |
d (bits) |
2 (bytes) |
r (bits) |
t (bytes) |
Value |
1024 |
150 |
19 |
3 |
64 |
□
(i) Signature process for ISO/IEC 9796
The signature process consists of 5 steps as per Figure 11.5(a).
Figure 11.5: Signature and verification processes for ISO/IEC 9796.
- 1. padding. If m is the message, form the padded message MP = 0^{r L}||m where 1 < r < 8, such that the number of bits in MP is a multiple of 8. The number of bytes in MP is г: MP = m_{z} ||т_{г}_ i || • • • 11i2||mi where each гтц is a byte.
- 2. message extension. The extended message, denoted ME, is obtained from MP by
repeated concatenation on the left of MP with itself until t bytes are in the string: ME = • • • ME2WME1 (each ME, is a byte). If t is not a multiple
of 2, then the last bytes to be concatenated are a partial set of bytes from MP, where these bytes are consecutive bytes of MP from the right. More precisely, ME_{i+}1 =
^{m}(i modz)+l for 0 < i < t 1.
3. message redundancy. Redundancy is added to ME to get the byte string MR =
MR.2tMR'2t-i ■ ■ ■ ||МЙ2||М/?1 as follows. MR is obtained by interleaving the t bytes of ME with t redundant bytes and then adjusting byte MR_{2z} of the resulting string. More precisely, = ME,■ and MR_{2}, = S(ME,) for 1 < i < t, where
S(u) is called the shadow function of the byte u, and is defined as follows. If и = u-211 u i where г/j andu2 are nibbles (strings ofbitlength 4), then S(u) = 7г(г/2) II tt(" i) where n is the permutation
- (For brevity, 7r is written with nibbles represented by hexadecimal characters.) Finally, MR is obtained by replacing MR._{2z} with г ф MR_{2z}.^{[1]}
- 4. truncation and forcing. Form the А-bit intennediate mteger IR from MR as follows:
- (a) to the least significant к — 1 bits of MR, append on the left a single bit 1;
- (b) modify the least significant byte гг_{2}||гц of the result, replacing it by wi Ц0110.
- (This is done to ensure that IR = 6 (mod 16).)
- 5. signature production. A signature mechanism is used which maps k-bit integers to к-bit integers (and allows message recovery). IR is signed using this mechanism; let s denote the resulting signature.
- 11.36 Note (RSA, Rabin) ISO/IEC 9796 was intended for use with the RSA (Algorithm 11.19)^{G }and Rabin (Algorithm 11.25)' digital signature mechanisms. For these particular schemes, signature production is stated more explicitly. Let e be the public exponent for the RSA or Rabin algorithms, n the modulus, and d the private exponent. First form the representative element RR which is: (i) IR if e is odd, or if e is even and the Jacobi symbol of IR (treated as an integer) with respect to the modulus n is 1; (ii) IR/2 if e is even and the Jacobi symbol of IR with respect to n is -1. The signature for m is s = (RR)^{d} mod n. ISO/IEC 9796 specifies that the signature s should be the lesser of(RR)^{d} mod n m6.n — ((RR)^{d} mod n).
- (ii) Verification process for ISO/IEC 9796
The verification process for an ISO/IEC 9796 digital signature can be separated into three stages, as per Figure 11.5(b).
- 1. signature opening. Let s be the signature. Then the following steps are performed.
- (a) Apply the public verification transformation to s to recover an integer IR'.
- (b) Reject the signature if IR' is not a string of к bits with the most significant bit being a 1, or if the least significant nibble does not have value 0110.
- 2. message recover}’. A string MR' of 2t bytes is constructed from IR' by performing the following steps.
- (a) Let X be the least significant к — 1 bits of IR'.
- (b) If 114 ЦизЦ U21|0110 are the four least significant nibbles of X, replace the least significant byte of X by 7r~^{:} (u_{4})||u2-
- (c) MR' is obtained by padding X with between 0 and 15 zero bits so that the resulting string has 2t bytes.
The values г and r are computed as follows.
- (a) From the 2t bytesof MR', compute the / sums MR_{2}ioS(MR_{2i}__{1}), 1 If all sums are 0, reject the signature.
- (b) Let z be the smallest value of i for which MR_{2i} ф S(MR'_{2i}__{L}) Ф 0.
- (c) Let r be the least significant nibble of the sum found hi step (b). Reject the signature if the hexadecimal value of r is not between 1 and 8.
From MR', the .г-byte string MR' is constructed as follows.
- (a) MP = MR'_{2i}_ , for 1 < i < z.
- (b) Reject the signature if the r — 1 most significant bits of MP' are not all 0’s.
- (c) Let M' be the 82 - r + 1 least significant bits of MP'.
- 3. redundancy checking. The signature s is verified as follows.
- (a) From M' construct a string MR" by applying the message padding, message extension, and message redundancy steps of the signing process.
- (b) Accept the signature if and only if the к — 1 least significant bits of MR" are equal to the к — 1 least significant bits of MR'. ^{[2]} ^{[3]}
- [1] The purpose of MR2z is to permit the verifier of a signature to recover the length d of the message. Sinced = 82 — r + 1, it suffices to know z and r. These values can be deduced from MR.
- [2] Since steps 1 through 4 of the signature process describe the redundancy function R, mm step la of Algorithm 11.19 is taken to be IR.
- [3] m is taken to be IR in step 1 of Algorithm 11.25.