Method of implementing elliptic curve cryptosystems in digital signatures or verification and privacy communication

A method of implementing a privacy communication comprising following procedures:

• (1) a network provider provides E{GF(p)} and a basepoint BP to be used for the privacy communication to each user;
• (2) each user who received E{GF(p)} and the basepoint BP selects an arbitrary natural number to find a value by adding said basepoint BP the selected natural number of times on E{GF(p)};
• (3) each user keeps his arbitrary selected natural number in secret, while notifying the value obtained by adding the BP said natural number of times on E{GF(p)} as his public key to a user to whom he would like to send a message;
• (4) two users make an agreement on a method of arithmetic operation for the public key, a random number, and a message to encipher and decipher the message using the notified common key and the random number;
• (5) one of the two users who received the public key enciphers the message in accordance with the agreement based on a random number he selected and the public key notified by the other user;
• (6) the one of the users sends an enciphered message to the other user who notified the public key;
• and
• (7) the other user deciphers the message enciphered in accordance with the agreement using his integer selected and kept in secret upon receipt of the enciphered message, wherein (E{GF(p)} is defined as follows:
• let d be a positive integer such that gives an imaginary quadratic field Q{(-d).sup.1/2 } a small class number;
• let p be a prime number such that a prime factor of 4 .times.p-a.sup.2 is d.times.square number where a is an integer, such that one of p+1-a and p+1+a is divisible by a prime number of 30 or more digits, and such that is expressed as 2.sup.t .+-..alpha., where t is a positive integer and .alpha. is a small positive integer;
• then an elliptic curve E has a finite field GF(p) as a definition field which has a solution modulo p for a class polynomial H.sub.d (x)=0 which is determined by d as a j-invariant.