Method, system, device for proving the authenticity of an entity and/or the integrity and/or the authenticity of a message using specific prime factors
AssigneesFrance Telcom, Tdf, Math Rizk
InventorsLouis Guillou, Jean-Jacques Quisquater
Life of this patent
Estimating the term…
Abstract
The proof is provided by means of the following parameters: a public module n formed by the product of f prime factors pi, f>2; a public superscript v; m base numbers gi, m>1. The base numbers gi are such that the two equations: x2≡gi mod n and x2≡−gi mod n cannot de solved in x in the ring of integers modulo n, and such that the equation xv≡gi2 mod n can be solved in x in the ring of integers modulo n in the case where the public superscript v is in the form v=2k, wherein k is a security parameter.
Claims12
A system for producing asymmetric cryptographic keys, said keys comprising m≧1 private values Q1, Q2, . . . , Qm and m respective public values G1, G2, . . . , Gm, the system comprising:
- a processor;
- and
- a memory unit coupled to the processor, the memory unit storing a set of instructions which when executed cause the processor to execute the following acts:
- selecting a security parameter k, wherein k is an integer greater than 1,
- determining a modulus n, wherein n is a public integer equal to the product of at least two prime factors p1, . . . , pf, at least two of these prime factors, say p1 and p2, being such that p1≡3 mod 4 and p2≡3 mod 4;
- selecting m base numbers g1, g2, . . . , gm, wherein each base number gi (for i=1, . . . , m) is an integer greater than 1 and is a non-quadratic residue of the ring of integers modulo n, and such that p2 is complementary to p1 with respect to one of the base numbers;
- calculating the public values Gi for i=1, . . . , m through Gi≡gi2 mod n;
- and
- calculating the private values Qi for i=1, . . . , m by solving either the equation Gi.Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein the public exponent v is such that v=2k.
A computer-readable storage medium storing instructions for producing asymmetric cryptographic keys, said keys comprising m≧1 private values Q1, Q2, . . . , Qm and m respective public values G1, G2, . . . , Gm, the medium storing instructions which when executed cause a processor to execute the following acts:
- selecting a security parameter k, wherein k is an integer greater than 1;
- determining a modulus n, wherein n is a public integer equal to the product of at least two prime factors p1, . . . , pf, at least two of these prime factors, say p1 and p2, being such that p1≡3 mod 4 and p2≡3 mod 4;
- selecting m base number g1, g2, . . . , gm, wherein each base number gi (for i=1, . . . , m) is an integer greater than 1 and is a non-quadratic residue of the ring of integers modulo n, and such that p2 is complementary to p1 with respect to one of the base numbers;
- calculating the public values Gi for i=1, . . . , m through Gi≡gi2 mod n;
- and
- calculating the private values Qi for i=1, . . . , m by solving either the equation Gi.Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein the public exponent v is such that v=2k.
A computer-implemented process for producing asymmetric cryptographic keys, said keys comprising m≧1 private values Q1, Q2, . . . , Qm, and m respective public values G1, G2, . . . ,Gm, the computer-implemented process comprising:
- selecting a security parameter k, wherein k is an integer greater than 1;
- determining a modulus n, wherein n is a public integer equal to the product of at least two prime factors p1, . . . , pf, at least two of these prime factors, say p1 and p2, being such that p1≡3 mod 4 and p2≡3 mod 4;
- selecting m base numbers g1, g2, . . . , gm, wherein each base number gi (for i=1, . . . , m) is an integer greater than 1 and is a non-quadratic residue of the ring of integers modulo n, and such that p2 is complementary to p1 with respect to one of the base numbers;
- calculating the public values Gi for i=1, . . . , m through Gi≡gi2 mod n;
- and
- calculating the private values Qi for i=1, . . . , m by solving either the equation Gi.Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein the public exponent v is such that v=2k.
Dependencies are inferred from the claim text.