易中守恒、信达天下 | 热线:010-68873631 |
Nanxh2001@163.com
(Sep. 2011)
CPK is a combined public key based on identity. It 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 pair. For example, if the sum of private keys is: r = (r1 + r2 + ┄ + rm) mod n. The sum of corresponding public keys will be R = R1 + R2 + ┄ + Rm. Then (r, R) will be a new valid key pair. This is because R = R1 +R2 + ┄ +Rm = r
Combining-Matrix is divided into private matrix and public matrix, and is denoted as (ri,j) and (Ri,j) respectively, r is random number less than n. Matrix (ri,j) is kept only in KDC, and is used to produce private keys. The public matrix (Ri,j) is derived from private matrix (ri,j), and used to compute public key.
ri,j×G=Ri,j.
Public matrix is distributed to every entity and is used to compute public keys.
Identity-key is derived from Combining-matrix A. the size of matrix A is (h1,32). Private matrix and public matrix is denoted as (ri,j) and (Ri,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 = Hashkey(ID) = w0,w1, … ,w32; v0,…, v8; u0,u1
Where w0 is a 6-bit character used to determine the permutation disk(3-bit), and starting point(3-bit), and w1,…,w32 is used to indicate the raw coordinate of matrix A, w is k1-bit character, h1 is the raw length of matrix A and h1=.
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 ti.
The private Identity-key isk is generated in the KMC through the addition on finite field Fn.
iskAlice = .
The public key is computed by relying party through point addition on elliptic curve E
IPKAlice = .
Particular-key is defined by district and generated by Combining-matrix B. The size of matrix B is (h2, 8), and the private and public matrix are denoted as (qi,j) and (Qi,j), respectively. The raw coordinates are indicated by vi in YS sequence.
v0 is a 6-bit character used to determine the permutation disk(3-bit), and starting point(3-bit). The output is denoted as ti (i=1,…,8).
v1,…,v8 is k2-bit character, h2 is the raw length of matrix B and h2=.
The matrix B can provide (h2)8 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.
sskAlice= mod n
The corresponding public key is calculated by individuals
SPKAlice=
General-key is a compound of Identity-key and Separating-key. Private General-key gsk is calculated by KMC for
gskAlice=(iskAlice +sskAlice) mod n=
Private General-key
The corresponding public General-key is calculated by relying party
GPKAlice=IPKAlice+SPKAlice
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 (h3, 2), and the private and public matrix are denoted as (pi,j) and (Pi,j), respectively. The raw coordinates are indicated by ui in YS sequence and the column coordinates are used in natural order.
u1,…,u2 is k3-bit character, h3 is the raw length of matrix C and h3=. The matrix C can provide (h3)2 different Particular-keys.
pskAlice=mod n
The corresponding public key is
PPKAlice=
DPKAlice=GPKAlice+PPKAlicer
The signing function is as follows.
SIGalice(h)=(s, c)
Where
kG = (x1, y1) (1)
c = x12 mod 2m (2)
s=k-1 {h +
Where 2m is used to select the length of checking code, if m=40, then the probability of wrong judgment will only be 1/240, while the sign length will be shortened greatly.
The verification function is as follows.
VERALICE(s)=c’
Where
Bob calculate the public key according to identity.
GPKAlice=IPKAlice+SPKAlice=
Bob verifies the sign according to sign=(s, c)
s-1 h G + s-1 c
c’ = (x1’)2 mod 2m (3)
If c= c’, the sign can be accepted.
The encrypting function is as follows.
ENCBOB(r)=β
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.
GPKBob= IPKBob+SPKBob=BOB (1)
r·BOB=β (2)
r G=(x1, y1) (3)
key = x12 mod 264(or 128) (4)
Ekey (data) = code (5)
The encrypting function is as follows.
DECbob(β)=r
Dkey(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 =(x1, y1) (1)
key = x12 mod 264(or 128) (2)
Dkey (code) = data (3).
CPK-chip provides 32K E2ROM 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 n1, matrix B be n2, the number of known private key be m1, and the number of user be m2, If m1 < (n1+n2), 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 E2ROM. 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 E2ROM 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 +
c = x12 mod 2m (2)
And x1comes from
k G=(x1, y1) (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 x1, and the exhaustion may be available. Let the key length n=192, check code length m=40, then there will be 2192/240=2152 possible results that accord with c.
It will cause 2152 possible k in item (3). Back to item (1), there still is 2152 possible private key
In addition, in this case, the probability of wrong judgment made in verification is only 1/240, 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 = Ekey (data) (2)
And the key comes from
r G = (x1, y1) (3)
key = x12 mod 264 (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 x1 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 2192/264=2128 or 2192/2128=264 possible x1 that accord with the key.
In item (3), one can find 2128 or 264 possible r on the base of the possible keys.
In item (1), one can find 2128or 264 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 |
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.