Introduction to Cryptography with Open-Source Software

134 Cryptography with Open-Source Software

The s ystem also requires a primitive root r modulo p. The public key consists

of (b

1

, b

2

, . . . , b

n

), wher e

a

i

= r

b

i

(mod p).

That is, the public key values are the discrete logar ithms o f the private key

values (mod p). Although discre te logarithms are in general hard to compute,

there is an algorithm that is efficient if p − 1 has small facto rs. But this is

guaranteed by condition 2 above.

Given a message m tha t is a binary block of length n, encryption is the

same as for the additive system; the ciphertext c is

c = b

1

m

1

+ b

2

m

2

+ b

3

m

3

+ ··· + b

n

m

n

.

To decrypt, compute

c

′

= r

c

(mod p)

and solve the equation

a

x

1

1