Introduction to Cryptography with Open-Source Software

98 Cryptography with Open-Source Software

That is, to compute

c

d

(mod pq),

the powers with smaller moduli

c

d

(mod p), c

d

(mod q)

can be c omputed first. But by Fermat’s theorem, these last two exponents

can be simplified to

c

d mod (p−1)

(mod p)

and

c

d mod (q−1)

(mod q).

So decryption can be performed entirely using exponentiation modulo the

smaller individual primes p and q. First define

m

p

= c

d mod (p−1)

(mod p)

m

q

= c

d mod (q−1)

(mod q).

Using s, t with sp + tq = 1 , then the plaintext will be

m = spm

q

+ tqm

p

(mod n).

For large primes p, q this method is about four times faster than attempting

to compute c

d

(mod pq).

Security issues

The RSA cryptosystem is secure only if the private key d cannot be de-

termined from the public key e, n. To obtain d requir e s the value