Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1999-01-27
2003-01-14
Barrón, Gilberto (Department: 2132)
Cryptography
Particular algorithmic function encoding
Public key
C713S170000
Reexamination Certificate
active
06507656
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to improved methods and apparatus for encryption and decryption of data.
BACKGROUND OF THE INVENTION
The present invention deals with the area of encryption and decryption of data messages. Encryption takes a cleartext message and produces an encrypted message also called a ciphertext. Decryption takes an encrypted message and produces its corresponding cleartext message.
It is known in the prior art how to take a message and turn it into an encrypted message using a first user's public key. The first user upon receiving the encrypted message can then decrypt it, to reveal the original message, using the first user's secret key. The first user's public key is as the name implies, available to the public so that others can send messages to the first user. However, the first user's secret key is not available. The public key is associated with a one-way function, i.e. once the message is encrypted it cannot be decrypted without the secret key even though the public key and the encryption algorithms are known.
El Gamal encryption is a standard method of encryption known in the art. In this method a first processor performing the encryption step, takes a message m as an input; chooses a random value “c”, and produces the outputs a=m*y
c
modulo p; b=g
c
modulo p. For El Gamal decryption, a second processor (which may be the first processor) calculates the data message m from m=a/b
x
modulo p. In the above y=g
x
modulo p is the public key and x is the secret key. The parameters g, x, and p and other system parameters are picked according to methods known to a person skilled in the art. The parameter g is a generator of the group G
p
. If we take all possible values of x and compute g
x
, this result will take all values in the group G
p
which is a large set of values. The value c is chosen at random by the entity that performs the encryption.
The ElGamal encryption method has the following weaknesses:
(1) Given an encryption (a,b) of an unknown data message m, it is possible to produce an encryption of a still unknown message, which corresponds to the value dm, by computing (a d modulo p, b). For example, if (a,b) is an encryption of the value m=3, then (a′,b′)=(4a,b) is an encryption of the value 4m=12. It is not necessary to know m to compute (a′,b′) from (a,b).
(2) Given the encryption pair or ciphertext (a,b) of data message m, it is possible to produce a ciphertext of m
d
as (a
d
modulo p, b
d
). For example, a correct message could be raised to some exponent and there would be no way of telling that had occurred.
(3) Given two ciphertexts (a
1
, b
1
) and (a
2
, b
2
), with (a
1
, b
1
) being an encryption of m
1
and (a
2
, b
2
) being an encryption of m
2
, it is possible to produce a ciphertext of the product of m
1
*m
2
modulo p as (a
1
*a
2
modulo p, b
1
*b
2
modulo p).
These three disadvantages and other and related ones are referred to in literature as malleability. Malleability is a threat to security, correctness of decryption of a message, and privacy in many situations. For example in an auction scenario if an offer for a product by a first individual is m$, given the ciphertext a second individual can overbid and make his offer 2*m without knowing how much “m” is but knowing that the second individual will win the bidding process. Using a similar attack one can duplicate votes in an election to determine (later when all votes are decrypted) what you voted (by looking for a duplicate). In the prior art malleability is avoided by forcing the value of the data message m to be encrypted to be of a particular form, such as to always end in a particular string of length approximately 100 bits. This technique of avoiding malleability has two disadvantages:
(a) First, it is not possible to determine that an encrypted message is of the valid form without decrypting it.
(b) Secondly, this is not known to result in a problem-free system (i.e. a ‘non-malleable encryption’) and cannot be proved to result in a non-malleable encryption.
However currently there are no other approaches better at dealing with the malleability problem without losing efficiency of the resulting scheme and ciphertext.
SUMMARY OF THE INVENTION
The present invention uses an encryption technique and a signing technique to provide a non-malleable encryption. An encryption processor takes a data message and produces an encryption using an encryption process. The encryption may also be called a ciphertext and typically would be comprised of first and second ciphertext portions. A signing processor takes the encryption and adds a signature to the first and second ciphertext portions using, for example, the second ciphertext portion as the public key for the signature. A receiver processor receives the ciphertext and the signature, decrypts the ciphertext to form a first data message, and determines if the first data message is valid by verifying the signature.
The encryption processor may employ ElGamal encryption for the encryption process to form the encryption. The signing processor may perform a Schnorr signature process for the signing process or any other similar discrete log based signature, as appreciated by those skilled in the art. The signing processor may use part of the encryption process to perform the signing process.
REFERENCES:
patent: 5265164 (1993-11-01), Matyas et al.
patent: 5627893 (1997-05-01), Demyktko
patent: 5901303 (1999-05-01), Chew
patent: 6279118 (2001-08-01), Johnson et al.
patent: 6282295 (2001-08-01), Young et al.
patent: 6298442 (2001-10-01), Kocher et al.
Schneier, Bruce, Applied Crytography 1996, John Wiley & Sons, Inc., Second ed., pp. 478-479, 483-494, and 510-512.
Barrón Gilberto
Lucent Technologies - Inc.
Meislahn Douglas J.
Tencza Jr. Walter J.
LandOfFree
Non malleable encryption apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Non malleable encryption apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non malleable encryption apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3050149