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

TABLE 16.1

1st Modulus 2nd Shadow 2nd Modulus Value for N'

1st Shadow

11 17 13 19 317 (mod 323)

11 17 9 23 147 (mod 391)

11 17 15 24 351 (mod 408)

11 17 14 25 164 (mod 425)

13 19 9 23 32 (mod 437)

13 19 15 24 279 (mod 456)

13 19 14 25 89 (mod 475)

9 23 15 24 423 (mod 552)

9 23 14 25 239 (mod 575)

15 24 14 25 39 (mod 600)

. We will see that if we try any other pair of
shadows, a similarly hopeless situation results. Consult Table 16.1, which shows all the
combinations of shadow pairs, and the corresponding values for

This is, of course, an incorrect value for N

N .

None of the values obtained here for N are correct. Because of the requirements in our

choice of the moduli and the prime p , two shadows simply do not provide us with enough

information to reconstruct N (and thus N ).

Java Algorithm We can write programs to demonstrate shadow making and key recon-
struction. To do this, we will define two classes:

The ShadowBuilder Class This will define a constructor that will accept a master
key, and the number of shadows to generate. It generates the shadows and their respective
moduli, plus the values of as described above. Methods are provided to

retrieve all these values. This class exhibits some differences from the scheme described
above. First, it sets the minimum number of shadows required for reconstruction at just over
half the total number of shadows; for example, if the total number of shadows generated
is 7, 4 of them will be required to recover the master key, and if 8 shadows are produced,
5 will be required for reconstruction. Second, the class produces a sequence of prime num-
bers for the moduli; these will certainly fulfill the requirement to be pairwise relatively
prime.

u, and the prime p

The KeyRebuilder Class This class is for recovering the master key. It will define a
constructor that accepts some shadows and their respective moduli, plus the values of u and
p . It assumes that enough shadows are being used, and that the moduli are pairwise relatively
prime. It reconstructs the master key from the shadows using the Chinese Remainder The-
orem, and provides a method to return the master key as a BigInteger.