As we have seen in the previous chapters RSA (Rivest−Shamir−Adleman) is a popular encryption method that protects data shared online. It relies on the mathematical features of very large prime numbers.

How RSA Encryption Works?

RSA encryption secures data by encoding it in a way that only authorized parties can decipher. Below is a brief overview of how RSA encryption works −

Key Generation

• Start with two large prime numbers, such as p and q.
• Multiply p and q to get n.
• Find Φ(n), which is calculated as (p-1) * (q-1). Φ represents Euler”s totient function.
• Choose an integer e that falls between 1 and Φ(n) and has no common factors with Φ(n) except 1 (they are coprime).
• Find d, the multiplicative inverse of e modulo Φ(n). This means that when e and d are multiplied, the result is 1 remainder Φ(n), denoted as d * e ≡ 1 (mod Φ(n)).

Encryption

• To encrypt a message, it is first converted into numbers, usually using a pre-defined code like ASCII or Unicode.
• Each chunk of the message is then encrypted on its own using the public key.
• Encryption involves raising the numerical form of the message chunk to the power of e and dividing the result by n, taking the remainder.
• The resulting encrypted message (ciphertext) is a string of numbers that cannot be read and can be sent over insecure channels.

Implementation of RSA using Python

RSA Encryption can be implemented using different methods like −

• Using the random module
• Using the RSA module
• Using the cryptography module

Hence, in the next few sections, we will detail each way in depth to provide you with an idea on how to create RSA encryption and a better understanding of Python.

Using the random Module

This program will use a random module of Python to create random numbers for key generation. In our code we will have generate_keypair() and encrypt(public_key, plaintext) methods. When the generate_keypair() method is called, it generates random prime numbers p and q.

Thus, the random module is required for generating random prime integers p and q, as well as calculating a random public exponent e. These random values are important for the security and randomness of the RSA encryption technique.

Example

Following is a python program to for RSA encryption using random module of Python −

import random

def gcd(a, b):
   while b != 0:
      a, b = b, a % b
   return a

def extended_gcd(a, b):
   if a == 0:
      return (b, 0, 1)
   else:
      g, y, x = extended_gcd(b % a, a)
      return (g, x - (b // a) * y, y)

def mod_inverse(a, m):
   g, x, y = extended_gcd(a, m)
   if g != 1:
      raise Exception(''Modular inverse does not exist'')
   else:
      return x % m

def generate_keypair():
   p = random.randint(100, 1000)
   q = random.randint(100, 1000)
   n = p * q
   phi = (p - 1) * (q - 1)

   while True:
      e = random.randint(2, phi - 1)
      if gcd(e, phi) == 1:
         break
    
      d = mod_inverse(e, phi)
      return ((e, n), (d, n))

def encrypt(public_key, plaintext):
   e, n = public_key
   cipher = [pow(ord(char), e, n) for char in plaintext]
   return cipher

# our public and private keys
public_key, private_key = generate_keypair()
# Our secret message
message = "Hello, world!"
print("Our plaintext message: ", message)
encrypted_message = encrypt(public_key, message)
print("Encrypted message:", encrypted_message)

Following is the output of the above example −

Input/Output

Our plaintext message:  Hello, world!
Encrypted message: [5133, 206, 9012, 9012, 7041, 3509, 7193, 3479, 7041, 6939, 9012, 1255, 3267]

Using the rsa module

RSA cryptography can be easily and efficiently implemented using Python”s rsa package.

Installing the rsa Module

First, if you do not have already installed the rsa module then you can install it with the help of pip −

pip install rsa

Generating RSA Keys

After installing the module you can generate RSA key pairs with the help of this rsa module. Here is how −

import rsa
# create a key pair with 1024 bits key length
(public_key, private_key) = rsa.newkeys(1024)

The above code will generate a pair of RSA keys: one for encryption (the public key) and the second one for decryption (the private key).

Encrypting the Messages

When you have the key pair, you can use them to encrypt and decrypt messages.

# Encrypting a message
message = b"Hello, world!"
encrypted_message = rsa.encrypt(message, public_key)

# Decrypting the message
decrypted_message = rsa.decrypt(encrypted_message, private_key)

print("Original message:", message.decode())
print("Decrypted message:", decrypted_message.decode()) 

Sign and Verify

RSA can also be used for digital signatures. Here is how to sign and verify a given message −

# Signing a message
signature = rsa.sign(message, private_key, ''SHA-256'')

# Verifying the signature
rsa.verify(message, signature, public_key)

Complete code

Below is the complete code for your reference. So run the code and see the output −

import rsa
# create a key pair with 1024 bits key length
(public_key, private_key) = rsa.newkeys(1024)

# Encrypting a message
message = b"Hello, world!"
encrypted_message = rsa.encrypt(message, public_key)

print("Original message:", message.decode())
print("Encrypted message:", encrypted_message)

# Signing a message
signature = rsa.sign(message, private_key, ''SHA-256'')

# Verifying the signature
rsa.verify(message, signature, public_key)

Following is the output of the above example −

Input/Output

Original message: Hello, world!
Encrypted message: b''gx078$xx,5A[x11hrx15v4x0f-?xa8x18xadxdax93xa8x982x1bxf3xaeexd3x85+MZ*=xd0x8fxefVxed5ixc9Axe4xa377x1dxcexf0xb6xa9/:xf8Yxf9xf1x866x8dx1c!xb9Jxf1x9dQ8qdx01tkxd61Ux8c2x81x05wpxcb)g6txe9x03xa0MQRxcbxa6Bhbx05xb5x06fx04rx17x9cxe8B%]x95xd8Dx84Xrx9cx93xc8xaeN[m''

Using the Cryptography Module

So we can generate RSA key pairs using the cryptography module. This code generates a private RSA key and extracts the matching public key. Both keys are converted to the PEM format and stored in separate files. These keys can be used to encrypt and decrypt messages.The provided code demonstrates encryption using the public key.

Example

Following is a python implementation for RSA encryption using cryptography module −

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa

# Generate an RSA private key
private_key = rsa.generate_private_key(
   public_exponent=65537,
   key_size=2048,
   backend=default_backend()
)

# Get the public key from the private key
public_key = private_key.public_key()

# The keys to PEM format
private_key_pem = private_key.private_bytes(
   encoding=serialization.Encoding.PEM,
   format=serialization.PrivateFormat.PKCS8,
   encryption_algorithm=serialization.NoEncryption()
)
public_key_pem = public_key.public_bytes(
   encoding=serialization.Encoding.PEM,
   format=serialization.PublicFormat.SubjectPublicKeyInfo
)

# Save the keys to files or use them as needed
with open(''private_key.pem'', ''wb'') as f:
   f.write(private_key_pem)

with open(''public_key.pem'', ''wb'') as f:
   f.write(public_key_pem)

# Encrypting a message
message = b"Hello, world!"
encrypted_message = public_key.encrypt(
   message,
   padding.OAEP(
      mgf=padding.MGF1(algorithm=hashes.SHA256()),
      algorithm=hashes.SHA256(),
      label=None
   )
)

print("Original message:", message.decode())
print("Encrypted message:", encrypted_message)

Following is the output of the above example −

Input/Output

Original message: Hello, world!
Encrypted message: b''Lxaex1fxf6xe6x91q#+Rxdftvxcbx8dxb6x03g)/x80=xb9xf7x98xe3xbfxdauxcbxbdnFToxe0xb9rcxf2x8c x03xeblx11xe7''xb4xe1xdaJxabx9cDx184xae4[xcbx94ax8bPxa5xac+rx9dxc1xc1Px82xfbxb4I"xa4Wx1ex0bxedxd8xc9x9d=x81xdanxfdxa2xb8&6T3xdf>xd5oxc0xc2x0cx05gkxa3xd2xfaxc4xe5cxe6xc88Hexff-x14xc2?@*xaaoxd3sxbeEExa5Tx8b1x0fx1aTx1cxd7?xefx8f$xf7x99(xc1x9cxd5xdbx92xe2b}Efzntjyxc7xdfxe6x1axbex9ex1auxe5xb2pxa4xbbxd6>xf4x83x9c]q7(x\x1bx83xe9Qx8aBxe3xe9fx1dyx15xf2rxdax01+xf9cxafxd5mxbax9duxda.xfc&xedQKxbax8exbe^x7fcx8dxabxbbxebKnx9ax01xe2qxcdxc61Txe2nx11x94xxa6?dLcx82x02%xf8x18-xea''

Implementation of RSA using Java

The below Java code uses the RSA encryption algorithm. The code utilises many Java standard library modules and classes, like java.math.BigInteger, java.security.SecureRandom, and java.lang.String. The BigInteger class accepts arbitrary-precision integers, which are useful for handling big numbers in RSA encryption and decryption. The SecureRandom class generates cryptographically strong random numbers, which are then used to generate RSA keys. The String class is used to manipulate strings.

Example

The implementation of RSA algorithm using Java is as follows −

import java.math.BigInteger;
import java.security.SecureRandom;

public class RSA {

   private BigInteger prKey;
   private BigInteger pubKey;
   private BigInteger mod;

   // Generate public and private keys
   public RSA(int bitLength) {
      SecureRandom random = new SecureRandom();
      BigInteger p = BigInteger.probablePrime(bitLength / 2, random);
      BigInteger q = BigInteger.probablePrime(bitLength / 2, random);
      mod = p.multiply(q);
      BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
      pubKey = BigInteger.probablePrime(bitLength / 4, random);
      while (phi.gcd(pubKey).intValue() > 1) {
         pubKey = pubKey.add(BigInteger.ONE);
      }
      prKey = pubKey.modInverse(phi);
   }

   // Encrypt plaintext
   public BigInteger encrypt(String message) {
      BigInteger plaintext = new BigInteger(message.getBytes());
      return plaintext.modPow(pubKey, mod);
   }

   public static void main(String[] args) {
      RSA rsa = new RSA(1024);

      // Message to encrypt
      String plaintext = "HELLO TUTORIALSPOINT";
      System.out.println("Plaintext: " + plaintext);
      // Encrypt the message
      BigInteger ciphertext = rsa.encrypt(plaintext);
      System.out.println("Ciphertext: " + ciphertext);
   }
}

Following is the output of the above example −

Input/Output

Plaintext: HELLO TUTORIALSPOINT
Ciphertext: 81613159022598431502618861082122488243352277400520456503112436392671015741839175478780136032663342240432362810242747991048788272007296529186453061811896882040496871941396445756607265971854347817972502178724652319503362063137755270102568091525122886513678255187855721468502781772407941859987159924896465083062

Implementation of RSA using C++

Below is a simple implementation of the RSA algorithm using C++. This code covers key generation, encryption, and decryption processes −

Example

#include<iostream>
#include<math.h>
using namespace std;
// find gcd
int gcd(int a, int b) {
   int t;
   while(1) {
      t= a%b;
      if(t==0)
      return b;
      a = b;
      b= t;
   }
}
int main() {
   //2 random prime numbers
   double p = 13;
   double q = 11;
   double n=p*q;//calculate n
   double track;
   double phi= (p-1)*(q-1);//calculate phi
   //public key
   //e stands for encrypt
   double e=7;
   //for checking that 1 < e < phi(n) and gcd(e, phi(n)) = 1; i.e., e and phi(n) are coprime.
   while(e<phi) {
      track = gcd(e,phi);
      if(track==1)
         break;
      else
         e++;
   }
   //private key
   double d1=1/e;
   double d=fmod(d1,phi);
   double message = 9;
   double c = pow(message,e); //encrypt the message
   c=fmod(c,n);
   cout<<"Original Message = "<<message;
   cout<<"n"<<"Encrypted message = "<<c;
   return 0;
}

Following is the output of the above example −

Input/Output

Original Message = 9
Encrypted message = 48

Summary

RSA encryption plays a vital role in securing data online. It involves generating pairs of public and private keys, which create a secure connection. These keys are used to encrypt and decrypt messages, ensuring that only intended recipients can access the information. You can implement RSA encryption in Python using different methods, such as the random module, the RSA module, or the cryptography module. Each method has its own strengths, giving you flexibility and efficiency in protecting your data. And also we have implemented the RSA algorithm using Java and C++.