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

1. A system for producing asymmetric cryptographic keys, said keys comprising m≧1 private values Q 1 , Q 2 , . . . , Q m and m respective public values G 1 , G 2 , . . . , G m , 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 p 1 , . . . , p f , at least two of these prime factors, say p 1 and p 2 , being such that p 1 ≡3 mod 4 and p 2 ≡3 mod 4;

selecting m base numbers g 1 , g 2 , . . . , g m , wherein each base number g i (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 p 2 is complementary to p 1 with respect to one of the base numbers;

calculating the public values G i for i=1, . . . , m through G i ≡g i 2 mod n; and

calculating the private values Q i for i=1, . . . , m by solving either the equation G i .Q i v ≡1 mod n or the equation G i ≡Q i v mod n, wherein the public exponent v is such that v=2 k .

2. The system according to claim 1 , wherein a number (f−e) (where e≧0) of prime factors of the modulus n which are congruent to 3 mod 4 is larger than 2, and those prime factors p j+1 for 2≦j≦m which are congruent to 3 mod 4 are determined iteratively as follows:

the profile profile j (g j ) of g j with respect to the prime factors p 1 , p 2 , . . . , p j is computed, and

if profile j (g j ) is flat, then the prime factor p j+1 is chosen such that p j+1 is complementary to p i with respect to g j ; else, a number g is chosen among the (j−1) base numbers g 1 , g 2 , . . . , g 1−1 , and all of their multiplicative combinations, such that profile j (g)=profile j (g j ), then p j+1 is chosen such that profile j+1 (g j )≠profile j+1 (g),

wherein the last prime factor p f−e congruent to 3 mod 4 is, in the case that f−e≦m, chosen such that p f−e is complementary to p i with respect to all of the base numbers g i such that f−e≦i≦m and whose profile profile f−e−1 (g i ) is flat.

3. The system according to claim 1 , wherein a number e of prime factors of the modulus n which arc congruent to 1 mod 4 is at least equal to 1, and each such prime factor is determined as follows:

a candidate prime number p is chosen, such that the Legendre symbol of each base number g i (for i=1, . . . , m) with respect to p is equal to +1,

the integer t is computed which is such that (p−1) is divisible by 2 t , but not by 2 i+1 ,

the integer s=(p−1+2 t )/2 t+1 is computed,

an integer b≡h p−1/2 i mod p, where h is a non-quadratic residue of the body of integers modulo p, is computed,

the m integers r i ≡g i 2s mod p for i=1, . . . , m are computed,

an integer u is initialized to u=0,

the following sequence of steps, where i is initialized to 1, is iteratively implemented:

an integer w is initialized to w=r i ,

if r i ≡±g i , the value of i is incremented and a sequence of steps with the new value of i is proceeded to if i>m, whereas the candidate prime number p is accepted as a factor of the modulus n if i=m,

if r i ≠±g i :

an integer jj is initialized to 1,

the following sequence of steps, where an integer ii is initialized to 1, is iteratively implemented;

x≡w 2 /g i 2 mod p is computed,

y≡x 2 mod p is computed, and

if y=+1, the sequence is terminated at the current value of ii,

if y=−1, jj is assigned the value jj=2 ii , the number w is assigned a new value equal to the old value multiplied by b jj modulo p, and

 for ii<t−2, the value of ii is incremented and a new iteration is proceeded to with the new value of ii,

 for ii=t−2, the value of number u is updated through the relation jj=2 t−ii , and

if t−u<k, the candidate prime number p is rejected as a factor of the modulus n,

if t−u>k, the value of i is incremented and a sequence of steps with the new value of i is proceeded to if i<n, whereas the candidate prime number p is accepted as a factor of the modulus n if i=m.

4. The system according to claim 3 , wherein, to compute f.m private components Q i,j of the private values Q 1 , Q 2 , . . . , Q m , the following steps are implemented for each couple (i, j):

an integer t is determined, which is equal to 1 if p j is congruent to 3 mod 4, and to the value obtained for t according to claim 3 if p j is congruent to 1 mod 4,

an integer u is determined, which is equal to 0 if p j is congruent to 3 mod 4, and to the value obtained for u according to claim 3 if p j is congruent to 1 mod 4,

the integer z≡G i s mod p j is computed, where s=(p−1+2 t )/2 t+1 ,

all the numbers zz are being considered, which:

if u=0, are such that zz=z or such that z is equal to the product modulo p j of z by each of the 2 ii−1 2 ii -th primitive roots of unity, for ii ranging from 1 to min(k,t),

if u>0, are such that zz is equal to the product modulo p j of za by each of the 2 k 2 k -th roots of unity, where za is the value obtained for w according to claim 3 , and

for each such number zz, a value for the component Q i,j is obtained by taking Q i,j equal to zz if the equation G i ≡Q i v mod n is used, or to the inverse of zz modulo p j if G i .Q i v ≡1 mod n is used for this value of i.

5. A computer-readable storage medium storing instructions for producing asymmetric cryptographic keys, said keys comprising m≧1 private values Q 1 , Q 2 , . . . , Q m and m respective public values G 1 , G 2 , . . . , G m , 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 p 1 , . . . , p f , at least two of these prime factors, say p 1 and p 2 , being such that p 1 ≡3 mod 4 and p 2 ≡3 mod 4;

selecting m base number g 1 , g 2 , . . . , g m , wherein each base number g i (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 p 2 is complementary to p 1 with respect to one of the base numbers;

calculating the public values G i for i=1, . . . , m through G i ≡g i 2 mod n; and

calculating the private values Q i for i=1, . . . , m by solving either the equation G i .Q i v ≡1 mod n or the equation G i ≡Q i v mod n, wherein the public exponent v is such that v=2 k .

6. The computer-readable storage medium storing instructions according to claim 5 , wherein a number (f−e) (where e≧0) of prime factors of the modulus n which are congruent to 3 mod 4 is larger than 2, and those prime factors p j+1 for 2≦j≦m which are congruent to 3 mod 4 are determined iteratively as follows:

the profile profile j (g j ) of g j with respect to the prime factors p 1 , p 2 , . . . , p j is computed, and

if profile j (g j ) is flat, then the prime factor p j+1 is chosen such that p j+1 is complementary to p 1 with respect to g j ; else, a number g is chosen among the (j−1) base numbers g 1 , g 2 , . . . , g i−1 and all of their multiplicative combinations, such that profile j (g)=profile j (g j ), then p j+1 , is chosen such that profile j+1 (g j )≠profile j+1 (g),

wherein the last prime factor p f−e congruent to 3 mod 4 is, in the case that f−e≦m, chosen such that p f−e is complementary to p i with respect to all of the base numbers g i such that f−e≦i≦m and whose profile profile f−e−1 (g i ) is flat.

7. The computer-readable storage medium storing instructions according to claim 5 , wherein a number e of prime factors of the modulus n which are congruent to 1 mod 4 is at least equal to 1, and each such prime factor is determined as follows:

a candidate prime number p is chosen, such that the Legendre symbol of each base number g i (for i=1 . . . , m) with respect to p is equal to +1,

the integer t is computed which is such that (p−1) is divisible by 2 t , but not by 2 t+1 ,

the integer s=(p−1+2 t )/2 t+1 is computed,

an integer b≡h p−1/2′ mod p, where h is a non-quadratic residue of the body of integers modulo p, is computed,

the m integers r i ≡g t 2s mod p for i=1 . . . , m are computed,

an integer u is initialized to u=0,

the following sequence of steps, where i is initialized to 1, is iteratively implemented:

an integer w is initialized to w=r i ,

if r i =±g i , the value of i is incremented and a sequence of steps with the new value of i is proceeded to if i<m, whereas the candidate prime number p is accepted as a factor of the modulus n if i=m,

if r i ≠±g i :

an integer jj is initialized to 1,

the following sequence of steps, where an integer ii is initialized to 1, is iteratively implemented:

x≡w 2 /g i 2 mod p is computed,

y≡x 2 mod p is computed, and

if y=+1, the sequence is terminated at the current value of ii,

if y=−1, jj is assigned the value jj=2 tt , the number w is assigned a new value equal to the old value multiplied by b jj modulo p, and

 for ii<−2, the value of ii is incremented and a new iteration is proceeded to with the new value of ii,

 for ii=t−2, the value of number u is updated through the relation jj=2 t−ii , and

if t−u<k, the candidate prime number p is rejected as a factor of the modulus n,

if t−u>k, the value of i is incremented and a sequence of steps with the new value of i is proceeded to if i<m, whereas the candidate prime number p is accepted as a factor of the modulus n if i=m.

8. The computer-readable storage medium storing instructions according to claim 7 , wherein, to compute f.m private components Q i,j of the private values Q 1 , Q 2 , . . . , Q m , the following steps are implemented for each couple (i, j):

an integer t is determined, which is equal to 1 if p j is congruent to 3 mod 4, and to the value obtained for t according to claim 7 if p j is congruent to 1 mod 4,

an integer u is determined, which is equal to 0 if p j is congruent to 3 mod 4, and to the value obtained for u according to claim 7 if p j is congruent to 1 mod 4,

the integer z≡G i j mod p j is computed, where s=(p−1+2 t )/2 t+1 ,

all the numbers zz are being considered, which:

if u=0, are such that zz=z or such that zz is equal to the product modulo p j of z by each of the 2 ii−1 2 ii -th primitive roots of unity, for ii ranging from 1 to min(k,t),

if u>0, arc such that zz is equal to the product modulo p j of za by each of the 2 k 2 k -th roots of unity, where za is the value obtained for w according to claim 7 , and

for each such number zz, a value for the component Q i,j is obtained by taking Q i,j equal to zz if the equation G i ≡Q i v mod n is used, or to the inverse of zz modulo p j if G i .Q i v ≡1 mod n is used for this value of i.

9. A computer-implemented process for producing asymmetric cryptographic keys, said keys comprising m≧1 private values Q 1 , Q 2 , . . . , Q m , and m respective public values G 1 , G 2 , . . . ,G m , 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 p 1 , . . . , p f , at least two of these prime factors, say p 1 and p 2 , being such that p 1 ≡3 mod 4 and p 2 ≡3 mod 4;

selecting m base numbers g 1 , g 2 , . . . , g m , wherein each base number g i (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 p 2 is complementary to p 1 with respect to one of the base numbers;

calculating the public values G i for i=1, . . . , m through G i ≡g i 2 mod n; and

calculating the private values Q i for i=1, . . . , m by solving either the equation G i .Q i v ≡1 mod n or the equation G i ≡Q i v mod n, wherein the public exponent v is such that v=2 k .

10. The computer-implemented process according to claim 9 , wherein a number (f−e) (where e≧0) of prime factors of the modulus n which are congruent to 3 mod 4 is larger than 2, and those prime factors p j+1 , for 2≦j≦m which are congruent to 3 mod 4 arc determined iteratively as follows.

the profile profile j (g j ) of g j with respect to the prime factors p 1 , p 2 , . . . , p j is computed, and

if profile j (g j ) is flat, then the prime factor p j+1 is chosen such that p j+1 is complementary to p i with respect to g j ; else, a number g is chosen among the (j−1) base numbers g 1 , g 2 , . . . , g j−1 and all of their multiplicative combinations, such that profile j (g)=profile j (g j ), then p j+1 is chosen such that profile j+1 (g j )≠profile j+1 (g),

wherein the last prime factor p f−e congruent to 3 mod 4 is, in the case that f−e≦m, chosen such that p f−e is complementary to p 1 with respect to all of the base numbers g j such that f−e≦i≦m and whose profile profile f−e−1 (g i ) is flat.

11. The computer-implemented process according to claim 9 , wherein a number e of prime factors of the modulus n which are congruent to 1 mod 4 is at least equal to 1, and each such prime factor is determined as follows:

a candidate prime number p is chosen, such that the Legendre symbol of each base number g i (for i=1, . . . , m) with respect to p is equal to +1,

the integer t is computed which is such that (p−1) is divisible by 2 t , but not by 2 t+ 1,

the integer s=(p−1+2 t )/2 t+1 is computed,

an integer b≡h p−1/2 t mod p, where h is a non-quadratic residue of the body of integers modulo p, is computed,

the m integers r i ≡g i 2s mod p for i=1, . . . , m arc computed,

an integer u is initialized to u=0,

the following sequence of steps, where i is initialized to 1, is iteratively implemented:

an integer w is initialized to w=r i ,

if r i =±g i , the value of i is incremented and a sequence of steps with the new value of i is proceeded to if i<m, whereas the candidate prime number p is accepted as a factor of the modulus n if i=m,

if r i ≠±g i :

an integer jj is initialized to 1,

the following sequence of steps, where an integer ii is initialized to 1, is iteratively implemented

x≡w 2 /g i 2 mod p is computed,

y≡x 2 mod p is computed, and

if y=+1, the sequence is terminated at the current value of ii,

if y=−1, jj is assigned the value jj=2 ii , the number w is assigned a new value equal to the old value multiplied by b jj modulo p, and

 for ii<t−2, the value of ii is incremented and a new iteration is proceeded to with the new value of ii,

 for ii=t−2, the value of number u is updated through the relation jj=2 t−tt , and

if t−u<k, the candidate prime number p is rejected as a factor of the modulus n,

if t−u>k, the value of i is incremented and a sequence of steps with the new value of i is proceeded to if i<m, whereas the candidate prime number p is accepted as a factor of the modulus n if i=m.

12. The computer-implemented process according to claim 11 , wherein, to compute f.m private components Q i,j of the private values Q 1 , Q 2 , . . . , Q m , the following steps are implemented for each couple (i, j):

an integer t is determined, which is equal to 1 if p j is congruent to 3 mod 4, and to the value obtained for t according to claim 11 if p j is congruent to 1 mod 4,

an integer u is determined, which is equal to 0 if p j is congruent to 3 mod 4, and to the value obtained for u according to claim 11 if p j is congruent to 1 mod 4,

the integer z≡G i s mod p j is computed, where s=(p−1+2 t )/2 i+1 ,

all the numbers zz are being considered, which:

if u=0, are such that zz=z or such that zz is equal to the product modulo p j of

z by each of the 2 ii−t 2 ii -th primitive roots of unity, for ii ranging from 1 to min(k,t),

if u>0, are such that zz is equal to the product modulo p j of za by each of the

2 k 2 k -th roots of unity, where za is the value obtained for w according to claim 11 , and

for each such number zz, a value for the component Q i,j is obtained by taking Q i,j equal to zz if the equation G i ≡Q i v mod n is used, or to the inverse of zz modulo p j if G i .Q t v =1 mod n is used for this value of i.