GB 15851-1995 Information technology security technology Digital signature scheme with message recovery
Some standard content:
GB15851—1995
This standard is equivalent to the international standard ISO/IEC9796:1991 "Information Technology Security Technology
Digital Signature Method with Message Recovery".
The scheme for digital signature of limited-length messages specified in this international standard is suitable for use in my country. Appendix A, Appendix B, Appendix C and Appendix D of this standard are all indicative appendices. This standard was proposed by the Ministry of Electronics Industry of the People's Republic of China. This standard is under the jurisdiction of the Standardization Research Institute of the Ministry of Electronics Industry. The drafting unit of this standard: the 30th Research Institute of the Ministry of Electronics Industry. The main drafters of this standard: Gong Qimin, Huang Yuejiang, Fang Guanbao, Lei Limin, Li Guiru. 631
GE15851-1995
ISO/IEC Foreword
ISO (International Organization for Standardization) and IEC (International Electrotechnical Commission) have formed a worldwide standardization specialized system. Member countries of ISO or IEC participate in the development of international standards through technical committees established by the respective organizations dealing with specific areas of technical activity. The technical committees of ISO and IEC cooperate in areas of common interest, and other official and non-official international groups in liaison with ISO and IEC also participate in this work.
In the field of information technology, ISO and IEC have established a joint technical committee [SO/IECJTCI]. Draft international standards accepted by the joint technical committee are sent to member countries for voting. The publication of an international standard requires at least 5 votes from member countries. International Standard ISO/IEC:9796 was developed by Technical Committee ISO/IECFTC1 of the Information Technology Association. Appendix A, B and C are for reference only.
GB 15851-1995
Digital signatures in electronic information exchange are very similar to handwritten signatures in traditional mail. Most digital signature schemes are based on some kind of public key system. All public key schemes involve three basic operations: a process of generating a key pair consisting of a secret key and a public key: a process using the secret key; and a process using the public key. In all public key digital signature schemes, the secret key is used in the message signing process and the public key is used in the signature verification process, so the key pair of the digital signature scheme consists of a "secret signing key" and a "public verification key". Obviously, there are two types of digital signature schemes: when the verification process requires the message as part of the input, the scheme is called a "signature scheme with appendix" and a hash function is used in the calculation of the appendix; when the verification process simultaneously reveals the message and its redundancy (sometimes called a "message shadow"), the scheme is called a "signature scheme with message recovery". This standard specifies a digital signature scheme for finite-length messages. The verification process of this digital signature scheme requires only minimal resources. It does not involve the use of hash functions, thus avoiding known attacks on this general methodbzxz.net
The message does not have to be written in natural language, but can be any bit string of finite length. Examples of such messages are confidential information and the result of a hash operation on a longer message, also known as a "message seal". A special case is a structured group of several bit strings generated by confidential software and hardware, one of which is the result of encoding control information generated in the hardware. Note: The use of this standard may involve certain patent provisions. 633
1 Scope
National Standard of the People's Republic of China
Information technology-Security techniques
Digital signature scheme giving message recovery
Information technology-Security techniques--Digital signature scheme giving message recoveryGB 15851—1995
idt ISO/IEC 9796:1991
This standard specifies a digital signature scheme with message recovery using a public key system for finite length messages. This digital signature scheme consists of the following two processes: a signing process, which uses a secret signing key and a signing function to sign a message; and a verification process, which uses a public verification key and a verification function to verify the signature and recover the message. In the signing process, the message to be signed is padded and extended if necessary, and then artificial holes related to the message itself are added, and no assumption is made about whether there are natural holes in the message. This artificial hole will be revealed by the verification process, and the message can be recovered by removing the artificial hole.
This standard does not specify the key generation process, the signing function and the verification function. Appendix A (suggestive appendix) gives an example of a public key system, including key generation, signing function and verification function. Appendix B (suggestive appendix) illustrates the steps of these operations by example. Several parameters in this scheme are related to security: this standard does not specify what values these parameters should take to achieve a given security level. However, they are specified in such a way that if some of these parameters must be changed in the use of this standard, the changes made are minimized.
2 Definitions
This standard adopts the following definitions.
2.1 Message message
A bit string of finite length.
2.2 Signature signature
The bit string obtained at the end of the signature process. 3 Symbols and Abbreviations
Padded message
Extended message
Extended message with redundancy
Intermediate integer
Number of bits of signature
Intermediate integer after recovery
Recovered message with redundancy
Approved by the State Administration of Technical Supervision on December 13, 1995, 634
Implemented on August 1, 1996
Recovered padded message Information
GB15851—1995
Signature function under the control of a secret signature keyVerification function under the control of a public verification keyArithmetic calculation of the modulus
Half byte
Half byte permutation
Shadow of a byte
Concatenation of two bit strings X and Y
Exclusive OR of two bit strings X and Y
1All integers (bit strings or byte strings) have their most significant digit (bit or byte) on the left. 2Hexadecimal notation of 0 to 9 and A to F is used in Table 1 and Appendix B (suggestive appendix) 4Overview
The following two chapters specify:
The signing process in Chapter 5;
The verification process in Chapter 6.
Each signing entity shall use its own signing key corresponding to the public verification key and keep it secret. If necessary, the message to be signed shall be padded and extended, and then the remainder shall be added according to the rules specified in clause 5. The signature of the extended message with the remainder shall be calculated using the secret signing key as specified in clause 5. Each verifying entity shall know and use the public verification key specific to the signing entity. The signature shall be acceptable if and only if the verification process specified in clause 6 succeeds. NOTE: The generation and distribution of keys is beyond the scope of this standard. 5 Signature process
Figure 1 summarizes this signature process.
Interception and forcing
Signature generation
Figure 1 Signature process
GB 15851--1995
Note: A preferred implementation of this signature process should physically protect these operations so that direct access to the signature function under the control of the secret signing key is not possible.
5.1 Padding
A message is a bit string with 0 to 7 zeros padded to the left to obtain a string of 1 octets. The exponent r (to be used later) is the number of padded zeros plus 1, so r has a value of 1 to 8. Thus, in the padded message MP, 8z+1 to r least significant bits are information bits. MP=m ll m1 llmz i ml
mz=(r-1 padded zeros) Ⅱ (9-r information bits) The number obtained by multiplying z by 16 should be less than or equal to k.+3. Therefore, the number of bits in the message to be signed should be at most 8 times the largest integer less than or equal to (k,+3)/16.
5.2 Extension
The exponent t (to be used later) is the smallest integer such that a 2t-byte string contains at least ks-1 bits. The extended message ME is obtained by repeating the bytes of MP on the left in sequence until a t-byte string is formed. For i from 1 to t, j is equal to (i-1) mod 1 plus 1 (so from 1 to z), and the i-th byte of ME is equal to the i-th byte of MP. ME=.m lmz Ilmi
t bytes→
Note: number ≥ is less than or equal to t, only when k.The two are equal only when they are congruent modulo 16 to 13, 14, 15, 0 or 1. 5.3 Remainder
The extended message MR with redundancy is obtained by alternately placing the t bytes of ME in odd positions and the t bytes in even positions. The lower half byte of the 2zth byte of MR is modified by the exponent r, and the message length is encoded by its value and position.
For i from 1 to t,
The (2i-1)th byte of MR is equal to the i-th byte of ME; the 2ith byte of MR is equal to the image of the shadow S of the i-th byte of ME as specified in Table 1, with the exception of the 2zth byte, which is equal to the result of the exclusive OR of the shadow of the i-th byte of ME and the exponent r. MR =*..S(mz) r Il m, l ..S(m2) Il mz Il S(m) Il m— — 2t Section—
Note: The calculation of the 2t bytes of MR(mr2 to mri) from the 1 bytes of MP(mp, to mp) is done by applying the following three formulas successively for i from 1 to t. j: = ((i-1) mod z) + 1smr21-1: —mp;smr2: = S(mp,). Finally, the 2zth byte is modified by the exponent r. mr2: = r@mrz
5.4 Truncating and forcing
The intermediate integer IR is encoded by a k, bit string with the most significant bit being 1, k. The least significant bit is k of MR, and the least significant bit is replaced. If μ2Ⅱμl is the least significant byte of MR, then the least significant byte of IR is μl6.
5.5 Signature Generation
Under the control of the secret signature key, the signature function is applied to IR to obtain k. The signature Z of the bit string. 636
GB 15851-1995
E =- Sign(IR)
Table 1 Substitution II and Shadow S
If μ is composed of four bits aaga, the image under substitution I is represented by (), then αaiαar1甲a:?aOlaOaar
If byte m is composed of two half bytes μ, the image under shadow S is represented by S(m), then I(μ)I(u). Verification Process
Figure 2 summarizes the verification process.
Signature Opening
Message Recovery
Residue Check
Recovered Message
【Signature Accepted】
Figure 2 Verification Process
6.1 Signature Opening
Under the control of the public verification key, the signature 3 is transformed into the recovered intermediate integer IR by applying the verification number to it. FRr = Veni(s)
If IR is not a bit string with the most significant bit being 1 and the least significant nibble being 6, then the signature 3 will be rejected. 6.2 Message Recovery
The recovered message MR with a perfect remainder is a 2t-byte string with the (1-k) (mod16) most significant bits being 0 and the ~1 least significant bits being the ~1 least significant bits of IR\, but the least significant byte is replaced. According to the substitution II specified in Table 1, if 26 is the least significant four nibbles of IR, then the least significant byte of MR' should be I()2. MR'= mgell mzi-, l *m2 llm:
: MR and MR may not be equal. MR is composed of the least significant bit of MR and the most significant bit filled with 0 to 15 zeros.
GB 158511995
From the 2t bytes of MR', t sums are calculated. According to the shadow S specified in Table 1, the i-th sum is equal to the XOR of the shadow of the 2i-th byte and the (2i1)-th byte.
m2: S(m2i-1)
If the t sums are all 0, the signature three will be rejected. Restore to the position of the first non-zero sum. The restored filled message MP' is the string consisting of the least significant bytes in the odd position of MR'.
MP = m2z- i mz- il -mzi- l -m ll m The exponent is restored to the value of the first non-zero least significant nibble. If the exponent is not between 1 and 8, or if the r-1 most significant bits of MP are not all zero, then the signature Z shall be rejected. m2-1 = (r-1 padded zeros) II (9r information bits) The message is restored to the string consisting of the 8z+1 least significant bits of MP. 6.3 Redundancy Check
Signature 2 is accepted if and only if the k-1 least significant bits of MR' are equal to the k-1 least significant bits of the message extended with redundancy calculated from the restored padded message MP\ according to 5.2 and 5.3. 638
A1 Definition
Modulus
The integer formed by the product of two prime numbers.
GB 15851-1995
Appendix A
(Suggested Appendix)
Example of a public key system for digital signature: public verification key, modulus and verification exponent.
Secret signature key, secret signature key, signature exponent.
A2 Symbols and Abbreviations
Icm(a,b)
Delegated Elements
Composite Integer
Bit Length of Modulus
Prime Factors of Modulus
Verifying Exponent
Signed Exponent
Least Common Multiple of Integers a and b
Jacobi Sign of a with Respect to n
Note: Let p be an odd prime and let a be a positive integer, then the Legendre sign of an integer a with respect to prime p is defined by the following formula: (alp) = a(pv)/2modp
When a is not a multiple of p, then the Legendre sign of an integer α with respect to prime p is +1 or -1, depending on whether the integer α is modulo p squared or not. The Legendre sign of a multiple of p with respect to prime p is 0. Let n be an odd positive integer, and let α be a positive integer such that the Jacobian of α with respect to n is equal to the product of the Legendre signs of α with respect to the prime factors of n. Therefore, if n = pq, then (an) = (alp)(alq) The Jacobian of any integer α with respect to any integer n can be efficiently computed without knowing the prime factors of n. A3 Key Generation
A3.1 Public Verification Exponent
Each signing entity shall select a positive integer as its public verification exponent. In certain applications, the public verification exponent may be standardized.
Note: There are particular advantages to using 2 and 3 as the public verification exponent. A3.2 Secret Prime Factors and Public Modulus Each signing entity shall secretly and randomly select two distinct odd primes g1 and g9 that satisfy the following conditions: - If g1 is odd, then g1 and g2 shall be relatively prime to g1; if g1 is even, then (1)/2 and (g1)/2 shall be relatively prime to g1 and g2, and g1 shall not be congruent modulo 8. The public modulus n is the product of the secret prime factors p and q. 639
The length of the modulus is, which should be equal to +1.
GB15851-1995
1Several other conditions on the selection of prime numbers should also be well considered to prevent the factorization of the modulus. 2Some forms of moduli have simple modular reduction operations and only require a small amount of storage tables. These forms are Fx.s. - : n = 264r c
Fry + in = 264 + c
Its length: table 64x bits,
Its length: k=64α+1 bits,
Where: 1≤2x and 264x-2.
In the negative form, all bits of the most significant bytes are 1, and their number can reach one-quarter of the length of the modulus. In the positive form, after the most significant bit with the value of 1, all bits of the 3 most significant bytes are 0, and their number can reach one-quarter of the length of the modulus. A3.3 Secret Signature Exponent
The secret signature exponent is the smallest positive integer s such that SV-1 is a multiple of the following numbers: -lcm(p1,g-1), if odd;
1/2lcm（-1,q-1）, if even. A4 Signature Function
The intermediate integer IR is the k～1 bit string calculated as described in 5.4. The representative element of IR with respect to n is denoted by RR.
If it is odd, then RR is IR;
If it is even and (IRn)=+1, then RR is IR; if it is even and (IR|n)=-1,Then RR is IR/2. Note: If n is even, the Jacobian sign of RR with respect to n is set to +1. Raise RR to the power of s modulo n, and the signature three is the result of this calculation or its complement with respect to n, whichever is smaller. Z - min(RR'mod n,n -- (RRmod n)) This defines the signature function "Sign". Z = Sign(IR)
A5 Verification function
The signature is a positive integer less than n/2, which is raised to the power of modulo n to obtain the composite integer IS. Thus, the recovered intermediate integer IR' is determined by the following decoding: - If IS is modulo 16 congruence 6, then IR is IS; - If nIS is modulo 16 congruence 6, then IR' is n~IS. Moreover, when n is even,
- If IS is modulo 8 congruence 3, then IR is 2IS; - If n-IS is modulo 8 congruence 3, then IR is 2(n-IS). In all other cases, the signature Z shall be rejected, and if IR' does not fall within the range of 2k-2 to 22k-11, the signature shall also be rejected.
This defines the verification function "Verif". GB 15851—1995
IR' - Verif(E)
Appendix B
(Suggestive Appendix)
Explanatory Example of Appendix A (Suggestive Appendix) (using hexadecimal notation)
Example with Public Exponent 3
B1.1 Key Generation
The public verification exponent √ is 3.
So the secret prime factors are all modulo 3 with remainder 2.
BA09106C
1B4CBB7A
q=16046EB39
CFF955B6
754EB6FE
7A782B15||t t||E03BEAB6
4B4F48B7
BBC21479
7C1BC152
21D03C08
EE152A32
9FF 1B 8DE
90A1A3AB
B8AE6B66
6BF8CB25
The 513-bit public modulus n has the form 2512+c, where 2c>2384>c (form F, + where α=8, y=16). 00000000
n=pq=1
00000000
BBA2D15D
25087920
12EC8CE6
BB303C8A
DD7CDF35
92F0A0B8
The secret signature exponent s is (n—p-q+3)/6. 2 AAAAAAA
C9F0783A
81C96A3F
DBF1149E
B1.2 Length of variable
AAAAAAAA
49DD5F6C
16AB5F95
4CDC3227
00000000
21 C5EBBC
8EA119FD
E8321B04
AAAAAAAA
5AF651F4
72D7CC3F
3FAADD3F
00000000
BAE52B71
66FB0640
1ACD 40B7
AAAAAAAA
C9DODC92
2D0F25A9
DA5DCDA7
is a positive integer less than or equal to (+2)/16, and is the largest integer less than or equal to (+13)/16. Therefore, when
is 513, the value of
ranges from 1 to 32, the message to be signed is a string of 1 to 256 bits, and the padded messages MP and MP are strings of 1 to 32 bytes; when
t is 32, the extended message ME is a string of 32 bytes, and the redundant messages MR and MR2 are strings of 64 bytes. Moreover, the intermediate integers IR and IR and the signature are all strings of 512 bits (-1 bit). B1.3 Example 1
This example illustrates the padding, extension, and truncation of a 100-bit message signature. The message is: CBBAA99887766554433221100
Signature Process
After padding with four zeros on the left, the padded message MP is a 13-byte string, so z=13, r=5. MP=0CBBAA99887766554433221100The extended message ME is formed by repeating the 13 consecutive bytes of MP and arranging them on the left until a 32-byte string is reached.
ME=55443322
2211000c
11000CBB
BBAA9988
The extended message MR with remainder is
GB15851-1995
AA998877
77665544
66554433
33221100
a 64-byte string obtained by alternating 32 bytes of ME and 32 bytes of remainder. The modification of the 26th byte (E2) gives the encoding of the message boundary. MR44559944
88335522
BBAADD99
55223311
FF772266
0088FF77
EE00E20C
44559944
3311EE00
22664455
66 BBBBAA
88335522
E70C66BB
99448833
DD990088
3311EED0
The intermediate integer IR is obtained from MR by truncating 511 bits, padding with a 1 on the left, and replacing the least significant byte, i.e., lμ=00 with μ6=06. Since V is an odd number, it represents the element RR is IR. RR--IR-C4559944
BBAADD99
55223311
FF772266
88335522
008BFF77
EE00E20C
44559944
3311EE00
22664455
66BBBBAA
88335522
E70C66BB
99448833
DD990088
3311EE06
Calculate RR to the power of s modulo n. Here, signature three is the complement of the calculation result with respect to n. Z=309F873D
137D3EBF
6BDD022E
E04D3E42
Verification process
8DED8379
D8F25AB5
A65DABAB
1CAAB 717
490F6097
F138D56A
920A8101
C90D89EA
EAAFDABC
719CDC52
3A85D092
45A8D23A
The signature Z is less than n/2. The composite integer IS is obtained by calculating its modulo n three times. I
3BAA66BB
FFF7F3C4
CFE6460E
13756A80
77CCAADD
BAA73D12
EF7BFD29
4E9B0774
CCEE 1 1 FF
FF5FA767
27E55E52
5FFEC5E1
18F39944
21AdA33D
89620587
E7BB52B1
The intermediate integer is a 512-bit string, in which the most significant bit is 1 and the value of the least significant half byte is 6. Because n here is modulo 16 remainder 7 and IS is modulo 16 remainder 1, the recovered intermediate integer IR is n-IS. Afraid=
C4559944
BBAADD99
55223311
FF772266
88335522
0088 FF77
EE00E20C
44559944
3311EE00
22664455
66BBBBAA
883 35522
E70C66BB
99448833
DD990088
3311EE06
The recovered message MR' with remainder is a 64-byte string in which, after a padding of 0, the 511 least significant bits of IR follow, except for the least significant byte. According to the description of I(0)=E in substitution five, EE06 represented by 216 will be replaced by 1! )+, whose value is EE00. MR44559944
BBAADD99
55223311
FF772266
88335522||tt| |0088FF77
EE00E20C
44559944
3311EE00
22664455
6 6BBBBAA
88335522
E70C668B
99448833
DD990088
3311EE00
The first non-zero sum is the 13th sum, which is 5, so =13 and =5. The restored padded message MP is the string of 13 bytes in the least significant odd positions of MR. MP'-0CBBAA99887766554433221100The four most significant bits of MP (.-1 = 4) are 0, so the message itself is restored to the string of the 100 least significant bits of MP (82 + 1 - r = 100).The restored padded message MP is the string of 13 bytes in the least significant odd positions of MR. MP'-0CBBAA99887766554433221100. The four most significant bits of MP (.-1 = 4) are 0, so the message itself is restored to the string of the 100 least significant bits of MP (82 + 1 - r = 100).The restored padded message MP is the string of 13 bytes in the least significant odd positions of MR. MP'-0CBBAA99887766554433221100. The four most significant bits of MP (.-1 = 4) are 0, so the message itself is restored to the string of the 100 least significant bits of MP (82 + 1 - r = 100).
Tip: This standard content only shows part of the intercepted content of the complete standard. If you need the complete standard, please go to the top to download the complete standard document for free.