|
The Creation of the RSA-CIPHER
You just learned how RSA works. On
this page, I am going to explain to you how the RSA inventors Rivest, Shamir and
Adleman came up with the idea for this cipher. Knowing the
mathematical background may inspire you to create a secure cipher yourself.
Now read and make sure you follow each of the 5 cipher creation steps. Step
1:
The Idea of Mod-Exponentiation.
You learned how to encode using mod-addition (Caesar Cipher) or
mod-multiplication (Multiplication Cipher). What other number operation may we use to encode? Mod-subtraction and mod-division work just as
mod-addition and mod-multiplication (Why?). What is left is
mod-exponentiation. I.e.: Using an exponent of 3 as a key and 26 as a
modulus, I may encode as follows:
B3= 13 = 1 mod 26,
C3=
23 = 8 mod 26,
D3= 33 = 1 mod 26.
We encountered this kind of problem already: Different plain letters encode to the same cipher letter
which makes proper decryption impossible. Thus, the questions the
inventors Rivest, Shamir and Adleman had to answer were:
1) How to choose
the exponent and the modulus to allow non-ambiguous encryption and proper decryption.
2) Based on the
choice of the encryption exponent, which decryption exponent will yield
the proper plain text?
At this point, an inspection of useful mathematical knowledge was needed: Which
mathematical theorems involving mod-exponentiation may help answering the two questions?
Step 2:
Making Use of an old Theorem: "Euler's Theorem"
The quest was answered quickly. Euler's Theorem is a central theorem in
number theory, the oldest branch of Mathematics. In its simplest form it states: When choosing
the modulus to be a prime number p, then any integer a - different from p -
raised to the power of p-1 yields 1. As a formula:
ap-1 = 1
mod p.
Example: When p=5:
24=1 mod 5,
34=1
mod 5,
44=1 mod 5,
64=1 mod 5, etc.
To use Euler's Theorem
for the RSA Cipher, the following generalization will be used (I will
explain later why):
a(p-1)*(q-1) = 1 mod (p*q).
Example: When
p=3 and q=5 then
a8 = 1 mod 15
for any integer a
that has no common divisor with p*q.
Verify that
|
28 = 1 mod
15, |
|
48 = 1 mod 15, |
|
78 = 1
mod 15, etc |
Predict if 128, 148, 168,188
yield 1 mod 15, then check?
Step 3: How does the Euler Theorem enable
the Construction of a Cipher?
With our knowledge of the previous ciphers, the answer is easy.
a) The modulus m must be greater than the number of used plain letters.
Also, it must be a product of two primes.
Say, we pick
m = 33 = 3 * 11.
Then, by Euler's Theorem:
a20
= 1 mod 33
and therefore also
a21
= a mod 33.
This is just what a cryptographer desires! Imagine a
is a plain letter, then raising it to a power (here 21) yields the original
letter - only when using the modulus 33.
If the exponentiation can be split into
two stages - an encryption and a decryption exponentiation - the cipher is
complete. Can it?
Of course it can, we know from our exponentiation rules that:
a21
= (a3)7.
Thus, we may choose the encoding key to be 3 and encode each plain letter
using
C = P3
mod 33.
To decode, the recipient uses his key 7 and decodes via
C7
= (P3)7 = P21 = P mod 33.
Wonderful. We are ready to describe
the
RSA encoding und decoding function:
The sender encodes the
plain text P using the public key (e,m) as follows:
C = Pe mod m.
The recipient decodes the cipher text C using his private key (d,m) as
follows:
P = Cd mod m.
|
Great, the decoding process yields the
original plain text. Just what we wanted. Question: Would you trust the
above encryption with m=33 for your credit card transactions over the
internet? You better not. Similar to the Caesar Cipher, although the cipher
works properly, it is far from being secure (for now)! Let me show you why.
Say you have to email your private tax statements to your tax advisor
(mailing such statements has always been an act of unjustified trust) . So,
I look up his publicly known encoding key pair (e=3, m=33) to encode my tax
statements. This publicly known key is sufficient information for an
eavesdropper to crack the secret key d.
Here is why: Since the eavesdropper
knows that
m = 33 = 11 * 3 = p *q,
he knows that the coding identity
a21
= a mod 33
is used. He easily computes the exponent:
21 = (p-1)*(q-1) + 1 = (11-1) * (3-1) + 1 = 10*2 + 1.
Since 21 = e*d and knowing that e = 3, the decoding key must be d = 7. The
eavesdropper intercepts the encoded email, he decodes it as if he were the
recipient and can enjoy reading the tax statements. Independent of the fact
whether Mr. X may be the IRS, the FBI or your neighbor, you want i.e. your
tax statements to be a secret between you and your advisor.
Conclusion:
The cipher works fine, however, it is far from being secure. So, let's move
on and learn what makes RSA a secure cipher?
Step 4: The Ingenuity of the RSA
Cipher: The Usage of a One-Way Function makes RSA a Secure Cipher.
The reason for its security is contradictory to what you just read:
"Although everybody in the world knows the modulus m and the encoding key e,
nobody can derive or guess the decoding key d."
This seemingly impossible endeavor was made reality through the usage of a
so-called "one-way" function:
"ALTHOUGH THE MULTIPLICATION OF ANY TWO ARBITRARY LARGE INTEGERS CAN BE
PERFORMED, THE OPPOSITE - FINDING THE FACTORS OF AN ARBITRARY LARGE NUMBER -
CAN NOT."
- Even when combining the most powerful computers in the world -
an assumption that not only applies to secret services.
That means: every computer finds that
146614475398596474507582355656921385929407476886138293940337371622857901730074383
*
759276910254348069600375341445293209365776080164945836100799699726864370921040551
=
1113209858792084582941156369031744876348153783763660689619579628181533014117646948
37737625838893687610402628112788959622813543185395045279971949456605272989305033
However given the product, there are no
means to find the two above factors. This is a classical example of a
one-way function which is the reason why RSA is a secure cipher. The
potential weakness: If somebody is capable of designing an algorithm that
finds the factors of a huge integer, the RSA Cipher can be broken.
However, no mathematician has been
able to solve this century-old problem - an "insult to
mathematicians" as the German Cryptographer Beutelspacher characterizes
it. Surely, combining the power of super computers (think of the powerful
NSA or FBI), 120-digit numbers can be factored. Thus, to assure the security
of the RSA cipher the key length (that is the modulus m) may simply be
chosen sufficiently large. Currently, RSA moduli consisting of at least
200-digits are recommended and guarantee security!
Step 5:
Assuring the Correctness of the Decoding Process.
Ciphers only make sense if the
decoding process is guaranteed to yield the original plain text. To assure
that the RSA cipher yields the proper plain text, we have to prove the
correctness of decoding process. Mathematics is the science that helps us to
achieve our goal. Thus, in this last section, I will give a strict
mathematical proof of the correct functioning of the RSA-decryption process.
Let's start with the above mentioned
Euler's Theorem:
a (p-1)*(q-1) = 1 mod (p*q)
(1)
for any integer a that has no common
factor with p*q. Thus,
a (p-1)*(q-1) +1 = a e*d =
a mod (p*q).
(2)
Important: The RSA
cipher only works correctly if
ae*d
yields a for ANY a so that the message recipient obtains the
correct plain letter a. However, Euler's Theorem (1) can only be
applied for certain values of a - namely those that have no common
divisor with p*q. Thus, let's prove that (2) is even true if a does
have a common divisor with p*q. (The chances of choosing such message are
(1/p) + (1/q) - (1/(p*q)) which is tiny since p and q were chosen as huge
prime numbers. We could have therefore neglected this possibility. Also, in
case we could not prove this case we could have assured in the encryption
process that no such a values would be encoded.) In
that case, a must be a multiple of either p or q. If
a
were a multiple of p*q it then would have at least the size of the modulus
p*q which is not the case for the RSA cipher. Thus, we may assume a
is a multiple of p. We may write this as:
a mod p = 0. (3)
Therefore, any multiple or power of a is a multiple of p:
a e*d mod p = 0. (4)
Subtracting (3) from (4) yields:
a e*d - a mod p = 0 for all
positive integers a (5).
This is almost our desired equation (2) except that the modulus is p instead
of p*q. So, let's work our way there by setting up an equation as in (5)
with modulus q so that we merge them into the one desired.
This is easy now: Since a is a multiple of p it can not be a
multiple of the other prime q. Thus, a and q have no common divisor
which allows us to use Euler's Theorem for the particular case that the
modulus is only p (This particular case of Euler's Theorem is called "Fermat's
little Theorem".) We may therefore write:
a q-1 = 1 mod q.
To obtain an expression similar to (5), I first raise both sides to the
power of (p-1) and secondly multiply both sides by a. I obtain:
(a(q-1))(p-1)
* a = 1(q-1) * a mod q
which simplifies to
a(q-1)(p-1)
* a = 1 * a mod q
which in turn simplifies to
a(q-1)(p-1)
+ 1 = a mod q.
This is just what we needed since the keys were chosen such that e*d =
(p-1)*(q-1) + 1:
a e*d
= a mod q for all a.
(6)
It remains to merge (5) and (6) into (2),
brief logical reasoning will do:
Equation (5) shows that p is a divisor of
a e*d
- a.
Similarly,(6) shows that q is a divisor of a e*d - a.
Since p and q are different primes and they both divide the same number a e*d
- a, the product p*q must be a divisor of a e*d - a
which writes as:
a e*d
- a = 0 mod (p*q)
or
a e*d
= a mod (p*q).
This proves (2) and shows that the RSA decryption process is guaranteed
to yield the proper plain letter a. How could the Suisse Leonard Euler or
the French Pierre Fermat have guessed that their discoveries in Mathematics
could be used for such powerful encryption purposes.
|