Non malleable encryption method and apparatus using key-encryption keys and digital signature

• US 6,931,126 B1
• Filed: 01/19/2000
• Issued: 08/16/2005
• Est. Priority Date: 01/27/1999
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Schnorr, Claus Peter, Jakobsson, Bjorn Markus
• Primary Examiner(s): Barron, Gilberto
• Assistant Examiner(s): KIM, JUNG W
• Application Number:
  US09/487,946
• Time in Patent Office: 2,036 Days
• Field of Search: 713/169, 713/176, 380/28, 380/30
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A fast encryption method particularly useful for long message lengths is provided. A message m is encrypted using a transmitter secret key z to form a quantity E. A transmitter processor prepares a quadruplet (a_new, b_new,s_new, E) where:
a_new=z*y^cmodulo p;
b_new=g^cmodulo p;
s_new=signature_c(a_new,b_new,E).

As in previous embodiments y=g^xmodulo p is the public key and x is the receiver secret key. The parameters g, x, and p according to methods known to a person skilled in the art and the parameter g is a generator of the group G_p. The parameter c is a random number. The transmitter processor sends the quadruplet (a_new, b_new,s_new, E) to a receiver processor. The receiver processor verifies the signature on s_new using methods known in the art. The receiver processor then decrypts a_new and b_new using the receiver secret key x to get the transmitter secret key z, i.e. in the following manner z=a_new/b_new^x. The receiver processor uses the transmitter secret key z to decrypt E to get the message M.

Claims

1. A method comprising the steps of:

encrypting a data message m at a transmitter processor using a primary transmitter secret key z, wherein z is known to the transmitter processor but not to a receiver processor, to form a quantity E;

preparing a quadruplet (a_new, b_new,s_new, E) at the transmitter processor where;

a_new=z*y^cmodulo p;

b_new=g^cmodulo p;

s_new=signature_c(a_new,b_new,E);

where y=g^xmodulo p, c is a random number, x is a receiver secret key of the receiver processor, and the parameters g, x, and p are picked using a known encryption method;

wherein s_new is a signature which is determined by using the same random number c that was used to determine a_new and b_new;

transmitting the quadruplet (a_new, b_new,s_new, E) from the transmitter processor to the receiver processor;

verifying the signature s_new at the receiver processor;

decrypting a_new and b_new at the receiver processor by using the receiver secret key x to get the primary transmitter secret key z;

using the primary transmitter secret key z to decrypt the quantity E and thereby obtaining the message m at the receiver processor.

2. The method of claim 1 and wherein:

the step of decrypting a_new and b_new at the receiver processor using the receiver secret key x to get the primary transmitter secret key z is comprised of computing z=a_new/b_new^x.

3. The method of claim 1 wherein:

the primary transmitter secret key z is determined at the transmitter processor from the formula of z=g^γ

modulo p, where γ

is a random value chosen from the set [0 . . . q], where q is a value picked using a known encryption method.

7. The method of claim 1 wherein

the signature s_new is determined by using a Schnorr signature method.

8. The method of claim 1 wherein

the signature s_new is determined using a Digital Signature Standard.

12. The method of claim 1 wherein

El Gamal encryption is used for the encrypting steps.

4. A method comprising the steps of:

creating a primary transmitter key z at a transmitter processor wherein the primary transmitter key is known to the transmitter processor but not to a receiver processor;

creating a secondary transmitter key z′

at the transmitter processor wherein the secondary transmitter key is known to the transmitter processor but not to the receiver processor, wherein the secondary transmitter key z′

is a function of z;

encrypting a data message m, at the transmitter processor, using the secondary transmitter secret key z′

to form a quantity;

preparing a quadruplet (a_new, b_new,s_new, E) at the transmitter processor, where;

a_new=z*y^cmodulo p;

b_new=g^cmodulo p;

s_new=signature_c(a_new,b_new,E);

where y=g^xmodulo p, c is a random number, x is a receiver secret key of the receiver processor, and the parameters g, x, and p are picked using a known encryption method;

wherein s_new is a signature which is determined by using the same random number c that was used to determine a_new and b_new;

transmitting the quadruplet (a_new, b_new,s_new, E) from the transmitter processor to the receiver processor;

verifying the signature s_new at the receiver processor;

decrypting a_new and b_new at the receiver processor, using the receiver secret key x to get the primary transmitter secret key z;

modifying the primary transmitter secret key z, at the receiver processor, to obtain the secondary transmitter secret key z′ and

using the secondary transmitter secret key z′

to decrypt the quantity E and thereby obtaining the message m, at the receiver processor.

5. The method of claim 4 and wherein:

the primary transmitter key z is provided which is not of the format used for producing the ciphertext E;

the secondary transmitter key z′

is computed as a function of z, where the function is an arbitrary function.

13. The method of claim 4 wherein

El Gamal encryption is used for the encrypting steps.

6. A method comprising the steps of:

creating a primary transmitter key z at a transmitter processor;

creating a secondary transmitter key z′

which is a function of z, at the transmitter processor;

providing a plurality of portion keys which are derived from the secondary transmitter key z′

, at the transmitter processor;

encrypting a data message m, at a transmitter processor, using the plurality of portion keys to form a quantity E;

preparing a quadruplet (a_new, b_new,s_new, E), at the transmitter processor, where;

a_new=z*y^cmodulo p;

b_new=g^cmodulo p;

s_new=signature_c(a_new,b_new,E);

where y=g^xmodulo p, c is a random number, x is a receiver secret key of a receiver processor, and the parameters g, x, and p are picked using a known encryption method;

wherein s_new is a signature which is determined by using the same random number c that was used to determine a_new and b_new;

transmitting the quadruplet (a_new, b_new,s_new, E) from the transmitter processor to the receiver processor;

verifying the signature s_new at a the receiver processor;

decrypting a_new and b_new, at the receiver processor, using the receiver secret key x to get the primary transmitter secret key z;

modifying the primary transmitter secret key z, at the receiver processor, to obtain the secondary transmitter secret key z′ and

using the secondary transmitter secret key z′

to determine the plurality of portion keys and using the plurality of portion keys to decrypt the quantity E and thereby obtaining the message m, at the receiver processor.

14. The method of claim 6 wherein

El Gamal encryption is used for the encrypting steps.

9. An apparatus comprising

a transmitter processor;

wherein the transmitter processor

encrypts a data message m using a primary transmitter secret key z, known to the transmitter processor but not known to a receiver processor, to form a quantity E; and

prepares a quadruplet (a_new, b_new,s_new, E) where;

a_new=z*y^cmodulo p;

b_new=g^cmodulo p;

s_new=signature_c(a_new,b_new,E);

where y=g^xmodulo p, c is a random number, x is a receiver secret key of the receiver processor, and the parameters g, x, and p are picked using a known encryption method; and

wherein s_new is a signature, and wherein the transmitter processor determines s_new by using the same random number c that was used to determine a_new and b_new.

10. The apparatus of claim 9 wherein

the transmitter processor uses a Schnorr signature method to determine s_new.

11. The apparatus of claim 9 wherein

the transmitter processor uses a Digital Signature Standard to determine s_new.

15. The apparatus of claim 9 wherein

El Gamal encryption is used for encrypting.