Elliptic Curve Cryptography - Elliptic Curves: Number Theory and Cryptography - page 184

problem in the finite field is still not trivial as long as the finite field is large
enough.
For simplicity, we'll consider a specific curve, namely the one discussed in
Section 6.2. Let E be defined by y 2 = x 3 +1 over F p ,where p ≡ 2(mod3).

Let ω ∈ F p 2 be a primitive third root of unity. Define a map

β : E ( F p 2 ) → E ( F p 2 ) , ( x, y ) → ( ωx, y ) , β ( ∞ )= ∞ .

Suppose P has order n .Then β ( P ) also has order n . Define the modified
Weil pairing

e n ( P 1 ,P 2 )= e n ( P 1 ,β ( P 2 )) ,
where e n is the usual Weil pairing and P 1 ,P 2 ∈ E [ n ]. We showed in Lemma 6.1

that if 3 n and if P ∈ E ( F p ) has order exactly n ,then e n ( P, P ) is a primitive

n th root of unity.
Since E is supersingular, by Proposition 4.33, E ( F p ) has order p + 1. We'll
add the further assumption that p =6 − 1 for some prime .Then6 P has
order or 1 for each P ∈ E ( F p ).
In the system we'll describe, each user has a public key based on her or
his identity, such as an email address. A central trusted authority assigns
a corresponding private key to each user. In most public key systems, when
Alice wants to send a message to Bob, she looks up Bob's public key. However,
she needs some way of being sure that this key actually belongs to Bob, rather
than someone such as Eve who is masquerading as Bob. In the present system,
the authentication happens in the initial communication between Bob and the
trusted authority. After that, Bob is the only one who has the information
necessary to decrypt messages that are encrypted using his public identity.
A natural question is why RSA cannot be used to produce such a system.
For example, all users could share the same common modulus n , whose fac-
torization is known only to the trusted authority (TA). Bob's identity, call it
bobid , would be his encryption exponent. The TA would then compute Bob's
secret decryption exponent and communicate it to him. When Alice sends
Bob a message m , she encrypts it as m bobid (mod n ). Bob then decrypts us-
ing the secret exponent provided by the TA. However, anyone such as Bob who
knows an encryption and decryption exponent can find the factorization of n
(using a variation of the method of Section 6.8), and thus read all messages
in the system. Therefore, the system would not protect secrets. If, instead,
a different n is used for each user, some type of authentication procedure is
needed for a communication in order to make sure that the n is the correct
one. This brings us back to the original problem.
The system described in the following gives the basic idea, but is not secure
against certain attacks. For ways to strengthen the system, see [15].
To set up the system, the trusted authority does the following:

1. Chooses a large prime p =6 − 1asabove.

2. Chooses a point P of order in E ( F p ).