Cryptographic Applications - Introduction to Cryptography with Java Applets - page 324

x 59917701 (mod 110171401)

x 69304686 (mod 110171401).

No one else can do this since only A knows the values of p and q . A selects one of these

roots (it doesn't matter which), say = 59917701. To compute the final ciphertext, it is nec-

essary that A reblock the text and add redundancy so that B's decryption machine can select
the correct root out of the four possible roots generated by the decryption transformation.
Thus, the message is split into

x

x 1 = 59915991
x 2 = 77017701
A then encrypts using B's public modulus:

C 1 59915991 2 20072206 (mod 121353541).

77017701 2

C 2 11711668 (mod 121353541).

This is the final ciphertext, which is sent to B. To recover the plaintext, B must first solve
for the square roots of C 1 and C 2 modulo 121353541:

( p 1)/4 ( q 1)/4

x C q q

C

p p (mod n * )

* * * *

p * q *

where q * p * is an inverse of q * modulo p * , and p * q * is an inverse of p * modulo q * . The val-
ues desired are

p

= 2253

*

q *

q * p * = 8569

This yields the four roots for C 1 :

x 36623739 (mod 121353541)

x 61437550 (mod 121353541)

x 84729802 (mod 121353541)

→ x 59915991 (mod 121353541).

Since the last root is the one possessing redundancy, it is chosen as the correct root. The
redundancy is discarded to yield x 1 = 5991. It is highly unlikely that another root will pos-

sess this redundancy (especially if we use large redundant blocks).
The four roots for C 2 are:

x 28117593 (mod 121353541)
x

44335840 (mod 121353541)

x 93235948 (mod 121353541)
→ x

77017701 (mod 121353541)