# RSA Implementation for very large `n = p.q` (prime numbers) with user interface

### Project group members
- Aditya Vardhan Kadambari - AM.EN.U4EAC19024
- Sai Akshith Naeeni - AM.EN.U4EAC19061
- Sai Kiran Rachakonda - AM.EN.U4EAC19044
- Hanwith Bellamkonda - AM.EN.U4EAC19010

## RSA Algorithm

- **RSA (Rivest, Shamir, Adleman)** is an Public Key Cryptosystem which is used to transmit messages over the internet, it is **based on the principle of factoring large prime numbers**.
- This type of encryption is called **Asymmetric cryptosystem**, it is said so because the key for encryption and decryption are different.
- They are the public key pair and the private key pair.
- Public key pair is available to everyone, while the private key pair is for the individuals own use and is kept a secret.
- The setup of an RSA cryptosystem involves the generation of two large primes, **say p and q**, from which, the RSA modulus is calculated as `n = p * q`. The greater the modulus size, the higher is the security level of the RSA system. The recommended RSA modulus size for most settings is 2048 bits to 4096 bits. Thus, the primes to be generated need to be 1024 bit to 2048 bit long.

## Source code

''' RSA algorithm '''
import random

''' Function : to generated keys '''
def generate_keypair(p, q,f,n):
    # Choose an integer e such that e and f(n) are coprime
    e = random.randrange(2, f)
    # To verify that e and f(n) are comprime
    g = gcd(e, f)
    while g != 1:
        e = random.randrange(2, f)
        g = gcd(e, f)

    # Use Extended Euclid's Algorithm to generate the private key
    d = inverse(e, f)

    #Return public and private keypair
    return ((e, n), (d, n))

''' Function : To check Prime '''
def isPrime(i):
	for j in range(2,i):
		if(i%j==0):
			return False
	return True

''' Function : To calcuate gcd '''
def gcd(a,b):
	if(b==0):
		return a
	else:
		return gcd(b,a%b)

''' Function : To calculate Inverse of e :
	using Extended Eculidean Method '''
def inverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
    if (m == 1) : 
        return 0
    while (a > 1) : 
        # q is quotient 
        q = a // m 
        t = m 
        m = a % m 
        a = t 
        t = y 
        # Update x and y 
        y = x - q * y 
        x = t 
    # Make x positive 
    if (x < 0) : 
        x = x + m0 

    return x 

''' Function : Encryption & Decryption 
	Cipher text c = m^e mod n 
	Plain text d= c^d mod n
	'''
def encrypt(publicKey, message):
    # Unpack the key 
    e, n = publicKey
    # Convert each letter in the plaintext to numbers based on the character using a^b mod m
    c = [(ord(char) ** e) % n for char in message]

    return c

def decrypt(privateKey, message):
    # Unpack the key 
    d, n = privateKey
    # Generate the plaintext based on the ciphertext and key using a^b mod m
    p = [chr((char ** d) % n) for char in message]
    # Return the array 
    return ''.join(p)

''' Input : Validates if entered p,q are Prime ''' 
while True:
	try:
		p = int(input('Enter the value of prime number p = ')) 
	except ValueError:
		print("InValid Input")
		continue
	if not isPrime(p):
		print("Enter a prime number")
		continue
	else:
		break
while True:
	try:
		q = int(input('Enter the value of prime number q = ')) 
	except ValueError:
		print("InValid Input")
		continue
	if not isPrime(q):
		print("Enter a prime number")
		continue
	else:
		break

# Calculate n=pq     
n = p*q      
# Calculate f(n) ( denoted by f in code ) =(p-1)(q-1)                                           
f = (p-1)*(q-1)  
publicKey , privateKey = generate_keypair(p,q,f,n)

# Input message to be encrypted
m = input('Enter the value of message m = ')
print('Public Key [e,n] = ',publicKey)

# Encrypt 
c = encrypt(publicKey,m)
# Decrypt
m = decrypt(privateKey,c)

print('Cipher text = ',c)
print('Private Key [d,n] = ',privateKey)
print('Plain text after decryption = ',m)

## Explanation of variables in souce code

- **p,q** : Two very large primes
- Choose two distinct primes p and q. Both the primes must be chosen randomly and must be similar in magnitude.
- **n** : Modulus, `n = p*q`
- Here, `n` is the value obtained after multiplying both the number p and q.
- **f(n)** : Euler's totient Function
- for n >= 1, f(n) denotes the numbers in the interval [1, n] which are relatively prime to n.
- It is the value obtained after multiplying `(p-1)` and `(q-1)`
- `f(n) = (p-1)(q-1)`
- **e** : Public key exponent
- **e** is an integer such that `1 < e < f(n)` and gcd(e, f(n)) = 1.
- **d** : Private key exponent
- **d** is computed as `d = e^(-1) mod f(n)`
- **m** : Padded message
- **m** is computed as `m = c^(d) mod n`
- **c** : Ciphertext
- **c** is computed as `c = M^(e) mod n`
- The pair `(e, n)` is known as **public key**.
- The pair `(d, n)` is known as **private key**.

## Output


## References

- https://github.com/kanika2296/RSA
- https://www.geeksforgeeks.org/how-to-generate-large-prime-numbers-for-rsa-algorithm/