1. Field of the Invention
The present invention relates to a method and apparatus for performing public key cryptography.
2. Description of the Prior Art
When communicating over public networks, it is often necessary to secure communications in order to prevent interception or fraud by a third party. Cryptographic schemes often use intractable mathematical problems to ensure security of communications. In private key systems, two correspondents share a secret key prior to initiating communications. They can then employ an encryption algorithm using the secret value to keep their communication private from those who do not know the secret value. However, with such systems it is necessary for the two correspondents to agree on the secret beforehand, which may be as difficult as communicating securely in the first place.
Public key cryptosystems address the problem of distributing keys by assigning a pair of keys to each user. Each user has a private key and a corresponding public key, which are mathematically related so that it is computationally infeasible to derive the private key from the public key. The public key may be published and therefore made widely available to all users. To encrypt a message for a particular recipient, the sender uses the recipient's public key. Only the recipient knows the corresponding private key and therefore is the only party able to decrypt the message.
NTRU is a public key encryption system described in U.S. Pat. No, 6,081,597. The NTRU system uses a mathematical structure called a truncated ring of polynomials, which is denoted by R. The NTRU system uses four publicly known system parameters to initially set up the system. These are the degree of polynomials N, two moduli p, q, and the window parameter T. Typically, p is chosen to be 3 or X+2, and q is chosen to be a power of 2. The elements of the ring R may be represented as polynomials of a degree less than N. Operations in the ring are performed by polynomial addition and multiplication with the additional identity that XN=1.
To generate keys in the NTRU system, each user chooses secret polynomials f and g in the ring R. From the polynomial f, the user computes inverses modulo p and q which are denoted as fq−1 and fp−1 respectively. The user can then compute its public key h as fq−1 g. The private key consists of the polynomials f and fp−1.
When a second user wants to send the first user an encrypted message, it uses the first user's public key h. The second user also has access to the system parameters. A message m is encrypted as e=m+prh (mod q). The value r is randomly chosen for each encryption.
Upon receipt of an encrypted message m, the recipient decrypts the message by computing a=ef(mod q). The recipient then establishes a window in the range
            -      q        2    ⁢          ⁢  to  ⁢          ⁢            q      2        .  The recipient selects coefficients for a in the window. The recipient computes m=a fp−1 (mod p). The recipient then checks that m is in the set of valid messages. If m is in the set of valid messages, then the message has been recovered. Otherwise, the recipient chooses a new window and proceeds to select coefficients in the new window. The four mentioned steps are repeated. This may continue for multiple windows until a valid message is found. Once a valid message is found, execution will stop. If all of the possible windows are exhausted and no valid message has been found, then the recipient will experience an error condition and report that the message cannot be deciphered.
In order to avoid indecipherable messages, it has been suggested that the parameter T be chosen to be at least 30, and as large as 150. Since a large number of windows may be tested, it is likely that a valid message will be found eventually. In most cases however it is not necessary to check all of the windows.