Programmed computer for identity verification, forming joint signatures and session key agreement in an RSA public cryptosystem

• US 5,905,799 A
• Filed: 10/15/1996
• Issued: 05/18/1999
• Est. Priority Date: 07/20/1994
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Bell Atlantic Network Services, Inc. (Verizon Communications Inc.)
• Inventors: Ganesan, Ravi
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/731,428
• Time in Patent Office: 945 Days
• Field of Search: 380/30, 380/21, 380/49
• US Class Current: 380/279
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

An article of manufacture for improving an RSA cryptosystem, includes computer readable storage medium with computer programming stored thereon. The stored computer programming is configured to be readable from the computer readable storage medium by a computer and thereby cause the computer to operate so as to generate a private exponent key, having an associated modulus N of a predetermined bit length and a bit length of no greater than fifteen percent of the bit length of the associated modulus N but not less than 56 bits, and a corresponding public exponent key, to divide the private exponent key into a first private key portion and a second private key portion, to direct said first private key portion to a first user, and to direct the second private key portion to one or more other users of the RSA system.

Claims

1. An article of manufacture for use in a cryptosystem, comprising:

computer readable storage medium; and

computer programming stored on said storage medium;

wherein said stored computer programming is configured to be readable from said computer readable storage medium by a computer and thereby cause said computer to operate so as to;

generate a private exponent key, having an associated modulus N of a predetermined bit length, and a corresponding public exponent key;

divide said private exponent key into a first private key portion, having a bit length of no greater than fifteen percent of the bit length of the associated modulus N but not less than 56 bits, and a second private key portion;

direct said first private key portion to a first user; and

direct said second private key portion to a selected one or more other users of the RSA system.

2. An article of manufacture according to claim 1, wherein said private exponent key is comprised of a private exponent and the modulus N, the modulus N is a product of two large prime numbers, and said public exponent key is comprised of a public exponent and the modulus N.

3. An article of manufacture according to claim 1, wherein said bit length of said first private key portion is between 56 and 72 bits.

4. A programmed computer for use in a cryptosystem, comprising:

a processor configured to generate a private exponent key, having an associated modulus N of a predetermined bit length, and a corresponding public exponent key, to divide said private exponent key into a first private key portion, having a bit length of no greater than fifteen percent of the bit length of the associated modulus N but not less than 56 bits, and a second private key portion, to direct said first private key portion to a first user, and to direct said second private key portion to a selected one or more other users of the RSA system; and

storage medium configured to store the public exponent key.

5. A programmed computer according to claim 4, wherein said private exponent key is comprised of a private exponent and the modulus N, the modulus N is a product of two large prime numbers, and said public exponent key is comprised of a public exponent and the modulus N.

6. A programmed computer according to claim 4, wherein said bit length of said first private key portion is between 56 and 72 bits.

7. An article of manufacture for use in a cryptosystem in which each user is associated with a private exponent key having an associated modulus N of a predetermined bit length, and a corresponding public exponent key, said private exponent key being divided into two private key portions, one private key portion being available to a first user, and the other private key portion being available to a second user of the cryptosystem, comprising:

computer readable storage medium; and

computer programming stored on said storage medium;

wherein said stored computer programming is configured to be readable from said computer readable storage medium by a computer and thereby cause said computer to operate so as to;

transform a message from the first user with a first private key portion having a bit length no greater than fifteen percent of the modulus N but not less than 56 bits; and

direct the transformed message to the second user, wherein the message is recoverable by applying a second private key portion and public exponent key thereto to verify that the message is from the first user.

8. An article of manufacture according to claim 7, wherein said stored computer programming is configured to be readable from said computer readable storage medium by the computer to thereby cause said computer to operate so as to:

recover a second message from the second user, encrypted with said second private key portion, by applying the first private key portion and public exponent key to the encrypted second message, to verify that the message is from the second user.

9. An article of manufacture according to claim 8, wherein said stored computer programming is configured to be readable from said computer readable storage medium by the computer to thereby cause said computer to operate so as to:

compare the recovered second message with another message to make said verification.

10. An article of manufacture according to claim 7, wherein said bit length of said first private key portion is between 56 and 72 bits.

11. An article of manufacture according to claim 7, wherein transformation of the message with the first private key portion serves as a signature of the first user on the message and said stored computer programming is configured to be readable from said computer readable storage medium by the computer to thereby cause said computer to operate so as to:

invert a jointly signed message, said jointly signed message having been formed by a further transformation of the transformed message with a second private key portion which serves a signature of the second user on said message, by applying thereto said public exponent key to verify the signatures of the first and the second users on the message.

12. A programmed computer for use in a cryptosystem in which each user is associated with a private exponent key having an associated modulus N of a predetermined bit length, and a corresponding public exponent key, said private exponent key being divided into two private key portions, one private key portion being available to a first user, and another private key portion being available to a second user of the cryptosystem, comprising:

a processor configured to transform a message from the first user with a first private key portion having a bit length no greater than fifteen percent of the modulus N but not less than 56 bits, and to direct the transformed message to the second user, wherein the message is recoverable by applying a second private key portion and public exponent key thereto to verify that the message is from the first user; and

a storage medium configured to store the public exponent key.

13. A programmed computer according to claim 12, wherein said processor is further configured to recover a second message from the second user, encrypted with said second private key portion, by applying the first private key portion and public exponent key to the encrypted second message, to verify that the message is from the second user.

14. A programmed computer according to claim 13, wherein said processor is further configured to compare the recovered second message with another message to make said verification.

15. A programmed computer according to claim 12, wherein said bit length of said first private key portion is between 56 and 72 bits.

16. A programmed computer according to claim 12, wherein transformation of the message with the first private key portion serves as a signature of the first user on the message and said processor is further configured to:

invert a jointly signed message, said jointly signed message having been formed by a further transformation of the transformed message with a second private key portion which serves as a signature of the second user on said message, by applying thereto said public exponent key to verify the signatures of the first and the second users on the message.

17. An article of manufacture for use in a cryptosystem in which each user is associated with a private exponent key and a corresponding public exponent key, said private exponent key being divided into two private key portions, one private key portion being available to a first user, and the other private key portion being available to a second user of the cryptosystem, and the public exponent key being available to said first and second users, comprising:

computer readable storage medium; and

computer programming stored on said storage medium;

wherein said stored computer programming is configured to be readable from said computer readable storage medium by a computer and thereby cause said computer to operate so as to;

transform a first number with a first private key portion having a bit length of (i) no greater than fifteen percent of a bit length of an associated modulus N and (ii) not less than 56 bits;

direct the transformed first number to the second user, wherein the first number is recoverable by applying a second private key portion and public exponent key thereto;

recover a second number, transformed with the second private key portion, by applying said first private key portion and the public exponent key to the transformed second number;

multiply the first number and the second number to form a joint symmetric session encryption key; and

transform a communication between said first user and said second user with said session encryption key.

18. An article of manufacture according to claim 17, wherein said first user key portion has a bit length between 56 and 72 bits.

19. A programmed computer for use in a cryptosystem in which each user is associated with a private exponent key and a corresponding public exponent key, said private exponent key being divided into two private key portions, one private key portion being available to a first user, and the other private key portion being available to a second user of the cryptosystem, and the public exponent key being available to said first and second users, comprising:

a processor configured (i) to transform a first number with a first private key portion having a bit length of no greater than fifteen percent of a bit length of an associated modulus N and not less than 56 bits, (ii) to direct the transformed first number to the second user, wherein the first number is recoverable by applying a second private key portion and public exponent key thereto, (iii) to recover a second number, transformed with the second private key portion, by applying said first private key portion and the public exponent key to the transformed second number, (iv) to multiply the first number and the second number to form a joint symmetric session encryption key, and (v) to transform a communication between said first user and said second user with said session encryption key; and

a storage medium configured to store the session encryption key.

20. A programmed computer according to claim 19, wherein said first user key portion has a bit length between 56 and 72 bits.