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

m 3 = 23
m 4 = 24
m 5 = 25.
Note that none of the moduli are divisible by 11, and that the product of the 3 smallest
moduli is greater than the prime

= 11 times the two largest moduli:
M = 17 19 23 = 7429 > 6600 = 11 24 25.
Now, we choose a random integer u smaller than M = 7429/11 675.36, say u = 439,
and then we compute

p

N = N + up = 10 + 439 11 = 4839.
The shadows are the least nonnegative residues of N modulo each modulus m i . Thus,
s 1 11 (mod 17)
s 2 13 (mod 19)
s 3

9 (mod 23)

s 4 15 (mod 24)

s 5

14 (mod 25).
Now, suppose we wish to reconstruct the secret N from any 3 of the shadows, say s 2 =

13, s 3 = 9, and s 5 = 14. First we find N using the Chinese Remainder Theorem, as follows:

N = 13 575 575 + 9 475 475 + 14 437 437

= 13 575 4 + 9 475 20 + 14 437 23

= 256114
4839 (mod 10925) (10925 = 19 23 25)
Once we have N , we recover the secret N by taking
N = Nup
= 4839 439 11
= 10.
It doesn't matter which 3 shadows we use to reconstruct N ; any 3 will do, as you may
like to verify. However, if we try to pull the secret N out of only 2 shadows, we should fail.
Suppose we try to reconstruct N from s 1 = 11, and s 4 = 15. We use CRT to form the quan-
tity

N = 11 24 24 + 15 17 17

= 11 24 5 + 15 17 17

= 5655

351 (mod 408).