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.




the bitlength of the signature.


the bitlength of the message m to be signed; it is required that d < 8 [(к + 3)/16j.


the number of bytes in the padded message; г = [d/8].


one more than the number of padding bits; r = Sz — d + 1.


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.


к (bits)

d (bits)

2 (bytes)

r (bits)

t (bytes)







(i) Signature process for ISO/IEC 9796

The signature process consists of 5 steps as per Figure 11.5(a).

Signature and verification processes for ISO/IEC 9796

Figure 11.5: Signature and verification processes for ISO/IEC 9796.

  • 1. padding. If m is the message, form the padded message MP = 0r 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 = mz ||тг_ 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, MEi+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 MR2z of the resulting string. More precisely, = ME,■ and MR2, = 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 г ф MR2z.[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~: (u4)||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 MR2ioS(MR2i_1), 1 If all sums are 0, reject the signature.
  • (b) Let z be the smallest value of i for which MR2i ф 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.
< Prev   CONTENTS   Source   Next >