Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1999-02-16
2004-02-24
Sheikh, Ayaz (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C380S028000, C380S044000
Reexamination Certificate
active
06697488
ABSTRACT:
TECHNICAL FIELD
The invention relates to secure communications. More particularly the invention relates to cryptographic communication systems and methods for use in data-processing systems to enhance security. The proposed public-key cryptosystem is secure against a lunch-time attack and an adaptive chosen ciphertext attack.
BACKGROUND OF THE INVENTION
Secrecy and security are important factors in today's computationally connected world. Transmitted information is restricted to an intended receiver and not suitable for everyone. For assuring secure and authenticated communications, cryptographic methods arc help- and useful. A cryptographic system is a system for sending a message from a sender to a receiver over a medium so that the message is ‘secure’. That means, only the intended receiver can recover the message. The cryptographic system converts the message, also referred to as plaintext, into an encrypted format, known as ciphertext. The encryption is accomplished by manipulating or transforming the message using a cipher key or keys. The receiver decrypts the message by converting the ciphertext back to plaintext. This is performed by reversing the manipulation or transformation process using the cipher key or keys. Such an encrypted transmission is secure, so long as only the sender and the receiver have knowledge of the cipher key. Several cryptographic systems have been proposed in the past such as public-key cryptosystems. In general, an information used with an algorithm to encrypt and decrypt a message is called a key. The public key cryptosystem uses two keys, one private and one public, which are related to each other. Hence, in the public-key cryptosystem, the private key is always linked mathematically to the public key. Therefore, it is always possible to attack a public-key system by deriving the private key from the public key. Typically, the defense against this is to make the problem of deriving the private key from the public key as difficult as possible.
Diffie-Hellman:
A first public-key cryptographic scheme was published by Diffie and Hellman, “New Directions in Cryptography”, IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, November 1976. This scheme, also referred to as Diffie-Hellman key agreement, describes a public-key system based on discrete exponential and logarithmic functions and is primarily used for public-key exchange and public-key cryptosystems. The basis for the technique is the difficulty of calculating logarithms in modular arithmetic. Say A and B wish to establish a key. A sends B a number g, a modulus p and the number h
1
=g
e1
mod(p), where e
1
is a large number. B then sends back to A the number h
2
=g
e1
mod(p). They each then use the number k=g
(e1 e2)
=h
1
e2
=h
2
e1
mod(p) as the private key. Any adversary must be able to calculate either e
1
from g, h
1
or e
2
from g, h
2
. This is believed to be very hard for large enough values of g and p, since no general, fast algorithms are known for solving a discrete logarithm function.
RSA:
Another public-key cryptosystem is disclosed in “On Digital Signatures and Public key Cryptosystems”, Commun. Ass. Comput. Mach., vol. 21, pp. 120-126, 1979, by R. L. Rivest, A Shamir, and L. M. Adelman. The so-called RSA scheme is based on the fact that it is easy to generate two large primes and multiply them, whereas it is much more difficult to factor the result, that is, to derive the large primes from their product. Therefore it should be computationally infeasible to perform this derivation. The product can therefore be made public as part of the enciphering key without compromising the primes that constitute the deciphering key.
ElGamal:
The publication “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms” by T. ElGamal in the IEEE Trans. Inform. Theory, vol. IT-31, pp. 469-472, 1985, proposes a further public-key cryptosystem which implements the Diffie-Hellman key agreement. The ElGamal scheme comprising a secret key z and a public key h can be described in a simple way as the following. A message m can be encoded as elements of a cryptographic group G. The secret key z can be chosen at random from a set of numbers modulo q, denoted as Z
q
. The public key h is calculated by h=g
z
, whereby g is also chosen from the group G at random. The encryption starts by choosing a random element r in Z
q
. A ciphertext comprising u and e is derived by u=g
r
and e=h
r
m. This ciphertext can be decrypted to the message m by m=e/u
z
. The security of the ElGamal encryption scheme relies on the difficulty of recomputing discrete logarithms, but the ElGamal encryption is only secure against passive attacks and not secure against chosen ciphertext attacks. In particular, the ElGamal encryption scheme is trivially malleable. Thus, if u, e encrypts m, then u, ea encrypts ma.
All mentioned schemes are insecure against active attacks, in which an attacker or adversary can inject chosen messages into the stream of data and observe the resulting behaviors. An “adaptive chosen ciphertext attack” is the strongest known form of this kind of attack and is generally accepted to be the most aggressive kind of attack that any cryptosystem should be expected to withstand. Such an attack is one in which an adversary has access to a “decryption oracle”, e.g. a server, allowing the adversary to decrypt ciphertexts of his choice. The word “adversary” is commonly used in cryptography to refer to an opponent, an enemy, or any other mischievous person that desires to compromise one's security. Typically, one distinguishes between a weak form of attack, known as a lunch-time attack, and the strongest possible form, the adaptive chosen ciphertext attack. In the lunch-time attack, the adversary queries the decryption oracle a number of times, after which the adversary obtains the target ciphertext that the adversary wishes to cryptanalyze, and is not allowed to query the decryption oracle further. In an adaptive attack, the adversary may continue to query the decryption oracle after obtaining the target ciphertext, whereby the adversary repeats the following process: he sends requests to the software or hardware units implementing the cryptographic scheme, observes the responses, and based on the responses constructs and sends more requests, with the aim of eventually breaking the scheme. In fact the adversary may send any ciphertext to the decryption oracle, except the target ciphertext. D. Bleichenbacher discloses in “Chosen ciphertext attacks against protocols based on RSA encryption standard PKCS #1”, Advances in Cryptology-Crypto '98, pp. 1-12, 1998, design flaws in the widely used Internet security protocol SSL (Secure Socket Layer). Bleichenbacher's attack is a direct attack on what is supposed to be secure: the security protocol and the underlying encryption system. As mentioned above, such an adversary does more than just eavesdrop: he plays an active rule, sending carefully crafted encryptions to the SSL server, and then observes how the server responds to these encryptions. Based on these observations, the adversary can crack the code.
For many years, no public-key system was shown to be secure under a chosen ciphertext attack. M. Naor and M. Yung presented the first scheme provably secure against lunch-time attacks in their publication “Public-key cryptosystems provably secure against chosen ciphertext attacks”, in 22nd Annual ACM Symposium on Theory of Computing, pages 427-437, 1990. Subsequently, D. Dolev, C. Dwork, and M. Naor presented in their publication “Non-malleable cryptography”, in 23rd Annual ACM Symposium on Theory of Computing, pages 542-552, 1991, a scheme which is secure against adaptive chosen ciphertext attack. All of the known schemes provably secure under standard intractability assumptions are completely impractical, as they rely on general and expensive constructions for non-interactive zero-knowledge proofs.
I Damgard. proposed in the publication “Towards practical pub
Cramer Ronald
Shoup Victor
Herzberg L.
Sheikh Ayaz
Song Hosuk
LandOfFree
Practical non-malleable public-key cryptosystem does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Practical non-malleable public-key cryptosystem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Practical non-malleable public-key cryptosystem will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3318689