Zero-knowledge proof cryptography methods and devices
View Patent ↗A cryptography method involving a keyholder having a number m≧1 of private keys Q 1 , Q 2 , . . . , Q m and respective public keys G 1 , G 2 , . . . , G m , each pair of keys (Q i , G i ) (where i=1, . . . , m) satisfying either the relationship G 1 =Q i v mod n or the relationship G i ×Q i v =1 mod n, where n is a public integer equal to the product of f (where f>1) private prime factors p 1 , . . . , p f , at least two of which are separate, and the exponent v is a public integer equal to a power of 2. Disclosed is what mathematical structure may be imparted to the public keys for it to be impossible to calculate said private keys from said public parameters in a reasonable time unless said prime factors are known. Devices adapted to implement the method are also disclosed.
1. An asymmetrical key cryptography method involving a processor-implemented keyholder having a number m≧1 of private keys Q 1 , Q 2 , . . . , Q m and respective public keys G 1 , G 2 , . . . , G m , each pair of keys (Q i , G i ) (where i=1, . . . , m ) satisfying either the relationship G i =Q i v mod n or the relationship G i ×Q i v =1 mod n, where n is a public integer equal to the product of f(where f>1) private prime factors p 1 , . . . , p f , at least two of which are separate, and the exponent v is a public integer equal to a power of 2, wherein the method comprises:
arranging, by a processor, exponent v to have the relationship v=2 b+k ,
where k is a strictly positive integer and b=max(b 1 , . . . , b f ), where b j (where j=1, . . . , f) is the highest integer such that (p j −1)/2 bj−1 is even; and
arranging, by the processor each public key G i (where i=1, . . . , m ) to have the form G i =g i 2 a i , mod n,
where the base numbers g i are integers strictly greater than 1 and the numbers a i , are integers such that 1≦a i , ≦b and at least one of them is strictly greater than 1.
2. A method according to claim 1 , wherein at least one of said prime factors p 1 , . . . , p f is congruent to 1 modulo 4 and the integers a i (where i=1, . . . , m) are all equal to said number b.
3. A method according to claim 1 , wherein said base numbers g 1 , . . . , g m include at least one number g s , and said prime factors p 1 , . . . , p f include at least two numbers p t and p u other than 2 such that, given said numbers b 1 , . . . , b f ,
if b t =b u , then ( g s *p t )=−( g s *p u ), and
if b t <b u , then ( g s *p u )=−1,
where (g s *p t ) and (g s *p u ) denote the Legendre symbols of g s relative to p t and p u .
4. A method according to claim 1 , wherein the base numbers g i , . . . , g m are prime numbers.
5. A method according to claim 1 , involving a processor-implemented controller and said processor-implemented keyholder, here called the process-implemented claimant, wherein the method comprises:
the processor-implemented claimant chooses at random an integer r, calculates the witness R=r v mod n and sends the witness to the processor-implemented controller,
the processor-implemented controller chooses at random m challenges d 1 , d 2 , . . . , d m and sends the challenges to the processor-implemented claimant,
the processor-implemented claimant calculates the response
D=r×Q 1 d 1 ×Q 2 d 2 × . . . ×Q m d m mod n,
and sends the response to the processor-implemented controller, and
the processor-implemented controller calculates
D v ×G 1 ε 1 d 1 ×G 2 ε 2 d 2 × . . . ×G m ε m d m mod n
where, for i=1, . . . , m, ε i =+1 if G i ×Q i v =1 mod n and ε i =−1 if G i =Q i v mod n, and verifies that the result is equal to the witness R.
6. A method according to claim 1 , enabling a processor-implemented controller to verify that a message M that it has received was sent to it by said processor-implemented keyholder, here called the processor-implemented claimant, wherein the method comprises:
the processor-implemented claimant chooses at random an integer r and first calculates the witness R=r v mod n, then calculates the token T=h(M, R), where h is a hashing function, and finally sends the token T to the processor-implemented controller,
the processor-implemented controller chooses at random in challenges d 1 , d 2 , . . . , d m , and sends the challenges to the processor-implemented claimant,
the processor-implemented claimant calculates the response
D=r×Q 1 d 1 ×Q 2 d 2 × . . . ×Q m d m mod n and sends the response to the controller, and
the processor-implemented controller calculates h(M, D v ×G 1 ε 1 d 1 ×G 2 ε 2 d 2 × . . . ×G m ε m d m mod n)where, for i=1, . . . , m, ε i =+1 if G i ×Q i v =1 mod n and ε i =−1 if G i ×Q i v mod n, and verifies that the result is equal to the token T.
7. A method according to claim 5 , wherein the challenges satisfy the condition 0≦d i ≦2 k −1 for i=1, . . . , m.
8. A method according to claim 1 , enabling said processor-implemented keyholder, here called the signatory, to sign a message M that it sends to a processor-implemented controller, wherein the method comprises:
the processor-implemented signatory chooses at random in integers r i , where i=1, . . . , m, and first calculates the witnesses R i =r i v mod n, then calculates the token T=h(M, R 1 , R 2 , . . . , R m ), where h is a hashing function producing a word of in bits, and finally sends the token T to the controller,
the processor-implemented signatory identifies the bits d 1 , d 2 , . . . , d m of the token T, the processor-implemented signatory calculates the responses D i =r i ×Q i d i mod n and sends the responses to the processor-implemented controller, and
the processor-implemented controller calculates
h ( M, D 1 v ×G 1 ε 1 d 1 mod n, D 2 v ×G 2 ε 2 d 2 mod n, . . . , D m v ×G m ε m d m mod n )
where, for i=1, . . . , m, ε i =+1 if G i ×Q i v =1 mod n and ε i =−1 if G i ×Q i v mod n, and verifies that the result is equal to the token T.
9. An electronic circuit including a processor and memories, wherein the electronic circuit is programmed to act as said processor-implemented keyholder in executing the method according to claim 1 .
10. A dedicated electronic circuit, including microcomponents enabling the electronic circuit to process data in such manner as to act as said processor-implemented keyholder in executing the method according to claim 1 .
11. A portable object adapted to be connected to a terminal to exchange data with that terminal, wherein the portable object includes an electronic circuit according to claim 9 or claim 10 and is adapted to store identification data and private keys specific to said processor-implemented key holder.
12. A terminal adapted to be connected to a portable object to exchange data with that portable object, wherein the terminal includes a data processing device programmed to act as said processor-implemented controller in executing a method according to any one of claims 5 - 8 .
13. A cryptography system comprising:
a portable object adapted to be connected to a terminal to exchange data with that terminal, wherein the portable object includes an electronic circuit,
wherein the electronic circuit is programmed to act as said processor-implemented keyholder in executing an asymmetrical key cryptography method involving the processor-implemented keyholder having a number m≧1 of private keys Q 1 , Q 2 , . . . , Q m and respective public keys G 1 , G 2 , . . . , G m , each pair of keys (Q i , G i ) (where i=1, . . . , m) satisfying either the relationship G i =Q i v mod n or the relationship G i ×Q i v =1 mod n where n is a public integer equal to the product of f (where f>1) private prime factors p 1 , . . . , p f , at least two of which are separate, and the exponent v is a public integer equal to a power of 2, wherein the method comprises:
arranging, by the processor, exponent v to have the relationship v=2 b+k ,
where k is a strictly positive integer and b=max(b 1 , . . . , b f ), where b j (where j=1, . . . , f) is the highest integer such that (p j −1)/2 b j −1 is even; and
arranging, by the processor, each public key G i (where i=1, . . . , m) to have the form G i =g i 2 a i mod n,
where the base numbers g i are integers strictly greater than 1 and the numbers a i are integers such that 1≦a i ≦b and at least one of them is strictly greater than 1,
and wherein the portable object is adapted to store identification data and private keys specific to said processor-implemented keyholder; and
a terminal adapted to be connected to the portable object to exchange data with that portable object, wherein the terminal includes a data processing device programmed to act as said processor-implemented controller in executing a method according to any one of claims 5 - 8 claim 6 .
14. Non-removable data storage means containing electronic data processing program code instructions for, as said processor-implemented keyholder, executing the method according to claim 1 .
15. Partially or totally removable storage means containing electronic data processing program code instructions for, as said processor-implemented keyholder, executing the method according to claim 1 .
16. A data processing device comprising storage means according to claim 14 or claim 15 .
17. Non-removable, partially removable, or totally removable data storage means containing electronic data processing program code instructions for, as said processor-implemented controller, executing the method according to any one of claims 5 - 8 .
18. A data processing device, wherein it comprises storage means according to claim 17 .
19. A cryptography system comprising:
a data processing device including storage means containing electronic data processing program code instructions for, as said processor-implemented keyholder, executing an asymmetrical key cryptography method involving the processor-implemented keyholder having a number m≧1 of private keys Q 1 , Q 2 , . . . , Q m and respective public keys G 1 , G 2 , . . . , G m , each pair of keys (Q i , G i ) (where i=1, . . . , m) satisfying either the relationship G i =Q i v mod n or the relationship G i ×Q i v =1 mod n, where n is a public integer equal to the product of f (where f>1) private prime factors p 1 , . . . , p f , at least two of which are separate, and the exponent v is a public integer equal to a power of 2, wherein the method comprises:
arranging, by processor, exponent v to have the relationship v=2 b+k ,
where k is a strictly positive integer and b=max(b 1 , . . . , b f ), where b j (where j=1, . . . , f) is the highest integer such that (p j −1)/2 b j −1 is even; and
arranging, by processor, each public key G i (where i=1, . . . , m to have the form G i =g i 2 a i mod n,
where the base numbers g 1 are integers strictly greater than 1 and the numbers a i are integers such that 1≦a i ≦b and at least one of them is strictly greater than 1; and
a data processing device including data storage means containing electronic data processing program code instructions for, as said processor-implemented controller, executing the method according to any one of claims 5 - 8 .
20. A method according to claim 4 , wherein the base numbers g 1 , . . . , g m are chosen from the first 54 prime numbers.