RSA Cipher in 8 Steps - Cryptography Tutorial

Do the RSA Cipher Step by Step

  
Cryptography >  Public Key Ciphers  > RSA Cipher (3/6) : RSA in 8 Steps (30 min.)  
 
Objectives:

1) Understand  the 8 RSA Encryption steps.

 

 

 

 

 

 

  

 RSA Cipher in 8 Steps 

On this page, perform the 8 steps involved when encoding using the RSA Cipher. Different from its practical usage, I am using primes p and q that are less than 30. As a consequence, the decoding key d could easily be broken and the cipher is far from being secure. This page serves solely demonstration purposes.
Observe that the first 6 steps are the key generation steps that are performed quickly by a computer. Steps 7 and 8 display the actual coding process. 

 
Steps 1-6: Preparation    

Exercise 1: Why does the modulus m = p * q have to be greater than 26? Give a counterexample and explain it. For instance, if the modulus is 13 only 13 different letters can be encrypted. i.e. b=1 and 0=14 are encrypted to the same cipher letter since 1=14 mod 13.

Exercise 2: When using p=17 and q=23 the modulus is m = 391. If e=3, how could you find the decoding key d? Try to find it yourself. d has to be the inverse of e=3 mod phi where phi=(p-1)*(q-1)=16*22=352. The Extended Euclidean Algorithm finds d=235.    

Exercise 3: When m = 209, among how many possible encoding keys e can we choose from? Is there a faster way than trial and error to find the number? 
 e has to be relative prime to phi=(11-1)*(19-1)=180. 
Euler's j-function shows that there are j(180) = 48  such integers. The Euclidean Algorithm finds such integers.   
1)
    

 
2)
    

 
3) Having generated 2 distinct random primes less than 30, we have to assure that their product is greater than 26. 

 
    

 
4)
   

 
5)
    
The key e has to be relative prime to (p-1)*(q-1). It is selected by simply checking 3, 5, 7, etc.  Remember that the security of RSA does not rely on the choice of e. 

 
6)
     

 

Steps 7 and 8: CODING PROCESS 

 Plain text (use lower case letters only)

Cipher text

 

 
   
      
 Cipher text   

 Plain text

  

 
   
     

 

 
The RSA Cipher was invented in 1976 by the 3  Mathematicians Rivest, Shamir and Adleman. 
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