Cryptography Reference
In-Depth Information
cryptosecurity of the scheme will be at least as good as the
underlying mathematical problem is hard to solve. This
has not been proven for any of the candidate schemes thus
far, although it is believed to hold in each instance.
However, a simple and secure proof of identity is pos-
sible based on such computational asymmetry. A user
first secretly selects two large primes and then openly
publishes their product. Although it is easy to compute
a modular square root (a number whose square leaves a
designated remainder when divided by the product) if the
prime factors are known, it is just as hard as factoring (in
fact equivalent to factoring) the product if the primes are
unknown. A user can therefore prove his identity, i.e., that
he knows the original primes, by demonstrating that he
can extract modular square roots. The user can be con-
fident that no one can impersonate him since to do so
they would have to be able to factor his product. There
are some subtleties to the protocol that must be observed,
but this illustrates how modern computational cryptogra-
phy depends on hard problems.
s
eCret
-s
haring
To understand public-key cryptography fully, one must
first understand the essentials of one of the basic tools in
contemporary cryptology: secret-sharing. There is only
one way to design systems whose overall reliability must
be greater than that of some critical components—as
is the case for aircraft, nuclear weapons, and commu-
nications systems—and that is by the appropriate use
of redundancy so the system can continue to function
even though some components fail. The same is true
for information-based systems in which the probability
of the security functions being realized must be greater
than the probability that some of the participants will
