Back to results
US 7,080,254 B1Granted
Method, system, device for proving authenticity of an entity or integrity of a message
AssigneeFrance Telecom
InventorsLouis Guillou, Jean-Jacques Quisquater
Life of this patent
Estimating the term…
Abstract
The invention concerns a method whereby the proof is established by: m(≧1) pairs of private Qi and public Gi=gi2 values; a public module n formed by the product of f(≧2) prime factors; an exponent v=2k(k>1), linked by the relationships of the type: Gi−Qiv≡1. mod n or Gi≡Qiv mod n. Among the m numbers obtained by increasing Qi or its inverse modulo n to modulo n square, k−1 times rank, at least one of them is different from ±gi. Among the 2m equations: x2≡gi mod n, x2≡−gi mod n, at least one of them has solutions in x in the ring of modulo n integers.
Claims11
A computer-implemented process comprising:
- obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1,G2, . . . ,Gm, each pair of keys (Qi,Gi) verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by pi, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi(for i=1, . . . ,m) is such that Gi≡gi2 mod n, wherein gi(for i=1, . . . ,m) is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and wherein, for at least one integer value l between 1 and m, gl or (−gl) is a quadratic residue of the body of integers modulo n, and wherein, for at least one integer value s between 1 and m, qs is neither congruent to gs mod n nor congruent to (−gs) mod n, wherein, for i=1, . . . ,m, qi≡Qi−v/2 mod n in the case Gi×Qiv=1 mod n and qi=Qiv/2 mod n in the case Gi=Qiv mod n;
- and
- using at least the private values Q1,Q2, . . . ,Qm in an authentication or in a signature method.
A system comprising:
- a memory storing a set of instructions;
- and
- a processor coupled to the memory for executing the set of instructions stored in the memory, the instructions including:
- obtaining a set of one or more private values Q1,Q2, . . . ,Qm and respective public values G1,G2, . . . ,Gm, each pair of keys (Qi,Gi) verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi (for i=1, . . . ,m) is such that Gi≡gi2 mod n, wherein gi (for i=1, . . . ,m) is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and wherein, for at least one integer value l between 1 and m, gl, or (−g1) is a quadratic residue of the body of integers modulo n, and wherein, for at least one integer value s between 1 and m, q, is neither congruent to gs mod n nor congruent to (−gs) mod n, wherein, for i=1, . . . ,m, qi≡Qi−v/2 mod n in the case Gi×Qiv=1 mod n and qi=Qiv/2 mod n in the case Gi=Qiv mod n;
- and
- using at least the private values Q1,Q2, . . . ,Qm in an authentication or in a signature method.
3 more elements
A computer-readable storage medium storing instructions which when executed cause a processor to execute the following acts:
- obtaining a set of one or more private values Q1,Q2, . . . ,Qm and respective public values G1,G2, . . . ,Gm, each pair of keys (Qi,Gi) verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . ,pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi (for i=1, . . . ,m ) is such that Gi≡gi2 mod n, wherein gi (for i=1, . . . ,m) is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and wherein, for at least one integer value l between 1 and m, gl or (−gl) is a quadratic residue of the body of integers modulo n, and wherein, for at least one integer value s between 1 and m, qs is neither congruent to gs mod n nor congruent to (−gs) mod n, wherein, for i=1, . . . ,m, qi≡Qi−v/2 mod n in the case Gi×Qiv=1 mod n and qi=Qiv/2 mod n in the case Gi=Qiv mod n;
- and
- using at least the private values Q1, Q2, . . . , Qm in an authentication or in a signature method.
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;
- selecting m base numbers g1,g2, . . . ,gm, wherein each base number gi (for i=1, . . . ,m) has an integer value greater than 1 and smaller than each of the prime factors p1, . . . ,pf, and wherein, for at least one integer value l between 1 and m, gl or (−gl) is a quadratic residue of the body of integers modulo n;
- 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, such that, for at least one integer value s between 1 and m, qs is neither congruent to gs mod n nor congruent to (−gs)mod n, wherein, for i=1, . . . ,m, qi≡Qi−v/2 mod n in the case Gi×Qiv=1 mod n and qi=Qiv/2 mod n in the case Gi=Qiv mod n.
3 more elements
Dependencies are inferred from the claim text.