Method of deriving a per-message signature for a DSS or El Gamal encryption system

• US 5,475,763 A
• Filed: 02/28/1994
• Issued: 12/12/1995
• Est. Priority Date: 07/01/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation PAT Law Group
• Inventors: Perlman, Radia J., Kaufman, Charles W.
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/203,740
• Time in Patent Office: 652 Days
• Field of Search: 380/23-25, 380/30, 380/49, 380/50, 380/46, 235/379, 235/380
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A signature system, such as an El Gamal or DSS system, involving the use of a long-term secret number and a per-message secret number generates the per-message secret number without the use of a random number generator or non-volatile storage. The per-message secret number is generated by applying a one-way hash function to a combination of the long-term secret number and the message itself.

Claims

1. A message authentication system of the type in which a signature of an originator of a message MSG, hereinafter the message originator, is transmitted to a recipient of the message and verified by the recipient, the message originator having a secret number S_L and a corresponding public number P_L, said system comprising:

means for receiving the MSG;

means for generating a secret message for each message, a per-message secret number, S_M by applying a one-way hash function to a combination of MSG and a generated secret number of the message originator,

means for generating a signature as a function of S_L, S_M and MSG.

2. The system defined in claim 1 further including:

means for generating a per-message public number P_M as a function of S_M, and

means for transmitting, to the recipient, the message, the signature and the per-message public number;

means for receiving, by the recipient, the message, the signature and the per-message public number.

3. The system defined in claim 2 including means for the message recipient to verify the signature SIG in accordance with a function of MSG, SIG, P_L and P_M.

4. The system of claim 1 in which said one-way hash function is a message digest function.

5. A message authentication system comprising:

A. a data terminal including;

1. means for receiving a message input and

2. means for communicating with a smart card, and

B. the smart card configured to communicate with said terminal and including;

1. means for storing a secret number specific to an owner of the smart card,

2. means for generating a secret number for each message, hereinafter referred to as a per-message secret number by, applying a one-way hash function to a combination of (a) a secret number specific to the owner of the smart card and (b) a message received by said terminal by way of said message input means,

3. means for generating a signature as a function of said secret number, said per-message secret number and said message,

4. means for generating a per-message public number as a function of said per-message secret number;

5. means for transmitting to said terminal the signature and the per-message public number; and

6. means for verifying in the terminal.

6. The system defined in claim 5 in which said one-way hash function is a message digest function.

7. The system defined in claim 5 in which said combination is a concatenation of the secret number and the message.

8. A smart card for use in authenticating messages, said smart card including:

A. means for storing a secret number specific to an owner of the smart card,

B. means for receiving a message to be authenticated,

C. means for generating a secret number for each message, hereinafter referred to as a per-message secret number, by applying a one-way hash function to a combination of said message and a secret number specific to said owner,

D. means for generating a signature as a function of said secret number, said per-message secret number and said message, and

E. means for transmitting said signature to a recipient.

9. The smart card defined in claim 8 in which said combination is a concatenation of said secret number and said message.

10. The smart card defined in claim 8 further including:

A. means for generating a per-message public message as a function of said per-message secret number, and

B. means for transmitting said per-message public number.

11. A method for enabling verification of an originator of a message, said method comprising the steps of:

A. generating a secret number for each message, hereinafter referred to as a per-message secret number, by applying a one-way hash function to a concatenation of said message with a secret number specific to the originator of the message,

B. generating a signature as a function of a secret number specific to the originator of the message, the short-term secret number, and the message; and

C. transmitting said signature and the message to a recipient for verification.

12. The method defined in claim 11 including the further steps of:

A. generating a per-message public number as a function of the per-message secret number and

B. transmitting said per-message public number to the recipient.