Method and apparatus for use in public-key data encryption system

• US 4,633,036 A
• Filed: 05/31/1984
• Issued: 12/30/1986
• Est. Priority Date: 05/31/1984
• Status: Expired due to Term

• Current Assignee: Martin E. Hellman
• Original Assignee: Martin E. Hellman
• Inventors: Hellman, Martin E., Bach, Carl E.
• Primary Examiner(s): Cangialosi, Salvatore
• Assistant Examiner(s): Lewis, Aaron J.
• Application Number:
  US06/615,634
• Time in Patent Office: 943 Days
• Field of Search: 178/22.11, 178/22.09
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/26 Testing cryptographic entity, e.g. testing integrity of encryption key or encryption algorithm
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

In an encryption scheme based on the use of a public key having secret factors p and q, additional requirements on p and q are invoked in order to ensure a high level of security. In particular, it is additionally required that a value p+1 have a large prime factor r and that the value r-1 also have a large prime factor r'"'"'.

Claims

1. For use in connection with an apparatus employing a public key n and a secret key comprising primary factors p and q where n=pq wherein said public key is used for authenticating data, for enciphering data, or for authenticating and enciphering data, and the secret key is used for signing the data, for deciphering the data, or for signing and deciphering the data, apparatus for generating said secret key and said public key such that recovery of said secret key from said public key is computationally infeasible, said apparatus comprising:

means for establishing a length of said public key;

means for establishing lengths of p-related secondary factors, p-related tertiary factors, q-related secondary factors and q-related tertiary factors which are functions of said secret key p and q;

means for choosing a tentative p value as one of said primary factors;

means for choosing a tentative q value as one of said primary factors;

means for testing said tentative p value for suitability as a part of said secret key based on two p-related secondary factors and two p-related tertiary factors, each one of said p-related tertiary factors and said p-related secondary factors being functions of said tentative p value; and

means for testing said tentative q value for suitability as a part of said secret key based on two q-related secondary factors and two q-related tertiary factors, each one of said q-related tertiary factors and said q-related secondary factors being functions of said tentative q value.

2. The apparatus according to claim 1 wherein said p value testing means comprises means for testing for primality of a value of a first said p-related secondary factor which is a factor of a value p+1 and means for testing for primality of a value of a second p-related secondary factors which is a factor of a value p-1.

3. The apparatus according to claim 2 wherein said q value testing means comprises means for testing for primality of a value of a first one of said q-related secondary factors which is a factor of a value q+1 and means for testing for primality of a value of a second one of said q-related secondary factors which is a factor of a value q-1.

4. The apparatus according to claim 1 wherein said q value testing means comprises means for testing for primality of a value of a first one of said q-related secondary factors which is a factor of a value q+1 and means for testing for primality of a value of a second one of said q-related secondary factors which is a factor of a value q-1.

5. The apparatus according to claim 1 wherein said value length establishing means includes means for establishing the length of factors of p+1, and p-1.

6. The apparatus according to claim 4 wherein said value length establishing means includes means for establishing the length of factors of p+1, and p-1.

7. The apparatus according to claim 3 wherein said p value testing means further includes means for testing for primality of said first p-related secondary factor, said first p-related secondary factor being designated as r and being a factor of p+1.

8. The apparatus according to claim 7 wherein said p value testing means further includes means for testing for primality of said second p-related secondary factor, said second p-related secondary factor being designated as s and being a factor of p-1.

9. The apparatus according to claim 8 wherein said q value testing means further includes means for testing for primality of said first q-related secondary factor, said first q-related secondary factor being designated as t and being a factor of q+1.

10. The apparatus according to claim 9 wherein said q value testing means further includes means for testing for primality of said second q-related secondary factor, said second q-related secondary factor being designated as u and being a factor of q-1.

11. The apparatus according to claim 1 wherein said p value testing means further includes means for testing for primality of said first p-related secondary factor, said first p-related secondary factor being designated as r and being a factor of p+1.

12. The apparatus according to claim 1 wherein said p value testing means further includes means for testing for primality of said second p-related secondary factor, said second p-related secondary factor being designated as s and being a factor of p-1.

13. The apparatus according to claim 12 wherein said value length establishing means includes means for establishing the length of factors of p+1, and p-1.

14. For use in connection with an apparatus employing a public key n and a secret key comprising primary factors p and q where n=pq wherein said public key is a digital signal used for authenticating, enciphering, or authenticating and enciphering data and the secret key is used for signing, deciphering, or signing and deciphering the data, a method for generating said secret key and said public key such that recovery of said secret key from said public key is computationally infeasible, said method comprising:

establishing a length of said public key based on a desired security level;

establishing lengths of p-related secondary factors and p-related tertiary factors, q-related secondary factors and q-related tertiary factors which factors are functions of said secret key p and q;

choosing a tentative p value as one of said primary factors;

choosing a tentative q value as one of said primary factors;

testing said tentative p value for suitability as a part of said secret key based on two p-related secondary factors and two p-related tertiary factors, each one of said p-related tertiary factors and said p-related secondary factors being functions of said tentative p value;

testing said tentative q value for suitability as a part of secret key based on two q-related secondary factors and two q-related tertiary factors, each one of said q-related tertiary factors and said q-related secondary factors being functions of said tentative q value; and

presenting said public key and said secret key as digital electronic signals to an output utilization means.

15. The method according to claim 14 wherein said p value testing step comprises testing for primality of a value of a first p-related secondary factor r which is a factor of a value p+1 and testing for primality of a value of a second p-related secondary factor s which is a factor of a value p-1.

16. The method according to claim 15 wherein said q value testing step comprises testing for primality of a value of a first q-related secondary factor t which is a factor of a value q+1 and testing for primality of a value of a second q-related secondary factor u which is a factor of a value q-1.

17. The methods according to claim 16 wherein said value length establishing test comprises establishing the length of factors of p+1, and p-1.

18. The method according to claim 14 wherein said p value testing step further includes testing for primality of said first p-related secondary factor, said first p-related secondary factor being designated as r and being a factor of p+1.

19. The method according to claim 18 wherein said p value testing step further includes testing for primality of said first p-related tertiary factor, said first p-related tertiary factor being designated as r'"'"' and being a factor of r-1.

20. The method according to claim 16 wherein said q value testing step further includes testing for primality of said first q-related secondary factor, said first q-related secondary factor being designated as t and being a factor of q+1.

21. The method according to claim 20 wherein said q value testing step further includes testing for primality of said first q-related tertiary factor said first q-related secondary factor being designated as t'"'"' and being of a factor of t-1.

22. The method according to claim 21 wherein said p value testing step further includes testing for primality of said first p-related tertiary factor, said first p-related tertiary factor being designated r'"'"' and being a factor of r-1.

23. The method according to claim 22 wherein said p value testing step further includes testing for primality of said second p-related tertiary factor, said second p-related tertiary factor being designated s'"'"' and being a factor of s-1.

24. The method according to claim 23 wherein said q value testing step further includes testing for primality of said second q-related tertiary factor, said second q-related tertiary factor being designated u'"'"' and being a factor of u-1.