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.