Quadratic Ciphers - Introduction to Cryptography with Java Applets - page 208

Now, for i from 1 to t do:
• Let x i x i 1 2 (mod n ) (0 < x i < n )
• Let p i be the h least significant bits of x i .
• Compute m i = p i c i .
and the plaintext message P = m 1 m 2 . . . m t is regained.
Why does this scheme work? In particular, how does the recipient retrieve the random
value x 0 chosen by the sender? Decryption hinges on this, for once the receiver computes
x 0 , she can compute each successive x i , and consequently compute each m i = p i c i . First,
observe that since x t is a square modulo n , that is, x t x t 1 2 (mod n ), has a solution, then
x t x t 1 2 (mod p ) also has a solution (see the proof of proposition 31). Thus, we have
x t ( p 1)/2

6.

1 (mod p ).
(This is called Euler's criterion; you were asked to prove this in order to prove proposition
30). Given this, note that
x t 1 ( p 1)/4 ( x t 2 ) ( p 1)/4

x t ( p 1)/2 = x t ( p 1)/2+1 x t ( p 1)/2 x t x t (mod p )

In the same way, x t ( p 1)/4

x t 1 (mod p ) and hence
( x t 1 ( p 1)/4 ) 2

x t 1 (mod p ).

Continuing in this way, we obtain
u x t 1 d

( x t 1 ( p 1)/4 ) t 1 x 0 (mod p ).

We obtain a similar result for v :
v x t 1 e ( x t 1 ( q 1)/4 ) t 1

x 0 (mod q ).
Note that we have not yet obtained x 0 ; only 2 residues of x 0 congruent to u and v mod-
ulo p and q , respectively. We need the lnr of x 0 modulo n , for this is x 0 itself. To achieve this,
we note that since

ap + bq = 1

we have both of the following:

1 (mod p )
ap 1 (mod q ).
Thus, using the above two congruences, we derive the two congruences

bq

vap + ubq x 0 (mod p )
vap + ubq x 0 (mod q )
and hence, by proposition 26, we know that

vap + ubq x 0 (mod n )
and hence the random seed x 0 is discovered, making decryption possible.