Method, system, device for proving authenticity of an entity or integrity of a message

This Application is a Section 371 National Stage of International Application No. PCT/FR00/02717 filed Sep. 29, 2000, published Apr. 12, 2001 as WO 01/26279, not in English.

The present invent ion relates to the methods, systems and devices designed to prove the authenticity of an entity and/or the integrity and/or authenticity of a message.

The patent EP 0 311 470 B1, whose inventors are Louis Guillou and Jean-Jacques Quisquater, describes such a method. Hereinafter, reference shall be made to their work by the terms “GQ patent” or “GQ method”. Hereinafter, the expression “GQ2”, or “GQ2 invention” or “GQ2 technology” shall be used to describe the present invention.

According to the GQ method, an entity known as a “trusted authority” assigns an identity to each entity called a “witness” and computes its RSA signature. In a customizing process, the trusted authority gives the witness an identity and signature. Thereafter, the witness declares the following: “Here is my identity; I know its RSA signature”. The witness proves that he knows the RSA signature of his identity without revealing it. Through the RSA public identification key distributed by the trusted authority, an entity known as a “controller” ascertains, without obtaining knowledge thereof, that the RSA signature corresponds to the declared identity. The mechanisms using the GQ method run “without transfer of knowledge”. According to the GQ method, the witness does not know the RSA private key with which the trusted authority signs a large number of identities.

The GQ technology described above makes use of RSA technology. However, whereas RSA technology truly depends on the factorization of the modulus n, this dependence is not an equivalence, indeed far from it, as can be seen in what are called “multiplicative attacks” against the various standards of digital signatures implementing RSA technology.

The goal of the GQ2 technology is twofold: on the one hand, to improve the performance characteristics of RSA technology and, on the other hand, to avert the problems inherent in RSA technology. Knowledge of the GQ2 private key is equivalent to knowledge of the factorization of the modulus n. Any attack on the triplets GQ2 leads to factorization of the modulus n: this time there is equivalence. With the GQ2 technology, the work load is reduced both for the signing or self-authenticating entity and for the controller entity. Through a better use of the problem of factorizing in terms of both security and performance, the GQ2 technology averts the drawbacks of RSA technology.

The GQ method implements modulo computations of numbers comprising 512 bits or more. These computations relate to numbers having substantially the same size raised to powers of the order of 2 16 +1. But existing microelectronic infrastructures, especially in the field of bank cards, make use of monolithic self-programmable microprocessors without arithmetical coprocessors. The work load related to the multiple arithmetical applications involved in methods such as the GQ method leads to computation times which, in certain cases, prove to be disadvantageous for consumers using bank cards to pay for their purchases. It may be recalled here that, in seeking to increase the security of payment cards, the banking authorities have raised a problem that is particularly difficult to solve. In fact, two apparently contradictory questions have to be examined: on the one hand, increasing security by using increasingly lengthy and distinct keys for each card while, on the other hand, preventing the work load from leading to excessive computation times for the users. This problem becomes especially acute inasmuch as it is also necessary to take account of the existing infrastructure and the existing microprocessor components.

The GQ2 technology is aimed at providing a solution to this problem while still increasing security.

Method

More particularly, the invention relates to a method designed to prove the following to a controller entity:

the authenticity of an entity and/or

the integrity of a message M associated with this entity.

This proof is established by means of all or part of the following parameters or derivatives of these parameters:

m pairs of private values Q 1 , Q 2 , . . . Q m and public values G 1 , G 2 , . . . G m (m being greater than or equal to 1),

a public modulus n constituted by the product of f prime factors p 1 , p 2 , . . . p f (f being greater than or equal to 2).

Said modulus and said private and public values are related by relationships of the type:

G i ·Q i v ≡1. mod n or G i ≡Q i v mod n

where v represents a public exponent of the type

v=2 k

where k is a security parameter greater than 1,

said m public values G i being the squares g i 2 of m distinct base numbers g 1 g 2 , . . . g m inferior to the f prime factors p 1 , p 2 , . . . p f ; said f prime factors p 1 , p 2 , . . . p f and/or said m base numbers g 1 g 2 , . . . g m being produced in such a way that the following conditions are satisfied.

First Condition:

According to the first condition, each of the equations

x v ≡g i 2 mod n   (1)

has solutions in x in the ring of integers modulo n.

Second Condition:

According to the second condition, in the case where G 1 ≡Q i v mod n, among the m numbers q i obtained by raising Q i to the square modulo n, k−1 rank times, one of them is different from ±g i (that is to say non-trivial).

According to the second condition, in the case where G i ·Q i v ≡1.mod n, among the m numbers q i obtained by raising the inverse of Q i modulo n to the square modulo n, k−1 rank times, one of them is different from ±g i (that is to say non-trivial).

It is to be noted here that according to current notation ±g i represents the number g i and n−g i .

Third Condition:

According to the third condition, among the 2 m equations:

x 2 ≡g i mod n   (2)

x 2 ≡−g i mod n   (3)

at least one of them has solutions in x in the ring of integers modulo n.

The method implements an entity called a witness in the steps defined here below. Said witness entity has f prime factors p i and/or m base numbers g i and/or parameters of the Chinese remainders of the prime factors and/or the public modulus n and/or the m private values Q i and/or the f.m components Q i,j (Q i,j ≡Q i mod p j ) of the private values Q i and of the public exponent v.

The witness computes commitments R in the ring of integers modulo n. Each commitment is computed either by:

performing operations of the type

R≡r v mod n

Where r is a random value such that 0<r<n,

or

** by performing operations of the type

R i ≡r i v mod p i

where r i is a random value associated with the prime number p i such that 0<r i <p i , each r i belonging to a collection of random values {r 1 , r 2 , . . . r f },

** then by applying the Chinese remainder method.

The witness receives one or more challenges d. Each challenge d comprises m integers d i hereinafter called elementary challenges. The witness, on the basis of each challenge d i computes a response D,

either by performing operations of the type:

D≡r.Q 1 d1 .Q 2 d2 .Q m dm mod n

or

** by performing operations of the type:

D i ≡r i .Q i,1 d1 ,Q i2 d2 . . . . Q i,m dm mod p i

** then by applying the Chinese remainder method.

The method is such that there are as many responses D as there are challenges d as there are commitments R. Each group of numbers R, d, D forms a triplet referenced {R, d, D}.

Case of the Proof of the Authenticity of an Entity

In a first variant of an embodiment, the method according to the invention is designed to prove the authenticity of an entity known as a demonstrator to an entity known as the controller. Said demonstrator entity comprises the witness. Said demonstrator and controller entities execute the following steps:

At each call, the witness computes each commitment R by applying the process specified above. The demonstrator sends the controller all or part of each commitment R.

The controller, after having received all or part of each commitment R, produces challenges d equal in number to the number of commitments R and sends the challenges d to the demonstrator.

The witness computes the responses D from the challenges d by applying the process specified above.

The demonstrator sends each response D to the controller.

First Case: The Demonstrator has Transmitted a Part of Each Commitment R.

If the demonstrator has transmitted a part of each commitment R, the controller, having the m public values G 1 , G 2 , . . . , G m , computes a reconstructed commitment R′, from each challenge d and each response D, this reconstructed commitment R′ satisfying a relationship of the type

R′≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or a relationship of the type

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm . mod n.

The controller ascertains that each reconstructed commitment R′ reproduces all or part of each commitment R that has been transmitted to it.

Second Case: The Demonstrator has Transmitted the Totality of Each Commitment R

If the demonstrator has transmitted the totality of each commitment R, the controller, having the m public values G 1 , G 2 , . . . , G m , ascertains that each commitment R satisfies a relationship of the type

R≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or a relationship of the type

R≡D v /G 1 d1 . G 2 d2 . . . . G m dm . mod n.

Case of the Proof of the Integrity of the Message

In a second variant of an embodiment capable of being combined with the first one, the method according to the invention is designed to provide proof to an entity, known as the controller entity, of the integrity of a message M associated with an entity called a demonstrator entity. Said demonstrator entity comprises the witness.

Said demonstrator and controller entities perform the following steps:

At each call, the witness computes each commitment R by applying the process specified above.

The demonstrator applies a hashing function h whose arguments are the message M and all or part of each commitment R to compute at least one token T. The demonstrator sends the token T to the controller. The controller, after having received a token T, produces challenges d equal in number to the number of commitments R and sends the challenges d to the demonstrator.

The witness computes the responses D from the challenges d by applying the process specified above.

The demonstrator sends each response D to the controller. The controller, having the m public values G 1 , G 2 , . . . G m , computes a reconstructed commitment R′, from each challenge d and each response D, this reconstructed commitment R′ satisfying a relationship of the type:

R′≡G 1 d1 . G 2 d2 . . . . G m dm . D v mod n

or a relationship of the type

R′≡D v /G 1 d1 . G 2 d2 . . . . G m dm . mod n.

Then the controller applies the hashing function h whose arguments are the message M and all or part of each reconstructed commitment R′ to reconstruct the token T′. Then the controller ascertains that the token T′ is identical to the token T transmitted.

Digital Signature of a Message and Proof of its Authenticity

In a third variant of an embodiment according to the invention, capable of being combined with the two preceding embodiments, the method according to the invention is designed to produce the digital signature of a message M by an entity known as the signing entity. Said signing entity includes the witness.

Signing Operation

Said signing entity executes a signing operation in order to obtain a signed message comprising:

the message M,

the challenges d and/or the commitments R,

the responses D.

Said signing entity executes the signing operation by implementing the following steps:

At each call, the witness computes each commitment R by applying the process specified above.

The signing entity applies a hashing function h whose arguments are the message M and each commitment R to obtain a binary train. From this binary train, the signing entity extracts challenges d in a number equal to the number of commitments R.

The witness computes the responses D from the challenges d by applying the process specified process above.

Checking Operation

To prove the authenticity of the message M, an entity called a controller checks the signed message. Said controller entity having the signed message carries out a checking operation by proceeding as follows,

Case Where the Controller has Commitments R, Challenges d, Responses D

If the controller has commitments R, challenges d, responses D, the controller ascertains that the commitments R, the challenges d and the responses D satisfy relationships of the type:

R≡G 1 d1 .G 2 d2 .G m dm .D v mod n

or relationships of the type:

R≡D v /G 1 d1 .G 2 d2 . G m dm . mod n.

Then the controller ascertains that the message M, the challenges d and the commitments R satisfy the hashing function:

d=h (message, R )

Case Where the Controller has Challenges d and Responses D

If the controller has challenges d and responses D, the controller, on the basis of each challenge d and each response D, reconstructs commitments R′ satisfying relationships of the type:

R′≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or relationships of the type:

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm . mod n.

Then the controller ascertains that the message M and the challenges d satisfy the hashing function:

D=h (message, R′ )

Case Where the Controller has Commitments R and Responses D

If the controller has commitments R and responses D, the controller applies the hashing function and reconstructs d′

d′=h (message, R ).

Then the controller ascertains that the commitments R, the challenges d′ and the responses D satisfy relationships of the type:

R≡G 1 d′1 .G 2 d′2 .G m d′m .D v mod n

or relationships of the type:

R≡D v G 1 d′1 .G 2 d′2 . . . . G m d′m . mod n.

System

The present invention also relates to a system designed to prove the following to a controller server:

the authenticity of an entity and/or

the integrity of a message M associated with this entity.

This proof is established by means of all or part of the following parameters or derivatives of these parameters:

m pairs of private values Q 1 , Q 2 , . . . Q m and public values G 1 , G 2 , . . . G m (m being greater than or equal to 1),

a public modulus n constituted by the product of f prime factors p 1 , p 2 , . . . p f (f being greater than or equal to 2).

Said modulus, and said private and public values are linked by relationships of the type:

G i .Q i v ≡1. mod n or G i ≡Q i v mod n

v designating a public exponent of the type:

v=2 k

where k is a security parameter greater than 1,

said m public values G i being the squares g i 2 of distinct m base numbers g 1 , g 2 , . . . g m inferior to the f prime factors p 1 , p 2 , . . . p f ; said f prime factors p 1 , p 2 , . . . p f and/or said m base numbers g 1 , g 2 . . . g m being produced such that the following conditions are satisfied.

First Condition

According to the first condition, each of the equations:

x v ≡g i 2 mod n   (1)

can be solved in x in the ring of integers modulo n.

Second condition

According to the second condition, in the case where G i ≡Q i v . mod n, among the m numbers q i obtained by raising Q i to the square modulo n, k−1 rank times, one of them is different from ±g i (that is to say non trivial).

According to the second condition, in the case where G i . Q i v ≡1 mod n, among the m numbers q i obtained by raising the inverse of Q i modulo n to the square modulo n, k−1 rank times, one of them is different from ±g i (that is to say non trivial).

It is pointed out here that according to a current notation ±g i represents the numbers g i and n−g i .

Third Condition:

According to the third condition, among the 2 m equations:

x 2 ≡g i mod n   (2)

x 2 ≡g i mod n   (3)

at least one of them can be solved in x in the ring of integers modulo n.

Said system comprises a witness device, contained especially in a nomad object which, for example, takes the form of a microprocessor-based bank card. The witness device comprises a memory zone containing the f prime factors p i and/or the parameters of the Chinese remainders of the prime factors and/or the public modulus n and/or the m private values Q i and/or f.m components Q i,j (Q i,j ≡Q i mod p j ) of the private values Q i and of the public exponent v. The witness device also comprises:

random value production means hereinafter called random value production means of the witness device,

computation means, hereinafter called means for the computation of commitments R of the witness device.

The means of computation make it possible to compute commitments R in the ring of integers modulo n. Each commitment is computed

either by performing operations of the type

R≡r v mod n

where r is a random value produced by the random factor production means, r being such that 0<r<n.

or by performing operations of the type

R i ≡r i v mod p i

where r i is a random value associated with the prime number p i such that 0<r i <p i , each r i belonging to a collection of random values {r 1 , r 2 , . . . r f }, produced by the random factor production means and then by applying the Chinese remainder method.

The witness device also comprises:

reception means hereinafter called the means for the reception of the challenges d of the witness device, to receive one or more challenges d; each challenge d comprising m integers d i hereinafter called elementary challenges.

computation means, hereinafter called means for the computation of the responses D of the witness device, for the computation on the basis of each challenge d, of a response D:

either by carrying out operations of the type:

D≡r.Q 1 d1 Q 2 d2 . . . . Q m dm mod n

or by carrying out operations of the type:

D i ≡r i .Q i,1 d1 .Q i,2 d2 . . . . Q i,m dm mod p i

and then by applying the Chinese remainder method.

The witness device also comprises transmission means to transmit one or more commitments R and one or more responses D. There are as many responses D as there are challenges d as there are commitments R. Each group of numbers R, d, D forming a triplet referenced {R, d, D}.

Case of the Proof of the Authenticity of an Entity

In a first variant of embodiment, the system according to the invention is designed to prove the authenticity of an entity called a demonstrator to an entity called a controller.

Said system is such that it comprises a demonstrator device associated with a demonstrator entity. Said demonstrator device is interconnected with the witness device by interconnection means. It may especially take the form of logic microcircuits in a nomad object, for example the form of a microprocessor in a microprocessor-based bank card.

Said system also comprises a controller device associated with the controller entity. Said controller device especially takes the form of a terminal or remote server. Said controller device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a computer communications network, to the demonstrator device.

Said system is used to execute the following steps:

At each call, the means of computation of the commitments R of the witness device compute each commitment R by applying the process specified above. The witness device comprises means of transmission, hereinafter called the transmission means of the witness device, to transmit all or part of each commitment R to the demonstrator device through the interconnection means. The demonstrator device also comprises transmission means, hereinafter called the transmission means of the demonstrator, to transmit all or part of each commitment R to the controller device through the connection means.

The controller device comprises challenge production means for the production, after receiving all or part of each commitment R, of the challenges d equal in number to the number of commitments R. The controller device also comprises transmission means, hereinafter called the transmission means of the controller, to transmit the challenges d to the demonstrator through the connection means.

The means of reception of the challenges d of the witness device receive each challenge d coming from the demonstrator device through the interconnection means. The means of computation of the responses D of the witness device compute the responses D from the challenges d by applying the process specified above.

The transmission means of the demonstrator transmit each response D to the controller. The controller device also comprises:

computation means, hereinafter called the computation means of the controller device,

comparison means, hereinafter called the comparison means of the controller device.

First Case: the Demonstrator has Transmitted a Part of Each Commitment R.

If the transmission means of the demonstrator have transmitted a part of each commitment R, the computation means of the controller device, having m public values G 1 , G 2 , . . . G m , compute a reconstructed commitment R′, from each challenge d and each response D, this reconstructed commitment R′ satisfying a relationship of the type:

R′≡G 1 d1 .G 2 d2 . . . . G m dm . D v mod n

or a relationship of the type:

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n.

The comparison means of the controller device compare each reconstructed commitment R′ with all or part of each commitment R received.

Second Case: The Demonstrator has Transmitted the Totality of Each Commitment R

If the transmission means of the demonstrator have transmitted the totality of each commitment R, the computation means and the comparison means of the controller device, having m public values G 1 , G 2 , . . . , G m , ascertain that each commitment R satisfies a relationship of the type:

R≡G 1 d1 .G 2 d2 . . . . G m dm . D v mod n

or a relationship of the type:

R≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n.

Case of the Proof of the Integrity of a Message

In a second variant embodiment capable of being combined with the first one, the system according to the invention is designed to give proof to an entity, known as a controller of the integrity of a message M associated with an entity known as a demonstrator. Said system is such that it comprises a demonstrator device associated with the demonstrator entity. Said demonstrator device is interconnected with the witness device by interconnection means. It may especially take the form of logic microcircuits in a nomad object, for example in the form of a microprocessor in a microprocessor-based bank card. Said system also comprises a controller device associated with the controller entity. Said controller device especially takes the form of a terminal or remote server. Said controller device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a data-processing communications network, to the demonstrator device.

Said system is used to execute the following steps:

At each call, the means of computation of the commitments R of the witness device compute each commitment R by applying the process specified above. The witness device has means of transmission, hereinafter called transmission means of the witness device, to transmit all or part of each commitment R to the demonstrator device through the interconnection means.

The demonstrator device comprises computation means, hereinafter called the computation means of the demonstrator, applying a hashing function h whose arguments are the message M and all or part of each commitment R to compute at least one token T. The demonstrator device also comprises transmission means, hereinafter known as the transmission means of the demonstrator device, to transmit each token T through the connection means to the controller device. The controller device also has challenge production means for the production, after having received the token T, of the challenges d in a number equal to the number of commitments R. The controller device also has transmission means, hereinafter called the transmission means of the controller, to transmit the challenges d to the demonstrator through the connection means.

The means of reception of the challenges d of the witness device receive each challenge d coming from the demonstrator device through the interconnection means. The means of computation of the responses D of the witness device compute the responses D from the challenges d by applying the process specified above.

The transmission means of the demonstrator transmit each response D to the controller. The controller device also comprises computation means, hereinafter called the computation means of the controller device, having m public values G 1 , G 2 , . . . , G m , to firstly compute a reconstructed commitment R′, from each challenge d and each response D, this reconstructed commitment R′ satisfying a relationship of the type:

R′≡G 1 d1 . G 2 d2 . . . . G m dm . D v mod n

or a relationship of the type:

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n

and then, secondly, to compute a token T′ by applying the hashing function h having as arguments the message M and all or part of each reconstructed commitment R′.

The controller device also has comparison means, hereinafter known as the comparison means of the controller device, to compare the computed token T′ with the received token T.

Digital Signature of a Message and Proof of its Authenticity

In a third variant of an embodiment according to the invention, capable of being combined with one and/or the other of the first two embodiments, the system according to the invention is designed to prove the digital signature of a message M, hereinafter known as a signed message, by a n entity called a signing entity.

The signed message comprises:

the message M,

the challenges d and/or the commitments R,

the responses D.

Signing Operation

Said system is such that it comprises a signing device associated with the signing entity. Said signing device is interconnected with the witness device by interconnection means and may especially take the form of logic microcircuits in a nomad object, for example in the form of a microprocessor in a microprocessor-based bank card.

Said system is used to execute the following steps:

At each call, the means of computation of the commitments R of the witness device compute each commitment R by applying the process specified above. The witness device comprises means of transmission, hereinafter called the transmission means of the witness device, to transmit all or part of each commitment R to the signing device through the interconnection means.

The signing device comprises computation means, hereinafter called the computation means of the signing device, applying a hashing function h whose arguments are the message M and all or part of each commitment R to compute a binary train and extract, from this binary train, challenges d whose number is equal to the number of commitments R.

The means for the reception of the challenges d of the witness device receive each challenge d coming from the signing device through the interconnection means. The means for computing the responses D of the witness device compute the responses D from the challenges d by applying the process specified above. The witness device comprises transmission means, hereinafter called means of transmission of the witness device, to transmit the responses D to the signing device, through the interconnection means.

Checking Operation:

To prove the authenticity of the message M, an entity known as the controller checks the signed message.

Said system comprises a controller device associated with the controller entity. Said controller device especially takes the form of a terminal or remote server. Said controller device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a computer communications network, to the signing device.

Said signing device associated with the signing entity comprises transmission means, hereinafter known as the transmission means of the signing device, for the transmission, to the controller device, of the signed message through the connection means. Thus the controller device has a signed message comprising:

the message M,

the challenges d and/or the commitments R.

the responses D.

The controller device comprises:

computation means hereinafter called the computation means of the controller device,

comparison means, hereinafter called the comparison means of the controller device.

Case Where the Controller Device has Commitments R, Challenges d, Responses D

If the controller device has commitments R, challenges d, responses D, the computation and comparison means of the controller device ascertain that the commitments R, the challenges d and the responses D satisfy relationships of the type

R≡G 1 d1 .G 2 d2 .G m dm . D v mod n

or relationships of the type:

R≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n.

Then, the computation and comparison means of the controller device ascertain that the message M, the challenges d and the commitments R satisfy the hashing function:

d=h (message, R )

Case Where the Controller Device has Challenges d and Responses D

If the controller has challenges d and responses D, the computation means of the controller reconstruct, on the basis of each challenge d and each response D, commitments R′ satisfying relationships of the type

R′≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or relationships of the type:

R′≡D v /G 1 d1 .G 2 d2 .G m dm mod n.

Then the computation and comparison means of the controller device ascertain that the message M and the challenges d satisfy the hashing function:

d=h (message, R′ )

Case Where the Controller has Commitments R and Responses D

If the controller device has commitments R and responses D, the computation means of the controller device apply the hashing function and compute d′ such that:

d′≡h (message, R )

Then the computation and comparison means of the controller device ascertain that the commitments R, the challenges d′ and the responses D satisfy relationships of the type:

R≡G 1 d′1 .G 2 d′2 . . . . G m d′m .D v mod n

or relationships of the type:

R≡D v /G 1 d′1 .G 2 d′2 . . . . G m d′m mod n.

Terminal Device

The invention also relates to a terminal device associated with an entity. The terminal device especially takes the form of a nomad object, for example the form of a microprocessor in a microprocessor-based bank card, The terminal device is designed to prove the following to a controller device:

the authenticity of an entity and/or

the integrity of a message M associated with this entity.

This proof is established by means of all or part of the following parameters or derivatives of these parameters:

m pairs of private values Q 1 , Q 2 , . . . Q m and public values G 1 , G 2 , . . . G m (m being greater than or equal to 1),

a public module n constituted by the product of f prime factors p 1 , p 2 , . . . p f (f being greater than or equal to 2).

Said module and said private and public values are related by relationships of the type

G i ·Q i v ≡1 mod n or G i ≡Q i v mod n

v designating a public exponent of the type

v=2 k

where k is a security parameter greater than 1.

Said m public values G i are the squares g i 2 of m distinct base numbers g 1 ,g 2 , . . . g m inferior to the f prime factors p 1 , p 2 , . . . p f ; said f prime factors p 1 , p 2 , . . . p f and/or said m base numbers g 1 ,g 2 , g m being produced such that the following conditions are satisfied.

First Condition

According to the first condition, each of the equations:

x v ≡g 1 2 mod n   (1)

can be solved in x in the ring of integers modulo n.

Second Condition

According to the second condition, in the case where G 1 ≡Q i v mod n, among the m numbers q i obtained by raising Q i to the square modulo n, k−1 times, one of them is different from ±g i (that is to say non trivial).

According to the second condition, in the case where G i . Q i v ≡1 mod n, among the m numbers q i obtained by raising the inverse of Q i modulo n to the square modulo n, k−1 times, one of them is different from ±g i (that is to say non trivial).

It is pointed out here that according to a current notation ±g i represents the numbers g i and n−g i .

Third Condition:

According to the third condition, among the 2 m equations:

x 2 ≡g i mod n   (2)

x 2 ≡g i mod n   (3)

at least one of them can be solved in x in the ring of integers modulo n.

Said terminal device comprises a witness device comprising a memory zone containing the f prime factors p i and/or the parameters of the Chinese remainders of the prime factors and/or the public modulus n and/or the m private values Q i and/or f.m components Q i,j (Q i,j =Q j mod p j ) of the private values Q i and of the public exponent v.

The witness device also comprises:

random value production means hereinafter called random value production means of the witness device,

computation means, hereinafter called means for the computation of commitments R of the witness device in the ring of the integers modulo n.

Each commitment is computed

either by performing operations of the type:

R≡r v mod n

where r is a random value produced by the random value production means, r being such that 0<r<n.

or by performing operations of the type:

R i ≡r i v mod p i

where r i is a random value associated with the prime number p i such that 0<r i <p i , each r i belonging to a collection of random values {r 1 , r 2 , . . . r f } produced by the random value production means, then by applying the Chinese remainder method.

The witness device also comprises:

reception means hereinafter called the means for the reception of the challenges d of the witness device, to receive one or more challenges d, each challenge d comprising m integers d i hereinafter called elementary challenges;

computation means, hereinafter called means for the computation of the responses D of the witness device, for the computation, on the basis of each challenge d, of a response D,

either by performing operations of the type:

D≡r.Q 1 d1 .Q 2 d2 . . . . Q m dm mod n

or by performing operations of the type:

D≡r i .Q i,1 d1 .Q i,2 d2 . . . . Q i,m dm mod p i

and then by applying the Chinese remainder method.

Said witness device also comprises transmission means to transmit one or more commitments R and one or more responses D. There are as many responses D as there are challenges d as there are commitments R. Each group of numbers R, d, D forms a triplet referenced {R, d, D}.

Case of the Proof of the Authenticity of an Entity

In a first embodiment variant, the terminal device according to the invention is designed to prove the authenticity of an entity called a demonstrator to an entity called a controller.

Said terminal device is such that it comprises a demonstrator device associated with a demonstrator entity. Said demonstrator device is interconnected with the witness device by interconnection means. It may especially take the form of logic microcircuits in a nomad object, for example the form of a microprocessor in a microprocessor-based bank card.

Said demonstrator device also comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a data-processing communications network, to the controller device associated with the controller entity. Said controller device especially takes the form of a terminal or remote server.

Said terminal device is used to execute the following steps:

At each call, the means of computation of the commitments R of the witness device compute each commitment R by applying the process specified above.

The witness device has means of transmission, hereinafter called transmission means of the witness device, to transmit all or part of each commitment R to the demonstrator device through the interconnection means. The demonstrator device also has transmission means, hereinafter called the transmission means of the demonstrator, to transmit all or part of each commitment R to the controller device, through the connection means

Steps 2 and 3: Act of Challenge d, Act of Response D

The means of reception of the challenges d of the witness device receive each challenge d coming from the controller device through the connection means between the controller device and the demonstrator device and through the interconnection means between the demonstrator device and the witness device. The means of computation of the responses D of the witness device compute the responses D from the challenges d by applying the process specified above.

The transmission means of the demonstrator transmit each response D to the controller device that carries out the check.

Case of the Proof of the Integrity of a Message

In a second embodiment variant capable of being combined with the first embodiment, the terminal device according to the invention is designed to give proof to a n entity, known as a controller, of the integrity of a message M associated with an entity known as a demonstrator. Said terminal device is such that it comprises a demonstrator device associated with the demonstrator entity, said demonstrator device being interconnected with the witness device by interconnection means. It may especially take the form of logic microcircuits in a nomad object, for example the form of a microprocessor in a microprocessor-based bank card. Said demonstrator device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a data-processing communications network, to the controller device associated with the controller entity. Said controller device especially takes the form of a terminal or remote server.

Said terminal device is used to execute the following steps:

At each call, the means of computation of the commitments R of the witness device compute each commitment R by applying the process specified above. The witness device has means of transmission, hereinafter called the transmission means of the witness device, to transmit all or part of each commitment R to the demonstrator device through the interconnection means.

Steps 2 and 3: Act of Challenge d, Act of Response D

The demonstrator device comprises computation means, hereinafter called the computation means of the demonstrator, applying a hashing function h whose arguments are the message M and all or part of each commitment R, to compute at least one token T. The demonstrator device also has transmission means, hereinafter known as the transmission means of the demonstrator device, to transmit each token T, through the connection means, to the controller device.

Said controller device, after having received the token T, produces challenges d in a number equal to the number of commitments R

The means of reception of the challenges d of the witness device receive each challenge d coming from the controller device through the interconnection means between the controller device and the demonstrator device and through the interconnection means between the demonstrator device and the witness device. The means of computation of the responses D of the witness device compute the responses D from the challenges d by applying the process specified above.

The transmission means of the demonstrator send each response D to the controller device which performs the check.

Digital Signature of a Message and Proof of its Authenticity

In a third embodiment variant, capable of being combined with either one of the first two, the terminal device according to the invention is designed to produce the digital signature of a message M, hereinafter known as the signed message, by an entity called a signing entity.

The signed message comprises:

the message M,

the challenges d and/or the commitments R,

the responses D.

Said terminal device is such that it comprises a signing device associated with the signing entity. Said signing device is interconnected with the witness device by interconnection means. It may especially take the form of logic microcircuits in a nomad object, fox example the form of a microprocessor in a microprocessor-based bank card. Said signing device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a data-processing communications network, to the controller device associated with the controller entity. Said controller device especially takes the form of a terminal or remote server.

Signing Operation:

Said terminal device is used to execute the following steps:

At each call, the means of computation of the commitments R of the witness device compute each commitment R by applying the process specified above. The witness device comprises means of transmission, hereinafter called the transmission means of the witness device, to transmit all or part of each commitment R to the signing device through the interconnection means.

The signing device comprises computation means, hereinafter called the computation means of the signing device, applying a hashing function h whose arguments are the message M and all or part of each commitment R, to compute a binary train and extract, from this binary train, challenges d whose number is equal to the number of commitments R.

The means for the reception of the challenges d receive each challenge d coming from the signing device through the interconnection means. The means for computing the responses D of the witness device compute the responses D from the challenges d by applying the process specified above. The witness device comprises transmission means, hereinafter called means of transmission of the witness device, to transmit the responses D to the signing device, through the interconnection means.

Controller Device

The invention also relates to a controller device. The controller device may especially take the form of a terminal or remote server associated with a controller entity. The controller device is designed to check:

the authenticity of an entity and/or

the integrity of a message M associated with this entity.

This proof is established by means of all or part of the following parameters or derivatives of these parameters:

m pairs of public values G 1 , G 2 , . . . G m (m being greater than or equal to 1),

a public modulus n constituted by the product of f prime factors p 1 , p 2 , . . . p f (f being greater than or equal to 2), unknown to the controller device and the associated controller entity.

Said modulus and said private and public values are related by relationships of the type

G i .Q i v ≡1.mod n or G i ≡Q i v mod n

v designating a public exponent of the type:

v=2 k

where k is a security parameter greater than 1.

Said m public values G i being the squares g i 2 of m distinct base numbers g 1 ,g 2 , . . . g m inferior to the f prime factors p 1 , p 2 , . . . p f ; said f prime factors p 1 , p 2 , . . . p f and/or said m base numbers g 1 ,g 2 , . . . g m being produced such that the following conditions are satisfied.

First Condition

According to the first condition, each of the equations:

x v ≡g i 2 mod n   (1)

can be solved in x in the ring of integers modulo n.

Second Condition

According to the second condition, in the case where G i ≡Q i v .mod n, among the m numbers q i obtained by raising Q i to the square modulo n, k−1 rank times, one of them is different from ±g i (that is to say non trivial).

According to the second condition, in the case where G i .Q i v ≡1 mod n, among the m numbers q i obtained by raising the inverse of Q i modulo n to the square modulo n, k−1 rank times, one of them is different from ±g i (that is to say non trivial).

It is pointed out here that according to a current notation ±g i represents the numbers g i and n−g i .

Third Condition

According to the third condition, among the 2 m equations:

x 2 =g i mod n   (2)

x 2 =g i mod n   (3)

at least one of them can be solved in x in the ring of integers modulo n.

Case of the Proof of the Authenticity of an Entity

In a first embodiment variant, the controller device according to the invention is designed to prove the authenticity of an entity called a demonstrator and an entity called a controller.

Said controller device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a data-processing communications network, to a demonstrator device associated with the demonstrator entity.

Said controller device is used to execute the following steps:

Steps 1 and 2: Act of Commitment R, Act of Challenge d

Said controller device also has means for the reception of all or part of the commitments R coming from the demonstrator device through the connection means.

The controller device comprises challenge production means for the production, after receiving all or part of each commitment R, of the challenges d in a number equal to the number of commitments R, each challenge d comprising m integers d i hereinafter called elementary challenges.

The controller device also comprises transmission means, hereinafter called transmission means of the controller, to transmit the challenges d to the demonstrator through the connection means.

Steps 3 and 4: Act of Response D, Act of Checking

The controller device also comprises:

means for the reception of the responses D coming from the demonstrator device, through the connection means,

computation means, hereinafter called the computation means of the controller device,

comparison means, hereinafter called the comparison means of the controller device.

First Case: the Demonstrator has Transmitted a Part of Each Commitment R.

If the reception means of the controller device have received a part of each commitment R, the computation means of the controller device, having m public values G 1 , G 2 , . . . G m , compute a reconstructed commitment R′, from each challenge d and each response D, this reconstructed commitment R′ satisfying a relationship of the type:

R′≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or a relationship of the type:

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n.

The comparison means of the controller device compare each reconstructed commitment R′ with all or part of each commitment R received.

Second Case: the Demonstrator has Transmitted the Totality of Each Commitment R

If the reception means of the controller device have received the totality of each commitment R, the computation means and the comparison means of the controller device, having m public values G 1 , G 2 , . . . G m , ascertain that each commitment R satisfies a relationship of the type:

R′≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or a relationship of the type:

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n.

Case of the Proof of the Integrity of a Message

In a second embodiment variant capable of being combined with the first, the controller device according to the invention is designed to prove the integrity of a message M associated with an entity known as a demonstrator.

Said controller device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a data-processing communications network, to a demonstrator device associated with the demonstrator entity.

Said controller device is used to execute the following steps:

Steps 1 and 2: Act of Commitment R, Act of Challenge d

Said controller device has means for the reception of tokens T coming from the demonstrator device through the connection means. The controller device has challenge production means for the production, after having received the token T, of challenges d in a number equal to the number of commitments R, each challenge d comprising m integers d i hereinafter called elementary challenges. The controller device also has transmission means, hereinafter called the transmission means of the controller, to transmit the challenges d to the demonstrator through the connection means.

Steps 3 and 4: Act of Response D, Act of Checking

Said controller device also comprises means for the reception of the responses D coming from the demonstrator device, through the connection means. Said controller device also comprises computation means, hereinafter called the computation means of the controller device, having m public values G 1 , G 2 , . . . G m , to first of all compute a reconstructed commitment R′, from each challenge d and each response D, this reconstructed commitment R′ satisfying a relationship of the type:

R′≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or a relationship of the type:

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n

and then, secondly, to compute a token T′ by applying a hashing function h having as arguments the message M and all or part of each reconstructed commitment R′.

The controller device also has comparison means, hereinafter called the comparison means of the controller device to compare the computed token T′ with the received token T.

Digital Signature of a Message and Proof of its Authenticity

In a third embodiment variant, capable of being combined with either one or the other of the first two embodiments, the controller device according to the invention is designed to prove the authenticity of the message M by checking a signed message by means of an entity called a controller.

The signed message, sent by a signing device associated with a signing entity having a hashing function h (message, R) comprises:

the message M,

the challenges d and/or the commitments R,

the responses D.

Checking Operation

Said controller device comprises connection means for its electrical, electromagnetic, optical or acoustic connection, especially through a data-processing communications network, to a signing device associated with the signing entity. Said controller device receives the signed message from the signing device, through the connection means.

The controller device comprises:

computation means, hereinafter called the computation means of the controller device,

comparison means, hereinafter called the comparison means of the controller device.

Case Where the Controller Device has Commitments R, Challenges d, Responses D:

If the controller device has commitments R, challenges d, responses D, the computation and comparison means of the controller device ascertain that the commitments R, the challenges d and the responses D satisfy relationships of the type

R≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or relationships of the type:

R≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n.

Then the computation and comparison means of the controller device ascertain that the message M, the challenges d and the commitments R satisfy the hashing function:

d=h (message, R )

Case Where the Controller Device has Challenges d and Responses D:

If the controller device has challenges d and responses D, the computation means of the controller device can, on the basis of each challenge d and each response D, compute commitments R′ satisfying relationships of the type:

R′≡G 1 d1 .G 2 d2 . . . . G m dm .D v mod n

or relationships of the type:

R′≡D v /G 1 d1 .G 2 d2 . . . . G m dm mod n

and then the computation and comparison means of the controller device ascertain that the message M and the challenges d satisfy the hashing function

d=h (message, R′ )

Case Where the Controller Device h a s Commitments R and Responses D:

If the controller device has commitments R and responses D, the computation means of the controller device apply the hashing function and compute d′ such that

d′=h (message, R )

and then the computation and comparison means of the controller device ascertain that the commitments R, the challenges d′ and the responses D satisfy relationships of the type

R≡G 1 d′1 .G 2 d′2 .G m d′m .D v mod n

or relationships of the type:

R≡D v /G 1 d′1 .G 2 d′2 .G m d′m mod n.

FIGS. 1A–1D , 2 A, 2 B, 3 A and 3 B are graphs useful in explaining the present invention.

The goals of the GQ methods are the dynamic authentication of entities and messages together with the digital signature of messages. These are methods “without transfer of knowledge”. An entity proves that it knows one or several private numbers. Another entity checks; it knows the corresponding public number or numbers. The proving entity wants to convince the checking entity without revealing the private number or numbers, in such a way as to be able to use them as many times as needed.

Each GQ method depends on a public modulus composed of secret high prime numbers. A public exponent v and a public modulus n together form a verification key <v,n> meaning “raise to the power v modulo n” and implement by means of one or several generic equations, all of the same type, direct: G≡Q v (mod n) or inverse G×Q v ≡1(mod n). The type has an effect on the operation of the calculations within the checking entity, but not within the proving entity; in fact, the security analyses confound the two types. Each generic equation linked to a public number G and a private number Q together form a pair of numbers {G,Q}. To resume, each GQ method implements one or several pairs of numbers {G,Q} for the same key <v,n>.

A classic version of the GQ method, here called GQ1, uses an RSA digital signature mechanism. The verification key <v,n> is then an RSA public key where the odd exponent v is preferably a prime number. Each GQ1 method in general uses a single pair of numbers {G,Q}: the public number G is deduced from identification data according to a format mechanism which is an integral part of the RSA digital signature technology. The private number Q or its inverse modulo n is an RSA signature for identification data. The proving entity shows its knowledge of an RSA signature of its own identification data and this proof does not reveal the signature which therefore remains secret, to be used as many times as needed.

The GQ1 methods generally implement two levels of keys: the RSA private signing key is reserved for an authority accrediting entities distinguishing themselves one from the other by identification data. Such a mechanism is said to be “identity based”. Thus, an emitter of chip cards uses his RSA private key for the emission of each card to calculate a private number Q which is inscribed as diversified private key in the card; or furthermore, a client on a network of computers uses his RSA private key when entering each session to calculate a private number Q which will be the ephemeral private key of the client during the session. The proving entities, chip cards or clients in session, know an RSA signature of their identification data; they do not know the RSA private key which, in the key hierarchy, is at the next higher level. Nonetheless, dynamic authentication of entities by GQ1 with a modulus of 768 bits at the level of an authority requires almost the same work load as a dynamic authentication of entities by RSA with a modulus of 512 bits with three prime factors at the level of each entity, which allows the proving entity to use the Chinese remainder technique by calculating a modulo result for each of the prime factors before calculating a modulo result for their product.

However, the hierarchy of keys between an authority and the accredited entities is not obligatory. One can use GQ1 with a module belonging to the proving entity, which makes it possible to use the Chinese remainder technique to reduce the work loads of the proving entity, which does not change the work load of the checking entity fundamentally, apart from the fact that a modulus at the level of the proving entity can be shorter than a modulus at the level of the authority, for example 512 bits in comparison with 768 bits.

When the entity knows the prime factors of its own modulus, why call on an RSA digital signature mechanism??

Another version of GQ methods, here called elementary GQ2, treats directly the problem of factorization of a modulus n. In this context, “directly” means “without calling for the RSA signature”. The aim of GQ2 is to reduce work loads, not only of the proving entity but also of the checking entity. The proving entity demonstrates knowledge of a breakdown of its own modulus and this proof does not reveal the breakdown which therefore remains secret, so as to be able to be used as often as needed. The security of the GQ2 protocol is equivalent to factorization of the module.

Each proving entity has its own modulus n. Each GQ2 mechanism implements a parameter k, a small number greater than 1 fixing a public exponent v=2 k , and one or several pairs of numbers {G 1 ,Q 1 } to {G m ,Q m }. Each public number G i is the square of a small number g i greater than 1 and called a “base number”. All the proving entities can use the same public number or numbers G 1 to G m . The factorization of the modulus n and the private number or numbers Q 1 to Q m are then at the same level in the key hierarchy. Each set of elementary GQ2 keys is defined by two necessary and sufficient conditions:

for each base number, neither of the two equations x 2 ≡±g i (mod n) does not have a solution in x in the ring of integers modulo n, that is to say that the numbers ±g i are two non-quadratic residues modulo n.

for each base number, the equation x v ≡g i 2 (mod n) where v=2 k has solutions in x in the ring of integers modulo n. The private number Qi or its inverse modulo n is any one of these solutions.

Taking into account the second condition, in order that the numbers ±g i are two non-quadratic residues modulo n, the modulus n must comprise at least two prime factors congruent to 3 (mod 4) relative to which the Legendre symbol of g i differs. Consequently, any modulus composed of prime factors of which none or a single one is congruent to 3 (mod 4) does not allow a set of elementary GQ2 keys to be established, which privileges the prime factors congruent to 3 (mod 4). Thus, by taking high prime numbers at random, it appears that only half are congruent to 3 (mod 4) and half to 1 (mod 4). As a result, many RSA models in use cannot establish a set of elementary GQ2 keys.

Here we introduce the sets of generalised GQ2 keys to overcome this limitation in order to be able to use GQ2 technology with any modulus whatsoever, and in particular with any RSA modulus whatsoever: they depend on two necessary and sufficient principles.

The first principle reproduces the second elementary GQ2 condition:

For each base number g 1 to g m , the equation x v ≡g i 2 (mod n) where v=2 k has solutions in x in the ring of integers modulo n.

Because the private number Q or its inverse modulo n is a solution to the equation, successive squares k−1 modulo n transform it into a number q i which is a square root of G i in the ring of integers modulo n. Depending on whether the number q i is equal to one of the two numbers g i or n−g i , or different from the two numbers g i and n−g i , it is said that it is trivial or not. When a number q i is non trivial, n which divides q i 2 −g i 2 does not divide either q i −g i or q i +g i . Any non trivial number q thus reveals a breakdown of the modulus n.

n=pgcd ( n,q i −g i ) xpgcd ( n,q i +g i )

The second principle widens the first elementary GQ2 condition:

among the numbers q 1 to q m , at least one number q i is non trivial.

It is to be noted that if a number q+ exists while the numbers ±g i are two non-quadratic residues in the ring of integers modulo n, the number q i is manifestly non trivial. Thus, the set of elementary GQ2 keys are certainly part of the set of generalised GQ2 keys which make it possible to use any modulus whatsoever, that is to say any composition of high prime numbers indifferently congruent to 3 or to 1 (mod 4) at least two of which are distinct. On the other hand, many sets of generalised GQ2 keys are not sets of elementary GQ2 keys. Each set of generalised GQ2 keys is in accordance with one of the following cases:

when the 2×m numbers ±g 1 to ±g m are all non-quadratic residues, this is a set of elementary GQ2 keys.

when among the 2×m numbers ±g 1 to ±g m , there is at least one quadratic residue, this is not a set of elementary GQ2 keys, it is what is known here as a set of complementary GQ2 keys.

The present invention relates to the sets of complementary GQ2 keys, by definition these sets of generalised GQ2 keys not being elementary. Besides the two preceding principles, such a set must satisfy a third principle.

among the 2×m numbers ±g 1 to ±g m , there is at least one quadratic residue.

In order to assess the problem and understand the solution we provide, that is to say the invention, let us first of all analyse the breakdown of the modulus n revealed by a non trivial number q, and then recall the Chinese remainder technique, and then the notion of rank in a Galois field CG(p); and next, study the functions “raise to the square” in CG(p) and “take a square root” of a quadratic residue in CG(p); and finally, analyse the applicability of the three principles stated above.

Analysis of the Breakdowns of the Module:

Just as the modulus n is broken down into f prime factors p i to p f , the ring of integers modulo n is broken down into f Galois fields CG(p 1 ) to CG(p f ). In each field, there are two unit square roots, that is ±1. In the ring, there are thus 2 f unit square roots. Each private number Q i to Q m defines a number Δ i =q i /g i (mod n) which is one of these 2 f unit square roots in the ring; in other words, n divides Δi 2 −1.

when q i is trivial, that is to say Δ i =±1, n divides Δ i −1, or Δ i +1 and therefore Δ i does not reveal the breakdown of the modulus n.

when q i is non trivial, that is to say Δ i Δ±1, n does not divide either Δ i −1 or Δ i +1 and thus Δ reveals a breakdown, n=pgcd(n, Δ i −1)xpgcd(n, Δ i +1), resulting from the value of Δ i in each field: the prime factor or factors dividing Δ i −1 on the one hand, this or these dividing Δ i +1 on the other.

Examination of the rules of multiplicative composition of the numbers q. Two numbers {q 1 ,q 2 } give a composite number q 1 ×q 2 (mod n).

when q 1 is non trivial and q 2 is trivial, the composite number q 1 ×q 2 (mod n) is non trivial; it reveals the same breakdown as q 1 .

when q 1 and q 2 are non trivial and Δ 1 =±Δ 2 The composite number q 1 ×q 2 (mod n) is trivial; it does not reveal any breakdown.

when q 1 and q 2 are non trivial and Δ1 ≠±Δ2, the composite number q 1 ×q 2 (mod n) is non trivial; it reveals a third breakdown.

Three numbers {q 1 ,q 2 ,q 3 } give four composite numbers {q 1 ×q 2 , q 1 ×q 3 , q 2 ×q 3 , q 1 ×q 2 ×q 3 (mod n)}, that is a total of seven numbers; m numbers thus provide 2 m −m−1 composite numbers, that is a total of 2 m −1 numbers.

We shall now consider a set of generalised GQ2 keys comprising i base numbers g 1 to g i and i private numbers Q 1 to Q i giving i numbers q 1 to q i and therefore i numbers Δ 1 to Δ i which are the unit roots. Let us try to take into account another base number g i+1 by a private number Q i+1 giving a number q i+1 and thus a root Δ i+1 .

The total of the 2 i+1 −1 numbers comprises as many non trivial numbers in each of the following cases.

the root Δi+ 1 is trivial and at least one root Δ1 to Δ i is non trivial.

The root Δ i+1 is non trivial and figures among the 2×i roots ±Δ 1 and ±Δ i .

In the case where the root Δi+1 is non trivial and does not figure among the 2×i roots ±Δ 1 to ±Δ i , each composite number where q i+1 figures is non trivial.

Consequently, when among the m numbers q 1 to q m , at least one is non trivial, more than half the total of the 2 m −1 numbers are non trivial.

By definition, it is said that l<f non trivial numbers {q 1 ,q 2 , . . . q l } are independent relative to the modulus n when each of the 2 l -l−1 corresponding composite numbers is non trivial, that is to say that, in total, the 2 l −1 numbers are all non trivial. Each of these 2 l −1 numbers thus reveals a different breakdown of the modulus n.

When the f prime factors are distinct, there are 2 f-1 −1 breakdowns of the modulus n. Thus, if f−1 numbers q are independent, there is a bi-univocal correspondence between the 2 f-1 −1 breakdowns and a total of 2 f-1 −1 numbers comprising the f−1 independent numbers and the 2 f-1 −f corresponding composite numbers.

Chinese Remainders

Either two numbers a and b, prime numbers between themselves such as 0<a<b, and two numbers X a from 0 to a−1 and X b from 0 to b−1; it concerns the determination of the unique number X from 0 to axb−1 such that X a ≡X(mod a) and X b ≡X(mod b). The number x≡{b(mod a)} −1 (mod a) is the Chinese remainders parameter. The elementary Chinese remainders operation is given below:

x≡X b (mod a)

y=X a −x; if y is negative, replace y by y+a

z≡áxy(mod a)

X=zxb+X b

To resume, one writes: X=Chinese Remainders (X a ,X b ).

When f prime factors are arranged in increasing order, from the smallest p 1 to the biggest p f , the Chinese remainder parameters can be the following (there is one less than the prime factors, that is to say f−1).

The first parameter is x≡(p 2 (mod p 1 )) −1 (mod p 1 ).

The second parameter is β≡(p 1 ×p 2 (mod p 3 )) −1 (mod p 3 ).

The i-th parameter is λ≡(p 1 × . . . p i−1 (mod p i )) −1 (mod p i ).

And so on.

In f−1 elementary operations, one establishes a number X from 0 to n−1 starting from any set of f components from X 1 to X f with X j from 0 to p j −1:

a first result (mod p 1 ×p 2 ) with the first parameter,

then a second result (mod p 1 ×p 2 ×p 3 ) with the second parameter,

until the final result (mod n=p 1 ×p 2 × . . . p f ) with the last parameter.

To resume, given the prime factors p 1 to p f , each element of the ring of integers modulo n has two equivalent representations:

f numbers X 1 to X f , a prime factor component: X j ≡X(mod p j ),

a number X from 0 to n−1, X=Chinese remainders (X 1 ,X 2 , . . . X f ).

Rank of numbers in CG(p)—Let p be an odd prime number and a a number smaller than p i.e. 0<a<p. By definition, the rank of a with respect to p is the period of the sequence {X} defined by {x i =a; then, for i≧1, x i+1 ≡a×x i (mod p)}. By applying the Fermat theorem we obtain: x i+p ≡a p ×x i ≡a×x i ≡x i+1 (mod p). Therefore, the rank of a number a with respect to a prime number p is p−1 or a divider of p−1.

For example, when (p−1)/2 is an odd prime number p′, the Galois field CG(p) includes a number of rank 1: this is 1, a number of rank 2: this is −1, p′−1 numbers of rank p′ and p′−1 numbers of rank 2×p′=p−1. In CG(p), any number of rank p−1 is a “generator”. The name is due to the fact that the successive powers of a generator in CG(p), i.e. the terms of the sequence {X} for indices from 1 to p′−1, form a permutation of all the non-zero elements of CG(p).

Let y be a generator of CG(p). Let us evaluate the rank of the number y′ (mod y) according to i and p−1. When i is prime with p−1, this is p−1. When i divides p−1 this is (p−1)/i. In all cases, this is (p−1)/lgcd(p−1,i) (lgcd=largest common divisor).

By definition, Euler's function φ(n) is the number of numbers smaller than n and prime with n. In CG(p), there are φ(p−1)generators.

As an illustration, understanding the bases of the RSA is facilitated with the rank. Module n is the product of f prime factors p−1 to p−f, with f≧2. For each prime factor p i from p 1 to p f the public exponent e should be prime with p j −1. Now, key <e,p j > observes the rank of the elements of CG(p j ): it permutates the elements of CG(p j ); there exists a number d j , generally as small as possible, such that p −1 divides e×d j−1 . The key <d j , p j > inverts the permutation of the elements of CG(p j ). These f permutations, one in each field CG(p 1 ) to CG(p f ), are expressed in the ring of integers modulo n by the RSA permutation summarized by the public key <e, n>. There exists a number d, generally as small as possible, such that the smallest common multiple (scm) of (P 1- , P 2−1 , . . . p f−1 ) divides d×e−1. For each prime factor p j from p 1 to p f , we have d j ≡d (mod p j-1 ). The RSA permutation summarized by the public key <e, n> is inverted by the private key <d, n>.

Squares in CG(p)—Let us define a number t such that p−1 is dividable by 2 t , but not by 2 t−1 . Each large prime number appears in one and only one category: t=1, t=2, t=3, t=4, and so forth. If a sufficiently large number of successive prime numbers are considered, about one out of two appears in the first category where p is congruent to 3 (mod 4), one out of four in the second one, where p is congruent to 5 (mod 8), one out of height in the third one, where p is congruent to 9 (mod 16), one out of sixteen in the fourth one, where p is congruent to 17 (mod 32), and so forth; on the average, one out of 2 t appears in the nth category where p is congruent to 2 t+1 (mod 2 t+1 ).

Because numbers x and p−x have the same square in CG(p), key <2,p> does not permutate CG(p). The function “take the square” in CG(p) may be represented by an orientated graph wherein each non-zero element of the field finds its place. Let us analyze the structure of the graph into branches and cycles according to the parity of the rank of each element.

The zero element is set. This is 0. Rank is not defined for the zero element to which no other element is related; the zero element is isolated.

The unit element is set. This is 1, the only element of rank 1. All the roots of unity in CG(p) are located in the branch related to 1. Let y be a non-quadratic residue of CG(p), any residue; key <p−1)2 t , p> transforms y into a primitive 2 t−1 th root of −1 referenced as b; indeed, we have y (p-1)/2 ≡−1(mod p). Therefore, in CG(p), the powers of b for exponents from 1 to 2 t−1 , are the 2 t−1 roots of unity other than 1: they make up the branch related to 1.

The square of any element of even rank is another element the rank of which is divided by two. Therefore, each element of even rank is placed in a branch; each branch includes a rank number dividable by two, but not by four, next, if t≧2, two rank numbers dividable by four but not by eight, next, if t≧3, four rank numbers dividable by eight but not by sixteen, next, if t≧4, eight rank numbers dividable by sixteen but not by 32, and so forth. All the branches are similar to the branch related to 1; the 2 t−1 leaves of each branch are non-quadratic residues; each branch includes 2 t−1 elements and is related to an element of odd rank; there are (p−1)/2 t branches which are all of the same length t.

The square of any element of odd rank other than the unit element is another element having the same rank. Key <2,p> permutates the set of (p−1)/2 t elements of odd rank. The permutation is factorized into permutation cycles. The number of cycles depends on the factorization of (p−1)2 t . For each divider p′ of (p−1)/2 t , there is a cycle including the φ(p′) elements of rank p′. Let us recall that by definition, Euler's function φ(p′) is the number of numbers smaller than p′ and prime with p′. For example, when p′ equals (p−1)/2 t , is prime, the p′−1 numbers of rank p′ form a large permutation cycle.

FIGS. 1A–1D each illustrate a graph fragment for p congruent to 3 (mod 4), 5 (mod 8), 9 (mod 6) and 17 (mod 32), respectively.

The leaves on the branches are illustrated by white circles; these are non-quadratic residues.

The nodes in the branches are illustrated by grey circles; these are quadratic elements of even rank.

The nodes in the cycles are illustrated as black circles; these are quadratic elements of even rank.

Square roots in CG(p)—Knowing that a is a quadratic residue of CG(p), let us see how to calculate a solution to the equation x 2 ≡a (mod p) i.e. “take a square root” in CG(p). Of course, there are many ways for obtaining the same results; pages 31–36 of the book of Henri Cohen, a Course in Computation Algebraic Number Theory , published in 1993 by Springer in Berlin as volume 138 of the Graduate Texts in Mathematics series (GTM 138), may be consulted.

The number s=(p−1+2 t )/2 t+1 provides a key <s, p>) which is:

<(p+1)/4, p> when p is congruent to 3 (mod 4),

<(p+3)/8, p> when p is congruent to 5 (mod 8),

<(p+7)/16, p> when p is congruent to 9 (mod 16),

<(p+15)/32, p> when p is congruent to 17 (mod 32), and so forth.

Key <s, p> transforms any element of a cycle into the previous element in the cycle. When a is of even rank, it is the solution of odd rank, we name it w. Indeed, in CG(p), w 2 /a is equal to a to the power of (2×(p−1+2 t )/<2 t+1 )−1=(p−1)/2 t . The other solution is of even rank; this is p−w.

Generally, the key <s, p> transforms any quadratic residue a in a first approximation, into a solution which we name r. As a is a quadratic residue, the key <2 t−1 , p> certainly transforms r 2 /a into 1. To approach a square root of a, let us take the power 2 t−2 of r 2 /a (mod p) in order to obtain +1 or −1. The new approximation remains r if the result is +1 or else it becomes b×r (mod p) if the result is −1, knowing that p refers to any primitive 2 t th root of 1 in the field CG(p). Therefore, the key <2 t−2 , p> transforms the new approximation into 1. It may still be approached by using the key <2 t−3 , p> and by multiplying with b2 (mod p) if necessary, and so forth.

The following algorithm solves the equation. It uses numbers a, b, p, r and t, as defined above and two variables: c represents the successive corrections and w the successive approximations. At the beginning of the algorithm, c=b and w=r. At the end of the calculation, the two solutions are w and p−w.

For i from t−2 to 1, repeat the following sequence:

Apply key <2 t , p> to number w 3 /a (mod p) in order to obtain +1 or −1.

When −1 is obtained, replace w by w×c (mod p).

Replace c by c2 (mod p).

Applicability of the principles—By definition we state that a parameter k, a base number g and a prime factor p are compatible when the equation x v ≡g 2 (mod p) where exponent v is 2 k , has solutions in x in the field CG(p). Numbers k and g are small and larger than 1. Number p is a large prime number.

When t=1, i.e. p≡3 (mod 4), the equation has two solutions.

When t=2, i.e. p≡=5 (mod 8), according to the Legendre symbol of g with respect to p, the equation has four solutions if (g|p)=+1; it does not have any solution if (g|p)=−1.

When t>2, i.e. p≡1 (mod 8), let u be the number such that 2 lt divides the rank of the public number G=g 2 with respect to p, but such that 2 u+1 does not divide it; therefore, u is equal to one of the numbers from 0 to t−1. The equation has no solution if u>0 and k+u>t; it has 2 k solutions if k+u≦t; it has 2 t solutions if u=0 and k>t.

Therefore, there are two types of compatibility according to whether G is in a cycle, or else in a suitable position in a branch.

When G is in a cycle, i.e. u=0, regardless of the value of k, there is a solution of odd rank in the cycle and solutions of even rank disseminated in α=min(k, t) consecutive branches related to the cycle, i.e. 2 α solutions in all. FIG. 2A illustrates this case with k≧t=3, i.e. a prime factor congruent to 9 (mod 16), which imposes that u=0.

When G is in a suitable position in a branch, i.e. u>0 and u+k≦t, there are 2 k solutions, all of even rank and in the branch. FIG. 2B illustrates this case.

Given a parameter k, there are therefore two types of prime factors according to whether the value of t is less than k or else larger than or equal to k.

For any prime factor p j , such as t<k, each G i should be in a cycle, and there is no solution in the branch related to G i . Let us define a number Δ i,j which is +1 or −1 according to whether g i or −g i is in the cycle. There is n o choice for any of the m numbers Δ 1,j to Δ m,j . FIG. 3A illustrates a case with t<k: G i is in a cycle with a prime factor p j congruent to 9 (mod 16), i.e. u=0, t=3 with k>3.

For any prime factor p j such that t≧k, each G i should be such that u+k≦t, i.e., either in a cycle with u=0 or else, in a suitable position in a branch with 1≦u≦t−k. Let us define a number Δ i,j which is +1 or −1 according to whether Q ij is in the portion of the graph related to g i or to −g i . There is a choice for each of the m numbers Δ 1,j to Δ m,j ; each number Δ i,j may individually be switched from one value to the other. FIG. 3B illustrates a case when t≧k: G i is in a branch with a prime factor p j congruent to 17 (mod 32), i.e., u=1, t=4 with k=3.

Each set of f components {Δ i,j . . . Δ i,f } is a square root of unity in CG(p j ). This root is trivial or not according to whether the f components are equal or not; we then state that the set of f components is constant or variable, which expresses the fact that the number q i is either trivial or not. Therefore, when a number q i is non-trivial, the set of f components {Δ i,l . . . Δ i,f } summarizes a factorization of the module. It is therefore possible to test the principles before calculating the private components Q i,j .

When a public number G i is in a cycle for a prime factor p j , the number Δ i,j is +1 or −1, according to whether g i or −g i is in the cycle. When p j ≡3 (mod 4), this is Legendre's symbol: Δ i,j =(g i |p j )

When a public number G i is in a suitable position in a branch for a prime factor p j , the value to be given to Δ i,j may be determined by computing the private component Q i, .

Production of sets of keys—Given a parameter k, there are two strategies.

Either the generator requires f prime factors in order to determine m base numbers. The first prime numbers: 2, 3, 5, 7, . . . are examined for evaluating their compatibility with each of the f large prime factors p 1 to p f . Although g=2 is not compatible with p≡5 (mod 8), 2 may enter into the composition of a base number. Indeed, when two numbers are in a similar position in a branch, their product is closer to the cycle, exactly as a square brings the cycle closer. A base number may thereby be obtained by composing the numbers which are not appropriate individually.

Or the generator requires m base numbers and characteristics of the module such that a bit size (for example, 512, 768, 1024, 1536, 2048) and a number of bits successive to 1 with strong weights (for example, 1, 8, 16, 24, 32) in order to determine f>2 prime factors. Noted as G 1 , G 2 , . . . G m , the base numbers generally appear among the first prime numbers: 2, 3, 5, 7, 11 . . . or else these are combinations of the first prime numbers. Unless indicated otherwise, these are the first m prime numbers; G 1 =2, G 2 =3, G 3 =5, G 4 =7, . . . Let us note that p≡5 (mod 8), is not compatible with g=2. Module n will be the product of f prime factors with close sizes, i.e. the size assigned to the module divided by f.

First principle—The parameter k, each prime factor from p 1 to p f and each base number g from g 1 to g m should be compatible. Let us define a number h such as 2 h divides the rank of g with respect to p, whereas 2 h+1 does not divide it. To compute the number h, the following procedure uses Legendre's symbol (g|p) and a number b, a primitive 2 t th root of unity in CG(p).

If (g|p)=+1 with t=1, return “h=0”.

If (g|p)=+1 with t>1, apply the key <(p−1+2 t )/2 t+1 , p> to G in order to obtain a result called w.

If w=+g, return “h=0”.

If w=p−g, return “h=1”.

Else, set c to b and for i from t−1 to 2,

Apply key <2 i , p> to w|g (mod p) in order to obtain ±1,

If −1, set h to i and replace w with w×c (mod p),

Replace c with c2 (mod p).

Return “value of h from 2 to t−1”.

If (g|p)=−1, return “h=t”.

Let us recall that k, g and p are incompatible when u>0 with k+u>t; they are compatible when h=0 or 1, regardless of the value of k, and equally when k>1 with k+h≦t+1.

Second principle—The three following procedures correspond to different implementations of the second principle. In certain implementations, the second principle may be reinforced to the point of requiring that each number q 1 to q m be not trivial. The role of the base numbers is then balanced; balancing or not the second principle has an effect of certain aspects of the demonstration of the security of the scheme. Finally, when there are f>2 distinct prime factors, among the m numbers {q 1 . . . q m }, it may be required that there be at least one subset of f−1 independent numbers.

The three procedures use m×f numbers δ i,j defined as follows.

When p j is such that t<k, for i from 1 to m, δ i,j =Δ i,j , i.e. +1 if h i,j =0 and −1 if h i,j =1.

When p j is such that t≧k, for i from 1 to m, δ i,j =0, which means that Δ 1,j to Δ m,j may be selected according to the second principle.

A first procedure ascertains that at least one set {δ i,1 . . . δ i,f } is variable or zero, i.e. that at least one number q 1 to q m is non-trivial or may be chosen as non-trivial.

For i from 1 to m and j from 1 to f,

if δ i,j =0 or ≠δ i,1 , return “success”.

Return “failure”.

A second procedure ascertains that each set {δ i,1 . . . δ i,f } is variable or zero, i.e. that each number q 1 to q m is non-trivial or may be chosen as non-trivial.

For i from 1 to m,

For j from 1 to f,

if δ i,j =0 or ≠δ i,1 , skip to the next value of i,

Return “failure”.

Return “success”.

A third procedure ascertains that each pair of prime factors p j1 and p j2 , with 1≦ j1 ≦j 2 ≦f, there is at least one set {δ i,1 . . . δ i,j } where δ i,j1 is zero or different from δ i,j2 . It obviously fails when m is smaller than f−1. When it succeeds, among the m numbers q 1 to q m , there is at least one set of independent f−1 numbers with respect to the f prime factors.

For j 1 from 1 to f−1 and for j 2 from j 1 +1 to f,

For i from 1 to m,

If δ i,j1 =0 or ≠δ i,j2 , skip to the next values of j 1 and j 2 ,

Return “failure”.

Return “success”.

When a procedure fails, the generator of GQ2 key sets follows its strategy chosen from the two possible strategies:

Change one of the m base numbers while keeping the f prime factors,

Change one of the f prime factors while keeping the m base numbers.

Third principle—The following procedure determines whether the set of generalized GQ2 keys, either during production or already produced, is

either a set of elementary GQ2 keys, i.e. that the 2×m numbers ±g 1 to ±g m are all non-quadratic residues,

or else, a set of complementary GQ2 keys, i.e. that among the 2×m numbers ±g 1 to ±g m , there is at least one quadratic residue.

The procedure uses both Legendre's symbols (g i |p j ) and (−g i |p j ) for i from 1 to m and for j from 1 to f.

For i from 1 to m,

For j from 1 to f,

If (g i |p js)=− 1, skip to the next value of i.

Return “set of complementary GQ2 keys”.

For j from 1 to f,

If (g i |p i )=−1, skip to the next value of i.

Return “set of complementary GK2 keys”.

Return “set of elementary GK2 keys”.

Private components—For an equation of the direct type: x v ≡g i 2 (mod p j ) the following computation establishes all the possible values for the private component Q i,j . The two simplest and most current cases, i.e. t=1 and t=2, are followed by the more complex case, i.e. t>2.

For t=1, i.e. p j ≡3 (mod 4), the key <(p j +1)/4,p j > provides the quadratic square root of any quadratic residue in CG(p j ). From this, a number is derived

s j ≡((p j +1)/4) k (mod (p j −1)/2), which gives a key <s j , p j > transforming G i into w≡G i sj (mod p j ). Q i,j is equal to w or p j −w.

For t=2, i.e. p j ≡5 (mod 8), the key <(p j +3)/8, p j > provides the square root of odd rank for any element of odd rank in CG(p j ). From this, a number is derived s j ≡((p j +3)18) k (mod (p j −1)/4), which gives a key <s j , p j > transforming G i into w≡G i sj (mod p j ). Let us note that z≡2 (pj−1)/4 (mode p j ) is a square root of −1 because 2 is a non-quadratic residue in CG (p j ). Q i,j is either equal to w or to p j −w or else to w′≡w×z (mod p j ) or p j −w′.

For p j 2 t +1 (mod 2 t+1 ) with t>2, key <(p j −1+2 t )/2 t+1 , p j > provides the square root of odd rank of any element of odd rank. The compatibility test between k, g and p gave the value of h, next that of u.

When G i is in a cycle (u=0, regardless of the value of k), a number is established,

s j ≡((p j −1+2 t )/2 t+l ) k (mod (p j −1)/2 t ). Key <s j , p j >transforms G i into the solution of odd rank w≡G i sj (mod p j ). There are solutions of even rank distributed in min(k, t) consecutive branches related to the cycle, let us say, in α branches. Q i,j is equal to the product of w by any of the 2 α th roots of unity in CG(p j ).

When G j is in a suitable position in a branch (u>0, u+k≦t), all the solutions are in the same branch as G j , a branch related to a cycle by the 2 lt th power of the number G i . A number is established as

s j ≡((p j −1+2 t )/2 t+1 ) k+u (mod (p j −1)/2 t .

Key <s j , p j > transforms the 2 u th power of G i into a number of odd rank w. The set of products of w with the primitive 2 k+u th roots of unity in CG(p j ) comprises the 2 k values of Q i,j .

When p j is such that t≧k, as number b j is a primitive 2 t th root of unity in CG(p j ), the 2 t−u th power of b j in CG(p j ) exists; this is a primitive 2 k th root of unity. The value of number Δ i,j may be switched by multiplying Q i,j by a primitive 2 k th root of unity.

For an equation of the inverse type: 1≡x v ×g i 2 (mod p j ), it is sufficient to replace number s j with ((p j −1)/2 t )−s j in the key <s j , p j >, which amounts to inverting the value of Q i,j in CG(p j ).

Example of a Set of Keys with Two Prime Factors Congruent to 5 (mod 8)

p 1 =E6C83BF428689AF8C35E07EDD06F9B39A659829A58B79CD89 4C435C95F32BF25

p 2 =11BF8A68A0817BFCC00F15731C8B70CEF9204A34133A0DEF8 62829B2EEA74873D

n p 1 ×p 2 =FFFF8263434F173D0F2E76B32D904F56F4A5A6A50008C43D32 B650E9AB9AAD2EB713CD4F9A97C4 DBDA3828A3954F296458 D5F42C0126F5BD6B05478BEOA80ED1

Here are the Legendre symbols of the very first prime numbers.

(2 |p 1 )=−1; (3 |p 1 )=−1; (5 |p 1 )=+1; (7 |p 1 )=−1;

(1 |p 1 )=+1; (13 |p 1 )=−1; (17 |p 1 )=+1;

In CG(p 1 ), the rank is odd for −5, −11 and 17.

(2 |p 2 )=−1; (3 |p 2 )=+1; (5 |p 2 )=+1; (7 |p 2 )=+1;

(11 |p 2 )=+1; (13 |p 2 )=−1; (17 |p 2 )=−1;

In CG(p 2 ), the rank is odd for 3, −5, 7 and 11.

Carmichael's function is

λ(n)=scm((p 1 −1)/4, (p 2 −1)/4).

λ(n)=33331A13DA4304A5CFD617BD6F83431164212154 3334F40C3D57A9C8558555D5BDAA2EF6AED17B9E3794F51A6 5A1B37239B 18FA9B0F618627D8C7E1D8499C1B

With k=9, the number σ≡λ(n)−((1+λ(n))/2) 9 (mod λ(n)) is used as a private exponent, in order to use the generic equations of the inverse type.

σ=01E66577BC997CAC273671E187A35EFD25373ABC9FE6770E 7446C0CCEF2C72AF6E89D0BE277CC6165F1007187AC58028BD 2416D4CC 1121E7A7A8B6AE186BB4B0

Numbers 2, 3, 7, 13 and 17 are not suitable as base numbers.

Key <σ,n> transforms g 1 =5 into a private number Q 1 which does not shows any factorization. Indeed, in both fields, −5 is on a cycle.

Q 1 =818C23AF3DE333FAECE88A71C4591A70553F91D6C0DD5538E C0F2AAF909B5BDAD491FD8BF13F18E3DA3774CCE19D0097BC 4BD47C5D6EOE7EBF6D89FE3DC5176C

Key <σ,n> transforms g 2 =11 into a private number Q 2 which shows a factorization. Indeed, 11 is not in the same position in both fields.

Q 2 =25F9AFDF177993BE8652CE6E2C728AF31B6D66154D3935AC53 5196B07C 19080DC962E4E86ACF40D01FDC454F2565454F2900 50DA052089EEC96A1B7DEB92CCA7

Key <σ,n>transforms g 3 =21=3×7 into a private number Q 3 which shows a factorization.

Q 3=78 A8A2F30FEB4A5233BC05541AF7B684C2406415EA1DD 67D 18A0459A1254121E95D5CAD8A1FE3ECFE0685C96CC7EE86 167D99532B3A96B6BF9D93CAF8D4F6AF0

Key <σ,n> transforms g 4 =26=2×13 into a private number Q 4 which shows a factorization.

Q 4 =6F1748A6280A200C38824CA34C939F97DD2941DAD300030E 481B738C62BF8C673731514D1978AF5655FE493D659514A6CE 897AB76C01E50B5488C5DAD 12332E5

The private key may further be represented by both prime factors, the parameter of the Chinese remainders and eight private components. α≡(p 2 (mod p 1 )) −1 (mod p 1 )=ADE4E77B703F5FDEAC5B9AAE825D 649E06692D15FBFODF737B15DC4D012FD1D

Q 1,1 ≡Q 1 (mod p 1 )=7751 AEE918A8F5CE44AD73D613A4F465E06C6F 9AF4D229949C74DD6C18D76FAF

Q 1,2 ≡Q 1 (mod p 2 )=A9EB5FA1B2A981AA64CF88C382923 DB64376F 5FD48152C08EEB6114F31B7665F

Q 2,1 ≡Q 2 (mod p 1 )=D5A7D33C5FB75A033F2FOE8B20274B957FA3 4004ABB2C2AC1CA3F5320C5A9049

Q 2,2 ≡Q 2 (mod p 2 )=76C9F5EFD066C73A2B5CE9758 DB512DFC011 F5B5AF7DA8D39A961CC876F2DD8F

Q 3,1 ≡Q 3 (mod p 1 )=2FEC0DC2DCA5BA7290B27BC8CC85C938A514 B8F5CFD55820A174FB5E6DF7B883

Q 3,2 ≡Q 3 (mod p 2 )=010D488E6BOA38A1CC406CEE0D55DE59 013389D8549DE493413F34604A160C1369

Q 4,2 ≡Q 4 (mod p 1 )=A2B32026B6F82B6959566FADD9517 DB8ED852 4652145EE159DF3DCOC61FE3617

Q 4,2 ≡Q 4 (mod p 2 )=011A3BB9B607F0BD71BBE25F52B305C22489 9E5F1F8CDC2FE0D8F9FF62B3C9860F

Polymorphism of the private key GQ2—The different possible representations of the private key GQ2 prove to be equivalent: they all amount to knowing the factorization of the module n which is the actual GK2 private key. The representation of the GQ2 private key has an effect on the progress of the computations within the demonstrating entity hut not within the controlling entity. Here are the three main representations which are possible for the GQ2 private key. 1) The conventional representation of GQ private keys consists in storing m private numbers Q i and the public checking key <v, n>; for the GQ2 schemes, this representation is in competition with the following two. 2) The optimum representation in terms of work loads consists in storing the parameter k, the f prime factors p j , the m×f private components Q i,j and the f−1 parameters of the Chinese remainders. 3) The optimum representation in terms of private key size consists in storing the parameter k, the m base numbers g i and the f prime factors p j , and then in starting each use by establishing either m private numbers Q i and the module n so that it amounts to the first representation, or m×f private components Q i,j and the f−1 parameters of the Chinese remainders so that it amounts to the second representation.

Because the security of the dynamic authentication mechanism or of the digital signature is equivalent to knowing a factorization of the module, with the GQ2 schemes, it is not possible to distinguish two entities using the same module simply. Generally, each proving entity has its own GQ2 module. However, GQ2 modules with four prime factors may be specified, two of which are known to an entity and the other two to another one.

Dynamic authentication—The dynamic authentication mechanism is for proving to an entity called a controller, the authenticity of another entity called a demonstrator as well as the authenticity of a possible associated message M, so that the controller ascertains that it is actually dealing with the demonstrator and optionally that itself and the demonstrator are speaking of the same message M. The associated message M is optional, which means it may be empty.

The dynamic authentication mechanism is a sequence of four acts: an engagement act, a challenge act, a response act and a checking act. The demonstrator plays the engagement and response acts. The controller plays the challenge and checking acts.

Within the demonstrator, a witness may be isolated, in order to isolate the most sensitive parameters and functions of the demonstrator, i.e. the production of commitments and responses. The witness has the parameter k and the GQ2 private key, i.e. the factorization of the module n according to one of the three representations mentioned above: • the f prime factors and the m base numbers, • the m×f private components, the f prime factors and the f−1 parameters of the Chinese remainders, • the m private numbers and the module n.

The witness may correspond to a particular embodiment, for example • a chip card connected to a PC forming together the demonstrator or even • programs particularly protected within a PC or even • programs particularly protected within a chip card. The thereby isolated witness is similar to the witness defined hereafter within the signing entity. Upon each execution of the mechanism, the witness produces one or more commitments R, and then as many responses D to as many challenges d. Each set {R, d, D} forms a GQ2 triplet.

In addition to it comprising the witness, the demonstrator also has a hashing function and a message M, if necessary.

The controller has the module n, for example, from a directory of public keys or even from a certificate of public keys; if necessary, it also has the same hashing function and a message M′. The GQ2 public parameters, i.e. numbers k, m and g 1 to g m may be provided to the controller by the demonstrator. The controller is able to reconstruct a commitment R′ from any challenge d and from any response D. Parameters k and m inform the controller. Unless indicated otherwise, the m base numbers from g 1 to g m are the first m prime numbers. Each challenge d 1 should include m elementary challenges referenced from d l to d m : one per base number. Each elementary challenge from d l to d m is a number from 0 to 2 k-1 −1 (numbers from v/2 to v−1 are not used). Typically, each challenge is coded by m times k−1 bits (and not m times k bits). For example, with k=5 and m=4 base numbers, 5, 11, 21 and 26, each challenge includes 16 bits transmitted on four quartets. When the possible (k−1)×m challenges are equally probable, the number (k−1)×m determines the security brought by each GQ2 triplet: an impostor who by definition, does not know the factorization of the module n, has one chance of success out of 2 (k−1)×m, exactly. When(k− 1)×m is from 15 to 20, one triplet is sufficient for reasonably ensuring dynamic authentication. In order to achieve any level of security, triplets may be produced in parallel; they may also be produced in sequence, i.e. repeat the execution of the mechanism.

1) The act of commitment comprises the following operations.

When the witness does not use the Chinese remainders, it has the parameter k, the m private numbers from Q 1 to Q m and module n; it randomly and privately picks one or more random numbers r (0<r<n); and then by successively squaring them k times (mod n), it transforms each random number r into a commitment R.

R≡r v (mod n )

Here is an example with the previous set of keys without the Chinese remainders.

r=5E94B894AC24AF843131F437C1B1797EF562CFA53AB8AD426C 1AC016F1C89CFDA13120719477C3E2FB4B4566088E10EF9C010E 8F09C60D981512198126091996

R 6BBF9FFA5D509778D0F93AE074D36A07D95FFC38F70C8D7E33 00EBF234FA0BC20A95152A8FB73DE81FAEE5BF4FD3EB7F5EE3E3 6D7068D083EF7C93F6FDDF673A

When the witness uses the Chinese remainders, it has the parameter k, the first f prime factors from p 1 to p f , f−1 parameters of Chinese remainders and m×f private components Q i,j ; it randomly and privately picks one or more collections of f random numbers: every collection includes one random number r i per prime factor p i (0<r i <p i ); and then by successively squaring it k times (mod p i ), it transforms each random number r i into a commitment component R i .

R i ≡r i V (mod p i )

For each collection of f commitment components, the witness establishes a commitment according to the Chinese remainder technique. There are as many commitments as there are random number collections

R=Chinese remainders(R 1 , R 2 , . . . R f )

Here is an example with the previous set of keys and with the Chinese remainders.

r 1 =5C6D37F0E97083C8D120719475E080BBBF9F7392F11F3E2 44FDF0204E84D8CAE

R 1 =3DDF516EE3945CB86D20D9C49E0DA4D422811D07A7607 4DD4FE20C5C7C5E205DF66

r 2 =AC8F85034AC78112071947C457225E908E83A2621B0154 ED15DBFCB9A4915AC3

R 2 =01168CEC0F661EAA15157C2C287C6A5B34EE28F8EB4D8D 340858079BCAE4ECB016

R=Chinese remainders (R 1 ,R 2 )=0AE51D90CB4FDC3DC757C56E063C9ED86BE153B71FC65F47C1 23C27F082BC3DD15273D4A923804718573F2F05E991487D17 DAE0AAB7DF0D0FFA23E0FE59F95F0

In both cases, the demonstrator transmits to the controller, either all or part of each commitment R, or else a hashing code H obtained by hashing each commitment R and a message M.

2) The act of challenge consists in randomly picking one or more challenges d, each consisting of m elementary challenges d 1 , d 2 , . . . d m ; each elementary challenge d i is one of the numbers from 0 to v/2−1.

d=d 1 d 2 . . . d m

Here is a challenge for both examples, i.e. with k=5 and m=4.

d 1 =1011=11=‘B’; d 2 =0011=3; d 3 =0110=6; d 4 =1001=9,

d=d 1 ∥d 2 ∥d 3 ∥d 4 =1011001101101001=B369

The controller transmits each challenge d to the demonstrator.

3) The act of response includes the following operations.

When the witness does not use Chinese remainders, it has the parameter k, the m private numbers from Q 1 to Q m and the module n; it computes one or more responses D by using each random number r from the commitment act and the private numbers according to the elementary challenges.

D≡r i ×Q i d1 ×Q 2 d2 × . . . Q m dm (mod p i )

Here is the continuation of the example without the Chinese remainders.

D=027E6E808425BF2B401FD00B15B642B1A8453BE8070D86C0A7 870E6C1940F7A6996C2D871EBE611812532AC5875EOE116CC8 BA648FD8E86BE0B2ABCC3CCBBBE4

When the witness uses Chinese remainders, it has the parameter k, f prime factors from p 1 to p f , the f−1 Chinese remainder parameters and m×f private components Q i,j ; it computes one or more collections of f response components by using each collection of random numbers from the commitment act: each collection of response components includes one component per prime factor.

D≡r×Q 1,i d1 ×Q 2,i d2 × . . . Q m,i dm (mod p i )

For each collection of response components, the witness establishes a response according to the Chinese remainder technique. There are as many responses as there are challenges.

D=Chinese remainders(D 1 , D 2 , . . . D f )

Here is the continuation of the example without the Chinese remainders.

D 1 =r i ×Q 1,1 d1 ×Q 2,1 d2 ×Q 3,1 d3 ×Q 4,1 d4 (mod p 1 )

C71F86F6FD8F955E2EE434BFA7706E38E5E715375BC2CD2029A 4BD572A9EDEE6

D 2 =r 2 ×Q 1,2 d1 ×Q 2,2 d2 ×Q 3,2 d3 ×Q 4,2 d4 (mod p 2 )

0BE022F4A20523F98E9F5 DBEC0E10887902F3AA48C864A6C354 693AD0B59D85E

90CE7EA43CB8EA89ABDD0C814FB72ADE74F02FE6F098ABB98C 8577A660B9CFCEAECB93BE1BCC356811BF12DD667E2270134C 9073B9418CA5EBF5191218D3FDB3

In both cases, the demonstrator transmits each response D to the controller.

4) The act of checking consists in checking that each triplet {R, d, D} satisfies an equation of the following type for a non-zero value,

R×

∏ i = 1 m ⁢ ⁢ G i d i

≡D 2 k (mod n) or else R≡D×

∏ i = 1 m ⁢ ⁢ G i d i

(mod n)

or, in restoring each commitment: none of them must be zero

R′≡D 2 k /

∏ i = 1 m ⁢ ⁢ G i d i

(mod n) or else R′≡D 2 k ×

∏ i = 1 m ⁢ ⁢ G i d i

(mod n)

Optionally, the controller then computes a hashing code H′ by hashing each restored commitment R′ and the message M′. Dynamic authentication is successful when the controller thus retrieves what it has received at the end of the commitment act, i.e., all or part of each commitment R, or the hashing code H.

For example, a sequence of elementary operations transforms response D into a commitment R′. The sequence comprises k squares (mod n) separated by k−1 divisions or multiplications (mode n) by base numbers. For the i-th division or multiplication, which is performed between the i-th square and the i+1-th square, the i-th bit of the elementary challenge d 1 , indicates if g 1 must be used, the i-th bit of the elementary challenge d 2 indicates if g 2 must be used, . . . up to the i-th bit of the elementary d m which indicates if g m must be used.

Here is the end of the example without the Chinese remainders.

D=027E6E808425BF2B401FD00B15B642B1A8453BE8070D86C0A7 870E6C1940F7A6996C2D871EBE611812532AC5875E0E116CC8BA648FD8E86BE0B2ABCC3CCBBBE4

Take the square modulo n: 88BA681DD641D37D7A7D9818D0DBEA82174073997C6C32F7 FCAB30380C4C6229B0706D1AF6EBD84617771C31B4243C2F0 376CAF5DCEB644F098FAF3B1EB49B39

Multiply by 5 times 26=130, i.e. ‘82’ modulo n: 6ECABA65A91C22431C413E4EC7C7B39FDE14C9782C94FD6FA3CAAD7AFE192B9440C1113CB8DBC45619595D263C1067D3D0A840FDE008B415028AB3520A6AD49D

Take the square modulo n: 0236D25049A5217B13818B39AFB009E4D7D52B17486EBF844D64CF75C4F652031041328B29EBF0829D54E3BD17DAD21817 4A01E6E3AA650C6FD62CC274426607

Multiply by 21, i.e. ‘15’ modulo n: 2E7F40960A8BBF1899A06BBB6970CFC5B47C88E8F115B5DA59 4504A92834BA405559256A705ABAB6E7F6AE82F4F33BF9E912 27F0ACFA4A052C91ABF389725E93

Take the square modulo n: B802171179648AD687E672D3A32640E2493BA2E82D5DC87D BA2B2CC0325E7A71C50E8AE02E299EF868DD3FB916EBCBC0C5 569B53D42DAD49C956D8572E1285B0

Multiply by 5 times 11 times 21=1155, i.e. ‘483’ modulo n: 3305560276310DEFEC1337EB5BB5810336FDB28E91B350D485 B09188E0C4F1D67E68E9590 DB7F9F39C22BDB4533013625011 248A8DC417C667B419D27CB11F72

Take the square modulo n: 8871C494081ABD1AEB8656C38B9BAAB57 DBA72A4BD4EF902 9ECBFFF540E55138C9F22923963151FD0753145DF70CE22E9D0 19990E41 DB6104005EEB7B1170559

Multiply by 5 times 11 times 26=1430, i.e. ‘596’ modulo n: 2CF5F76EEBF128A0701B56F837FF68F81A6A5D175D0AD67A14 DAEC6FB68C362B1DC0ADD6CFC004FF5EEACDF794563BB09A1 7045ECFFF88F5136C7FBC825BC50C

Take the square modulo n: 6BBF9FFA5D509778D0F93AE074D36A07D95FFC38F70C8D7E33 00EBF234FA0BC20A95152A8FB73DE81FAEE5BF4FD3EB7F5EE3E3 6D7068D083EF7C93F6FDDF673A

The commitment r is retrieved. Authentication is successful.

Here is the end of the example with the Chinese remainders.

D=90CE7EA43CB8EA89ABDD0C814FB72ADE74F02FE6F098ABB98C 8577A660B9CFCEAECB93BE1BCC356811BF12DD667E2270134C 9073B9418CA5EBF5191218D3FDB3

Take the square modulo n 770192532E9CED554A8690B88F16D013010C903172B266C11 33B136EBE3EB5F13B170DD41F4ABE14736ADD3A70DFA43121 B6FC5560CDD4B4845395763C792A68

Multiply by 5 times 26=130, i.e. ‘82’ modulo n: 6EE9BEF9E52713004971ABB9FBC31145318E2A703C8A2FB3E144 E7786397CD8D1910E70FA86262 DB771AD1565303AD6E4CC6E 90AE3646B461D3521420E240FD4

Take the square modulo n: D9840D9A8E80002C4D0329FF97D7AD163D8FA98F6AF8FE2B21 60B2126CBBDFC734E39F2C9A39983A426486BC477F20ED2CA5 9E664C23CA0E04E84F2F0AD65340

Multiply by 21, i.e. ‘15’ modulo n: D7DD7516383F78944F2C90116E1BEE0CCDC8D7CEC5D7D1795ED33BFE8623 DB3D2E5B6C5F62A56A2DF4845A94F32BF3CAC36 0C7782B5941924BB4BE91F86BD85F

Take the square modulo n: DD34020DD0804C0757F29A0CBBD7B46A1 BAF949214F74FDFE 021B626ADAFBAB5C3F1602095DA39D70270938AE362F2DAE0B914855310C75BCA328A4B2643DCCDF

Multiply by 5 times 11 times 21=1155, i.e. ‘483’ modulo n: 038EF55B4C826D189C6A48EFDD9DADBD2B63A7D675A0587C 8559618EA2D83DF552D24EAF6BE983FB4AFB3DE7D4D254519 0F1B1F946D327A4E9CA258C73A98F57

Take the square modulo n: D1232F50E30BC6B7365CC2712E5CAE079E47B971DA03185B33 E918EE6E99252DB3573CC87C604B327E5B20C7AB920FDF142A 8909DBBA1C04A6227FF18241C9FE

Multiply by 5 times 11 times 26=1430, i.e. ‘596’ modulo n: 3CC768F12AEDFCD4662892B9174A21D1F0DD9127A54AB63C 984019BED9BF88247EF4CCB56D71E0FA30CFB0FF28B7CE45556 F744C1FD751BFBCA040DC9CBAB744

Take the square modulo n: 0AE51D90CB4FDC3DC757C56E063C9ED86BE153B71FC65F47C1 23C27F082BC3DD15273D4A923804718573F2F05E991487D17 DAE0AAB7DF0D0FFA23E0FE59F95F0

The commitment r is retrieved correctly. Authentication is successful.

Digital Signature

The digital signing mechanism enables an entity called a signing entity to produce signed messages and an entity called controller to ascertain signed messages. Message M is any binary sequence: it may be empty. The message M is signed by adding a signature appendix to it, which comprises one or more commitments and/or challenges, as well as the corresponding responses.

The controller has the module n, for example, from a directory of public keys or even from a certificate of public keys; it also has the same hashing function. The GQ2 public parameters, i.e. numbers k, m and g 1 to g m may be given to the controller by the demonstrator, for example by putting them in the signature appendix.

Numbers k and m inform the controller. Each elementary challenge from d 1 to d m , on the one hand is a number from 0 to 2 k−1 −1 (numbers v/2 to v−1 are not used). Each challenge d on the other hand should include m elementary challenges referenced from d 1 to d m , as many as there are base numbers. Further, unless indicated otherwise, the m base numbers, from g 1 to g m are the first m prime numbers. With (k−1)×m being from 15 to 20, it is possible to sign with four GQ2 triplets produced in parallel; with (k−1)×m being 60 or more, it is possible to sign with only one GQ2 triplet. For example, with k=9 and m=8, only one GQ2 triplet is sufficient; each challenge includes eight bytes and the base numbers are 2, 3, 5, 7, 11, 13, 17 and 19.

The signing operation is a sequence of three acts: a commitment act, a challenge act and a response act. Each act produces one or more GQ2 triplets each comprising: a commitment r (≠0), a challenge d consisting of m elementary challenges referenced by d 1 , d 2 , . . . d m and a response D (≠0).

The signing entity has a hashing function, the parameter k and the GQ2 private key, i.e., the factorization of the module n according to one of the three representations mentioned above. Within the signing entity, it is possible to isolate a witness which executes the commitment and response acts in order to isolate the most sensitive functions and parameters of the demonstrator. In order to compute commitments and responses, the witness has the parameter k and the GQ2 private key, i.e., the factorization of the module n according to one the three representations mentioned above. The thereby isolated witness is similar to the witness defined within the demonstrator. it may correspond to a particular embodiment, for example, • a chip card connected to a PC forming together the signing entity or even • programs particularly protected within a PC, or even, • programs particularly protected within a chip card.

1) The act of commitment comprises the following operations.

When the witness has the m private numbers Q 1 to Q m and the module n, it randomly and privately picks one or more random numbers r (0<r<n); and then, by k successive squarings (mode n), it transforms each random number r into a commitment R.

R≡r V (mod n )

When the witness has f prime factors from p 1 to p f and m×f private components Q 1,j , it randomly and privately picks one or more collections of f random numbers: each collection includes a random number r i per prime factor p i (0<r i <p 1 ); and then k successive squarings (mod p i ), it transforms each random number r i into a commitment component R i ,

R i ≡r i V (mod p i )

For each collection of f commitment components, the witness establishes a commitment according to the Chinese remainder technique. There are as many commitments as there are random number collections.

r ≡Chinese remainders ( R 1 , R 2 , . . . R f )

2) The act of challenge consists in hashing all commitments r and the message m to be signed in order to obtain a hashing code from which the signing entity forms one or more challenges each comprising m elementary challenges; each elementary challenge is a number from 0 to v/2−1; for example, with k=9 and m=8, each challenge includes eight bytes. There are as many challenges as there are commitments. d=d 1 , d 2 , . . . d m , extracted from the Hash(M, R) result 3) The act of response includes the following operations.

When the witness has m private numbers Q 1 , to Q m , and module n, it calculates one or more responses D by using each random number r of the commitment act and the private numbers according to the elementary challenges.

X≡Q 1 d1 ×Q 2 d2 × . . . Q m dm (mod n )

D≡r×X (mod n )

When the witness has f prime factors from p 1 to p f and m×f prime components Q i,j , it calculates one or more collections of f response components by using each collection of random numbers from the commitment act; each collection of response components includes one component per prime factor

x≡Q 1,i d1 ×Q 2,i d2 × . . . Q m,i dm (mod p i )

D i ≡r i ×X i (mod p i )

For each collection of response components, the witness establishes a response according to the Chinese remainder technique. There are as many responses as there are challenges.

D=Chinese remainders (D 1 , D 2 , . . . D f )

The signing entity signs the message M by adding a signature appendix comprising:

either each GQ2 triplet, i.e., each commitment R, each challenge d and each response D,

or each commitment R and each corresponding response D,

or each challenge d and each corresponding response D.

The running of the verification operation depends on the contents of the signature appendix. Three cases are distinguished.

Should the appendix comprises one or more triplets, the checking operation includes two independent processes for which chronology is indifferent. The controller accepts the signed message if and only if, both following conditions are satisfied.

Firstly, each triplet must be consistent (an appropriate relationship of the following type has to be verified) and acceptable (the comparison has to be done on a non-zero

R×

∏ i = 1 m ⁢ ⁢ G i d i

≡D 2 k (mod n) or else R≡D 2 k ×

∏ i = 1 m ⁢ ⁢ G i d i

(mod n)

For example, the response D is converted by a sequence of elementary operations: k squares (mod n) separated by k−1 multiplication or division operations (mod n) by base numbers. For the i-th multiplication or division which is performed between the i-th square and the i+ 1st square, the i-th bit of the elementary challenge d, indicates whether it is necessary to use g 1 , the i-th bit of the elementary challenge d 2 indicates whether it is necessary to use g 2 , . . . Up to the i-th bit of the elementary challenge d m which indicates if it is necessary to use g m . It is thus necessary to retrieve each commitment R present in the signature appendix.

Furthermore, the triplet or triplets must be linked to the message M. By hashing all the commitments R and the message M, a hashing code is obtained from which each challenge d must be recovered.

d=d 1 d 2 . . . d m , identical to those extracted from the result Hash(M, R).

If the appendix has no challenge, the checking operation starts with the reconstitution of one or more challenges d′ by hashing all the commitments R and the message M.

d=d′ 1 d′ 2 . . . d′ m , extracted from the result Hash(M, R).

Then, the controller accepts the signed message if and only if each triplet is consistent (an appropriate relationship of the following type is verified) and acceptable (the comparison is done on a non-zero value).

R×

∏ i = 1 m ⁢ ⁢ G i d i ′

≡D 2 k (mod n) or else R≡D 2 k ×

∏ i = 1 m ⁢ ⁢ G i d i ′

(mod n)

Should the appendix comprise no commitment, the checking operation starts with the reconstitution of one or more commitments R′ according to one of the following two formulae, namely the one that is appropriate. No re-established commitment should be zero.

R′≡D 2 k /

∏ i = 1 m ⁢ ⁢ G i d i

(mod n) or else R′≡D 2 k ×

∏ i = 1 m ⁢ ⁢ G i d i

(mod n)

Then, the controller must hash all the commitments R′ and the message M so as to reconstitute each challenge d.

d=d 1 d 2 . . . d m , identical to those extracted from the result Hash (M, R′).

The controller accepts the signed message if and only if each reconstituted challenge is identical to the corresponding challenge in the appendix.