Cryptography Reference
In-Depth Information
We multiply the two equations together and then multiply the two sides by
t
:
t(tq)
k
(
p
−
1
)(
q
−
1
)
= t mod p
Now, we remember the above rule that both sides of a congruence and the
module itself can be multiplied by the same number, in this case
q
:
(tq)
k
(
p
−
1
)(
q
−
1
)
+
1
= tq mod pq.
Thus (3) also holds for all multiples of
q
. Analogously, we show the equation
for multiples of
p
.
As a result, we have derived the RSA method and concurrently proved that it
works.
Using RSA
All you have seen so far were variables, but natural numbers hide behind them,
of course. How can all of this be turned into an encryption method? First of
all, we have to create a key pair:
1. We define a key length; 1024 bits are currently thought to be secure. We
create two different prime numbers,
p
and
q
, with a length of at least
1024
/
2
=
512 bits each (more about this further below).
2. We define an exponent,
e
. Common values are 3, 17, and 65 537
=
2
16
+
1(
m
e
can be calculated particularly fast for these special values).
e
has to be relatively prime to
p
−
1. If it weren't, we would
have to select
e
,or
p
and
q
, differently. But there won't be a problem
using the three values above for
e
, since they are prime numbers and
certainly not equal to
p
or
q
(for we want
p
and
q
to be extremely
large).
3. We use the extended Euclidean algorithm (it won't be discussed here;
you can find a C program in [SchnCr, 11.3]) to calculate a
d
by
−
1 and
q
de = 1 mod (p-1)(q-1).
