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

3. Alice computes e n ( bP, cP ) a , Bob computes e n ( aP, cP ) b ,andChriscom-
putes e n ( aP, bP ) c .

4. Since each of the three users has computed the same number, they use
this number to produce a key, using some publicly prearranged method.

Recall that, since E is supersingular, the discrete log problem on E can be
reduced to a discrete log problem for F q 2 (see Section 5.3.1). Therefore, q
should be chosen large enough that this discrete log problem is hard.
For more on cryptographic applications of pairings, see [57].

6.3 Massey-Omura Encryption

Alice wants to send a message to Bob over public channels. They have not
yet established a private key. One way to do this is the following. Alice puts
her message in a box and puts her lock on it. She sends the box to Bob. Bob
puts his lock on it and sends it back to Alice. Alice then takes her lock off
and sends the box back to Bob. Bob then removes his lock, opens the box,
and reads the message.
This procedure can be implemented mathematically as follows.

1. Alice and Bob agree on an elliptic curve E over a finite field F q such
that the discrete log problem is hard in E ( F q ). Let N =# E ( F q ).

2. Alice represents her message as a point M ∈ E ( F q ). (We'll discuss how
to do this below.)

3. Alice chooses a secret integer m A with gcd( m A ,N ) = 1, computes M 1 =
m A M , and sends M 1 to Bob.

4. Bob chooses a secret integer m B with gcd( m B ,N ) = 1, computes M 2 =
m B M 1 , and sends M 2 to Alice.

5. Alice computes m − 1 Z N . She computes M 3 = m − 1

∈ M 2 and sends M 3

A A

to Bob.

6. Bob computes m − 1 ∈ Z N . He computes M 4 = m − 1

M 3 .Then M 4 = M

B B

is the message.

Let's show that M 4 is the original message M . Formally, we have

M 4 = m − 1 m − 1 m B m A M = M,

B A

but we need to justify the fact that m − A , which is an integer representing
the inverse of m A mod N ,and m A cancel each other. We have m − 1 m A ≡ 1

A