Part One
Basic Theory

CHAPTER ONE
CPK Public Key

CPK is an identity-based public key established on ECC by combination method. CPK can provide signature function and encryption function. The private key can be calculated only by Key Distribution Center, while the public keys can be calculated by every one. The length of signature code is the shortest one as far. The security of CPK is analyzed.

In modern public key systems, the public-key distribution has been a hard problem. In 1984, Shamir put forward for the first time the famous identity-based crypto scheme: IBC. It has been a new direction for the development of public key system. According to “truth logic”, an entity is composed of identity and body, and the “identity” means the unique name of an entity. In 1989, the first identity-based pubic key system was created in China and applied to the defense network, and released in 2003 by the topic of “multi-layered public key” LPK. CPK has been formed a big family, including CPK-RSA, CPK-DLP, CPK-ECC, CPK-CCC(conic curve) and CPK-BLP(bi-linear pair), where in only CPK-ECC has the shortest signature code.

Now we are going to take CPK-ECC as an example to illustrate the working procedure.

1.1 Combining Principle

CPK-ECC is constructed on ECC over field Fp, E: y2 =x3 + ax + b mod p, the parameters are denoted as (a, b, G, n, p), in which a, b is coefficient, a,b,x,y∈Fp, p is prime, G is the base point of the addition group, n is the order of group generated by base point G. Let an arbitrary integer r∈Fn be a private key. Then the point, rG=R, is the corresponding public key. The ECC has a compounding feature: the sum of public keys and the sum of corresponding private keys are still the valid key pairs. For example, if the sum of private keys is

r=(r1 + r2 + … + rm) mod n

and the sum of corresponding public keys will be

R=R1 + R2 + … + Rm

then (r, R) will be a new key pair. This is because

R=R1 +R2 + … +Rm=r1G+r2G+ … +rmG

=(r1 +r2 + … +rm)G=rG

In the same way, if a given integer is less than n, the following formula is established:

r and R are a pair of keys, if k times of r is the new private key s, then the k times of R is the corresponding public key:

k*r=s;　k*R=S

If the private key r plus k is t, then R plus K is the new public-private key pair:

r+k=t;　R+K=T　(K=k*G)

1.2 Combination Matrix

Combining-Matrix is divided into private matrix and public matrix, and is denoted as (ri,j) and (Ri,j) respectively, where r is 32×h random integers less than n including some linear dependent variables. Matrix (ri,j) is kept secret only in KDC, and is used to produce private keys for individual entity. The public matrix (Ri,j) is derived from private matrix (ri,j)

Public matrix is distributed to every entity and used to compute the public key of relying party. However, it is still protected as secret variables in the system to deal with exhausting attack.

1.3 Combination Key

The key management center defines the Hash key Hkey. The given identity (ID) is hashed to YS serial under Hkey:

YS =HashHkeyi (ID)=v0,v1,v2,...,v31;

Row coordinates of the matrix are indicated by vi, and column ordinates are used in natural order. Alice's key pair are combined as

Where alice and ALICE is matrix key pair which will conbined with year key to form the private key and public key respectively.

The last 8 bytes v24, …, v31 Forms a matrix dividing parameters (mdp). It allows different identities to use different levels of matrix.

In matrix dividing transfomation, the keys are multiplied by matrix dividng para mdp. The private key is expressed as:

HashHkey (Alice) → i, j;　∑ (ri, j)=cskAlice *mdp → alice

The public key is expressed as:

HashHkey (Alice)=i, j;　∑ (Ri, j)=CPKAlice * mdp → ALICE

1.4 Annual Key

Annual key is used as backup key. Annual key year2018 and YEAR2018 is defined by the Center. An user's private year key is:

alice2018=alice+year2018 mod n

The YEAR2018 and alice2018 is distributed by the Center.

1.5 Digital Signature

CPK signature protocol is established on the ECDSA, but was revised. The signing function is as follows.

SIGalice(h)=sign=(s, c)

Where alice is private key, h is an object to be signed, such as identity of entity, time of date or Hash code of data, s is signing code, c is checking code.

Alice chooses a random number k (0<k<n) and computes

kG=(x1, y1)

c=(x1+y1)2 mod 2m

s=k-1 {h + alice c} mod n

Where 2m is used to select the length of checking code

Alice sends {s, c}

Bob verifies

VERALICE(h,s)=c'

Bob calculates the public key according to identity:

alice→ALICE

Bob verifies the signature according to sign=(s, c)

s-1 h G + s-1 c ALICE=(x1', y1')

c'=(x1'+y1')2 mod 2m

If c=c', the signature can be accepted.

Here m is fixed at 40 bit, so the length of the sign code s is equal to the length of key and the length of checking code c is fixed at 5 bytes.

1.6 Key Encryption

CPK key delivery protocol is self designed with reference to the published key exchange protocols.

Suppose that Alice sends data to Bob. The encryption function is

ENCBOB(key)=β

Ekey(data)=code

Where ENC means encryption with asymmetric key, BOB is public key, r is a random number, E means encryption with symmetric key.

Alice calculates Bob's public combined-key: Bob→BOB

Alice selects a random number r, and calculates

r BOB=β

r G=(x1, y1)

key=(x1+y1)2 mod 264

Ekey (data)=code

Alice sends {β, code} to Bob.

The decryption function is

DECbob(β)=key

Dkey(code)=data

Where DEC means decryption with asymmetric key, bob is private key, D means decryption with symmetric key.

Bob calculates β with his private key bob provided by CPK system

bob-1 β=bob-1 (r BOB)=r G =(x1, y1)

key=(x1+y1)2 mod 264

Dkey (code)=data

1.7 Security Analysis

1.7.1 Security of Private Matrix

ECC is additive group, and the key combination is realized by addition. Linear operations provide the possibility of linear equations (open problems). But CPK private matrix is composed of integers that is not all linear independent. There will be only limitless solutions, so the private matrix is secure.

1.7.2 Security of Signature Code

The signature code and key encryption code is composed of independent and dependent variables to prevent the possibility of exhaustion attack.

CPK signature code s:

s=k-1 (h+c*sk)

The signature code s is obviously composed of two unknown factors: the random number k and private key sk. k and sk are difficult to decompose.

CPK key encryption code β:

r*G=key

β=ENCBOB(key)=key*BOB

The encrypted key β is composed of a random number and the private key bob hidden in BOB. The random number key and bob forms the independent variable and the dependent variable, which is difficult to decompose.

1.7.3 Security of Public Matrix

The computational complexity of the current public keys is difficult to deal with quantum computing attacks. Therefore, an year key is added in this scheme.

1.7.4 Security of Private Key

This is a problem that is solved by key management. The principle is: whether the CPK is implemented in chip or memory, the private key is always not exposed in the form of primitive code in any time.

Summary

CPK has the characteristics of combination. The combination feature points out a feasible way to turn the general public key into an identity-based public key system adapting to the general demand of the large-scale key management, and also points out a feasible way to deal with exhaustion attack with variable structure and scheme update. The key management must be realized by online automatically. The key updating can reduce the requirement of key length, which can realize shorter signature.