Cryptography Reference
In-Depth Information
CHAPTER 16
Cryptographic Applications
The classical use of cryptography was to use it to pass secret messages between enti-
ties. More recently, cryptography has shown its usefulness in many other ways. We will
investigate some of these topics in this chapter.
16.1
SHADOWS
The Chinese Remainder Theorem has many important applications in cryptography. One of
these applications is the protection of vital information from both disclosure (whether inten-
tional or not), and from loss. Suppose there is a secret that must be protected from exposure.
This might be done by giving separate individuals (who may not even know each other) a
piece of the information. To retrieve it, everyone supplies his or her piece and the secret is
recovered. However, if one of these persons dies, or if his piece of the information has
become somehow inaccessible, we must be able to protect the secret from being lost. That
is, we should require that any subset of these individuals (of a predetermined minimum
size) be able to reconstruct the secret. CRT provides us with a way to do this.
Let the secret be represented by
N
, a large integer. From this
N
we will construct a
sequence of integers
s 1 ,
s 2 , ...,
s r , called “shadows,” and give them to
r
different individ-
uals. We generate the shadows thus: Choose a prime
p
greater than
N
, and a sequence of pair-
wise relatively prime integers not divisible by
p
, say
m 1 ,
m 2 , ...,
m r such that
m 1 <
m 2 < . . .
<
m r , and such that
m rr 2 .
This last inequality says that if we take the smallest
m 1 m 2 ...
m r >
pm r m r 1 ...
r
integers, their product must be
greater than
p
times the largest
r
1 integers. This implies that if
M
=
m 1 m 2 ...
m r , then
M
/
p
is greater than the product of any subset of
r
1 integers from {
m 1 ,
m 2 , ...,
m r }.
Now, choose a random integer
u
<
M
/
p
1, and let
N
=
N
+
up
,
Search WWH ::




Custom Search