A.2.3SM2 Public-Key Encryption Algorithm

In December 2010, OSCCA announced the SM2 elliptic curve public-key cryptography algorithm [164], including public-key encryption algorithm, digital signature algorithm and key exchange protocol. The specific description of the SM2 public-key encryption algorithm is as follows:

Supposing elliptic curve E(Fp) over finite field, select the base point G in E(Fp) on the condition that the order of G is a big prime n.

(1) Key Generation. Randomly select integer d ∈ [1, n – 1] and calculate Q = dG. The public-key algorithm is {G, Q}, and the private key is {d}.

(2)Encryption. Let the plaintext message to be encrypted be the bit string M and klen be the bit length of M.

(a)Randomly select k ∈ [1, n – 1] to compute the ciphertext: C1 = kG = (x1, y1), kP = (x2, y2).

(b)Calculate t = KDF(x2||y2, klen), where KDF is the key derivation function with output length equal to klen.

(c)Calculate C2 = Mt, C3 = Hash(x2||M||y2). Here, Hash is the hash function. The final ciphertext is : C = C1||C2||C3.

(3)Decryption. In order to decrypt the ciphertext C = C1||C2||C3, the following steps should be implemented:

(a)Take out the bit string C1 from the C, convert the data type of C1 to the point on the elliptic curve and verify whether it satisfies the elliptic curve equation. If not, report errors and exit.

(b)Calculate dC1 = (x2, y2), and convert the data type of x2 and y2 to bit string.

(c)Calculate t = KDF(x2||y2, klen). If t is the bit string t with all zeros, report errors and exit.

(d)Take out the bit string C2 from the C and calculate M = C2t. Then calculate u = Hash(x2||M||y2) and take out the bit string C3 from the C. If u = C3, M is the plaintext by decryption.

A.3Digital Signature Algorithm

Digital signature is a method of signing the message in electronic form. The digital signature algorithm is that a signer generates the digital signature for data, and a verifier verifies the validity of signature. Every signer has a public key and a private key. The private key is used to generate the digital signature and the verifier takes signer’s public key to verify the signature. A digital signature scheme should have the following basic characteristics:

(1)Unforgeability: Without knowing the signer’s private key, no other person can forge the signature.

(2)Non-repudiation: The signer cannot deny his signature on the message.

(3)Ensurance of the Message’s Integrity: Any change to the message will lead to failure of the signature verification. The characteristic of the digital signature plays an important role in electronic commerce and electronic government system, which makes the digital signature widely popular in application protocols such as electronic payment, bidding, auction, lottery tickets and voting.

Public-key cryptography algorithm can provide a powerful digital signature scheme, without the need for the receiver keeping the verification key in secret. Currently, many digital signature schemes are based on public-key cryptography algorithms. Figure A.3 describes the digital signature scheme using public-key encryption algorithm like RSA.

Figure A.3: Digital signature based on public-key encryption algorithm.

In addition to the RSA digital signature scheme, there are several other digital signature schemes with different functions and types. Here, we introduce two important digital signature schemes: the ISO digital signature standard ECDSA, and the SM2 elliptic curve digital signature of Chinese commercial cryptography algorithm.

A.3.1ECDSA Digital Signature Algorithm

ECDSA digital signature algorithm [165] uses an elliptic curve to simulate digital signature algorithm DSA. ECDSA became ISO standards in 1998, the ANSI standard in 1999, the standard of IEEE and FIPS in 2000.

ECDSA is a variant of ElGamal public-key cryptography algorithm, whose security depends on the discrete logarithm hard problem on elliptic curve. The concrete description of the ECDSA digital signature algorithm is as follows:

Supposing the elliptic curve E(Fp) in finite field, select the basis point G in the E (Fp) with the order of G being a big prime n.

(1)Key Generation. Randomly select the integer d ∈ [1, n – 1], calculate Q = dG. The public key of the algorithm is {G, Q} and the private key is {d}.

(2)Signature. Assuming that the message to be signed is m, execute the following operations:

(a)Randomly select k ∈ [1, n – 1] to calculate kG = (x1, y1).

(b)Calculate r = x1 mod n. If r = 0, return to (a).

(c)Calculate s = k–1 (hash(m)+dr) mod n. If s = 0, return to (a). Here, hash is hash function.

In the end, the signature of the message m is (r, s).

(3)Signature Verification. In order to verify the received message m and its digital signature (rʹ, sʹ), the verifier should perform the following calculations:

(a) Check whether rʹ ∈ [1, n – 1] and sʹ ∈ [1, n – 1]. If not, the signature is invalid.

(b)Calculate e = hash (mʹ); w = sʹ–1 mod n.

(c)Calculate u1 = ewmod n, u2 = rʹw mod n.

(d)Calculate X = u1G + u2Q. If X = O, the signature is invalid. Otherwise, X = (x1,y1)and calculatev = x1mod n.

If v = rʹ mod n, signature is valid.

A.3.2SM2 Digital Signature

In December 2010, OSCCA announced the recommended SM2 elliptic curve public-key cryptography algorithms [164], including public-key encryption algorithm, digital signature algorithm and key exchange protocol. Similar to the ECDSA digital signature algorithm, security of SM2 digital signature algorithm also depends on the discrete logarithm hard problem on elliptic curve group. The detailed description of the SM2 digital signature algorithm is as follows:

Supposing the elliptic curve in finite field is denoted by E(Fp), select the basic point G in the E (Fp) with the order of G being a big prime n.

(1)Key Generation. Randomly select the integer d ∈ [1, n – 1] and calculate Q = dG. The public key of the algorithm is {G, Q} and the private key is {d}.

(2)Signature. Assuming that the message to be signed is m, perform operations as follows:

(a)Set m = Z ||m, where Z is the signer’s identity, a part of system parameters and hash value of signer’s public key.

(b)Calculate e = hash(m). Here, hash is the hash function.

(c)Randomly select k ∈ [1, n – 1] and calculate kG = (x1, y1).

(d)Calculate r = (e + x1)mod n. If r = 0 or r + k = n, return to (c).

(e)Calculate s = ((1 + d) – 1(krd))mod n. If s = 0, return to (c).

In the end, the signature of the message m is (r, s).

(3)Signature Verification. In order to verify the received message mʹ and its digital signature (rʹ, sʹ), the verifier should achieve the following steps:

(a)Check whether rʹ ∈ [1, n – 1] and sʹ ∈ [1, n – 1]. If not, the signature is invalid.

(b)Set m̄ ʹ = Zmʹ.

(c)Calculate eʹ = hash (mʹ) .

(d)Calculate t = (rʹ + sʹ) mod n. If t = 0, the signature is invalid.

(e)Calculates (x1,y1)=sG+tQand v(e+x1)mod n.

If v = rʹ mod n, signature is valid.

A.4Hash Function

The hash function can compress message with arbitrary length to a hash value with fixed length. Hash functions must have the following properties:

(1)One-way. For a given hash value, it is not feasible in calculation to construct an input message to map it to the value.

(2)Collision Resistance. It is not feasible in calculation to construct two different messages and map them to the same hash value.

Hash function can be used to construct block ciphers, stream cipher and message authentication code. It is also an important component of the digital signature. It may break the algebraic structure of input, and do the message source authentication. Besides, it is also used to construct pseudorandom number generator, do the key derivation and so on. It is a formidable task to design a safe and efficient hash function. Many different hash functions have been proposed, but most of them have been confirmed with some vulnerabilities. Common hash functions are: hash functions based on block ciphers algorithm; MD series hash functions, such as MD2, MD4 and MD5, all with a 128-bit output; SHA series hash functions, including SHA1, SHA-224, SHA-256, SHA-384 and SHA-512, designed by the National Security Agency (NSA), which are the US standards. SHA1 iswidely used inmany security protocols, including SSL, PGP, SSH, S/MIME and IPsec. But the security of SHA1 is now seriously challenged by the cryptographers. The last four algorithms are sometimes referred to as SHA-2. The effective attack has not yet appeared on the SHA-2. The National Institute of Standards and Technology (NIST) has formulated new hash function standard algorithm (SHA-3) in the form of public solicitation. This section details the two important hash functions: SHA-256 algorithm [166], and Chinese commercial cipher algorithm SM3 [167].

We will use the following notations:

mod: modular arithmetic

∧: 32 bits and operations

∨: 32 bits or operation

⊕: 32 bits XOR operation

¬: 32 bits not operation

+: mod232 arithmetic addition operation

←: Left to assignment operator

Sn(X): X rotate n bits to right

Ln(X): X rotate n bits to left

Rn(X): X shift n bits to right.

A.4.1SHA-256 Hash Algorithm

For the message mwhose length is l (l < 264), the output length is 256 bits, that is, eight words after padded and iteratively compressed by SHA-256 hash algorithm.

A.4.1.1Message Padding

Assume that length of message m is l bits. First, add bit “1” to the end of the message m, and then add k bits “0” again, where k is the minimum nonnegative integer meeting l + 1+ k ≡ 448 mod 512. Next add a 64-bit string, which is the binary representation of length l. The bit length of the padded message is in multiples of 512, that is, mʹ = m||1||0k||f. Here f is the binary representation of the length l.

A.4.1.2Message Extension

There are n 512-bit message blocks after the message is padded: mʹ = B(0)B(1) . . . B(n–1). Each message block is divided into 16 words with lengths of 32 bits, for example, B(i) = W0W1 ... W15. These 16 message blocks are extended to 64 message blocks W0W1 . . . W63 by the message extension algorithm in the following way:

FOR j = 16 to 63

Wj=σ1(Wj2)+Wj7+σ0(Wj15)+Wj16

ENDFOR

Among them, σ0 (X) = S7 (X) ⊕ S18 (X) ⊕ R3 (X), σ1 (X) = S17 (X) ⊕ S19 (X) ⊕ R10 (X).

A.4.1.3Iterative Compression

For the message mʹ = B(0)B(1) . . . B(n–1), SHA-256 hash algorithm is constructed as follows:

Among them, CF is the compression function, V(0) is a 256-bit initial value. V1(0)=6a09e667,V2(0)=bb67ae85,V3(0)=3c6ef372,V4(0)=a54ff53a,V5(0)=510e527f,V6(0)=9b05688c,V7(0)=1f83d9ab,V8(0)=5be0cd19and the output of SHA-256 hash algorithm is V(n).

Setting A, B, C, D, E, F, G, H as shift registers, the specific calculation process of compression function Vi(i+1i) = CF (V(i), B(i))(0 ≤ in – 1) is described as follows:

(1) First of all, using V(i) give the initial value to the shift registers A, B, C, D, E, F, G, H, that is, AV1(i),BV2i,HV8(i).

(2)Perform computations as follows:

(3)Calculate V(i+1):V1(i+1)A+V1(i),V2(i+1)B+V2(i),,V8(i+1)H+V8(i).Here K0, ⋅⋅ ⋅ , K63 are taken from the first 32 bits of fractional part of the first 64 prime cube roots. The corresponding logic functions are as follows:

Ch(X,Y,Z)=(XY)(XZ);Maj(X,Y,Z)=(XY)(XZ)(YZ);0(X)=S2(X)S13(X)S22(X);1(X)=S6(X)S11(X)S25(X)

A.4.2SM3 Hash Algorithm

In order to meet the application requirements like electronic authentication service system, OSCCA released the SM3 hash algorithm in December 2010, which is used in digital signature and verification, message authentication code generation and verification and random number generation of commercial cryptographic applications. The parameter designs of SM3 and SHA-256 are similar.

For the message m whose length is l(l < 264), after padded and iteratively compressed by SM3 hash algorithm, the output length of m is 256 bits in length, which is eight words.

A.4.2.1 Constants and Functions

Initial vectors are as follows:

IV1 = 7380166f IV2 = 4914b2b9 IV3 = 172442d7 IV4 = da8a0600

IV5 = a96f30bc IV6 = 163138aa IV7 = e38dee4d IV8 = b0fb0e4e

SM3 algorithm uses the following constants:

Tj={79cc45190j157a879d8a16j63.

The SM3 algorithm uses the following Boolean functions:

FFj(X,Y,Z)={XYZ0j15(XY)(XZ)(YZ)16j63,GGj(X,Y,Z)={XYZ0j15(XY)(XZ)16j63

SM3 algorithm uses the following permutation functions:

P0(X)=XL9(X)L17(X),P1(X)=XL15(X)L23(X).

A.4.2.2Message Padding and Message Extension

Message padding algorithm is the same as SHA-256. The length of padded message mʹ is a multiple of 512 bits.

The padded message has n 512-bit message blocks: mʹ = B(0)B(1) ⋅⋅ ⋅ B(n–1). Every message block B(i) = W0W1 . . . W15 is extended from 16 words to 132 words W0,W1,,W67,W0,W1,,W63by the message extension algorithm as follows:

A.4.2.3Iterative Compression

For the message mʹ = B(0)B(1) ⋅⋅ ⋅ B(n–1), the iterative compression process of SM3 algorithm is as follows:

Among them, CF is the compression function, V(0) is the 256-bit initial value IV and V(n) is the output result of SM3 hash algorithm.

Let A, B, C, D, E, F, G, H be word registers, SS1, SS2, TT1, TT2 be intermediate variables, then the specific calculation process of compression function V(i+1) = CF (V(i), B(i))(0 ≤ in – 1) is described as follows:

(1)ABCDEFGHV(i)

(2)FOR j = 0 to 63

(3)V(i+1)ABCDEFGHV(i)

A.5Key Exchange Protocols

In general, the communication participants need to assure confidentiality and authentication of data as transmitting data in the open network environment. To achieve this goal, data must be encrypted and authenticated, which requires using the session key. The key exchange protocol is a process in which two or more parties establish the secret session key in the open network environment. The session key is a parameter of input function generated by the protocol participants.

Usually, key exchange protocol needs to meet the following security properties:

(1)Implicit Key Authentication: The protocol participants can be convinced that no one can get the secret session key except the designated entity.

(2)Key Confirmation: The participants of protocol can determine that the other party has got a specific session key.

(3)Explicit Key Authentication: If the implicit key authentication and key confirmation properties are satisfied simultaneously.

(4)Known Key Security (KKS): The leakage of a session key does not affect the security of the other session keys.

(5)Forward Security (FS): The leakage of the participant’s long-term key does not affect the security of the session key established earlier.

(6)Key Compromise Impersonation Resilience (KCIR): When one side’s long-term private key is compromised, for example, Alice’s, the adversary can explicitly impersonate Alice to communicate with any other side, Bob. However, we would like to guarantee that the adversary cannot impersonate the other side, Bob, to communicate with Alice and so establishes the same session key successfully even in above case.

(7)Unknown Key-Share Resilience (UKSR): Assume adversary Malice makes Alice consider herself to have established a session key K with Bob and Bob establishes the same session key K with Malice. These two sessions should be independent in essence. However, their keys are the same. So, adversary Malice can get K from Bob to break Alice’s session. The protocol that can resist this kind of attack is called UKSR.

In the following section, we introduce two important two-side key exchange protocols: MQV key exchange protocol, and SM2 key exchange protocol.

A.5.1MQV Key Exchange Protocol

MQV protocol was first proposed by Menezes et.al. in 1995 [168]. This protocol is adopted as cryptography standard by many authoritative standard organizations in the world, such as ANSI, IEEE and NIST. MQV is also incorporated into “next-generation cryptography” standard system by NSA for protecting the important and sensitive data whose level is up to national secrets. The concrete description of MQV key exchange protocol is as follows.

A.5.1.1System Settings

Users A and B want to negotiate shared session key K. Let G be a cyclic group whose prime order is q and generator is g. User A randomly selects dA ∈ [1, q – 1] as the private key, and calculates PA=gdAas A’s public key. Similarly, user B randomly selects dB ∈ [1, q – 1] as his private key and calculates PB=gdBas the public key.

A.5.1.2 Key Exchange

User A randomly selects x ∈ [1, q – 1], then calculates X = gx as his own ephemeral public-key value. User B randomly selects y ∈ [1, q – 1], then calculates y ∈ [1, q – 1] as his own ephemeral public-key value. Both the users exchange their identity and ephemeral public-key values, that is, user A sends message (A, B, X) to user B and user B sends message (B, A, Y) to user A.

After receiving the message, A verifies whether Y ≠ 0. If yes, A computes session key K=H((YPBY¯)x+X¯dA).Similarly, B verifies whether X ≠ 0. If yes, B computes session key K=H((YPAY¯)x+X¯dB).Here, X ̄ = 2l + (Xmod2l), Ȳ = 2l + (Ymod2l) and l = |q| /2.

A.5.2SM2 Key Exchange Protocol

In December 2010, OSCCA announced the SM2 elliptic curve public-key cryptography recommended algorithms [164], including public-key encryption algorithm, digital signature algorithm and key exchange protocol. SM2 key exchange protocol is suitable for the key exchange in commercial cryptographic application. This protocol allows both sides in communication to compute and obtain a shared session key jointly through two-time or optional three-time information transfer process.

The system settings for the SM2 key exchange protocol are as follows: Users A and B want to negotiate shared session key K with klen-bit length. Based on the elliptic curve E(Fp) in finite field, select the basic point G with order being a big prime n. User A randomly selects dA ∈ [1, n – 1] as his private key, and calculates PA = dAG as his public key. Similarly, user B randomly selects dB ∈ [1, n – 1] as his private key, and calculates PB = dBG as his public key. In the protocol, Z A and ZB are hash values of user A and user B identities, respectively, and h is the cofactor, h = #E(Fq)/n. Here, #E(Fq) is the order of elliptic curve E(Fq); w = ⌈(⌈log2 n⌉/2)⌉ – 1, among them, ⌈x⌉ is the smallest integer that is greater than or equal to x.

In order to obtain the same session key, both users should achieve the following operations:

(1)User A performs the following operations:

(a)Generate random number rA ∈ [1, n–1], compute R A = rAG = (x1, y1) and send R A to user B.

(b)Compute tA = (dA + x̄1rA) modn, here, x̄1 = 2w + (x1&(2w – 1)).

(2)User B performs the following operations:

(a)Generate random number rB ∈ [1, n–1], compute RB = rBG = (x2, y2) and send RB to user A.

(b)Compute tB = (dB + x̄2rB)modn, here, x̄2 = 2w + (x2&(2w – 1)).

(c) Verify whether R A satisfies elliptic curve equation. If not, the key negotiation fails; otherwise, compute

V=(htB)(PA+x¯1RA)=(xV,yV).

If V is the infinite point, the negotiation fails, otherwise, compute

KB=KDF(xV||yV||ZA||ZB,klen).

Here, KDF(, klen) is the key derivation function whose output length is klen.

(d)Calculate SB = Hash (0x02||yv||Hash(xv||ZA||ZB||x1||y1||x2||y2)); here, Hash(⋅) is the hash function.

(e)Send RB (or SB) to user A.

(3)User A performs the following operations:

(a)Verify whether RB satisfies elliptic curve equation. If not, the key negotiation fails; otherwise, calculate

U=(htA)(PB+x¯2RB)=(xU,yU).

If U is infinite point, the key negotiation fails; otherwise calculate

KA=KDF(xU||yU||ZA||ZB,klen).

(b)Calculate S1 =Hash (0x02||yu||Hash (xu||ZA||ZB||x1||y1||x2||y2)) and check whether S1 = SB. If not, the key confirmation from B to A fails.

(c)Calculate SA =Hash (0x03||yu||Hash (xu||ZA||ZB||x1||y1||x2||y2)) and send SA to user B.

(4)User A performs the following operations:

Calculate S2 = Hash (0x03||yv||Hash (xv||ZA||ZB||x1||y1||x2||y2)) and verify whether S2 = S A. If not, the key confirmation from A to B fails.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.220.136.165