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)).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 over GF(p) will have a j-invariant as a solution modulo p for a class polynomial H.sub.d (x)=0 which is fixed by d, finding an order of a point other than a zero element from 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.