Exponential Ciphers - Introduction to Cryptography with Java Applets - page 269

To execute this attack we have two plaintext messages; suppose the first is unknown to
the adversary:
P = 30249875309285709328759302875930285709327590347524096346

The second plaintext message, however, is known to the adversary:
P * = 9238652389765892365982365826589265892569823659826892659823
We will choose a random k for encryption, but we will make the mistake of using the same
k for both messages:
k = 2388424515437026664851549783676880762378680269832085250306583

We now compute the ciphertext values for both messages, and send them. The adversary
now has both ciphertext messages.
c g k (mod p )

1642888020851138839985143747652209853264823298182518021833998
d P r k (mod p )

2423699272959365071299919696965347809128019098341877537393147
c * = c g k (mod p )
1642888020851138839985143747652209853264823298182518021833998
d *

P * r k (mod p )

1394500791523696367305442526712905312818729871045966459248084
With this information, the adversary computes inverse of d * modulo p ; this is easily done:
( d * ) = 171164269300021014098269930428606194139335616620654362864166
The adversary can now obtain the first plaintext message without decrypting, by com-
puting the lnr of P *

( d * )

modulo p :
30249875309285709328759302875930285709327590347524096346.

d

This should convince you that you should never use the same value for k to encrypt mul-
tiple messages.

14.8

THE RSA CIPHER
Rivest, Shamir, and Adleman created the RSA cipher (hence the acronym RSA). They were
among the first to patent their work in public key cryptography, and they even claimed their
patent included all forms of public key cryptography! Regardless, their patent has now
expired.
RSA works like this:

1. The receiver of a message generates two large strong primes, p and q , forms their prod-

uct, say n = pq , and makes public the value of n . At current levels of computing power,