RSA is a Public Key Cryptosystem - Cryptography Tutorial

Cryptography >  Public Key Ciphers  > RSA Cipher (4/6) : PUBLIC-KEY-Cryptosystem (30 min.)  

1) Understand  what makes RSA a Public Key Cipher.








 RSA is a PUBLIC-KEY-Cryptosystem

1) Why is the RSA cryptosystem so successful? 
The success of the RSA Cipher is based on the fact that it is a secure "public-key-cryptosystem". Such systems - also called "asymmetric cryptosystems" - allow users to publish their public key without revealing their private key.

2) Why are public key systems so important?
Because they solve the key distribution problem which arises for the symmetric cryptosystems (i.e. Linear Cipher or one time pad) where each correspondent has to share a different secret key with each other correspondents. Similarly, they do too. The table shows the rapidly increasing number of keys dependent on the number of correspondents:

#corresp.: 2 3 4 5 6 10 100 1000 n
#keys: 1 3 6 10 15 45 4950 499500 n*(n-1)/2

Thus, 100 Internet users require a total of 4950 keys when using any symmetric cryptosystem. However, only 100 key pairs are needed for symmetric cryptosystems. The 100 public encoding keys can be looked up at a central register (similar to a telephone book), whereas each of the 100 private decoding keys is secretly sheltered by its owner. In this way, the two correspondents don't have to meet to define a secret key prior to their correspondence - an enormous advantage i.e. for today's email communication.   

Exercise 1:  
On this page we generate various moduli m. If both primes p and q are less than 20, how many moduli between 77 and 400 can be formed? Verify your answer by generating all possible keys and en- and decode "safe" below for such keys. 
Only 77, 91, 119, 133, 143, 187, 209, 221, 247 and 323 are possible moduli.

Exercise 2: 
Every RSA user has his own key because he uses a unique (his)  modulus m. You may wonder: Considering the great number of people using the RSA cryptosystem, are there enough different RSA keys?  Answer: Yes. Remember that the modulus shall be a 200-digit number which allows many more moduli than there will ever be RSA users. A review questions: Why do these huge moduli prevent eavesdroppers to figure out the decoding key d although e and m are publicly known? 
Given that m is at least a 200 digit number, no computer in the world is able to find the factors p and q.  


1) Key Selection (Combining the 6 preparation steps into 1 step.)

with: 77 <= m <= 400  

Public key: (e,m) =

Private (secret) key:  (d,m) =

2) 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: on RSA

Pictures of the 3 RSA Inventors on the 3 RSA inventors

Yahoo's Encryption & Security


PBS Online

Introduction to Cryptography

Enigma and the Codebreakers

Enigma History

Enigma Emulator




back  next