Aim: RSA Algorithm
Assignment No: 1
Problem Statement: Write a program in C++ or Java to implement RSA Algorithm for Key 
generation and cipher verification
Objectives:
 To learn asymmetric key cryptography/ public key cryptography
 To understand working of RSA without APIs
Theory:
Asymmetric key cryptography/ Public key cryptography
Write theory here about Asymmetric key cryptography/ Public key cryptography
RSA Algorithm
In cryptography, RSA (which stands for Rivest, Shamir and Adleman who first publicly 
described it) is an algorithm for public-key cryptography. It is the first algorithm known to be 
suitable for signing as well as encryption, and was one of the first great advances in public 
key cryptography. RSA is widely used in electronic commerce protocols, and is believed to 
be sufficiently secure given sufficiently long keys and the use of up-to-date implementations.
Operation
The RSA algorithm involves three steps: key generation, encryption and decryption.
Key generation
RSA involves a public key and a private key. The public key can be known to everyone and 
is used for encrypting messages. Messages encrypted with the public key can only be 
decrypted using the private key. The keys for the RSA algorithm are generated the following 
way:
1. Choose two distinct prime numbers p and q.
For security purposes, the integer’s p and q should be chosen at random, 
and should be of similar bit-length. Prime integers can be efficiently found 
using a primality test.
2. Compute n = pq.
n is used as the modulus for both the public and private keys
3. Compute φ(n) = (p – 1)(q – 1), where φ is Euler's totient function.
4. Choose an integer e such that 1 < e < φ(n) and gcd(e,φ(n)) = 1, i.e. e and φ(n) are co-
prime.
 e is released as the public key exponent.
e having a short bit-length and small Hamming weight results in more 
efficient encryption - most commonly 0x10001 = 65537. However, small 
values of e (such as 3) have been shown to be less secure in some settings.