RSA Cipher Creation - Cryptography Tutorial

How the RSA Cipher was created

  
Cryptography >  Public Key Ciphers  > RSA Cipher (2/6) : Creation  (60 min.)  
 
Objectives:

1) Understand how RSA was invented and understand the underlying mathematics.

2) Learn which One Way Function is used for RSA.

3) Learn Euler's Theorem. 

 

Mod - exponentiation can be used for encryption. However, the exponents used have to be chosen wisely to ensure proper decryption.

 

 

 

 

Generally, Euler's Theorem states that
 aj(n)  = 1 mod n 
if a and n have no common divisor. However, RSA just uses a special case. Using n = p * q then j(n) = j(p*q) = (p-1)*(q-1), it states that a(p-1)*(q-1) = 1 mod p*q.
 

a = 
exp =
m =   
   
aexp mod m =

 

 

 

 

 

 

 

 

 

 

 

Exponential identities such as aK = a where K can be factored into two integers e and d (the encoding and decoding keys) is what cryptographers use to construct ciphers.

 

 

 

 

 

 

 

 

 

 

 

Knowing the public key (e,n)  = (3,33) is sufficient information for an eavesdropper to figure out the private (secret) key: (d,n)  = (7,33). 

 

 

 

 

Expanding the idea of mod - exponentiation into a secure cipher was a major breakthrough for which the three Israelis Rivest, Shamir and Adleman (1977) deserve credit. However, Simon Singh describes in "The Code Book", 1999, that the two British Mathematicians Ellis and Cocks discovered the RSA cipher 4 years earlier. Their disadvantage: both worked for the British Military where such discoveries had to remain secret. I should mention that Simon Singh incorporated a cipher challenge consisting of 10 ciphers of increasing difficulty. Try the first problems yourself. More     

 

 

 

 

A One-way function may produce a certain result, however, this result can not be undone. I.e. Breaking an egg is a one-way function. Multiplication of large numbers is the one-way function that makes the RSA Cipher secure.  

 

There is an ongoing RSA challenge at www.rsa.com where you can find the latest factoring records. 

 

 

 

Example: Using the primes p=3 q=5 we obtain (p-1)*(q-1) + 1= 2*4 + 1 = 9 and thus the coding equation: 
a9 = a mod 3*5. Verify the correctness for all a between 1 and 14 here: 

a =   
exp =
m =   
   
aexp mod m =

 

To make the proof of correctness more tangible, I will illustrate it by using the primes p=3 q=5 and a=6. I will demonstrate algebraically that 
69 mod 15 = 6. 

Since 6 mod 3 = 0,
also 69 mod 3 = 0.
Subtraction yields: 
69 - 6 mod 3 = 0.                 (5)
(or 10077690 mod 3 = 0)
(Check: since the sum of the digits (=30) is divisible by 3, 10077690 is aswell.)

Using Euler's Theorem,
6(5-1) = 64 mod 5 = 1, thus,
(64)2 mod 5 = 12 = 1 and also
(64)2 * 6 mod 5 = 6 or 
69 mod 5 = 6 or 
69 - 6 mod 5 = 0.  
(or 10077690 mod 5 = 0)       (6)
(Check: any integer ending in a "0" is divisible by 10 and therefore also by 5.) 

(5) shows that 3 divides 69 - 6 (=10077690), 
(6) shows that 5 divides
69 - 6  (=10077690).
Since the primes 3 and 5 divide the same number, we may write:
69 - 6 = 3 * 5 * B for some integer B. Dividing both sides by 3*5 yields the integer B as an answer which shows that 69 - 6 (=10077690) is evenly divisible by 15. Thus, we may write
69 - 6 mod 15 = 0 or 
69 mod 15 = 6  which shows that the RSA decryption works properly even for integers a that are multiples of the primes 3 or 5 (here a = 6). 
Exercise: verify algebraically that 109 mod 15 = 10.  
  

 

 
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 
           
          a
21 = 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: 

             a
21 = (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 

            C
7 = (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) + 1a  mod q. 

This is just what we needed since the keys were chosen such that e*d = (p-1)*(q-1) + 1:

          a e*da  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. 

 

 Plain text (use lower case letters only)

Cipher text

 

 
   
 
Cipher text   

Plain text

 

 
    
      

 

 
Click here to view pictures of the RSA inventors and other famous cryptographers. You can also link to their cryptography pages and learn more about their impact on modern cryptography.
Read Textbook on the RSA Cipher and its History

Related web sources:

Ask.com on RSA

RSA.com

Pictures of the 3 RSA Inventors

Yahoo.com on the 3 RSA inventors 

Encarta.com

Yahoo's Encryption & Security

Glossary

PBS Online

Introduction to Cryptography

Enigma and the Codebreakers

Enigma History

Enigma Emulator

 

 

  top

back  next