1. Field of the Invention
This invention relates to the field of cryptographic systems.
2. Background Art
A cryptographic system is a system for sending a message from a sender to a receiver over a medium so that the message is xe2x80x9csecurexe2x80x9d, that is, so that only the intended receiver can recover the message. A cryptographic system (or cryptosystem) converts a message, referred to as xe2x80x9cplaintextxe2x80x9d into an encrypted format, known as xe2x80x9cciphertext.xe2x80x9d The encryption is accomplished by manipulating or transforming the message using a xe2x80x9ccipher keyxe2x80x9d or keys. The receiver xe2x80x9cdecryptsxe2x80x9d the message, that is, converts it from ciphertext to plaintext, by reversing the manipulation or transformation process using the cipher key or keys. So long as only the sender and receiver have knowledge of the cipher key, such an encrypted transmission is secure.
A xe2x80x9cclassicalxe2x80x9d cryptosystem is a cryptosystem in which the enciphering information can be used to determine the deciphering information. To provide security, a classical cryptosystem requires that the enciphering key be kept secret and provided to users of the system over secure channels. Secure channels, such as secret couriers, secure telephone transmission lines, or the like, are often impractical and expensive.
A system that eliminates the difficulties of exchanging a secure enciphering key is known as xe2x80x9cpublic key encryption.xe2x80x9d By definition, a public key cryptosystem has the property that someone who knows only how to encipher a message cannot use the enciphering key to find the deciphering key without a prohibitively lengthy computation. An enciphering function is chosen so that once an enciphering key is known, the enciphering function is relatively easy to compute. However, the inverse of the encrypting transformation function is difficult, or computationally infeasible, to compute. Such a function is referred to as a xe2x80x9cone way functionxe2x80x9d or as a xe2x80x9ctrap door function.xe2x80x9d In a public key cryptosystem, certain information relating to the keys is public. This information can be, and often is, published or transmitted in a non-secure manner. Also, certain information relating to the keys is private. This information may be distributed over a secure channel to protect its privacy (or may be created by a local user to ensure privacy).
In the prior art, the trap door functions have been based on the difficult problem of factoring integers. The factoring scheme is based on the fact that it is easy to generate two very large prime numbers and multiply them together, but it is much more difficult to factor the result, that is, to determine the very large prime numbers from their product. The product can therefore be made public as part of the enciphering key without compromising the prime numbers that effectively constitute the deciphering key.
Another form of public key cryptosystem is referred to as an xe2x80x9celliptic curvexe2x80x9d cryptosystem. An elliptic curve cryptosystem is based on points on an elliptic curve E defined over a finite field F. Elliptic curve cryptosystems rely for security on the difficulty in solving the discrete logarithm problem. An advantage of an elliptic curve cryptosystem is there is more flexibility in choosing an elliptic curve than in choosing a finite field. Nevertheless, elliptic curve cryptosystems have not been widely used in computer-based public key exchange systems due to their computational intensiveness. Computer-based elliptic curve cryptosystems are slow compared to other computer public key exchange systems. Elliptic curve cryptosystems are described in xe2x80x9cA Course in Number Theory and Cryptographyxe2x80x9d (Koblitz, 1987, Springer-Verlag, New York).
The invention is a cryptographic system using chaotic dynamics. A chaotic system is used to generate a public key and an adjustable back door from a private key. The public key is distributed and can be used in a public key encryption system. The invention can also be used for authentication purposes. The adjustable back door of the invention can be used in conjunction with the public key to derive the private key. The degree of difficulty involved in deriving the private key is dependent on the adjustable back door whose value can be adjusted to vary the difficulty involved in deriving the private key.
In its application to a public key encryption system, the invention uses a chaotic system model to generate a public key from a private key. A set of initial conditions is generated from the private key and becomes input to the chaotic system. The chaotic system generates a set of final conditions from which the public key is derived. The public key is distributed to the public. The public key can be used to encrypt a message that is then decrypted using the private key.
The invention can also be used for authentication. A chaotic system that implements a chaotic-dynamic model generates a public key from a private key. The public key is distributed to and stored at an authenticating site. During authentication, one wishing to authenticate oneself enters the private key that generated the public key into a chaotic system. The chaotic system implements the same chaotic-dynamic model that generated the public key from the private key. The output of the chaotic system is a public key. The authenticating system compares its stored public key with the new public key. If the two public keys are the same, authentication is successful. If the two public keys are not the same, authentication fails.
Using this approach, it is not necessary to disclose sensitive information to an authenticating system, or authenticator. Therefore, there is no need to rely on the authenticator to secure the information so that it is not accessible by an unauthorized person. Further, since the sensitive information is not transmitting to an authenticator, there is no danger of it being intercepted by an unauthorized person. Instead, a key that is not considered to be sensitive, the public key, is distributed and stored at the authenticating site. If authentication is performed as a prelude to accessing an account at a bank, for example, it is not necessary to store a bank user""s pin number or other secret information. At the time of authentication, the bank user enters the private key used to generate the public key into the chaotic system. The public key that results is compared with the stored public key to authenticate the user.
In one embodiment of the invention, the chaotic system is based on the xe2x80x9cN-bodyxe2x80x9d problem to provide cryptographic security. The general N-body problem is described by a Hamiltonian from classical physics. A Hamiltonian function describes all forces between all N bodies. One manifestation is the celebrated N-body scenario of Newtonian gravity. In this particular setting, one considers N (greater than 2) bodies acting under mutual gravitation. For example, the Newtonian gravity manifestation of the N-body problem can be described by considering a solar system with three or more planets in orbit. Given an initial condition and a set of rules or equations governing motion of the planets over time, and which are subject to chaotic variation, the future positions of the planets after a known fixed time period (e.g. after ten solar years) can be determined. However, given only the present conditions of the planets, it is extremely difficult to determine what the initial conditions were without knowing the elapsed time, all the rules governing the motion of the planets, and all the chaotic variations in motion that occurred. Thus, the N-body problem is a one way function.
The N-body problem describes a xe2x80x9cchaotic systemxe2x80x9d. This is because slight perturbations to the initial conditions of one or more of the bodies will cause radical system changes in the future. Accordingly, an inexact estimate of such initial conditions will result in a faulty final state. If someone tried to guess the initial conditions and ran the system for 10 solar years, the resulting positions would be very different from the positions that would occur using the correct initial conditions.
The invention uses mathematical representations of the N-body problem. The composition of the N-body system, and its initial conditions, rules of motion and time period are known only to the sender. A future state can be generated using the initial conditions and is used in the encryption process to generate a public key.