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

TABLE 16.2

i C is congruent to R i modulo p i

1 74111215 234 499

2 74111215 201 503

3 74111215 147 563

Using the write subkeys, we encipher the records by forming the sum

C w 1 R 1 + w 3 R 3

108744576 234 + 98327950 201 + 75550097 147
56316012993

w 2 R 2 +

74111215 (mod 141311311).
To retrieve a particular record R i from the database, we simply compute the least non-
negative residue of C modulo p i . Table 16.2 shows all the retrieved records.

Editing a Record Note that modifying some record R i to some new value R i with this
scheme is particularly easy, for it does not involve recomputing the entire sum

C w i R i (mod M ) 0 ≤ C < M , i = 1, 2, . . . , n .
All we have to do is compute the difference between the new value and the old value:
D = R i R i ,
then add this to the sum to get a new enciphered value for the database.
C C + w i D (mod M ).

This works because

C C w i D

w 1 R 1 + w 2 R 2 + . . . + w i R i + . . . + w n R n + w i D
w 1 R 1 +

+

w 2 R 2 + . . . + w i R i + . . . + w n R n + w i ( R i R i )

w 1 R 1 +

w i R i
w 1 R 1 + w 2 R 2 + . . . + w i R i + . . . + w n R n (mod M ).

w 2 R 2 + . . . + w i R i w i R i + . . . + w n R n +

E XAMPLE .

Suppose in our previous example that individual 2 wishes to change
R 2 = 201

to the new value

R 2 = 103.