Standards related to:

GM/T 0044.2-2016GM/T 0044.2-2016

GM

CRYPTOGRAPHY INDUSTRY STANDARD

OF THE PEOPLE’S REPUBLIC OF CHINA

ICS 35.040

L 80

File No.. 55614-2016

Identity-based cryptographic algorithms

SM9 - Part 2. Digital signature algorithm

ISSUED ON. MARCH 28, 2016

IMPLEMENTED ON. MARCH 28, 2016

Issued by. State Cryptography Administration

Table of Contents

Foreword ... 3

Introduction .. 4

1 Scope .. 5

2 Normative references ... 5

3 Terms and definitions ... 5

4 Symbols ... 6

5 Algorithm parameters and auxiliary functions ... 8

5.1 General ... 8

5.2 System parameter group ... 8

5.3 Generation of system signature master key and user signature key ... 9

5.4 Auxiliary functions ... 9

6 Digital signature generation algorithm and flow .. 11

6.1 Digital signature generation algorithm ... 11

6.2 Digital signature generation algorithm flow ... 12

7 Digital signature verification algorithm and flow .. 13

7.1 Digital signature verification algorithm ... 13

7.2 Digital signature verification algorithm flow ... 13

Foreword

GM/T 0044 “Identity-based cryptographic algorithms SM9” consists of five parts.

- Part 1. General;

- Part 2. Digital signature algorithm;

- Part 3. Key exchange protocol;

- Part 4. Key encapsulation mechanism and public key encryption algorithm;

- Part 5. Parameter definition.

This Part is Part 2 of GM/T 0044.

This Part was drafted in accordance with the rules given in GB/T 1.1-2009.

Attention is drawn to the possibility that some of the elements of this document

may be the subject of patent rights. The issuing authority shall not be held

responsible for identifying any or all such patent rights.

This Part was proposed by and shall be under the jurisdiction of Code Industry

Standardization Technical Committee.

Main drafting organizations of this Part. National Information Security

Engineering Center, Shenzhen Olym Information Security Technology Co., Ltd.,

Wuhan University, Shanghai Jiao Tong University, Institute of Information

Engineering of Chinese Academy of Sciences, North Institute of Information

Technology.

Main drafters of this Part. Chen Xiao, Cheng Zhaohui, Ye Dingfeng, Hu Lei,

Chen Jianhua, Lu Beike, Ji Qinguang, Cao Zhenfu, Yuan Wengong, Liu Ping,

Ma Ning, Yuan Feng, Li Zengxin, Wang Xuejin, Yang Hengliang, Zhang Qingpo,

Ma Yanli, Pu Yusan, Tang Ying, Sun Yisheng, An Xuan.

Introduction

A. Shamir proposed the concept of Identity-Based Cryptography in 1984. In the

identity-based cryptographic system, the user’s private key is calculated by the

key generation center (KGC) based on the master key and the user identity.

The user's public key is uniquely identified by the user identity so that the user

does not need to guarantee the authenticity of his public key through a third

party. Compared with certificate-based public key cryptographic system, the

key management in the identity-based cryptographic system may be properly

simplified.

In 1999, K. Ohgishi, R. Sakai and M. Kasahara proposed in Japan an identity-

based key sharing scheme constructed using elliptic curve pairing. In 2001, D.

Boneh and M. Franklin, as well as R. Sakai, K. Ohgishi and M. Kasahara, et al.

independently proposed the identity-based public key encryption algorithm

constructed using elliptic curve pairing. These efforts led to a new development

of identity-based cryptography. A number of identity-based cryptographic

algorithms implemented using elliptic curve pairing have emerged, such as

digital signature algorithm, key exchange protocol, key encapsulation

mechanism and public key encryption algorithm.

Elliptic curve pairing has the property of bi-linearity. It establishes a relationship

between cyclic subgroups of elliptic curve and multiplicative cyclic subgroups

of extended field, and forms difficult problems such as bilinear DH, bilinear

inverse DH, deterministic bilinear inverse DH, τ-bilinear inverse DH and τ-Gap-

bilinear inverse DH. When elliptic curve discrete logarithm problem and

extended field discrete logarithm problem are equally difficult to solve, it may

use elliptical curve pairing to construct identity-based cryptography with both

safety and efficiency.

This Part describes the identity-based digital signature algorithm implemented

using elliptic curve pairing.

Identity-based cryptographic algorithms

SM9 - Part 2. Digital signature algorithm

1 Scope

This Part of GM/T 0044 specifies the identity-based digital signature algorithm

implemented using elliptic curve pairing, including digital signature generation

algorithm and verification algorithm, and gives digital signature and verification

algorithm and their corresponding flows.

This Part is applicable for recipients to verify the integrity of date and the identity

of date sender through the signer’s identity, and for third parties to determine

the authenticity of the signature and the signed data.

2 Normative references

The following referenced documents are indispensable for the application of

this document. For dated references, only the dated edition cited applies. For

undated references, the latest edition of the referenced document (including all

amendments) applies.

GM/T 0004-2012 SM3 cryptographic hash algorithm

GM/T 0044.1-2016 Identity-based cryptographic algorithms SM9 - Part 1.

General

3 Terms and definitions

For the purpose of this document, the following terms and definitions apply.

3.1

message

A bit string of any finite length.

3.2

signed message

A set of data elements consisting of a message and a digitally signed portion of

< P>. looping group generated by element P.

[u]P. u times element P in addition group G1, G2.

ڿݔۀ. ceiling function, the minimum integer not less than x. For example, ڿ7ۀ =

7, ڿ8.3ۀ = 9.

ہݔۂ. floor function, the maximum integer not greater than x. For example, ہ7ۂ =

7, ہ8.3ۂ = 8.

x II y. concatenation of x and y; x and y are bit strings or byte strings.

[x, y]. a set of integers not less than x and not more than y.

β. twist curve parameter.

5 Algorithm parameters and auxiliary functions

5.1 General

This Part specifies an identity-based digital signature algorithm implemented

using elliptic curve pairing. The signer of this algorithm holds an identity and a

corresponding signature private key, which is generated by the key generation

center through the combination of signature master private key and signer's

identity. The signer generates a digital signature of the data with its own

signature private key, and the verifier verifies the reliability of the signature with

the signer's identity.

Before the signature generation and verification process, the message to be

signed M and the message to be verified M’ are compressed by cryptographic

hash function.

5.2 System parameter group

The system parameter group consists of curve identifier cid; parameters of

elliptic curve base field Fq; parameters a and b of elliptic curve equation;

parameter β of twist curve (if the lower 4 bits of cid are 2); prime factor N of

curve order and remaining factor cf relative to N; number of embedding times

of curve E (Fq) relative to N; generator P1 of N order cyclic subgroup G1 of E

(Fqd1) (d1 divides k); generator P2 of N order cyclic subgroup G2 of E (Fqd2) (d2

divides k); identifier eid of bilinear pairing e; homomorphism map ψ of (options)

G2 to G1.

The range of the bilinear pairing e is N order multiplicative cyclic group GT.

For a detailed description of system parameters and their verification, see

7 Digital signature verification algorithm and flow

7.1 Digital signature verification algorithm

In order to verify the received message M' and its digital signature (h', S'), the

user B as the verifier shall implement the following calculation steps.

B1. According to the details given in 6.2.3 of GM/T 0044.1-2016, convert the

data type of h' into integer, and verify whether h' ∈ [1, N - 1] is true, if not,

the verification fails;

B2. According to the details given in 6.2.9 of GM/T 0044.1-2016, convert the

data type of S' into point on the elliptic curve; according to the detail given

in 4.5 of GM/T 0044.1-2016, verify whether S' ∈ G1 is true, if not, the

verification fails;

B3. Calculate element g = e (P1, Ppub-s) in group GT;

B4. Calculate element t = gh' in group GT;

B5. Calculate integer h1 = H1 (IDA II hid, N);

B6. Calculate element P = [h1] P2 + Ppub-s in group G2;

B7. Calculate element u = e (S', P) in group GT;

B8. Calculate element w' = u • t in group GT; and convert the data type of w'

into the bit string according to the details given in 6.2.6 and 6.2.5 of GM/T

0044.1-2016;

B9. Calculate the integer h2 = H2 (M' II w', N), verify if h2 = h' is true, if yes, pass

the verification; otherwise, the verification fails.

7.2 Digital si...

...