Cryptography – Key management – Key distribution
Reexamination Certificate
1997-10-24
2002-05-28
Barron, Jr., Gilberto (Department: 2132)
Cryptography
Key management
Key distribution
C380S283000, C713S168000, C713S169000, C713S170000, C713S181000
Reexamination Certificate
active
06396928
ABSTRACT:
This invention relates to a method and system for performing digital message signature and encryption for secure and authenticated communication.
To avoid forgery and ensure confidentiality of a message, for example the contents of a letter, for centuries it has been a common practice for the originator of the letter to sign his/her name on it and then seal it in an envelope, before effecting delivery. More recently, digital messages, communicated telephonically or the like, have become increasingly used, and public key cryptography has been employed to conduct secure and authenticated communications.
It is thereby possible for people who have never met before to communicate with one another in a secure and authenticated way over an open and insecure network such as Internet. In doing so the same two-step approach used for conventional letters has been followed. Namely, before a message is sent out, the sender of the message would sign it using a digital signature scheme, and then encrypt the message (and the signature) using a private key encryption algorithm under a randomly chosen message encryption key. The random message encryption key would then be encrypted using the recipients public key. This two-step approach is referred to as signature-then-encryption.
Signature generation and encryption consume machine cycles, and also introduce “expanded” bits to an original message. Hence the cost of a cryptographic operation on a message is typically measured in the message expansion rate and the computational time invested by both the sender and the recipient. With the current standard signature-then-encryption, the cost of delivering a message in a secure and authenticated way is essentially the sum of the cost for digital signature and that for encryption.
The present invention aims to provide a method and system, referred to as “signcryption”, in which the processes of encryption and authentication of a message are combined so as to achieve improved computational efficiency and reduced message transmission overhead.
In accordance with the present invention, there is provided a method for authenticated encryption of a digital message m for transmission from a sender having a public key y
a
and a secret key x
a
and a receiver having a public key y
b
and a secret key x
b
, comprising:
determining a message key k using the receiver public key and a randomly selected number x;
calculating a first message parameter r, comprising a message authentication code from said digital message m and a first portion of said message key k;
calculating a second message parameter s from the sender private key, the randomly selected number x and the first message parameter r, such that said message key k is recoverable by the receiver from an arithmetic operation of said first and second message parameters, the sender public key and the receiver private key; and
encrypting said digital message m using a second portion of said message key k to obtain cipher text c.
Preferably the cipher text c is transmitted from said sender to said receiver together with said first and second message parameters. The receiver may then recover the message key k from said first and second message parameters with said sender public key and said receiver private key, and decrypt the cipher text c using the second portion of the recovered message key to obtain said digital message. The recovered digital message can then be validated by calculating the first message parameter using the recovered digital message and the first portion of the recovered message key and making a comparison with the first message parameter received with the cipher text.
In one form of the invention the message key k is calculated according to k=y
b
x
mod p, where p is a large prime. Before splitting the message key into first and second portions, it is possible to apply a ore-way hashing or folding function, for example, in order to obtain first and second message key portions which are of suitable length for calculating said first message parameter and encrypting said digital message, respectively.
Preferably, the first message parameter comprises a keyed hash of the digital message using the first portion of the message key.
Preferably the second message parameter is calculated according to a modified ElGamal signature scheme in which the hashed digital message value is replaced by the value 1 or the first message parameter. A similar modification of the Schnorr signature scheme or Digital signature standard may similarly be used to calculate the second message parameter.
The digital message itself may be encrypted using any suitable keyed encryption algorithm, such as the Digital Encryption Standard (DES), or the like.
Advantageously, the only data required to be transmitted between the sender and receiver to enable secure authenticated message delivery is the cipher text c and the first and second message parameters r and s, because the message key can be recovered from the first and second message parameters, and the message content can be verified using the message key and the first message parameter r.
The present invention also provides a method of preparing a digital message m for secure and authenticated communication from a sender having a public key y
a
and a private key x
a
to a receiver having a public key y
b
and a private key x
b
, comprising:
determining a message key k based on the receiver public key y
b
and a randomly selected number x;
splitting the message key k into first and second keys k
1
and k
2
;
calculating a first message parameter r as a keyed hash of said digital message using said first key k
1
;
calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key x
a
and said first message parameter r;
encrypting said digital message using said second key k
2
to obtain cipher data c; and appending said cipher data c with said first and second message parameters for transmission to said receiver.
In a system for transmission of digital messages between a sender having a public key y
a
and a secret key x
a
and a receiver having a public key y
b
and a secret key x
b
, and having public parameters p being a prime number, q being a prime factor of (p−1), and g being an integer in the range 1 to (p−1) with order (p−1) modulo p, the present invention also provides a method for authenticated encryption of a digital message m, comprising the steps of:
selecting a random number x in the range 1 to (p−1) such that x does not divide (p−1); determining a message key;
splitting the message key k into first and second keys k, and k
2
;
calculating a first message parameter r as a keyed hash of said digital message m using said fist key k
1
;
calculating a second message parameter s on the basis of modular arithmetic to base q utilising said random number x, said sender private key x
a
and said first message parameter r;
encrypting said digital message m using said second key k
2
to obtain cipher data c; and
appending said cipher data c with said first and second message parameter r and s for transmission to said receiver.
The preset invention further provides a method for secure and authenticated communication of a digital message m from a sender having a public key y
a
and a private key x
a
to a receiver having a public key y
b
and a private key x
b
, comprising.
determining a message key k based on the receiver public key y
b
and a randomly selected number x;
splitting the message key k into first and second keys k
1
and k
2
;
calculating a first message parameter r as a keyed hash of said digital message using said first key k
1
;
calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key x
a
and said first message parameter r;
encrypting said digital message using said second key k
2
to obtain cipher data c;
transmitting the cipher data c and the first and second message parameters r and s to said receiver;
recovering said message key from an operation using said
Baker & Botts L.L.P.
Barron Jr. Gilberto
Darrow Justin T.
Monash University
Sullivan Jeffrey D.
LandOfFree
Digital message encryption and authentication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital message encryption and authentication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital message encryption and authentication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2911215