CPK Cryptosystem (Standard)

 

NAN Xiang Hao

Nanxh2001@163.com

(Sep. 2011)

1 Introduction

CPK is a combined public key based on identity. It is constructed on ECC over field Fp, E: y² =x³ + 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 pair. For example, if the sum of private keys is: r = (r₁ + r₂ + ┄ + r_m) mod n. The sum of corresponding public keys will be R = R₁ + R₂ + ┄ + R_m. Then (r, R) will be a new valid key pair. This is because R = R₁ +R₂ + ┄ +R_m = r₁G+r₂G+ ┄ +r_mG = (r₁ +r₂ + ┄ +r_m)G = rG.

Combining-Matrix is divided into private matrix and public matrix, and is denoted as (r_i,j) and (R_i,j) respectively, r is random number less than n. Matrix (r_i,j) is kept only in KDC, and is used to produce private keys. The public matrix (R_i,j) is derived from private matrix (r_i,j), and used to compute public key.

r_i,j×G=R_i,j.

Public matrix is distributed to every entity and is used to compute public keys.

1 Identity-key

    Identity-key is derived from Combining-matrix A. the size of matrix A is (h₁,32). Private matrix and public matrix is denoted as (r_i,j) and (R_i,j) respectively. The mapping from identity to the coordinates of the matrix is implemented through a Hash function under a certain key.

The output is an integer string.

YS = Hash_key(ID) = w₀,w₁, … ,w₃₂; v₀,…, v₈; u_0,u₁

Where w₀ is a 6-bit character used to determine the permutation disk(3-bit), and starting point(3-bit), and w_1,…,w₃₂ is used to indicate the raw coordinate of matrix A, w is k₁-bit character, h₁ is the raw length of matrix A and h₁=.

The first 8 columns of matrix A is not published, and the column coordinates are given by permutation table. The rest 24 column coordinates are used in natural order.

Permutation Table

 (0) (1) (2) (3) (4) (5) (6) (7)

[0]  7  4  2  3  5  1  6  7

[1]  4  6  3  5  0  7  2  3

[2]  6  0  7  6  4  3  7  5

[3]  1  2  6  1  7  0  5  6

[4]  2  7  0  2  3  5  1  0

[5]  0  1  3  7  6  2  4  4

[6]  5  3  1  0  2  4  3  2

[7]  3  5  5  4  1  6  0  1

The column indicates the permutation disk and the row indicates the starting point. For an example, let the number of disk be 3, starting point of disk be 1, the permutation is as follows.                                     

                Input   h g f e d c b a

span style='mso-ignore:vglayout; ;z-index:251657728;left:0px;margin-left:197px;margin-top:3px; width:141px;height:44px'

Permutation Table      3 4 0 7 2 1 6 5

                       0 7 6 5 4 3 2 1

                Output  f e b a g h d c 

The output is the new coordinates of the first 8 column, and the rest 24 columns are denoted as t_i.

The private Identity-key isk is generated in the KMC through the addition on finite field Fn.  Alice’s private key is

isk_Alice = .

The public key is computed by relying party through point addition on elliptic curve E

IPK_Alice = .

2 Separating-key

Particular-key is defined by district and generated by Combining-matrix B. The size of matrix B is (h₂, 8), and the private and public matrix are denoted as (q_i,j) and (Q_i,j), respectively. The raw coordinates are indicated by v_i in YS sequence.

v₀ is a 6-bit character used to determine the permutation disk(3-bit), and starting point(3-bit). The output is denoted as t_i (i=1,…,8).

v₁,…,v₈ is k₂-bit character, h₂ is the raw length of matrix B and h₂=.

The matrix B can provide (h₂)⁸ different Separating-keys. Separating-key can be used repeatedly, i.e., different users can share the same Separating-key. Therefore, the number of Separating-keys can be much less than the number of users.

Alice’s private Separating-key is generated by KMC

ssk_Alice= mod n

The corresponding public key is calculated by individuals

SPK_Alice=

3 General-key

General-key is a compound of Identity-key and Separating-key. Private General-key gsk is calculated by KMC for Alice

gsk_Alice=(isk_Alice +ssk_Alice) mod n=alice.

Private General-key alice is written into ID-card.

The corresponding public General-key is calculated by relying party

GPK_Alice=IPK_Alice+SPK_Alice

4 District-key (Option)

If a closed district network has the need to connect with outside, then users must have the General-key and District-key at the same time.

Particular-key is defined by district and generated by Combining-matrix C. The size of matrix C is (h₃, 2), and the private and public matrix are denoted as (p_i,j) and (P_i,j), respectively. The raw coordinates are indicated by u_i in YS sequence and the column coordinates are used in natural order.

u_1,…,u₂ is k₃-bit character, h₃ is the raw length of matrix C and h₃=. The matrix C can provide (h₃)² different Particular-keys.

Alice’s private Particular-key is

psk_Alice＝mod n

The corresponding public key is

PPK_Alice＝ 

Alice’s public District-key is the compound of General-key and, Particular-key.

DPK_Alice=GPK_Alice+PPK_Alicer

5 Digital Signature

The signing function is as follows.

SIG_alice(h)=(s, c)

Where alice is private key, h is hash code, s is signing code, c is checking code.

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

kG = (x₁, y₁)                    (1)

c = x₁² mod 2^m                  (2)

s=k^-1 {h + alice c} mod n           (3)

Where 2^m is used to select the length of checking code, if m=40, then the probability of wrong judgment will only be 1/2⁴⁰, while the sign length will be shortened greatly. 

The verification function is as follows.

VER_ALICE(s)=c’

Where ALICE is public key.

Bob calculate the public key according to identity.

GPK_Alice=IPK_Alice+SPK_Alice=ALICE        (1)

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

s^-1 h G + s^-1 c ALICE = (x₁’, y₁’)          (2)

c’ = (x₁’)² mod 2^m                   (3)

If c= c’, the sign can be accepted.

6 Key Delivery

The encrypting function is as follows.

ENC_BOB(r)=β

E_key(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 General-key

GPK_Bob= IPK_Bob+SPK_Bob=BOB            (1)

Alice selects a random number r, and calculates

r·BOB=β                            (2)

r G=(x₁, y₁)                          (3)

key = x₁² mod 2^{64(or 128)}                  (4)

E_key (data) = code                      (5)

Alice sends {β , code} to Bob.

The encrypting function is as follows.

DEC_bob(β)=r

D_key(code)=data

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

Bob calculates β with his privat key bob in the ID-card

bob^-1 β = bob^-1 (r BOB)= r G =(x₁, y₁)        (1)

key = x₁² mod ^{264(or 128)}                  (2) 

D_key (code) = data                      (3).

7 Security

CPK-chip provides 32K E²ROM for the security of key variables. The security is related to two main aspects: the security of system keys and the security of individual keys.

1. The Security of System Keys

Let the dimension of matrix A be n₁, matrix B be n₂, the number of known private key be m₁, and the number of user be m₂, If m₁ < (n₁+n₂), then the system keys will be secure. However, following measures must be added to assure the security.

1) It will be hard to obtain the private keys. The private key in ID-card is protected by E²ROM. It cannot be read from outside, and will be disappeared automatically when someone attempts to anatomize the chip.  

2) It will be hard to describe the equations. The mapping procedure is kept private so that the linear equation can not be described.

3) It will be hard to solve the equations. The false cards will be used normally in the system, which will result in no solution for the equation.

2. The Security of Individual Keys

Whole or parts of public Combining-matrix are kept secret in E²ROM of ID-card. The public key generating procedure and public keys are not exposed to outside. The works with private key such as signature and decryption must be done inside the chip, and the private key can never be exposed. In the same way, the works with public key such as verification and encryption can be done inside the chip, and the public key can never be exposed. Individual keys are mainly used in signature function and key delivery function. If the functions are secure, then the individual keys are secure, too.

1) Individual keys in the signature function

Only Hash code h, sign code s and check code c are open factors in the process of signature function, where

s = k^-1 (h + alice c) mod n     (1)

c = x₁² mod 2^m             (2)

And x₁comes from

k G=(x₁, y₁)                (3)

In the item (1), there are two unknown factors included, the random number k and private key alice, and they can not be separated form each other. Therefore there is no unique solution.

In the item (2), there is only one unknown factor x₁, and the exhaustion may be available. Let the key length n=192, check code length m=40, then there will be 2¹⁹²/2⁴⁰=2¹⁵² possible results that accord with c.

It will cause 2¹⁵² possible k in item (3). Back to item (1), there still is 2¹⁵² possible private key alice. Therefore, the private key is secure.

In addition, in this case, the probability of wrong judgment made in verification is only 1/2⁴⁰, but it will greatly shorten the length of sign code (shortened to 32 Byte from 48 Byte).

2) Individual keys in key the key delivery function

In the process of key delivery function, only the factors {β, code} are exposed, where

β = r BOB                         (1)

code = E_key (data)                   (2)

And the key comes from

r G = (x₁, y₁)                       (3)

key = x₁² mod 2^{64 (or128)}                (4)

In item (1), s is a product of random number r and public key BOB.

β = r BOB = r bob G = v G

Because v is a product of two factors, they can not be separated from each other.

In item (2), the key can be exhausted if the decrypted data provides distinguishing base. In this case, the key is a known factor. How to make the decrypted data not to be a distinguishing base is of another topic, and beyond the scope of this paper.

In item (4), if key is known, then x₁ can be exhausted. Suppose that ECC modular n is 192-bit, the key length of bloc cipher is 64 or 128-bit, then there will be 2¹⁹²/2⁶⁴=2¹²⁸ or 2¹⁹²/2¹²⁸=2⁶⁴ possible x₁ that accord with the key.

In item (3), one can find 2¹²⁸ or 2⁶⁴ possible r on the base of the possible keys.

In item (1), one can find 2¹²⁸or 2⁶⁴ possible public key BOB on the base of the possible r. Therefore, the public key BOB is secure.

In view of this, it is suggested that the width of bloc cipher could not be too wide, because a long data can provide a more high level of distinguishing base.

In CPK functional module, the input and output elements are as follows.

Functional module	Input	Output
Signing module	M	(s, c)
Verifying module	ID, s	c’
Encrypting module	ID，data	β, code
Decrypting module	β，code	data

Summary

CPK is an Identity-based cryptosystem. It integrates the key generation and distribution, and greatly reduces the complexity of the key management. The security of system key is ensured by a large group of main keys. It can be used in signature and authentication, encryption and decryption without any outside support.

Quantum computation makes the exhaustion search possible that was impossible in the past. The main way to cope with quantum computation is to make the exhausting search meaningless. If an equation has no distinguishing base, then the exhaustion turns to be meaningless. In such a case, it is nothing to do with the computing speed. In the existing ECC equation, aG=A, once the public key A is open, the private key a can be exhausted, because the public key A provides the distinguishing basis. Therefore, the public key must be kept secret. Under existing public key system, only the identity-based key system has the capacity to keep the public keys secret.

 

View original