Tweet
Código:
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.