ISO IEC 9796:1991 download free.Information technology — Security techniques — Digital signature scheme giving message recovery.
1 Scope
ISO IEC 9796 specifies a digital signature scheme giving message recovery for messages of limited length and using a public-key system.
This digital signature scheme includes
— a signature process using a secret signature key and a signature function for signing messages;
— a verification process using a public verification key and a verification function for checking signatures while recovering messages.
During the signature process, messages to be signed are padded and extended if necessary, Artificial redundancy is then added, depending upon the message itself. No assumption is made as to the possible presence of natural redundancy in the messages. The artificial redundancy is revealed by the verification process. The removal of this artificial redundancy gives message recovery.
ISO IEC 9796 does not specify the key production process, the signature function and the verification function. Annex A gives an example of a public-key system including key production, signature function and verification function. The various steps of these operations are illustrated by examples in annex B.
Some parameters in the scheme are related to security:
ISO IEC 9796 does not specify the values to be used in order to reach a given level of security. However, ISO IEC 9796 is specified in such a way as to minimize the required changes in its uso if some of these parameters have to be modified.
2 Definitions
For the purposes of ISO IEC 9796, the
following dofinitions apply.
2.1 message: String of bits of limited length.
22 signature: String of bits resulting from the signature process.
3 Symbols and abbreviations
MP Padded message
MC Extended message
MR Extended message with redundancy
IR Intermediate integer
I Signature
Length of the signature in bits
1H Recovered intermediate i ntege
MR’ Recovered message with redundancy
MP Recovered padded message
Sign Signature function under control of the secret signature key
Verif Verification function under control of the public verification key
mod z Arithmetic computation rnodulo z Nibble
JJ Permutation of the nibbles
m Byte
S Shadow of the bytes
Xli V Concatenation of strings of bits Xand V
XG Y Exclusive-oc of strings of bits Xand Y
NOTES
1 All integers (and all strings of bits or bytes) are written with
the most significant digit (or bit or byte) in left position.
2 The hexadecimal notation, with the digits 0 to 9 and A to r, is used in table 1 and in annex B.
4 General overview
The next two clauses specify
— the signature process in clause 5;
— the verification process in clause 6.
Each signing entity shall use and keep secret its own signature key corresponding to its own public verification key.
Messages to be signed shall be padded and extended if necessary. Redundancy is then added according to rules specified in clause 5. From the extended messages with redundancy, signatures shall be computed using the secret signature key as specified in clause 5.
Each verifying entity should know and use the public verification key specific to the signing entity. A signature shall be accepted if and only if the verification process specified in clause 6 is successful.
NOTE — The production and the distribution of keys fall outside the scope of this International Standard.
5 Signature process
Hgure 1 summarizes the signature process.
Messago
Parding
Tricatioi and ocing
Signature production
Signature
Figure 1 — Signature process
NOTE — A good implementation of the signature process should physically prntnct th npratinns in such a way that there is no direct access to the signature function under control of the secret signature key.
5.1 Padding
The message is a string of bits. This string of bits is padded to the left by 0 to 7 zeroes so as to obtain a string of z bytes. Index r, to be used later on, is the number of padded zeroes plus one. Index r is thus valued from 1 to 8.
Consequently, in the padded message denoted by MP, the 8z+1—r least significant bits are information bearing.
MP=m1lIm1lI…ro2llm1
mz = (r—1 padded zeroes) 11 (9—r information bits)
Number z multiplied by sixteen shall be less than or equal to number k+3. Consequently, the number of bits of the message to be signed shall be at most 8 times the largest integer less than or equal to (k+3)/1 6.
5.2 Extension
Number r. to be used later on. is the least integer such that a string of 2t bytes includes at least k—1 bits.
The extended message ME is obtained by repeating the z bytes of MP, as many times as necessary, in order and concateneted to the left, until forming a string of t bytes.
For i valued from 1 to t and j equal to i—i (mod z) plus one (j is therefore valued from 1 to z), the i-th byte of ME equals the j-th byte of MR
ME= … iull … in2 II fri1
rbytes
NOTE — Number z is less than or equal to number r. The equality may occur only if k5 is congruent to 13, 14, 15. 0 or 1 mod 16.
5.3 Redundancy
The extended message with redundancy MI? is obtained by interleaving the t bytes of ME in odd positions and t bytes of redundancy in even positions, Altered by index r, the least significant nibble of the 2z-th byte ot MH codes the message length by its value and its position.
For ivalued from 1 to t.
— the (21—1)-th byte of MR equals the i-th byte of ME:
— the 2i-th byte of MR equals the image of the i-th byte of ME according to the shadow S specified in table 1, except for the 2z-th byte of MR which equars the exclusive-or of index r with the shadow of the z-th byte of ME.
NOTE — The computation of the 2t bytes of MR Cm,21 to rn,1)
from the z bytes of MP (mp, to mp1) is petormed by applying successively the following three formulae for i valued from 1 to r.
j :=(-1modz.1; mr2,…1:=mp,; rnr2:—mp1)
Finally, the 2z-th byte is altered by index r.
5.4 Truncation and forcing
The intermediate integer IR is coded by a string of k5 bits where the most siqnificant bit is valued to 1 and where the k3—1 least significant bits are those of MR. except for the least significant byte which is replaced. If P2 II p is the least significant byte of MR. then the least significant byte of IR shall be p II 6.
5.5 Signature production
The signature E is obtained as a string of k5 bits by applying to 1R the signature function under control of the secret signature key.
1= Sign(IR)
specified in table 1, if 4U,4 II p II P2 II 6 are the four least significant nibbles of IA, then the least significant byte of MR’shall be JJ’(u4) II P2.
MR = m II m2t1 II … rr II m
NOTE — The strings MR and MR’ may be unequal. The string MR’ consists of the k,—1 least significant bits of MR padded by 0 to 15 zeroes in the most significant bits.
From the 2 bytes of MW, r sums are computed. According to the shadow S specified in table 1. the i-th sum equals the exclusive-or of the 2i-th byte with the shadow of the (2 1—1 )-th byte.
m2, D S(m2,i)
The signature shall be rejected if the I sums are null.
Number z is recovered as the position of the first non-null sum The recovered padded message MP is the string of the z least significant bytes in odd positions in MW.
MP’ = m.1 II m2 II … rn21..1 II … ,r II m1
Index r is recovered as the value of the least significant iiibbl of th first non-null suni.
The signature shall be rejected if index r is not valued from 1 to 8, and also if the r—1 most significant bits of MP’ are not all null.
m2Z_1 = (r—1 padded zeroes) II (9—r information bits)
The message is recovered as the string of the 8z+1—r least
significant bits of MI”.
6.3 Redundancy checking
The signature E shall be accepted if and only if the k5—1 least significant bits of MR are equal to the k5—1 least significant bits of another extended message with redundancy computed from the recovered padded message MI” according to 5.2 and 5.3.