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

* , it is necessary for A to separate C 1 into blocks, and add redundancy before
applying the transformation

2. If C 1 ≥ n

C C 1 2 (mod

* )

n

and form the final ciphertext to send to B.
To decrypt the message sent by A, B does the following:

1. B decrypts the message C by sending it through his decryption machine to regain C 1 . That

is, it computes the square roots of C modulo n

* . If redundancy was added at the proper
point, his decryption machine can determine the correct root congruent to C 1 out of the
four possible roots calculated.

2. B then computes

P C 1 2 (mod n )

using A's public modulus to recover the plaintext.

Once again, the enciphering and deciphering transformations are used not only to ensure
that the message was from the sender, but also to ensure that no one other than the intended
recipient can decipher it.

E XAMPLE . For simplicity's sake, we will use small parameters. Suppose individual A (the
sender) chooses p = 10259, and q = 10739, so that n = 110171401. Individual B (the recip-
ient) chooses p

* = 121353541. Note that all primes are
congruent to 3 modulo 4. (There is a table in the appendices listing all primes less than
12000, plus their lnr's modulo 4.)
A wishes to send the message P = 1696082 to B with a signature. This message may not
have a square root modulo n . A first checks this, and discovers that it does not; so by adding
salt (just a single digit will do here), she eventually obtains a value that has a square root;
namely,

* = 10691, and q * = 11351, so that n

P

= 16960824
A then computes the square roots of 16960824 modulo 110171401. B does this by com-
puting

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

x P qq p P pp q (mod n )

where q p is an inverse of q modulo p , and p q is an inverse of p modulo q . The values desired

are

p q = 1320
q p = 8998

This yields the four roots

x 50253700 (mod 110171401)
x

40866715 (mod 110171401)