Introduction to Cryptography with Open-Source Software

Elliptic curves and cryptosystems 315

Parameters. An elliptic curve E and a point P ∈ E of high safe

prime order p.

Key generation. The private key is any A < p. The public key is

Q = AP.

Encryption. For a message m = (m

0

, m

1

) ∈ Z

2

p

the ciphertext is

(c

0

, c

1

, c

2

) = (kP, xm

0

mod p, ym

1

mod p) for a randomly cho-

sen k < p and where (x, y) = kQ.

Decryption. m = (c

1

x

−1

mod p, c

2

y

−1

mod p).

FIGURE 12.7: Menezes–Vanstone cryptosy stem.

sage: A = randint(1,p);A

56

sage: Q = A*P;Q

(82 : 54 : 1)

Suppo se Bob wishes to send m = (100, 50) to Alice. He needs to generate a

message key and multiply Q by it:

sage: k = randint(1,p);k

89

sage: X = k*Q

sage: (x,y) = (X[0],X[1]);(x,y) ...