Introduction to Cryptography with Open-Source Software

310 Cryptography with Open-Source Software

To send a message m (encoded as a point of E), Bob cho oses a random

integer k and sends the pair

(C

1

, C

2

) = (kP, kQ + m)

as the ciphertext to Alice.

This can be easily decrypted by Alice using

m = C

2

− rC

1

.

To see that this works, note that

C

2

− rC

1

= kQ + m − r(kP )

= kQ + m − k(rP )

= kQ + m − kQ

= m.

Figure 1 2.6 describes this s ystem.

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

Key generation. The private key is any r < n. The public key is

Q = rP .

Encryption. For a message m ∈ E the ciphertext is (C

1

, C

2

) =

(kP, kQ + m) for a randomly chosen k < n.

Decryption. m = C

2

− rC

1

.

FIGURE 12.6: Elliptic ...