Graphics Programs Reference
In-Depth Information
The numbers in the previous example were chosen for their relevance to
RSA. Assuming the values for
P
and
Q
are 11 and 13,
N
would be 143. There-
fore, φ(
N
) = 120 = (11 − 1) · (13 − 1). Since 7253 is relatively prime to 120,
that number makes an excellent value for
E
.
If you recall, the goal was to find a value for
D
that satisfies the following
equation:
E
·
D
=
S
· φ(
N
)+1
Some basic algebra puts it in a more familiar form:
D
·
E
+
S
· φ(
N
)=1
D
·7253±
S
·120=1
Using the values from the extended Euclidean algorithm, it's apparent
that
D
= −43. The value for
S
doesn't really matter, which means this math
is done modulo φ(
N
), or modulo 120. That, in turn, means that a positive
equivalent value for
D
is 77, since 120 − 43 = 77. This can be put into the
prior equation from above:
E
·
D
=
S
· φ(
N
)+1
7253 · 77 = 4654 · 120 + 1
The values for
N
and
E
are distributed as the public key, while
D
is
kept secret as the private key.
P
and
Q
are discarded. The encryption and
decryption functions are fairly simple.
Encryption:
C
=
M
E
(mod
N
)
Decryption:
M
=
C
D
(mod
N
)
For example, if the message,
M,
is 98, encryption would be as follows:
98
7253
= 76(mod143)
The ciphertext would be 76. Then, only someone who knew the value for
D
could decrypt the message and recover the number 98 from the number 76,
as follows:
76
77
= 98(mod143)
Obviously, if the message,
M
, is larger than
N
, it must be broken down
into chunks that are smaller than
N
.
This process is made possible by Euler's totient theorem. It states that
if
M
and
N
are relatively prime, with
M
being the smaller number, then
when
M
is multiplied by itself φ(
N
) times and divided by
N
, the remainder
will always be 1:
If gcd(
M
,
N
) = 1 and
M
<
N
then
M
φ(
N
)
= 1(mod
N
)
