ANSI INCITS ISO IEC 9796-1991 Information Technology - Security Techniques - Digital Signature Scheme Giving Message Recovery (Adopted by INCITS).pdf

1、INTERNATIONAL STANDARD ISO/IEC 9796 First edition 1991-09-15 Information technology - Security techniques - Digital signature scheme giving message recovery Technologies de /information - Techniques de s - a process using a secret key; - a process using a public key In any public-key digital signatu

2、re scheme, the secret key is involved in a signature process for signing messages, and the public key is involved in a verification process for verifying signatures. A pair of keys for a digital signature scheme thus consists of a “secret signature key and a “public verification key”. Two types of d

3、igital signature schemes are clearly identified -When the verification process needs the message as part of the input, the scheme is named a “signature scheme with appendix”. The use of a hash-function is involved in the calculation of the appendix. -When the verification process reveals the message

4、 together with its specific redundancy (sometimes called the “shadow of a message”), the scheme is named a “signature scheme giving message recovery”. This International Standard specifies a scheme for digital signature of messages of limited length. This digital signature scheme allows a minimal re

5、source requirement for verification. It does not involve the use of a hash-function and it avoids the known attacks against the generic algorithm in use. The message need not be in a natural language. It may be any arbitrary string of bits of limited length. Examples of such messages are cryptograph

6、ic key materials and the result of hashing another, longer message, which is also called the imprint of a message. A characteristic example is a structured set of a few strings of bits generated by cryptographic software and hardware, one of these strings coding control information produced within t

7、he hardware. NOTE -The use of this International Standard may involve patented items iv INTERNATIONAL STANDARD ISO/IEC 9796 : 1991 (El Information technology - Security techniques - Digital signature scheme giving message recovery 1 Scope This International Standard specifies a digital signature sch

8、eme 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 verificatio

9、n 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 t

10、he messages. The artificial redundancy is revealed by the verification process. The removal of this artificial redundancy gives message recovery. This International Standard does not specify the key production process, the signature function and the verification function. Annex A gives an example of

11、 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: this International Standard does not specify the values to be used in orde

12、r to reach a given level of security. However, this International Standard is specified in such a way as to minimize the required changes in its use if some of these parameters have to be modified. 2 Definitions For the purposes of this International Standard, the following definitions apply. 2.1 me

13、ssage: String of bits of limited length. 2.2 signature: String of bits resulting from the signature process. 3 Symbols and abbreviations MP ME MR IR ix ks IR MR MP Sign Verif mod z P I7 m S XII Y X0Y NOTES Padded message Extended message Extended message with redundancy Intermediate integer Signatur

14、e Length of the signature in bits Recovered intermediate integer Recovered message with redundancy Recovered padded message Signature function under control of the secret signature key Verification function under control of the public verification key Arithmetic computation modulo z Nibble Permutati

15、on of the nibbles Byte Shadow of the bytes Concatenation of strings of bits Xand Y Exclusive-or of strings of bits Xand Y 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

16、9 and A to F, 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. 1 ISO/IEC 9796 : 1991 (El Each signing entity shall use and keep secret its own signature key corresponding to its own public ve

17、rification 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

18、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 Signatu

19、re process Figure 1 summarizes the signature process Message / I Padding I Extension I Redundancy I Truncation and forcing Signature production I / V Signature Figure 1 - Signature process NOTE -A good implementation of the signature process should physically protect the operations in such a way tha

20、t 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 p

21、lus one. Index r is thus valued from 1 to 8. Consequently, in the padded message denoted by MP, the 8z+l -r least significant bits are information bearing. MP= m,II m,l II m;! II ml m, = (r-1 padded zeroes) II (9-r information bits) Number z multiplied by sixteen shall be less than or equal to numbe

22、r 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)/16. 5.2 Extension Number f, 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

23、obtained by repeating the z bytes of MP, as many times as necessary, in order and concatenated to the left, until forming a string of t bytes. For i valued from 1 to t and j equal to i-l (mod z) plus one (j is therefore valued from 1 to I), the i-th byte of ME equals the j-th byte of MP. ME= m,ll _

24、m2 II ml NOTE - Number z is less than or equal to number t. The equality may occur only if k, is congruent to 13, 14. 15, 0 or 1 mod 16. 5.3 Redundancy The extended message with redundancy MR is obtained by interleaving the t bytes of ME in odd positions and t bytes of redundancy in even positions.

25、Altered by index r, the least significant nibble of the 2z-th byte of MR codes the message length by its value and its position. For ivalued from 1 to t, - the (2i-1 )-th byte of MR equals the i-th byte of ME; - the 2i-th byte of MR equals the image of the ;-th byte of ME according to the shadow S s

26、pecified in table 1, except for the 2z-th byte of MR which equals the exclusive-or of index r with the shadow of the z-th byte of ME. MR = S(m,) 0 r II m,ll S(ma) II m2 II S(m,) II ml NOTE -The computation of the 2t bytes of MR (mrpr LO mr,) from the z bytes of MP hp, to mp,) is performed by applyin

27、g successively the following three formulae for ivalued from 1 to t. j := (i-1 mod zJ+l ; mrz,-t := mp,; mr2, := .S(mp,) Finally, the 2z-th byte is altered by Index r. mr2, := r mr2, 5.4 Truncation and forcing The intermediate integer IR is coded by a string of k, bits where the most significant bit

28、 is valued to 1 and where the ks-1 least significant bits are those of MR, except for the least significant byte which is replaced. If 2 II 1 is the least significant byte of MR. then the least significant byte of IR shall be 1 II 6. 5.5 Signature production The signature C is obtained as a string o

29、f k, bits by applying to IR the signature function under control of the secret signature key. C = Sign( IR) 2 ISO/IEC 9796 : 1991 (EI Table 1 - Permutation n and shadow S P 0123456789ABCDEF LW E3 5 8 9 4 2 F 0 DB6 7 AC 1 I If nibble p consists of the bits a4 a3 a2 a, then under the permutation II, i

30、ts image denoted by I) consists of the bits a4f3a2ea,e1; a4ea3ea,1; a4ea3a2e31; a3a2eaI. If byte m consists of the nibbles p2 p, then under the shadow S, its image denoted by Slml consists of the nibbles II(p21 II,. 6 Verification process Figure 2 summarizes the verification process. Signature Rejec

31、t I Recovered message (Signature accepted) Figure 2 - Verification process 6.1 Signature opening The signature C is transformed into the recovered intermediate integer I/? by applying to Z the verification function under control of the public verification key. IR = Verif( 1) The signature C shall be

32、 rejected if IR is not a string of k, bits where the most significant bit is valued to 1 and where the least significant nibble is valued to 6. 6.2 Message recovery 6.3 Redundancy checking The recovered message with redundancy MR is the string of 2r bytes where the l-k, (mod 16) most significant bit

33、s are null and where the k,l least significant bits are those of It?, except for the least significant byte which is replaced. According to the permutation fl The signature Z shall be accepted if and only if the k,-1 least significant bits of MR are equal to the k,-1 least significant bits of anothe

34、r extended message with redun- dancy computed from the recovered padded message MP according to 5.2 and 5.3. specified in table 1, if p4 II 3 II 2 II 6 are the four least significant nibbles of If?, then the least significant byte of MRshall be IZ-rf! II ml NOTE -The strings MR and MR may be unequal

35、. 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 2r bytes of MR, t sums are computed. According to the shadow S specified in table 1, the i-th sum equals the exclusive-or of the 2Lth byte with the shadow of the (2i-1 I-

36、th byte. mp, 0 .S(mp;-1) The signature 1 shall be rejected if the r 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 MR. MP= m2z-1 II rnzz-3 II ,-t II Q II ml Index r is

37、recovered as the value of the least significant nibble of the first non-null sum. The signature C shall be rejected if index r is not valued from 1 to 8, and also if the r-l most significant bits of MP are not all null. m2z-1 = (r-1 padded zeroes) II (9-r information bits) The message is recovered a

38、s the string of the 8z+l-r least significant bits of MP. 3 ISO/IEC 9796 : 1991 (El Annex A (informative) Example of a public-key system for digital signature A. 1 Definitions Modulus: Integer constructed as the product of two primes. Public verification key : Modulus and verification exponent. Secre

39、t signature key : Signature exponent. A.2 Symbols and abbreviations RR Representative element IS Resulting integer n Modulus k Length of the modulus in bits Ps q Prime factors of the modulus V Verification exponent s Signature exponent Icm(a, b) Least common multiple of integers a and b (al n) Jacob

40、i symbol of a with respect to n NOTE - Let p be an odd prime, and let a be a positive integer. The Legendre symbol of integer a with respect to prime p IS defined by the following formula. la I p) = a(P1)R mod p When integer a is not a multiple of p, then the Legendre symbol of integer a with respec

41、t to prime p is valued to either +1 or -1 depending on whether integer a is or is not a square modulo p. The Legendre symbol of multiples of p with respect to prime p is null. Let n be an odd positive integer, and let a be a positive integer. The Jacobi symbol of integer a with respect to integer n

42、is the product of the Legendre symbols of integer a with respect to the prime factors of n. Therefore if n = p q, then (a I n) = (a I p) (a I q), The Jacobi symbol of any integer a with respect to any integer n may be efficiently computed without the prime factors of n. A.3 Key production A.3.1 Publ

43、ic verification exponent Each signing entity shall select a positive integer v as its public verification exponent. 4 The public verification exponent may be standardized in specific applications. NOTE -Values 2 and 3 may have some practical advantages. A.3.2 Secret prime factors and public modulus

44、Each signing entity shall secretly and randomly select two distinct odd primes p and q subject to the following conditions. - If v is odd, then p-l and q-l shall be coprime to v. - If v is even, then (p-1)/2 and (q-1)/2 shall be coprime to v. Moreover, p and q shall not be congruent to each other mo

45、d 8. The public modulus n is the product of the secret prime factors p and q. n=pq The length of the modulus is k. Number k shall equal k,+l NOTES 1 Some additional conditrons on the choice of primes may well be taken into account in order to deter factorization of the modulus. 2 Some forms of the m

46、odulus srmplify the module reduction and need less table storage. These forms are F x, y, _ : n = 264x-c of length : k = 64x bits, F x,y,+: “=264x+c of length : k = 64x+1 bits, where: 11y12x and cc2 64x - 8Y 2384 c (form F, , + with x = 8 and y = 16). n=pq= 1 00000000 00000000 00000000 00000000 BBA2

47、D15D BB303C8A 21C5EBBC BAE52B71 25087920 DD7CDF35 8EA119FD 66FB0640 12EC8CE6 92FOAOB8 E8321 B04 lACD40B7 The secret signature exponent s is (n-p-q+3)/6. s= 2AAAAAAA AAAAAAAA AAAAAAAA AAAAAAAA C9F0783A 49DD5F6C 5AF651 F4 C9DODC92 81 C96A3F 16A85F95 72D7CC3F 2DOF25A9 DBFl149E 4CDC3227 3FAADD3F DA5DCDA

48、7 B.1.2 Length of the variables Number z is a positive integer less than or equal to k+2 divided by 16. Number r is the largest integer less than or equal to kt 13 divided by 16. Consequently, when number k is 513, - number z is valued from 1 to 32, the messages to be signed are strings of 1 to 256

49、bits, and the padded messages MP and MP are strings of 1 to 32 bytes; - number r is 32, the extended messages ME are strings of 32 bytes, and the messages with redundancy MR and MR are strings of 64 bytes. Moreover, the intermediate integers IR and IR and the signatures 1 are strings of 512 bits (k-l bits). B.1.3 Example 1 This example illustrates padding, extension and truncation for signing a message of 100 bits. C BBAA 9988 7766 5544 3322 1100 Signature process After padding four zeroes to the left, the padded message MP is a string of 13