Public key cryptosystem with an elliptic curve

Abstract

The present invention provides a public key cryptosystem with an elliptic curve which comprises the steps of informing public data, selecting first and second privacy keys at the end of first and second users, mutually notifying numbers calculated by the public data and the first and second privacy keys, calculating a common key by using the first privacy key and the number from the second user or by using the second privacy key and the number from the first user, ciphering transmission data using the common key by either the first or second user, and deciphering the ciphered data using the common key by the other use. The step of informing public data includes the stages of choosing d as a positive integer such that gives an imaginary quadratic field Q((-d))1/2) a small class number, choosing p as a prime number such that 4*p-1=d*square number, so that an elliptic curve E over GF(p) will have a j-invariant as a solution modulo p for a class polynomial Hd(x)=0 which is fixed by d, finding an order of a point other than a zero element from E1(GF(p)), choosing an elliptic curve E over (GF(p)) having exact p order, and choosing an element other than the zero element of E(GF(p)) as a base point.

What is claimed is: 
     
       1. A method of applying a public key encryption network system to users from a provider by using an elliptic curve, comprising the steps of: supplying on the network system public data to each of the users from the provider;   selecting a first privacy key at a terminal of a first user and selecting a second privacy key at a terminal of a second user wherein the first and second privacy keys are different;   notifying a number calculated with the public data and the first privacy key to the second user from the first user, and notifying a number calculated with the public data and the second privacy key to the first user from the second user;   calculating a common key by using the first privacy key and the number from the second user at the site of the first user, and calculating the common key by using the second privacy key and the number from the first user at the site of the second user;   ciphering data to be transmitted using the common key at a site of one of the first and second users; and   deciphering the ciphered data using the common key at the site of other user,   wherein the step of supplying public data includes the steps of:   choosing d as a positive integer such that it gives an imaginary quadratic field Q(-d) 1/2 ) a small class number, choosing p as a prime number such that 4*p-1=d*square number, so that an elliptic curve E having GF(p) as a field of definition will have a j-invariant as a solution modulo p for a class polynomial H d  (x)=0 which is filed by d;   finding an order of a point other than a zero element from a group consisting of the elements of GF(p) denoted as E 1  (GF(p));   choosing an elliptic curve E over GF(p) having exact p order; and   choosing an element other than the zero element of E(GF(p)) as a base point.   
     
     
       2. The method of claim 1, wherein 1 is a class number for the imaginary quadratic field Q((-d 1/2 ). 
     
     
       3. A secure communication network system for transmitting data with a plurality of elliptic curves, comprising: means for enciphering a data message for each user of the network system;   means for deciphering the data message for each user of the network system;   means for generating an identity data code for each user and exchanging the same with a network provider to create individual enciphering keys between the network provider and each user; and   means for communicating the data message over the network including enciphering the data message with a user enciphering key with a first elliptic curve, deciphering the data message by the network provider with the same enciphering key and re-enciphering the data message with a second elliptic curve and transmitting it to another user by use of that user's enciphering key.   
     
     
       4. A method of privacy communication over a television subscriber network between a program supplier and individual users, comprising the steps of: providing a communication network to a plurality of users;   providing data of an elliptic curve E and an element p, to each user who wishes to receive communications over the network;   the users exchanging with the program supplier an enciphering key which combines the elliptic curve E, element p and a predetermined value known only to the user and the program supplier whereby the program supplier creates an individual enciphering key for each user constructed by an algorithm with E (GF(p)) whose number of elements is exactly p, assuming that p is a prime number and E(GF(p)) is a group of elements of GF(p) on the elliptic curve E; communicating a communication enciphered with said key over the network.   
     
     
       5. The method of claim 4 wherein the algorithm includes defining d as a positive integer in such a manner to provide an imaginary quadratic field Q((-d 1/2 ) with a small class number; finding a prime number p such that 4*p-1=d*square number; and   finding a solution of a class polynomial H d  (x)=0 modulo p that is defined by d and given with a j-invariant.   
     
     
       6. A method of claim 5, wherein said elliptic curve is given 1 as the class number.