Two-factor combined public key generation and authentication method

<u>Field of Invention</u>

0001The present invention relates to public key crypto-system and authentication field. Especially, the present invention relates to public key crypto-system and authentication system that is combined by identity key and random key, uses two public keys composed of identity and random public key as exterior public key, and has multiple public/private key pairs and a plurality of combined structures.

<u>Background of the Invention</u>

0002Since the birth of public key cryptosystem, there have been two types of authentication systems: one is certificate-based authentication system, and the other one is identity-based authentication system.

00031) Certificate-based authentication system

0004In the conventional public key crypto-system, the relationship between public key and private key is:

0005Public key = F (Private key)

0006F is an one-way function. It is easy to calculate the public key from the user key (i.e., private key). However, it is a puzzle to calculate the private key from the public key. The bonding of public key and user identity needs proof by the certificate issued by the key management authority. The certificate authentication system needs calculation of many sections such as certificate issuance, verification, abolition, updating, and support and consumption of communication resources, and thus it is hard to match the large-scale network demand (e.g., the network with entity number of 10⁹)_.

00072) Identity-based authentication system

0008Identity-based authentication system uses a user identity as a public key or generates a public key with a user identity, to integrate the identity with the public key; while the private key is generated by the key management authority who uses its controlled master key with the user identity as an independent variable. In the identity-based public key crypto-system, the relationship between the public key and the private key is:

0009Private key = F (master key, user identity)

0010In the identity-based public key crypto-system, the user identity integral with the public key is an independent variable in the functional relation. Under the control of the master key of the key management center, upon the user identity is given, the private key is uniquely determined. It is a puzzle for an attacker who has no control of the master key to try to obtain the private key from the user identity (public key). In 1999, NAN, Xianghao, a Chinese scholar proposed an identity-based combined public key system (called CPK), in which a method of selecting and combining elements of seed key matrix is used to generate an identity-based key. This is a new member of the identity-based public key crypto-system family.

0011In a typical identity-based public key crypto-system, entity private keys are all generated by the key management center based on identities and the master key. The entity does not have absolute private right or privacy. However, in an identity-based combined public key system, the private key is not a linear sum of the seed private keys, and theoretically there is a possibility for the private key to be collusively attacked, so as to affect the security of the system and application of scalability.

<u>Summary of the Invention</u>

0012The present invention provides a two-factor combined public key system and authentication system combined by identity key and random key. The identity key is generated by selecting and combining a seed key set with a number-sequence generated from a user identity. The random key is generated based on one-way function principle relied by typical public key crypto-system. The exterior public key adopts two-public-key form of identity plus random public key, and the interior key has a number of various combined structures of multiple key pairs, each of which belongs to multiple combined modes of multiple key pairs of random key and identity key. This not only can satisfy the demand of centralized management, but also can entrust the user with absolute privacy to the private key. The authentication system based on this key generation method has the advantages that identity authentication does not need a third party certificate proof and the random private key of the typical public key crypto-system is highly randomized and private. The system can be widely used in authentication of various scale (especially super-large scale) open systems, to satisfy the authentication demand in the fields including trusted connecting, trusted loading, e-bank, trusted transaction, and trusted logistics.

0013According to the present invention, the functional relation between the public key and the private key in the identity key is the public key/private key relationship of the identity-based pubic key crypto-system:

Private key = F (seed private key set, user identity)

0014The relation between public key and private key in self-defined random key follows the functional relation of conventional public key crypto-system:

0015Public key = F (private key)

0016Thus, the key of two-factor public key crypto-system combines two types of public key/private key relation of identity-based public key crypto-system and conventional public key crypto-system, and is a new public key crypto-system characterized by dual exterior public keys and multiple interior key pairs and their combined modes after the certificate-based authentication system and identity-based authentication system. The two-factor public key crypto-system keeps the respective advantages of the two public key crypto-systems, and overcomes the respective disadvantages of the two.

0017According to the present invention, the key management center registers and approves the identities and generates the seed key set, and publishes the seed public key set for individual entity to calculate the identity public key. The calculation process of the identity public key provides integrity proof for the identity and identity public key. Thus, there is no need for proof of third party certificate.

0018According to the present invention, the key management center can bond and publish the entity identity and the random public key defined by the center (i.e., first-order random public key) for using by the encrypting party or verifier.

0019According to the present invention, the individual entity is allowed to self-define the random key and add the random public key (RaPK _(USER)) to the random public key defined by the key management center, to generate a second-order random public key which is published for using by encrypting party or verifier.

0020According to the present invention, individual entity is allowed to conduct real time self-definition of new random key to update the random key and add the new random public key (RaPK '_(USER)) to the (n-1)_th-order (n≧3) random public key, to generate a n_th-order random public key, which is published for using by encrypting party or verifier.

0021According to a preferred embodiment of the present invention, when performing digital signature, the random public key shall be sent to the verifier as a part of the signature code.

0022According to a preferred embodiment of the present invention, the verifier and encrypting party first uses the other party's identity and the published seed public key set to calculate the identity public key (IdPK), and adds it to the random public key (RaPK) published or provided by the signer to calculate the public key (PK).

0023According to the present invention, a two-factor combined public key generation and authentication method is provided, comprising the following steps:

0024Step 1: generating an identity key including an identity public key and an identity private key;

0025Step 2: generating a random key including a random public key and a random private key;

0026Step 3: the key management center (KMC) combining the identity key and the self-defined random key to generate a first-order two-factor key;

0027Step 4: the user combining the first-order two-factor key and the self-defined random key to generate a second-order two-factor key;

0028Step 5: the user combining the (n-1)_th-order two-factor key (n≧3) and the self-defined updating random key to generate a n_th-order two-factor key;

0029Step 6: the verifier or encrypting party, by combining the identity public key calculated from the other party's identity and the random public key provided in the other party's signature or published by the management center, to obtain the user's public key.

0030According to a preferred embodiment of the present invention, Step 1 includes:

0031a) the key management center checks and approves the identity submitted by a user, to ensure its authenticity and uniqueness;

0032b) the key management center defines and generates seed private key set (seedSK) and seed public key set (seedPK) corresponding to each other;

0033c) the user identity is used as input of a hash function, to calculate hash value H (ID) of the identity;

0034d) the key management center constructs and selects number sequence with the H (ID), selecting from the seed private key set and generating a user identity private key (IdSK) with combination operation;

0035e) the encrypting party or verifier constructs and selects number sequence with the H (ID), selecting from the seed public key set and generating a user identity public key (IdPK) with combination operation.

0036According to a preferred embodiment of the present invention, in Step b), the seed key set (seedSK and seedPK) can be constructed in the different form of matrix, sequence, etc.

0037According to a preferred embodiment of the present invention, the construction form and scale of the seed key set is determined based on the actual needs of the system.

0038According to a preferred embodiment of the present invention, the seed public key set is published to the public, and the seed private key set is kept by the center in confidential.

0039According to a preferred embodiment of the present invention, Step 2 includes:

0040f) the key management center uses a random number generator to randomly generate a positive integer of modulo n as a random private key (RaSK _(KMC)) defined by the center, and generates a random public key (RaPK _(KMC)) defined by the center through scalar multiplication operation of elliptic curve group.

0041g) the user uses the random number generator to generate a positive integer of modulo n as a random private key (RaSK _(USER)) self-defined by the user, and generates a random public key (RaPK _(USER)) self-defined by the user through scalar multiplication operation of elliptic curve group.

0042According to a preferred embodiment of the present invention, Step 3 includes:

0043h) the key management center adds the user identity private key (IdSK) with the random private key (RaSK_(KMC)) randomly generated by the center, to generate a first-order private key (SK₁);

0044i) the key management center writes SK₁ and RaPK _(KMC) into a chip to provide to the user who owns the identity;

0045j) the identity and random public key RaPK_(KMC) are sent out by the user or published by the key management center;

0046k) the encrypting party or verifier uses the user identity to generate an identity public key (IdPK), and adds it with RaPK_(KMC) being published or sent, to generate a first-order public key (PK₁).

0047According to a preferred embodiment of the present invention, Step 4 includes:

00481) the user uses a random number generator to generate RaSK_(USER), and generates RaPK_(USER) through scalar multiplication operation of elliptic curve group;

0049m) the user adds SK₁ with RaSK_(USER) to generate a second-order private key (SK₂);

0050n) the user adds RaPK(_USER) with RaPK_(KMC) to generate a second-order random public key (R_aPK₂);

0051o) the user writes SK₂ and R_aPK₂ into a chip, and deletes SK₁ and RaPK _(KMC);

0052p) the identity and R_aPK₂ are sent out by the user or published by the key management center;

0053q) The encrypting party or verifier generates IdPK by using the user identity, and adds it with R_aPK₂ being published/sent out, to obtain a second-order public key (PK₂).

0054According to a preferred embodiment of the present invention, Step 5 includes:

0055r) the user using a (n-1)_th-order combined key as an initial state, to generate n_th-order combined key, wherein n≧3;

0056s) When updating the key pair, the user using a random number generator to generate RaSK_(USER), and generating RaPK_(USER) through scalar multiplication operation of elliptic curve group;

0057t) adding (n-1)_th-order private key (SK_n-1) stored in the original chip with RASK_(USER) newly defined, to generate n_th-order private key (SK_n);

0058u) accumulating (n-1)_th-order random public key (RaPK_n-1) stored in the original chip and R_aSK_(USER) newly defined, to obtain n_th-order random public key (RaPK_n);

0059v) the user writing SK_n and RaPK_n into a chip, and deleting SK_n-1 and RaPK_n-1;

0060w) the identity and random public key (RaPK_n) are sent out by the user or published by the key management center, including that the user provides the identity and random key to verifier through digital signature, and the user submits the identity and random key to the key management center for publication.

0061According to a preferred embodiment of the present invention, Step 6 includes:

0062x) the encrypting party or verifier using the other party's user identity and the published seed public key set to calculate identity public key (IdPK) of the user;

0063y) adding the identity public key (IdPK) of the user with the random public key (RaPK) being sent or published, to obtain a public key (PK) of the user.

0064According to a preferred embodiment of the present invention, the two-factor combined key is composed of combining multiple public key/private key pair that respectively belongs to identity key and random key.

0065According to a preferred embodiment of the present invention, the key defined by the key management center is a first-order two-factor key; and the key that adds the user defined random key on the basis of the first-order or (n-1)_th-order two-factor key is a second-order or n_th-order (n≧3) two-factor key.

0066According to a preferred embodiment of the present invention, the first-order public key (PK₁) = IdPK+ RaPK _(KMC) = IdPK+ RaPK₁, wherein RaPK₁ indicates that the random public key is only constructed by one random public key;

0067The second-order public key (PK₂) = IdPK+ RaPK _(KMC)+ RaPK _(USER) = IdPK+ RaPK₂, wherein RaPK₂ indicates that the random public key is constructed by adding up two random public keys;

0068The n_th-order public key (PK_n) =IdPK+ RaPK_n, wherein n≧3, RaPK_n indicates that the random public key is constructed by adding up n random public keys;

0069According to a preferred embodiment of the present invention, the user is allowed to change the self-defined random public/private key pair at any time as desired, and to generate new public/private key pair.

0070According to a preferred embodiment of the present invention, the user adds the self-defined random private key with the combined private key stored in the chip, to obtain a combined private key of that order; and adds the self-defined random public key with the random public key stored in the chip, to obtain a random public key of that order; in which the chip shall include the user identity (ID), the private key of that order and the random public key of that order therein.

0071According to a preferred embodiment of the present invention, when using private key (SK₁, SK₂, or SK_n) to sign, the random public key (RaPK_(KMC), RaPK₂ or RaPK_n) is also sent to the relying party as a part of the signature code.

0072According to a preferred embodiment of the present invention, when verifying the signature, the verifier first uses the published user identity and seed public key set to calculate identity public key (IdPK), and adds it with the random public key RaPK published or sent by the signer, to calculate the other party's public key (PK), for verifying authenticity of the signature.

0073In view of above, the present invention has the following advantages:

00741) The present invention uses the identity and random public key as exterior public key, and the interior key uses multiple public/private key pairs that respectively belong to identity key and random key. The multi-level overlaying structure of multiple combination modes applies to various authentication needs of various scale network systems.

00752) The authentication system constructed according to the present invention uses the identity key as a component part of the combined key, and thus bonding of the user identity and public/private key pairs does not need the third party certificate proof. The system can support ultra-large scale public network authentication, is simple in structure, and is convenient and economic for management, maintenance and running.

00763) Encryption of the self-defined random private key to the identity private key can not only make the possibility of generating huge number of useful keys with small amount of seed keys combination under secure condition to become true, but also can be independent of the seed key set scale to maximize the key space, so that the system becomes an actual means to solve the authentication puzzle under large scale network circumstance.

00774) In the present invention, the user self-defined random key allows the user to have absolute privacy to the private key. Except for the user, anyone including the key management center cannot infringe the user's privacy.

00785) The self-defined random key gives the key structure great flexibility, which can be used by KMC to generate RaSK _(KMC) to construct a first-order private key and random public key; which can be used by the user to generate RaSK _(USER) to construct a second-order private key and random public key; and which can be used by the user to repeatedly generate RaSK' _(USER) to construct higher-order private key and random public key. Different application circumstances can choose different application modes of self-defined random key.

00796) With the self-defined random key, the key can be completely randomized, and the useful key space can be maximized, which provides a scientific calculation possibility for key collision probability, so as to provide reliable basis for determining user scale.

0080The objects and other advantages of the present invention can be realized and obtained with the specific structures in the following specification, claims, and drawings.

<u>Brief Description of the Drawings</u>

0081In order to make the objects, technical solutions and advantages of the present invention more clear, detailed description in connection with the drawings will be made to the present invention, in which:

0082∑ ++ ++ represents elliptic curve point operation;

0083∑ + + represents modulo-n integer operation;

0084.G represents scalar multiplication of elliptic curve group;

0085<img file="EP2285040A1_D0001.tif" /> represents confidential part;

0086<img file="EP2285040A1_D0002.tif" /> represents public part;

0087<figref idref="f0001">Fig. 1</figref> shows a first-order two-factor private key and random public key generation mode according to the present invention;

0088<figref idref="f0001">Fig. 2</figref> shows a second-order two-factor private key and random public key generation mode according to the present invention;

0089<figref idref="f0002">Fig. 3</figref> shows a higher-order two-factor private key and random public key generation mode according to the present invention;

0090<figref idref="f0002">Fig. 4</figref> is a schematic view of generating public key based on identity and random public key according to the present invention;

0091<figref idref="f0003">Fig. 5</figref> is a functional block diagram of the key management center according to the present invention;

0092<figref idref="f0004">Fig. 6</figref> is a functional diagram of the authentication chip according to the present invention;

0093<figref idref="f0005">Fig. 7</figref> shows a generation process of the anti-forgery electronic tag according to the present invention; and

0094<figref idref="f0005">Fig. 8</figref> shows a verification process of the anti-forgery electronic tag according to the present invention.

<u>Detailed Description of the Preferred Embodiment</u>

0095The two-factor combined public key system (TF-CPK) of the present invention uses identity plus random public key as the exterior public key, while the interior adopts multi-level overlaying key structure of the public/private key pairs with two types of keys (identity key and random key) and the multiple combination modes. The system involves: basis of cryptography, rule of key combination, random number, identity, hashing function, seed key, etc.. This invention uses elliptic curve crypto-system (ECC) as the basis of the system construction. Below is detailed description to the principle of key generation method and implementation according to the present invention. It shall be noted that the embodiments of the two-factor combined public key technology and identity authentication system of the present invention are only for examples, and the present invention shall not be limited to the embodiments.

00961. Several elements of two-factor combined public key crypto-system

0097The elements of this crypto-system includes: elliptic curve group, point multiplication and discrete logarithm, rule of key combination, random number generator, user identity, hashing function, seed key, etc.

00981.1 Elliptic curve group

0099The discrete logarithm puzzle of elliptic curve is the mathematical basis of the security of this crypto-system. The selected elliptic curve group is defined in quintuple (a, b, G, n, p):

0100p: is a big prime number, and the elliptic curve is established on a finite field of mod P;

0101a, b: defining cubic equation y²=x³+ax+b (mod P);

0102G: is a basic point, all the point multiplication of which constitute the elliptic curve group;

0103n: is a big prime number, and is an order of the elliptic curve group generated by the basic point G;

01041.2 Point multiplication and discrete logarithm

0105(a, b, G, n, p) is the solution of cubic equation defined by a and b, and an additive group composed of points of infinity. The elements in the group are integer pair (x, y) that satisfies the equation y²=x³+ax+b (mod P) and a point of infinity (marked as O).

0106The additive operation rule of elements P and Q of the additive group is:

01071) <maths id="math0001"><math display="block"><mi mathvariant="normal">P</mi><mo mathvariant="normal">+</mo><mi mathvariant="normal">O</mi><mo mathvariant="normal">=</mo><mi mathvariant="normal">P</mi><mo mathvariant="normal">;</mo></math><img file="EP2285040A1_D0003.tif" /></maths>

01082) If point P=(x, y), Q=(x, -y), then P+Q=O.

01093) If P=(x₁, y₁), Q=(x₂, y₂), and P≠-Q, then the value calculation rule of P+Q=(x₃, y₃) is:

0110<maths id="math0002"><math display="block"><msub><mi mathvariant="normal">x</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">≡</mo><msup><mi mathvariant="normal">λ</mi><mn mathvariant="normal">2</mn></msup><mo mathvariant="normal">-</mo><msub><mi mathvariant="normal">x</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msub><mi mathvariant="normal">x</mi><mn mathvariant="normal">2</mn></msub><mspace width="1em" /><mi>mod p</mi></math><img file="EP2285040A1_D0004.tif" /></maths>

0111<maths id="math0003"><math display="block"><msub><mi mathvariant="normal">y</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">≡</mo><mi mathvariant="normal">λ</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">x</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">-</mo><msub><mi mathvariant="normal">x</mi><mn mathvariant="normal">3</mn></msub></mfenced><mo mathvariant="normal">-</mo><msub><mi mathvariant="normal">y</mi><mn mathvariant="normal">1</mn></msub><mspace width="1em" /><mi>mod p</mi></math><img file="EP2285040A1_D0005.tif" /></maths> dans la formule mettre un 3 en indice après y

0112wherein: <maths id="math0004"><math display="block"><mrow><mo>{</mo><mtable><mtr><mtd><mspace width="1em" /></mtd><mtd><mfrac><mrow><msub><mi mathvariant="italic">y</mi><mn>2</mn></msub><mo>-</mo><msub><mi mathvariant="italic">y</mi><mn>1</mn></msub></mrow><mrow><msub><mi>x</mi><mn>2</mn></msub><mo>-</mo><msub><mi>x</mi><mn>1</mn></msub></mrow></mfrac></mtd><mtd><mi>if P</mi><mo>≠</mo><mi mathvariant="normal">Q</mi></mtd></mtr><mtr><mtd><mi mathvariant="normal">λ</mi><mo>=</mo></mtd><mtd><mspace width="1em" /></mtd><mtd><mspace width="1em" /></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mfrac><mtable><mtr><mtd><mn>3</mn><mo>⁢</mo><msup><msub><mi>x</mi><mn>1</mn></msub><mn>3</mn></msup><mo>+</mo><mi mathvariant="normal">a</mi></mtd></mtr></mtable><mrow><mn>2</mn><mo>⁢</mo><msub><mi>y</mi><mn>1</mn></msub></mrow></mfrac></mtd><mtd><mi>if P</mi><mo>=</mo><mi mathvariant="normal">Q</mi></mtd></mtr></mtable></mrow></math><img file="EP2285040A1_D0006.tif" /></maths>

0113The addition of P≠Q is called point addition operation; and the operation of P=Q is called point multiplication operation.

0114The point of n_a times G is marked as n_a.G. G generates elements n_a.G (n_a=1, 2, •••, n) in the additive group with point multiplication operation and point additive operation. n_a is the discrete logarithm of n_a.G. Given n_a and G to obtain n_a.G is called scalar multiplication, which is easy to calculate. However, with G and n_a.G to obtain n_a is a discrete logarithm puzzle of elliptic curve. In the elliptic curve crypto-system, (n_a.G, n_a) constitutes public key and private key pair, i.e., in which point multiplication n_a.G is the public key, and discrete logarithm n_a is the private key.

01151.3 Rule of key combination

0116Rule of key combination of the elliptic curve crypto-system is an important cryptographic property of the elliptic curve group.

0117Rule of key combination: if (n₁.G, n₁) and (n₂.G, n₂) are two sets of public key/private key pairs, then the sum of their public keys <maths id="math0005"><math display="block"><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">3</mn></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">1</mn></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">2</mn></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mspace width="1em" /><mfenced><mi>elliptic curve group operation</mi></mfenced></math><img file="EP2285040A1_D0007.tif" /></maths>

0118and the sum of their private keys <maths id="math0006"><math display="block"><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">3</mn></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">2</mn></msub><mspace width="2em" /><mfenced><mi>mod n integer addition</mi></mfenced></math><img file="EP2285040A1_D0008.tif" /></maths>

0119constitute combined public key/private key pair (n₃.G, n₃).

0120The more common expression of rule of key combination is: if (n₁.G, n₁), (n₂.G, n₂), •••, (n_t.G, n_t) are public key/private key pairs of the elliptic curve, then the sum of their public keys <maths id="math0007"><math display="block"><mi mathvariant="normal">P</mi><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">1</mn></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">2</mn></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mo mathvariant="normal">+</mo><mo>⋯</mo><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">n</mi><mi mathvariant="normal">t</mi></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mfenced><mi>elliptic curve group operation</mi></mfenced></math><img file="EP2285040A1_D0009.tif" /></maths>

0121and the sum of their private keys <maths id="math0008"><math display="block"><mi mathvariant="normal">S</mi><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">1</mn></msub><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">n</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">+</mo><mo>⋯</mo><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">n</mi><mi mathvariant="normal">t</mi></msub><mfenced><mi>mod n integer addition</mi></mfenced></math><img file="EP2285040A1_D0010.tif" /></maths> constitute combined public key/private key pair (P, S).

01221.4 random number generator

0123The private key in the self-defined random key pair is a random number RN. RN is generated by a random number generator RNG, to avoid the negative impact resulted from habits and inertia. The random number generated by the random number generator shall be properly selected (e.g., the random number shall not have very small value), so as to apply to the key. The key management center generates different random numbers through the RNG as the random keys for encrypting the identity private key; and the user generates self-defined random keys through the RNG to exclusively own the private key and update the private key at any time.

01241.5 user identity

0125User identity (ID) is constituted of exclusive properties such as name, address of an entity. The user identity shall be registered and approved by the key management center (KMC), to have authenticity and uniqueness.

0126Hashing function

0127Hashing function recommended by the international standard is adopted. It uses the user identity with various lengths as the input, to output equal length of bit strings, for generating selected number sequence.

0128Assuming that the selected number sequence is constructed of u-bit binary numbers with the number of v, then the output length of the hashing function is defined as v×u, i.e., H (ID)=(a₀, a₁, ••• a_vu-1).

0129The output number sequence is: w₀, w₁, •••, W_v-1<maths id="math0009"><math display="block"><msub><mi mathvariant="normal">w</mi><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">=</mo><msub><mi mathvariant="normal">a</mi><mi>iu</mi></msub><mo mathvariant="normal">×</mo><msup><mn mathvariant="normal">2</mn><mrow><mi mathvariant="normal">u</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">a</mi><mrow><mi>iu</mi><mo mathvariant="normal">+</mo><mn mathvariant="normal">1</mn></mrow></msub><mspace width="1em" /><mi mathvariant="normal">x</mi><mspace width="1em" /><msup><mn mathvariant="normal">2</mn><mrow><mi mathvariant="normal">u</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">2</mn></mrow></msup><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">a</mi><mrow><mi>iu</mi><mo mathvariant="normal">+</mo><mn mathvariant="normal">2</mn></mrow></msub><mo mathvariant="normal">×</mo><msup><mn mathvariant="normal">2</mn><mrow><mi mathvariant="normal">u</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">3</mn></mrow></msup><mo mathvariant="normal">+</mo><mo mathvariant="normal">…</mo><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">a</mi><mrow><mi>iu</mi><mo mathvariant="normal">+</mo><mi mathvariant="normal">u</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo mathvariant="normal">×</mo><msup><mn mathvariant="normal">2</mn><mn mathvariant="normal">0</mn></msup><mo mathvariant="normal">,</mo><mspace width="1em" /><mi mathvariant="normal">i</mi><mo mathvariant="normal">=</mo><mn mathvariant="normal">0</mn><mo mathvariant="normal">,</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">,</mo><mo mathvariant="normal">…</mo><mo mathvariant="normal">,</mo><mi mathvariant="normal">v</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></math><img file="EP2285040A1_D0011.tif" /></maths>

0130The simplified form of the above formula is<maths id="math0010"><img file="EP2285040A1_D0012.tif" /></maths>

01311.7 Seed key sequence

01322^u×v key pairs (P₀, S₀), (P₁, S₁), •••, (P ₂^u_xv-1, S₂^u_×v-1) are selected from the keys pace, to construct a seed key set, including a seed public key set (P₀, P₁, •••, P ₂^u_×v-1) and a seed private key set (So, S₁, •••, S ₂^u×_v-1).

01332. Key construction of the two-factor combined public key crypto-system

0134The keys include:

0135self-defined random key pair (R_aPK, P_aSK);

0136identity key pair (IdPK, IdSK);

0137seed key pair (P, S);

0138combined key pair (PK, SK).

01392.1 Self-defined random key

0140The self-defined random key is a public key/private key pair (R_aPK, P_aSK) composed of random public key R_aPK and random private key P_aSK.

0141The random private key is a random number RN generated by the random number generator, i.e. P_aSK=RN.

0142The random public key is obtained from scalar multiplication operation with RN as the multiples of the basic point, i.e., R_aPK=RN.G (scalar multiplication of elliptic curve group).

0143The self-defined random key comprises (R_aPK_(KMC), P_aSK_(KMC)) generated by the key management center (KMC) and (R_aPK_(USER), P_aSK_(USER)) generated by the user (USER). <maths id="math0011"><math display="block"><msub><mi mathvariant="normal">R</mi><mi mathvariant="normal">a</mi></msub><mo>⁢</mo><msub><mi>PK</mi><mfenced><mi>KMC</mi></mfenced></msub><mo mathvariant="normal">=</mo><msub><mi>RN</mi><mfenced><mi>KMC</mi></mfenced></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mspace width="2em" /><mfenced><mi>scalar multiplication of elliptic curve group</mi></mfenced></math><img file="EP2285040A1_D0013.tif" /></maths><maths id="math0012"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi mathvariant="normal">R</mi><mi mathvariant="normal">a</mi></msub><mo>⁢</mo><msub><mi>SK</mi><mfenced><mi>KMC</mi></mfenced></msub><mo mathvariant="normal">=</mo><msub><mi>RN</mi><mfenced><mi>KMC</mi></mfenced></msub></mtd></mtr><mtr><mtd><mspace width="5em" /><msub><mi>RN</mi><mfenced><mi>KMC</mi></mfenced></msub><mspace width="1em" /><mi>is a random number generated by KMC with the help of RNG</mi></mtd></mtr></mtable></math><img file="EP2285040A1_D0014.tif" /></maths><maths id="math0013"><math display="block"><msub><mi mathvariant="normal">R</mi><mi mathvariant="normal">a</mi></msub><mo>⁢</mo><msub><mi>PK</mi><mfenced><mi>USER</mi></mfenced></msub><mo mathvariant="normal">=</mo><msub><mi>RN</mi><mfenced><mi>USER</mi></mfenced></msub><mn mathvariant="normal">.</mn><mi mathvariant="normal">G</mi><mspace width="2em" /><mfenced><mi>scalar multiplication of elliptic curve group</mi></mfenced></math><img file="EP2285040A1_D0015.tif" /></maths><maths id="math0014"><math display="block"><msub><mi mathvariant="normal">R</mi><mi mathvariant="normal">a</mi></msub><mo>⁢</mo><msub><mi>SK</mi><mfenced><mi>USER</mi></mfenced></msub><mo mathvariant="normal">=</mo><msub><mi>RN</mi><mfenced><mi>USER</mi></mfenced></msub></math><img file="EP2285040A1_D0016.tif" /></maths> RN _(USER) is a random number generated by USER with the help of RNG

01442.2 Identity key

0145Identity key is a public key/private key pair (IdPK, IdSK) composed of identity public key (IdPK) and identity private key (IdSK).

0146The output of the hashing function that uses the identity as the input <maths id="math0015"><math display="block"><mi mathvariant="normal">H</mi><mfenced><mi>ID</mi></mfenced><mo mathvariant="normal">=</mo><mfenced><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">0</mn></msub><msub><mi mathvariant="normal">w</mi><mn mathvariant="normal">1</mn></msub><mo>⋯</mo><msub><mi mathvariant="normal">w</mi><mrow><mi mathvariant="normal">v</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mrow></msub></mfenced></math><img file="EP2285040A1_D0017.tif" /></maths>

0147c is selected to be a positive integer (0&lt;c&lt;2^u), then the selected bit (sw_i) is calculated with the following formula: <maths id="math0016"><img file="EP2285040A1_D0018.tif" /></maths>

0148The calculation formula of the identity public key/private key pair is: <maths id="math0017"><img file="EP2285040A1_D0019.tif" /></maths><maths id="math0018"><img file="EP2285040A1_D0020.tif" /></maths>

01493. Multiple key combination modes of the two-factor combined public key crypto-system

01503.1 First-order two-factor key mode

0151Attention is directed to <figref idref="f0001">Fig. 1</figref>, which shows a first-order two-factor key mode according to the present invention.

0152In the first-order two-factor key mode, the user key is completely generated by the key management center (KMC). This mode applies for closed systems of any scale, in which the users absolutely trust the key management center. In addition, the first-order two-factor key is the basis to generate a second-order or n_th-order two-factor key. Its workflow includes:

0153① defining and generating seed private key set (seedSK) and seed public key set (seedPK) that correspond to each other;

0154② checking and approving the identity submitted by the user to ensure its authenticity and uniqueness;

0155③ using the user identity as the input of the hash function, to calculate the hash value H (ID) of the identity;

0156④ using H (ID) to construct selected number sequence, selecting from the seed private key set and generating the user identity private key (IdSK) through combination operation;

0157⑤ using the random number generator to generate the random key R_aSK_(KMC) and R_aPK_(KMC) defined by the center;

0158⑥ adding IdSK and R_aSK_(KMC) to obtain the first-order two-factor private key SK_1;

0159⑦ writing (SK₁ | R_aPK_(KMC) into a chip to provide to the user.

01603.2 Second-order two-factor key mode

0161Attention is directed to <figref idref="f0001">Fig. 2</figref>, which shows a second-order two-factor key mode according to the present invention.

0162The Second-order two-factor key mode, based on the first-order two-factor key mode, adds user self-defined random key. This mode mainly applies for open systems of any scales (including large scale and super-large scale), in which the users require private right to the private keys that is not controlled by the key management center. The generating process includes:

0163① The user using a random number generator to generate a user self-defined random private key R_aSK_(USER), and generate a user self-defined random public key R_aPK_(USER) through scalar multiplication operation of elliptic curve group;

0164② The user adding R_aSK_(USER) with SK₁ to generate a second-order two-factor private key (SK₂);

0165③ The user adding R_aSK_(USER) with R_aPK_(KMC) to generate a second-order random public key (R_aPK₂);

0166④ The user writing the SK₂ and R_aPK₂ into a chip, and deleting SK₁ and R_aPK_(KMC).

01673.3 n_th-order two-factor key mode

0168Attention is directed to <figref idref="f0002">Fig. 3</figref>, which shows a n_th-order two-factor key mode according to the present invention.

0169The n_th-order two-factor key mode mainly applies for systems in which the users require to have self-updating right to the private keys at any time. The generating process is as follows:

0170① The user using a random number generator to generator a user self-defined random private key R_aSK_(USER) and generate a user self-defined random public key R_aSK_(USER) through scalar multiplication operation of elliptic curve group;

0171② The user adding SK₂ with the newly generated R_aSK_(USER) to generate a n_th-order two-factor private key (SK_n);

0172③ The user adding the newly generated R_aSK_(USER) with R_aPK₂ to generate a n_th-order random public key (R_aPK_n);

0173④ The user writing SK_n and R_aPK_n into a chip, and deleting SK₂ and R_aPK₂.

0174The above process can be repeatedly performed. In addition, the user updating key can also be implemented by repeatedly using the second-order two-factor key mode. When using the second-order two-factor key mode to implement key updating, initial status of the process shall always be the first-order two-factor private key and center-defined random public key (SK₁ ∥ R_aPK_(KMC)).

01753.4 Conversion from two-public-key to public key

0176The verifier or encryptor needs to know the public key actually used by the other party. Thus, conversion from identity and random public keys to public key is needed. The conversion process is as follows:

0177① The verifier or encryptor first needs to obtain the user identity ID and its corresponding random public key (R_aPK) sent by the signer or published by the key management center;

0178② The user identity ID is used as the input of hash function, to calculate the hash value H(ID) of the identity;

0179③ The H(ID) is used to construct the selected number sequence, selecting from the seed private key set and generating the user identity public key (IdPK) through combination operation;

0180④ IdPK is added with R_aPK, to obtain the public key (PK) used by the user. Attention is directed to <figref idref="f0002">Fig. 4</figref>, which shows a flow chart of generating public key based on identity and random public key according to the present invention.

01814. Digital signature algorithm

0182The digital signature algorithm adopts ECDSA algorithm recommended by the international standard.

01834.1 Public parameters and algorithm

0184① Five-parameter group (a, b, G, n, p) of elliptic curve group;

0185② hash function h to the message;

0186③ Seed public key set(P₀, P₁, •••, P ₂^u_×v-1);

0187④ The identity ID and random public key R_aPK sent by signer A

01884.2 Signing process of A to message m

0189① Randomly selecting k∈Zn

0190② Calculating: k.G=(x, y) (scalar multiplication of elliptic curve group)

0191③ Calculating: r=x mod n

0192④ Calculating: S=k^-1 (h(m) + SK. r) mod n

0193⑤ A sends m and signature (r, s) to B

01944.3 Signature verification process of B to A

0195① generating identity public key IdPK with A's identity via seed public key set

0196② Calculating: PK=IdPK + R_aPK (point operation of elliptic curve);

0197③ Calculating: u₁=h(m).S^-1 mod n <maths id="math0019"><math display="block"><msub><mi mathvariant="normal">u</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">=</mo><mi mathvariant="normal">r</mi><mn mathvariant="normal">.</mn><msup><mi mathvariant="normal">S</mi><mrow><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mrow></msup><mo>⁢</mo><mi>mod n</mi></math><img file="EP2285040A1_D0021.tif" /></maths>

0198④ Calculating: R=u₁.G+u₂.PK (point operation of elliptic curve) Represented by R=(x', y');

0199⑤ Calculating: v=x' mod n; if v=r, then the verification is passed, and the signature is valid. Otherwise, the signature is invalid.

02005. Key transfer algorithm for data encryption

0201The key for data encryption is called session key. The session key shall be updated at each communication.

02025.1 Public parameters

0203① Five-parameter group (a, b, G, n, p) of elliptic curve group

0204② Seed public key set(P₀, P₁, •••, P₂^u_×v-1)

0205③ The identity ID and random public key R_aPK_B of the receiver B

02065.2 Key transmission of sender A

0207① using the identity ID of receiver B with the seed public key set to generate identity public key IdPK_B of party B

0208② calculating public key of party B <maths id="math0020"><math display="block"><msub><mi>PK</mi><mi mathvariant="normal">B</mi></msub><mo mathvariant="normal">=</mo><msub><mi>IdPK</mi><mi mathvariant="normal">B</mi></msub><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">R</mi><mi mathvariant="normal">a</mi></msub><mo>⁢</mo><msub><mi>PK</mi><mi mathvariant="normal">B</mi></msub><mspace width="1em" /><mfenced><mi>point operation of elliptic curve</mi></mfenced><mo mathvariant="normal">;</mo></math><img file="EP2285040A1_D0022.tif" /></maths>

0209③ randomly selecting k ∈ Zn

0210④ calculating: k.G=(x, y) (scalar multiplication)

0211⑤ selecting r=x (mod n) as a session key

0212⑥ calculating k.PK_B

0213⑦ sending k.PK_B to B

02145.3 Process of receiver B obtaining session key

0215① receiving k.PK_B

0216② calculating: SK_B^-1.(k.PK_B)=k.G=(x, y)

0217③ selecting r=x (mod n) as a session key

02186. Authentication system based on two-factor combined public key (TF-CPK) crypto-system

0219Authentication system of any scale (including ultra-large scale) can be constructed by using two-factor combined public key (TF-CPK) technology. In addition, terminal-to-terminal direct authentication can be realized. The authentication process does not need support of third party online database. The system is mainly composed of key management center and user terminal.

0220<figref idref="f0003">Fig. 5</figref> shows KMC functional block diagram according to the present invention.

02216.1 Key management center

0222The key management center mainly comprises:

0223① user-registration, responsible for checking and approving user identities, to ensure authenticity and uniqueness, in which the user identity can be defined based on name, unit/organization name, bank account, and phone number, etc.;

0224② seed key generation, responsible for generating seed key set (SeedSK, SeedPK);

0225③ user key generation and distribution, using the user identity, seed private key set and random number generator to generate first-order private key (SK₁) and center-defined random public key (R_aPK_(KMC)), and writing SK₁ and R_aPK_(KMC) into a dedicated chip (which can be encapsulated into IC card, U-Key, etc.) to distribute to the users. The key generating process is in <figref idref="f0003">Fig 5</figref>.

02266.1 First-order two-factor key mode

0227④ public data publication, the published contents including: seed public key set, revocatory identity list, and user identity and its corresponding R_aPK_(KMC) and R_aPK_(USER), etc.. The below table shows the user identity and data format of its corresponding random public key published by KMC. <tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="16mm" /><colspec colnum="2" colname="col2" colwidth="54mm" colsep="0" /><colspec colnum="3" colname="col3" colwidth="34mm" /><tbody><row><entry rowsep="0">User</entry><entry>+RaPK_(KMC)</entry><entry>first-order postfix</entry></row><row><entry rowsep="0">Identity</entry><entry>+ R_aPK_(KMC)+ R_aPK_(USER)= R_aPK₂</entry><entry>second-order postfix</entry></row><row><entry>ID</entry><entry>+ R_aPK_n-1+ R_aPK_(USER)= R_aPK_n</entry><entry>n_th-order postfix</entry></row></tbody></tgroup></table></tables> data format published by KMC

02286.2 User terminal

0229The user terminal is mainly comprised of authentication chip (which can be encapsulated in forms easy to use, such as IC card, USB-Key, etc.) and client software. The authentication process of TF-CPK authentication system is mainly conducted between client and server (the function of which corresponds to that of the client), and between clients. The chip has calculation and storage unit, algorithm protocol and user private key and public key data embedded therein, corresponding to a complete authentication system (see the function diagram of the system). The private key, upon encrypted with the user <i>pin</i> code, is stored in the safe memory area of the chip. All the operations involving the private key, such as digital signature, key-exchange, are conducted in the chip, to ensure safety of the private key.

0230Attention is directed to <figref idref="f0004">Fig. 6</figref>, which shows a structure and function diagram of TF-CPK authentication chip according to the present invention.

02317. Application Field

0232TF-CPK authentication system theoretically can be used in all the fields that require authenticity proof, such as: electronic seal, anti-forgery of electronic tag and the like. In addition, TF-CPK authentication system can publish user identity having random public key with the help of the center, to realize key exchange, such as encrypting the email, etc..

02337.1 Electronic seal system

0234Attention is directed to <figref idref="f0005">Fig. 7</figref>, which shows an electronic seal system according to the present invention.

0235The electronic seal system proves authenticity of the transaction information with the digital signature, and is widely used in fields such as e-business, e-government. The workflow is as follows:

02367.1.1 Signer A uses the private key in the authentication chip to sign on the original data m. The signing process is as follows:

0237① Randomly selecting k ∈ Zn

0238② Calculating: k.G=(x, y) (scalar multiplication of elliptic curve group)

0239③ Calculating: r=x mod n

0240④ Calculating: S=k^-1 (h(m) + SK. r) mod n

0241⑤ A sending m and signature (r, s) to B

02427.1.2 Verifier B verifies the signature data of A. The verification process is as follows:

0243① using A's identity, with seed public key set, to generate identity public key IdPK;

0244② Calculating: PK=IdPK + R_aPK (point operation of elliptic curve)

0245③ Calculating: u₁=h(m).S^-1 mod n <maths id="math0021"><math display="block"><msub><mi mathvariant="normal">u</mi><mn mathvariant="normal">2</mn></msub><mo mathvariant="normal">=</mo><mi mathvariant="normal">r</mi><mn mathvariant="normal">.</mn><msup><mi mathvariant="normal">S</mi><mrow><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mrow></msup><mo>⁢</mo><mi>mod n</mi><mo mathvariant="normal">;</mo></math><img file="EP2285040A1_D0023.tif" /></maths>

0246④ Calculating: R=u₁.G+u₂.PK (point operation of elliptic curve) recorded as: R=(x', y');

0247⑤ Calculating: v=x' mod n, if v=r, then verification is passed, and the signature is valid. Otherwise, the signature is invalid.

02487.2 Anti-forgery of electronic tag

0249Anti-forgery of electronic tag is a novel anti-forgery technology having both physical and logical anti-counterfeiting features generated by combining TF-CPK digital signature technology and RFID technology. The technology can effectively prevent forgery and duplication, and has universal verification capability. The implementation process is as follows:

02507.2.1 Manufacture of anti-forgery electronic tag

0251<figref idref="f0005">Fig. 8</figref> shows a generation process of anti-forgery electronic tag according to the present invention.

0252① Reading a unique number on a RFID chip;

0253② Using TF-CPK algorithm and private key to perform digital signature to anti-forgery information, such as the holder's personal information, the certificate issuing unit or product information and manufacturer, along with the RFID unique number and a random public key corresponding to the private key (see 7.11 for signature algorithm), to generate a signature information;

0254③ Writing the signature information into the RFID chip;

02557.2.2 Verification of anti-forgery electronic tag

0256<figref idref="f0005">Fig. 9</figref> shows the verification process of anti-forgery electronic tag according to the present invention.

0257① Using TF-CPK algorithm to calculate an identity public key of the signer, and adding it to a random public key being sent, to obtain a useful public key of the signer;

0258② Using the public key to interpret the digital signature information on the anti-forgery chip (see 7.11 for algorithm);

0259③ It is true if the information can be properly displayed, otherwise it is false.

02607.3 Safe email system

0261Email is the most widely used network information exchange means. Use of TF-CPK technology can conduct digital signature and encryption to the email contents, to effectively ensure authenticity, integrity and privacy of the information.

02627.3.1 Digital signature and verification to email contents

0263The signer uses the private key to perform digital signature, and provides the user identity and random public key of his own in the signature;

0264The verifier uses the other party's identity, with the published seed public key set, to calculate the other party's identity public key; adds it with the random public key sent by the other party to obtain a useful public key of the other party; and verifies the signature contents with it.

02657.3.2 Encryption/decryption of email contents

0266The sender A calculates the public key of the receiver B with the user identity and random public key postfix published by the center; Randomly selecting k ∈ Zn Calculating: k.G=(x, y) (scalar multiplication); Selecting r=x (mod n) as a session key; Calculating k.PK_B; Sending k.PK_B with the encrypted information to B; The receiver B receiving the encrypted information having k.PK_B; Calculating: SK_B^-1.(k.PK_B)=k.G=(x, y); Selecting r=x (mod n) as the session key, to decrypt the encrypted information.

0267The above description is only for the preferred embodiments, and is not intended to limit the invention. Apparently, people skilled in the art can make various modifications and variations to the present invention without departing from the scope and spirit of the invention. Thus, if such modifications and variations fall into the scope of the appended claims or equivalent to those disclosed, they are intended to be included in the invention.