Cryptography Reference
In-Depth Information
THE EXTENDED EUCLIDEAN ALGORITHM
We need to be able to find modular inverses in order to set up key pairs for the
RSA cryptosystem. RSA works with modular numbers that are very large, so the
idea of exhaustively trying out all the possible numbers less than our modulus is
not going to be a practical method of finding modular inverses.
Fortunately there is a process, known as the
Extended Euclidean Algorithm
,
which can be used to calculate modular inverses. The Extended Euclidean
Algorithm is not complicated, but neither is it simple to explain in a few
paragraphs. We thus refer the interested reader elsewhere and choose to accept
that we can find modular inverses easily, whenever we need them, using the
Extended Euclidean Algorithm.
A.3.3
RSA key pair setup
We now explain how all the simple ideas that we have just discussed come together
in the RSA cryptosystem.
There are four basic steps involved in setting up an RSA public and private
key pair. Although we covered this material in Section 5.2, we provide a reminder
here using the mathematical terms that we have just explained:
1.
Generating the modulus
. Choose two primes
p
and
q
and let
n
=
p
×
q
.
2.
Generating e
. Choose
e
to be a number smaller than (
p
−
1)
×
(
q
−
1) that is
1). The reason that we require this is because we
want
e
to have a modular inverse.
3.
Forming the public key
. Let the public key be (
n
coprime to (
p
−
1)
×
(
q
−
e
).
4.
Generating the private key
. The private key
d
is the unique modular inverse of
e
modulo (
p
,
1). This number
d
can be calculated using the Extended
Euclidean Algorithm by anyone who knows
p
and
q
.
An example of this process was given in Section 5.2.1.
−
1)
×
(
q
−
A.3.4
Why RSA works
We now explain why RSA works. This section contains simple mathematical
arguments based on information that we have just described. However, there is
no need to concern yourself with the detailed discussion in this section unless
you want to know exactly why RSA works. If you simply want to understand
the main mathematical 'mechanics' behind RSA then this has already been
done.
We know from Section 5.2.2 that RSA encryption consists of taking a plaintext
P
and computing
C
C
d
mod
n
.
We now provide an explanation as to why these two operations 'reverse' one
another.
=
P
e
mod
n
, while decryption is given by
P
=
