Method of privacy communication using elliptic curves

The present invention provides a method of privacy communication, in which an elliptic curve E and an element thereof are notified to all parties who wish to communicate, and data are transmitted from one party to another by using a calculation of the element and coded data made in secret by each party. The method is characterized by a construction of E(GF(p)) such whose number of elements has 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. More particularly, E(GF(p)) is constructed by an algorithm: let d be a positive integer such that gives an imaginary quadratic field Q((-d.sup.1/2)) with a small class number; then find a prime number p such that 4.multidot.p-1=d.multidot.square number; and find a solution of a class polynomial H.sub.d (x)=0 modulo p such that is defined by d and given with a j-invariant.

BACKGROUND OF THE INVENTION 
(1) Field of the Invention 
The present invention relates to a privacy communication technique to 
provide security for information transmission, and more particularly, to a 
privacy communication technique using elliptic curves. 
(2) Description of Related Art 
Privacy communication enables a sender to transmit information to an 
intended receiver alone without leakage to third parties, and a public key 
cryptosystem(PKC) is one of the methods thereof via a public digital 
communication network. In PKC, two keys--an enciphering key and a 
deciphering key--are given to each party; the former is open to the public 
while the latter is kept in secret. Given that it is relatively easy to 
manage these public keys, PKC has now become an essential technique when 
one wishes to communicate with more than one party in secret. 
The security for PKC often depends on difficulty of a discrete logarithm 
problem(DLP) on finite abelian groups, and finite fields have been used as 
the finite abelian groups. However, owing to a toil of researchers, the 
time required to solve DLP has been reduced with every advancement they 
make. The history of such advancement is compiled in "Cryptography: A 
Prime", Alan G. Konheim, John Wiley & Sons, Inc. Accordingly, a method 
that uses elliptic curves in place of the finite abelian groups was 
proposed to maintain the security for PKC against is advancement. This 
proposed method is described in "A Course in Number Theory and 
Cryptography", Neal Koblits, Springer-Verlag, 1987, and the DLP on 
elliptic curves(EDLP) reads: 
Let q be a power of a prime number, GF(q) be a finite field, E(GF(g)) be a 
group of elements of GF(q) on an elliptic curve E, and an element P of 
E(GF(q)) be a base point, find an integer x such that Q=xP (Q is a given 
element of E(GF(q)), if such an integer x exists. 
The researchers correspondingly began to apply this EDLP to the methods of 
the privacy communication such as PKC, because if effectively applied, it 
was envisaged that 
1) the speed of communication would be sharply increased without impairing 
the security, for there had been no solution proposed such that could 
confer a sub-exponential algorithm on EDLP, 
2) the communication in volume would be reduced, 
3) a greater number of the finite abelian groups would be available 
compared with the finite fields. 
However, unlike the finite fields which define DLP, the researchers found 
it very difficult to construct appropriate elliptic curves which in effect 
define EDLP, and their interest has shifted to how easily one can 
construct them. Conventionally, the elliptic curves are constructed by the 
following method: 
1) Method I 
With this method, an elliptic curve called a supersingular elliptic curve 
is constructed. This method is described in "The Implementation of 
Elliptic Curve Cryptosystems", Alfred Menezes, Scott Vanstone, Auscrypt 
90, 1990, and following is the recapitulation thereof. This method 
consists of 2 steps as is shown in FIG. 1. 
(i) Determination of a Prospective Elliptic Curve 
Let E.sub.1, E.sub.2, and E.sub.3 be supersingular elliptic curves defined 
over GF(2) given by 
EQU E.sub.1 :y.sup.2 +y=x.sup.3 +x+1 
EQU E.sub.2 :y.sup.2 +y=x.sup.3 +x 
EQU E.sub.3 :y.sup.2 +y=x.sup.3 
Let E.sub.i (GF(2.sup.m))(i=1-3) be a group consisting of the elements of 
GF(2.sup.m) on each supersingular elliptic curve, then 
EQU E.sub.1 (GF(2.sup.m))={x,y.epsilon.GF(2.sup.m).vertline.y.sup.2 +y=x.sup.3 
+x+1}U{.infin.} 
EQU E.sub.2 (GF(2.sup.m))={x,y.epsilon.GF(2.sup.m).vertline.y.sup.2 +y=x.sup.3 
+x}U{.infin.} 
EQU E.sub.3 (GF(2.sup.m))={x,y.epsilon.GF(2.sup.m).vertline.y.sup.2 +y=x.sup.3 
}U{.infin.} 
(.infin. is an infinite point which is known as a zero element). 
As can be seen in the above, the elements of E.sub.i (GF(2.sup.m)) 
constitute a finite abelian group; for addition is applied among 
themselves. 
Further, let m be an odd number, then the number of E.sub.i 
(GF(2.sup.m)(i=1-3), or #E.sub.i (GF(2.sup.m), is found as given below by 
Deu's theorem and Hasse's theorem. 
##EQU1## 
(ii) Determination of a Suitable Extension Degree m 
It is known that EDLP is easily solved unless the order of the element P, 
or the base point, has a large prime factor. Therefore, a necessary and 
sufficient condition for the element P is that #E.sub.i (GF(2)) has a 
large prime factor. Thus, m such that satisfies the necessary and 
sufficient condition is found. 
The elliptic curves found in Step (i) and m in Step (ii) are used to 
construct EDLP. Accordingly, #E.sub.3 (GF(2.sup.m)) factorized, and it is 
found that : 
when m is 191, 
EQU #E.sub.3 (GF(2.sup.m))=2.sup.191 +1=3.multidot.p.sub.1, 
when m is 252, 
EQU #E.sub.3 (GF(2.sup.m))=2.sup.251 +1=3.multidot.238451.multidot.p.sub.2 
(p.sub.1 and p.sub.2 are prime numbers.) 
This leads to a conclusion that EDLP can be constructed by finding a 
supersingular elliptic curve defined over E.sub.3 (GF(2.sup.191)) with the 
base point P whose order has exactly p.sub.1 or E.sub.3 (GF(2.sup.251) 
with the base point P whose order has exactly p.sup.2. In other words, the 
enciphering and deciphering keys are made by using these E.sup.3 
(GF(2.sup.191)) and the base point P, or E.sup.3 (GF(2.sup.251) and the 
base point P. 
In 1991, however, a solution using a reducing method was proposed. This 
method is effective in solving EDLP on supersingular elliptic curves, for 
it confers a sub-exponential algorithm thereon, thereby impairing security 
for privacy communication. 
"Reducing Elliptic Curve Logarithm to Logarithms in a Finite Field", A. 
Menezes, S. Vanston, and T. Okamoto, STOC, '91, gives an explanation on 
the reducing method, and it reads: 
Let q be a square of a prime number, E an elliptic curve defined over 
GF(q), E(GF(q)) be a group consisting of elements of GF(q) on the elliptic 
curve E. Then, EDLP on the elliptic curve having the base point 
P.epsilon.E(GF(q)) can be solved by reducing it to DLP over an extension 
field GF(q.sup.r) of GF(q), provided that the order of the base point P is 
prime to q. EDLP on supersingular elliptic curves, in particular, can be 
solved by reducing it to the sextic extension field of GF(q) -GF(q.sup.6)- 
at most. 
Attacked by this reducing method, EDLP constructed by Method I can no 
longer secure PKC unless n of GF(2.sup.n) is increased to a number larger 
than 256, which in turn causes a steep decrease of the communication 
speed. 
Given these circumstances, another constructing method of EDLP which can 
secure PKC against this attack was proposed. 
2) Method II 
With this method, ordinary elliptic curves which defines EDLP unsolvable by 
the reducing method is constructed. This method is described in 
"Non-supersingular Elliptic Curve for Public Key Cryptosystems", T. Beth, 
F. Schaefer, Eurocrypt 91, 1991, and the following is the recapitulation 
thereof. This method consists of 2 steps as is shown in FIG. 2. 
(i) Determination of a Prospective Elliptic Curve 
Let E.sub.i (i=4,5) be a non-supersingular, i.e. ordinary, elliptic curve 
defined over GF(2) given by 
EQU E.sub.4 :y.sup.2 +xy=x.sup.3 +x.sup.2 +1 
EQU E.sub.5 :y.sup.2 +xy=x.sup.3 +1 
Let E.sub.i (GF(2.sup.m)) be a group consisting of the elements of 
GF(2.sup.m)(i=4,5) on each elliptic curve, then the number thereof, or 
#E.sub.i (GF(2.sup.m)), is found as given below by Deu's theorem and 
Hasse's theorem. 
EQU #E.sub.4 (GF(2.sup.m))=1+2.sup.r -{(1+(-7).sup.1/2)/2}.sup.m 
-{(1-(-7).sup.1/2)/2}.sup.m 
EQU #E.sub.5 (GF(2.sup.m))=1+2.sup.r -{(-1+(-7).sup.1/2)/2}.sup.m 
-{(-1-(-7).sup.1/2)/2}.sup.m 
(ii) Determination of an Extension Degree m 
Let m be an extension degree for E.sub.i (i=4,5) such that it satisfies the 
two following conditions: 
Condition 1: 
#E.sub.i (GF(2.sup.m)) must have a large prime factor. 
Condition 2: 
Let p be the largest prime factor of #E.sub.i (GF(2.sup.m)), and t be a 
sufficiently large positive integer, then 2.sup.mk -1 does not have p as a 
prime factor(k is an arbitrary positive integer smaller than t). 
Condition 1 is given to provide #E.sub.i (GF(2.sup.m)) with a large prime 
factor and Condition 2 to increase t as far as possible, for the security 
increases as t becomes larger; more particularly, when EDLP on the 
elliptic curve defined over E.sub.i (GF(2.sup.m) is reduced to DLP on the 
elliptic curve defined over the extension field of GF(2.sup.m), the 
extension degree m becomes larger than t. 
The elliptic curves found in Step (i) and m in Step (ii) are used to 
construct EDLP. Accordingly, #E.sub.4 (GF(2.sup.m)) is factorized, and it 
is found that when m is 107, #E.sub.4 (GF(2.sup.m))=2.multidot.p.sub.3 
(p.sub.3 is a prime number). 
It is easy to calculate 2.sup.mk -1 with today's advanced computers, and to 
prove that 2.sup.mk -1 does not have p.sub.3 as a prime factor when k is a 
number from 1 to 6. Thus, it can be concluded that an ordinary elliptic 
curve defined over E.sub.4 (GF(2.sup.107) with the base point P whose 
order has exactly p.sub.3 must be found to construct EDLP, on which the 
security of PKC depends. In other words, the enciphering and deciphering 
keys are made by using these E.sub.4 (GF(2.sup.107)) and the base point P. 
PKC using such ordinary elliptic curves is secure when n of GF(2.sup.n) is 
a number more than 100 with the level of today's computer technology. Yet, 
such security can not be guaranteed without increasing n endlessly to meet 
rapid progress in this field, which in turn reduces the speed of privacy 
communication. Therefore, a method of constructing elliptic curves such 
that define EDLP unsolvable by the reducing method has been sought after. 
SUMMARY OF THE INVENTION 
Accordingly, the present invention has an object to provide a method of 
privacy communication using elliptic curves which define an EDLP 
unsolvable by the reducing method. 
The above object is fulfilled by a method of privacy communication in which 
an elliptic curve E and an element thereof are notified to all parties who 
wish to communicate, and data are transmitted from one party to another by 
using a calculation of the element and coded data made in secret by each 
party, the method is characterized by a construction of E(GF(p)) whose 
number of elements has 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. Further, 
E(GF(p)) is constructed by an algorithm : let d be a positive integer such 
that it gives an imaginary quadratic field Q((-d.sup.1/2)) with a small 
class number; then find a prime number p such that 
4.multidot.p-1=d.multidot.square number; and find a solution of a class 
polynomial H.sub.d (x)=0 modulo p such that is defined by d and given with 
a j-invariant. The elliptic curve may be given 1 as the class number. 
According to the above mentioned method, the number of the elements of 
E(GF(p)) has exactly p with the elliptic curve E, and the order of an 
element other than the zero element is not prime to p. Therefore, EDLP on 
such an elliptic curve E can not be solved by the reducing method, hence 
the privacy communication using such an elliptic curve E is highly secure.

DESCRIPTION OF THE PREFERRED EMBODIMENTS 
EMBODIMENT I 
As a way of example, PKC using the method of privacy communication of the 
present invention is described with referring to FIGS. 3 and 4. 
As can be seen in FIG. 3, users A and B are two parties who wish to 
communicate through PKC, a user S is a party who wishes to eavesdrop the 
communication, and a network provider Z is a party who does initial 
setting of PKC; all of them are connected to the network N, and take the 
followings steps summarized in FIG. 4. 
In Step 1, the network provider Z calculates an elliptic curve E defined 
over GF(p) and an element P.sub.1 thereof; this process will be discussed 
more in detail later, for it is the gist of the present invention. 
In Step 2, the network provider Z notifies all the users connected to the 
network N of E(GF(p)) and P.sub.1. In Step 3, both users A and B select 
respective arbitrary integers x.sub.A and x.sub.B in secret as their 
deciphering keys. In Step 4, the users A and B calculate their public keys 
Y.sub.A and Y.sub.B on E(GF(p)) using P.sub.1 : Y.sub.A =x.sub.A P.sub.1, 
Y.sub.B =x.sub.B P.sub.1, and notify all the other users of them. 
The user A wishing to send a message M(plaintext) to the user B selects a 
random integer r.sub.a in secret to encipher the message M using r.sub.a 
and Y.sub.B, and sends the enciphered message consisting of C.sub.1 and 
C.sub.2 as below to the user B. 
EQU C.sub.1 =r.sub.a P.sub.1 
EQU C.sub.2 =M+x(r.sub.a Y.sub.b) 
where x(r.sub.a Y.sub.B) is the X-coordinate of r.sub.B Y.sub.B. 
Being the element of the elliptic curve E, r.sub.a Y.sub.B is quadratic 
data expressed as (r.sub.x, r.sub.y) in X-Y coordinate, whereas M is 
linear data. For this reason, only r.sub.x is used to generate C.sub.2 on 
an agreement made between the users A and B in advance. 
Accordingly, the user B deciphers the enciphered message using x.sub.B, the 
key strictly kept to himself, as follows: 
EQU M=C.sub.2 -x(x.sub.B C.sub.1) 
where x(x.sub.B C.sub.1) is the X-coordinate of x.sub.B C.sub.1. 
According to this method, the user A is able to transmit the message M to 
the user B in secret, and should the user A erroneously transmit the 
enciphered message to an unintended user, there is no way for him to 
decipher it, for the deciphering key x.sub.B is kept secret to him. 
Back to Step 1, how the network provider Z does the initial setting is 
described. As is shown in FIG. 5, Step 1 consists of 4 sub-steps of: 
1) determining a positive integer d; 
2) generating a prime number; 
3) finding a solution modulo p for the class polynomial H.sub.d (x); and 
4) determining an elliptic curve. 
These sub-steps are explained more in detail hereunder. 
1) Determining a Positive Integer d 
Let d be a positive integer such that gives a small class number to an 
imaginary quadratic field Q((-d).sup.1/2)). The imaginary quadratic field 
and class number are described in detail in "VORLESUNGEN UEBER ZAHLEN 
THEORIE" and "Algebraic Number Theory" S. Lang, GTM110, Springer-Verlag, 
New York, 1986. For explanation's convenience, let d be 19 and class 
number be 1; although there are 1, 2, 3, 7, 11, 43, 67 or 163 for d for 
the class number 1, and for the class number 2, there are 10, 15, 26, 30 
or so forth as is described in myriads books on the theory of number for 
the quadratic fields. However, not all these numbers are applicable to the 
present invention. For example, when d is 1, 2, or 7, the following step 
can not be applied. 
2) Generating a Prime Number p 
Let p be a prime number such that 4.multidot.p-1=d.multidot.square number; 
for this purpose, d must satisfy d.ident.-1(mod 4)(d=19 meets this 
condition). However, as previously mentioned, there exists no prime number 
such that satisfies 4.multidot.p-1=d.multidot.square number when d is 1, 
2, or 7. 
For example, let p be a 29-digit number of 23520860746468351934891841623, 
then, 
EQU 4.multidot.p-1=19.multidot.(1451.multidot.48496722383).sup.2. 
Given the fact that a prime number of approximately 30-digit can be easily 
generated, a prime number such that satisfies the above condition can be 
found relatively easy as well, albeit by trial and error. 
3) Finding a Solution Modulo p for the Class Polynomial H.sub.d (x) 
A solution Modulo p for the class polynomial H.sub.d (x) (d=19) is found by 
Fourier series as shown below whose detailed explanation is in "The 
Arithmetic of Elliptic Curves", J. H. Silberman, Springer-Verlag. 
##EQU2## 
wherein j(t) is a modular function, C(n) is an integer, and 
q=e.sup.2.pi.it 
then, 
##EQU3## 
thus, H.sub.d (x)=x+884736 so, a solution modulo p is x.ident.-884736 (mod 
p) 
4) Determining an Elliptic Curve 
There exist two elliptic curves E.sub.1 and E.sub.2 defined over GF(p) with 
a solution of H.sub.d (x) modulo p as a j-invariant modulo 
GF(p)-isomorphism : 
i) E.sub.1 for 
##EQU4## 
given by 
EQU E.sub.1 :y.sup.2 .noteq.x.sup.3 +3ax+2a 
where j=0,1728 
ii) E.sub.2 for a non-quadratic residue c that is (c/p)=-1 given by 
EQU E.sub.2 :y.sup.2 =x.sup.3 +3ac.sup.2 x+2ac.sup.3. 
where j.noteq.0,1728 
Then, let j=-884736, thus, 
EQU E.sub.1 :y.sup.2 =x.sup.3 
+18569100589317119948598822307x+9903520314302463972586038632 
EQU E.sub.2 :y.sup.2 =x.sup.3 
+18569100589317119948598822307x+13617340432165887962305802991 
From Deu's theorem and Hasse's theorem, #E.sub.i (GF(p))(i=1,2) is either p 
or p+2. Therefore, the elliptic curve to defined EDLP is the one with an 
element other than the zero element whose order has exactly p. In effect, 
the base point is fixed to an arbitrary element other than the zero 
element of E.sub.i (GF(p)), for p is the order of an element such that 
becomes the zero element when multiplied with p. 
Thus, in EDLP having the base point other than the zero element of E.sub.1 
(GF(p)), #E.sub.1 (GF(p)) is not prime to p. Therefore, it can not be 
solved by the reducing method. As a result, security for PKC which depends 
on such EDLP is ensured without decreasing the speed of communication. 
Algorithm based on the above mentioned 4 sub-steps is summarized in the 
flowchart in FIG. 6; numerals 1-4 in the left show a correspondence with 
the steps in FIG. 5. In FIG. 7, arithmetic operations for constructing a 
small elliptic curve as an easy example are shown; P1 through P7 shows a 
correspondence with the flowchart in FIG. 6. These two correspondences are 
not identical, for all components are calculated in the latter. 
As previously mentioned, there are some positive integers other than 19 for 
d, and several examples of elliptic curves constructed with such integers 
are the given in following: 
A) Let d be 11 and a prime number p be p=100000000000069784500614201619 
then, 
EQU 4p-1=11.multidot.190692517849185.sup.2 
thus, 
EQU H.sub.11 (x)=x+(2.sup.5).sup.3 
then 
EQU x=-(2.sup.5).sup.3 
therefore, 
##EQU5## 
Then, whether the respective orders of elements other than the zero element 
of E.sub.1 and E.sub.2 have exactly p is checked by a calculation, and in 
this case, it is found that E.sub.1 is the elliptic curve with p elements. 
B) Let d be 43 and a prime number p be p=100000000000067553784390207169 
then, 
EQU 4p-1=43.multidot.96448564434115.sup.2 
thus, 
EQU H.sub.43 (x)=x+(2.sup.6.3.5).sup.3 
then, 
EQU x=-(2.sup.6.3.5).sup.3 
therefore, 
##EQU6## 
Then, whether the respective orders of elements other than the zero element 
of E.sub.1 and E.sub.2 have exactly p is checked by a calculation, and in 
this case, it is found that E.sub.1 is the elliptic curve with p elements. 
C) Let d be 67 and a prime number p be p=100000000000039914906156290257 
then, 
EQU 4p-1=67.multidot.77266740928641.sup.2 
thus, 
EQU H.sub.67 (x)=x+(2.sup.5.3.5.11).sup.3 
then, 
EQU x=-(2.sup.5.3.5.11).sup.3 
therefore, 
##EQU7## 
Then, whether the respective orders of elements other than zero element of 
E.sub.1 and E.sub.2 have exactly p is checked by a calculation, and in 
this case, it is found that E.sub.2 is the elliptic curve with p elements. 
D) Let d be 163 and a prime number p be p=100000000000088850197895528571 
then, 
EQU 4p-1=163.multidot.49537740461829.sup.2 
thus, 
EQU H.sub.163 (x)=x+(2.sup.6.3.5.23.29).sup.3 
then, 
EQU x=-(2.sup.6.3.5.23.29).sup.3 
therefore, 
##EQU8## 
Then, whether the respective orders of elements other than the zero element 
of E.sub.1 and E.sub.2 have exactly p is checked by a calculation, and in 
this case, it is found that E.sub.2 is the elliptic curve with p elements. 
It is to be noted that the elliptic curves constructed as above are used 
for strictly confidential messages such as banks' data transmitted 
throughout the nation. However, not all the messages transmitted through 
privacy communication are strictly confidential, and for these less 
confidential messages, the network provider Z may construct elliptic 
curves with a small prime number by two following sub-steps of: 
1) checking whether #E.sub.i (GF(p))(i is an arbitrary number) has exactly 
p for any elliptic curve E.sub.i given by E.sub.i :y.sub.2 =x.sup.3 +ax+b 
(a, b are random numbers and p is a given prime number). 
2) constructing an elliptic curve by finding a solution modulo p for the 
class polynomial H.sub.r (x) to find a j-invariant when p such that 
4.multidot.p-1=r.multidot.b (r, b are natural numbers) is found. 
This method requires a massive volume of arithmetic operations, but today's 
most advanced computers can construct the appropriate elliptic curves when 
p is a small prime number. 
Although the present invention was applied to PKC as an example of the 
privacy communication, it is needless to say that the present invention 
can be applied to non-public key cryptosystems. 
EMBODIMENT II 
In this embodiment, the present invention is applied to electric signature: 
the user A wishing to transmit a message to the user B does so by way of 
the user C, a third party who plays the role of the network provider Z in 
Embodiment I. 
To begin with, the user C calculates two elliptic curves E.sub.1 and 
E.sub.2 given as below in the same manner of Embodiment I: 
EQU E.sub.1 :y.sup.2 =x.sup.3 
+18569100589317119948598822307x+9903520314302463972586038632 
EQU E.sub.2 :y.sup.2 =x.sup.3 
+18569100589317119948598822307x+1361734043216588796230502991 
The user C selects a base point P.sub.A and a base point P.sub.B ; the 
former is an element other than the zero element of E.sub.1 (GF(p)), and 
the latter is that of E.sub.2 (GF(p)). Then, the user C notifies the user 
A alone of E.sub.1 and the base point P.sub.A, and the user B alone of 
E.sub.2 and the base point P.sub.B. 
In the mean time, the user A selects an arbitrary integer x.sub.A in secret 
and generates Y.sub.A, i.e. his identity data to the user C, defined by 
EQU Y.sub.A =x.sub.A P.sub.A 
Subsequently, the user C selects an arbitrary integer x.sub.AC in secret 
and generates Y.sub.AC, i.e. his identity data to the user A, defined by 
EQU Y.sub.AC =x.sub.AC P.sub.A 
Then, the users A and C exchange Y.sub.A and Y.sub.AC to make a common key 
K.sub.AC defined by 
EQU K.sub.AC =x.sub.A Y.sub.AC =x.sub.AC Y.sub.A. 
The user A enciphers the message M using the common key as an enciphering 
key and transmits the enciphered message to the user C alone, whereas the 
user C deciphers the enciphered message using the common key as a 
deciphering key. In general, the message is enciphered/deciphered by a 
block cipher method such as DES(Data Encryption Standard), but this can be 
done with Exclusive-OR of the common key as well. 
On the other hand, the user B selects an arbitrary integer x.sub.B in 
secret, and generates Y.sub.B, i.e. his identity data to the user C, 
defined by 
EQU Y.sub.B =x.sub.B P.sub.B 
Subsequently, the user C selects an arbitrary integer x.sub.BC in secret, 
and generates Y.sub.BC, his i.e. identity data to the user B, defined by 
EQU Y.sub.BC =x.sub.BC P.sub.B 
Then, the users B and C exchange Y.sub.B and Y.sub.BC to make a common key 
K.sub.BC defined by 
EQU K.sub.BC =x.sub.BC Y.sub.B =x.sub.B Y.sub.BC. 
The user C enciphers the message M received from the user A using the 
common key as an enciphering key and transmits the enciphered message to 
the user B alone, whereas the user B deciphers the enciphered message 
using the common key as a deciphering key. The message is 
enciphered/deciphered by the block cipher method in general, but this can 
be done with Exclusive-NOR as well. Thus, the message M is transmitted in 
secret from the user A to the User B by way of the User C. 
Different elliptic curves are used in the communication between the users A 
and C, and between the users B and C to prevent the user B from receiving 
the communication between the users A and C by any chance, and vice versa. 
Also, it would be better to use different calculation methods in the 
communication between the users A and B, and between the user B and C to 
increase security against a transmission failure by the user C. 
Although the present invention has been fully described by way of example 
with reference to the accompanying drawings, it is to be noted that 
various changes and modification will be apparent to those skilled in the 
art. Therefore, unless otherwise such changes and modifications depart 
from the scope of the present invention, they should be construed as being 
included therein.