Cryptography Reference
In-Depth Information
The two keys for the RSA are chosen so they both multiply to-
gether to give
1
modulo
)
. One is chosen at random and the
other is calculated by finding the inverse of it. Call these
φ
(
pq
e
d
and
Neal Koblitz's book,
[Kob87], gives a good
introduction to finding
this inverse.
de
=1mod
φ
(
pq
)
.Thismeansthat:
where
ed
mod
x
pq
=
x.
This can be converted into an encryption system very easily. To en-
crypt with this public key, calculate
e
mod
x
pq
.Todecrypt,raisethis
answer to the
d
power. That is, compute:
e
mod
)
d
mod
de
mod
(
x
pq
pq
=
x
pq
=
x.
This fulfills all of the promises of the public-key encryption sys-
tem. There is one key,
, that can be made public. Anyone can en-
crypt a message using this value. No one can decrypt it, however,
unless they know
e
. This value is kept private.
The most direct attack on RSA is to find the value of
d
φ
(
pq
)
.This
can be done if you can factor
.
Actually implementing RSA for encryption requires attention to a
number of details. Here are some of the most important ones in no
particular order:
pq
into
p
and
q
Converting Messages into Numbers
Data is normally stored as bytes.
RSAcanencryptanyintegerthatislessthan
. So there needs
to be a solidmethod of converting a collection of bytes into and
out of integers less than
pq
. The easiest solution is to glue to-
gether bytes until the string of bytes is a number that is greater
than
pq
. Then remove one byte and replace it with random bits
so that the value is just less than
pq
pq
. To convert back to bytes,
simply remove this padding.
The equations here
make it easy to describe
RSA, but they aren't
enough to make it easy
to build a working
implementation. Dan
Boneh, Antoine Joux,
and Phong Q. Nguyen
found major
weaknesses in naive
solutions for converting
a message into a
number. [BJN00]
e
mod
Fast Modulo Computation
Computing
x
pq
does not require
multiplying
x
together
e
times. This would be prohibitive be-
cause
could be quite large. An easier solution is to compute
x, x
2
mod
e
pq, x
4
mod
pq, x
8
mod
pq,...
That is, keep squaring
x
. Then choose the right subset of them to multiply together to
get
e
mod
th
bit of
x
pq
. This subset is easy to determine. If the
i
x
2
i
mod
e
is
1
,thenmultiplyin
pq
the binary expansion of
into
the final answer.
Finding Large Prime Numbers
The security of the RSA system de-
pends on how easy it is to factor
[BFHMV84], [Bri82],
[Mon85], and [QC82]
discuss efficient
multiplication
algorithms.
are large
prime numbers, then this is difficult. Identifying large prime
numbersasluckwouldhaveit,isprettyeasytodo.Thereare
pq
.Ifboth
p
and
q
