Cryptography Reference
In-Depth Information
so that 0
. This is so since
0
≤
N
=
N
+
up
<
p
+
up
= (
u
+ 1)
p
< (
M
/
p
)
p
=
M
.
Now, this is how to produce the shadows,
≤
N
<
M
s
1
,
s
2
, ...,
s
r
; let
s
j
be the least nonnegative
residue of
N
(mod
m
j
); that is,
s
j
N
.
In order to recover the secret
N
from the shadows, we will need at least
r
of them, so
say we have some subset of the shadows
s
j
1
,
s
j
2
, . . . ,
s
j
r
}. Using CRT, we can find the least
nonnegative residue of
N
modulo
M
j
where
M
j
=
m
j
1
m
j
2
...
m
j
r
. Now, note that
M
≤
M
j
(since
M
=
m
1
m
2
...
m
r
is the product of the
r
smallest integers), and thus, since
0
(mod
m
j
)
0
≤
k
j
<
m
j
, and
i
= 1, 2, . . . ,
r
M
≤
M
j
,
the least nonnegative residue obtained by using CRT is in fact
≤
N
<
N
, the very integer we seek.
We then recover the secret
N
by computing
N
=
Nup
.
However, if we have fewer than
r
shadows to work with, we cannot determine
N
, and
hence cannot retrieve the secret
N
. To see this, suppose we only have
r
1 shadows
s
i
1
,
s
i
2
, ...,
s
i
r
1
. CRT allows us to determine the lnr (say
z
) of
N
modulo
M
i
where
M
i
=
m
i
1
,
m
i
2
, ...,
m
i
r
1
, and so we know that
N
M
i
.
Now, we know (by our choice of
p
and the moduli) that
M
/
p
is greater than any product
of
r
1 of the moduli, so since
=
z
+
yM
i
where
y
= 0, 1, . . . ,
M
/
M
/
p
>
M
i
we have
M
/
M
i
>
p
.
This tells us that as
y
traverses the integers smaller than
M
/
M
i
,
y
takes on every value mod-
ulo
p
, and so also does
N
, since
N
=
z
+
yM
i
and since
M
i
is relatively prime to
p
. (Recall
that all of the moduli are chosen so that they are not divisible by
p
.) Thus, we cannot pin
N
(and hence
N
) down to any value, because
N
could be in any of the residue classes mod-
ulo
p
.
E
XAMPLE
.
= 10 from prying eyes. (Of course,
we are choosing an example with ridiculously small values so that you can readily observe
how this works.) We choose a prime greater than the secret, say
Suppose we want to hide the secret number
N
p
= 11. Now, suppose we
want to have
r
= 5 shadows, and we wish to be able to recover the secret
N
from at least
r
= 3 of the shadows. We choose the moduli as
m
1
= 17
m
2
= 19
Search WWH ::
Custom Search