Public key cryptosystem with an elliptic curve

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).sup.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.sub.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.sub.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.