Cryptography Reference
In-Depth Information
not cheat. Secret-sharing, which requires a combination
of information held by each participant in order to deci-
pher the key, is a means to enforce concurrence of several
participants in the expectation that it is less likely that
many will cheat than that one will.
The RSA cryptoalgorithm described in the next sec-
tion is a two-out-of-two secret-sharing scheme in which
each key individually provides no information. Other
security functions, such as digital notarization or certifi-
cation of origination or receipt, depend on more complex
sharing of information related to a concealed secret.
rsa e
nCryPtion
The best-known public-key scheme is the Rivest-Shamir-
Adleman (RSA) cryptoalgorithm. In this system a user
secretly chooses a pair of prime numbers
p
and
q
so large
that factoring the product
n
=
pq
is well beyond projected
computing capabilities for the lifetime of the ciphers. At
the beginning of the 21st century, U.S. government secu-
rity standards called for the modulus to be 1,024 bits in
size—i.e.,
p
and
q
each were to be about 155 decimal digits
in size, with
n
roughly a 310-digit number. However, over
the following decade, as processor speeds grew and com-
puting techniques became more sophisticated, numbers
approaching this size were factored, making it likely that
1,024-bit moduli would soon no longer be safe, and so in
2011 the U.S. government recommended shifting to 2,048-
bit moduli.
Having chosen
p
and
q
, the user selects an arbitrary
integer
e
less than
n
and relatively prime to
p
− 1 and
q
− 1,
that is, so that 1 is the only factor in common between
e
and
the product (
p
− 1)(
q
− 1). This assures that there is another
number
d
for which the product
ed
will leave a remainder
