RSA Algorithm in Cryptography - GeeksforGeeks (2024)

// C program for RSA asymmetric cryptographic// algorithm. For demonstration values are// relatively small compared to practical// application#include <bits/stdc++.h>using namespace std;// Returns gcd of a and bint gcd(int a, int h){ int temp; while (1) { temp = a % h; if (temp == 0) return h; a = h; h = temp; }}// Code to demonstrate RSA algorithmint main(){ // Two random prime numbers double p = 3; double q = 7; // First part of public key: double n = p * q; // Finding other part of public key. // e stands for encrypt double e = 2; double phi = (p - 1) * (q - 1); while (e < phi) { // e must be co-prime to phi and // smaller than phi. if (gcd(e, phi) == 1) break; else e++; } // Private key (d stands for decrypt) // choosing d such that it satisfies // d*e = 1 + k * totient int k = 2; // A constant value double d = (1 + (k * phi)) / e; // Message to be encrypted double msg = 12; printf("Message data = %lf", msg); // Encryption c = (msg ^ e) % n double c = pow(msg, e); c = fmod(c, n); printf("\nEncrypted data = %lf", c); // Decryption m = (c ^ d) % n double m = pow(c, d); m = fmod(m, n); printf("\nOriginal Message Sent = %lf", m); return 0;}// This code is contributed by Akash Sharan.

/*package whatever //do not write package name here */import java.io.*;import java.math.*;import java.util.*;/* * Java program for RSA asymmetric cryptographic algorithm. * For demonstration, values are * relatively small compared to practical application */public class GFG { public static double gcd(double a, double h) { /* * This function returns the gcd or greatest common * divisor */ double temp; while (true) { temp = a % h; if (temp == 0) return h; a = h; h = temp; } } public static void main(String[] args) { double p = 3; double q = 7; // Stores the first part of public key: double n = p * q; // Finding the other part of public key. // double e stands for encrypt double e = 2; double phi = (p - 1) * (q - 1); while (e < phi) { /* * e must be co-prime to phi and * smaller than phi. */ if (gcd(e, phi) == 1) break; else e++; } int k = 2; // A constant value double d = (1 + (k * phi)) / e; // Message to be encrypted double msg = 12; System.out.println("Message data = " + msg); // Encryption c = (msg ^ e) % n double c = Math.pow(msg, e); c = c % n; System.out.println("Encrypted data = " + c); // Decryption m = (c ^ d) % n double m = Math.pow(c, d); m = m % n; System.out.println("Original Message Sent = " + m); }}// This code is contributed by Pranay Arora.

# Python for RSA asymmetric cryptographic algorithm.# For demonstration, values are# relatively small compared to practical applicationimport mathdef gcd(a, h): temp = 0 while(1): temp = a % h if (temp == 0): return h a = h h = tempp = 3q = 7n = p*qe = 2phi = (p-1)*(q-1)while (e < phi): # e must be co-prime to phi and # smaller than phi. if(gcd(e, phi) == 1): break else: e = e+1# Private key (d stands for decrypt)# choosing d such that it satisfies# d*e = 1 + k * totientk = 2d = (1 + (k*phi))/e# Message to be encryptedmsg = 12.0print("Message data = ", msg)# Encryption c = (msg ^ e) % nc = pow(msg, e)c = math.fmod(c, n)print("Encrypted data = ", c)# Decryption m = (c ^ d) % nm = pow(c, d)m = math.fmod(m, n)print("Original Message Sent = ", m)# This code is contributed by Pranay Arora.

/* * C# program for RSA asymmetric cryptographic algorithm. * For demonstration, values are * relatively small compared to practical application */using System;public class GFG { public static double gcd(double a, double h) { /* * This function returns the gcd or greatest common * divisor */ double temp; while (true) { temp = a % h; if (temp == 0) return h; a = h; h = temp; } } static void Main() { double p = 3; double q = 7; // Stores the first part of public key: double n = p * q; // Finding the other part of public key. // double e stands for encrypt double e = 2; double phi = (p - 1) * (q - 1); while (e < phi) { /* * e must be co-prime to phi and * smaller than phi. */ if (gcd(e, phi) == 1) break; else e++; } int k = 2; // A constant value double d = (1 + (k * phi)) / e; // Message to be encrypted double msg = 12; Console.WriteLine("Message data = " + String.Format("{0:F6}", msg)); // Encryption c = (msg ^ e) % n double c = Math.Pow(msg, e); c = c % n; Console.WriteLine("Encrypted data = " + String.Format("{0:F6}", c)); // Decryption m = (c ^ d) % n double m = Math.Pow(c, d); m = m % n; Console.WriteLine("Original Message Sent = " + String.Format("{0:F6}", m)); }}// This code is contributed by Pranay Arora.

//GFG//Javascript code for this approachfunction gcd(a, h) { /* * This function returns the gcd or greatest common * divisor */ let temp; while (true) { temp = a % h; if (temp == 0) return h; a = h; h = temp; }}let p = 3;let q = 7;// Stores the first part of public key:let n = p * q;// Finding the other part of public key.// e stands for encryptlet e = 2;let phi = (p - 1) * (q - 1);while (e < phi) { /* * e must be co-prime to phi and * smaller than phi. */ if (gcd(e, phi) == 1) break; else e++;}let k = 2; // A constant valuelet d = (1 + (k * phi)) / e;// Message to be encryptedlet msg = 12;console.log("Message data = " + msg);// Encryption c = (msg ^ e) % nlet c = Math.pow(msg, e);c = c % n;console.log("Encrypted data = " + c);// Decryption m = (c ^ d) % nlet m = Math.pow(c, d);m = m % n;console.log("Original Message Sent = " + m);//This code is written by Sundaram

#include <bits/stdc++.h>using namespace std;set<int> prime; // a set will be the collection of prime numbers, // where we can select random primes p and qint public_key;int private_key;int n;// we will run the function only once to fill the set of// prime numbersvoid primefiller(){ // method used to fill the primes set is seive of // eratosthenes(a method to collect prime numbers) vector<bool> seive(250, true); seive[0] = false; seive[1] = false; for (int i = 2; i < 250; i++) { for (int j = i * 2; j < 250; j += i) { seive[j] = false; } } // filling the prime numbers for (int i = 0; i < seive.size(); i++) { if (seive[i]) prime.insert(i); }}// picking a random prime number and erasing that prime// number from list because p!=qint pickrandomprime(){ int k = rand() % prime.size(); auto it = prime.begin(); while (k--) it++; int ret = *it; prime.erase(it); return ret;}void setkeys(){ int prime1 = pickrandomprime(); // first prime number int prime2 = pickrandomprime(); // second prime number // to check the prime numbers selected // cout<<prime1<<" "<<prime2<<endl; n = prime1 * prime2; int fi = (prime1 - 1) * (prime2 - 1); int e = 2; while (1) { if (__gcd(e, fi) == 1) break; e++; } // d = (k*Φ(n) + 1) / e for some integer k public_key = e; int d = 2; while (1) { if ((d * e) % fi == 1) break; d++; } private_key = d;}// to encrypt the given numberlong long int encrypt(double message){ int e = public_key; long long int encrpyted_text = 1; while (e--) { encrpyted_text *= message; encrpyted_text %= n; } return encrpyted_text;}// to decrypt the given numberlong long int decrypt(int encrpyted_text){ int d = private_key; long long int decrypted = 1; while (d--) { decrypted *= encrpyted_text; decrypted %= n; } return decrypted;}// first converting each character to its ASCII value and// then encoding it then decoding the number to get the// ASCII and converting it to charactervector<int> encoder(string message){ vector<int> form; // calling the encrypting function in encoding function for (auto& letter : message) form.push_back(encrypt((int)letter)); return form;}string decoder(vector<int> encoded){ string s; // calling the decrypting function decoding function for (auto& num : encoded) s += decrypt(num); return s;}int main(){ primefiller(); setkeys(); string message = "Test Message"; // uncomment below for manual input // cout<<"enter the message\n";getline(cin,message); // calling the encoding function vector<int> coded = encoder(message); cout << "Initial message:\n" << message; cout << "\n\nThe encoded message(encrypted by public " "key)\n"; for (auto& p : coded) cout << p; cout << "\n\nThe decoded message(decrypted by private " "key)\n"; cout << decoder(coded) << endl; return 0;}

import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Random;public class GFG { private static HashSet<Integer> prime = new HashSet<>(); private static Integer public_key = null; private static Integer private_key = null; private static Integer n = null; private static Random random = new Random(); public static void main(String[] args) { primeFiller(); setKeys(); String message = "Test Message"; // Uncomment below for manual input // System.out.println("Enter the message:"); // message = new Scanner(System.in).nextLine(); List<Integer> coded = encoder(message); System.out.println("Initial message:"); System.out.println(message); System.out.println( "\n\nThe encoded message (encrypted by public key)\n"); System.out.println( String.join("", coded.stream() .map(Object::toString) .toArray(String[] ::new))); System.out.println( "\n\nThe decoded message (decrypted by public key)\n"); System.out.println(decoder(coded)); } public static void primeFiller() { boolean[] sieve = new boolean[250]; for (int i = 0; i < 250; i++) { sieve[i] = true; } sieve[0] = false; sieve[1] = false; for (int i = 2; i < 250; i++) { for (int j = i * 2; j < 250; j += i) { sieve[j] = false; } } for (int i = 0; i < sieve.length; i++) { if (sieve[i]) { prime.add(i); } } } public static int pickRandomPrime() { int k = random.nextInt(prime.size()); List<Integer> primeList = new ArrayList<>(prime); int ret = primeList.get(k); prime.remove(ret); return ret; } public static void setKeys() { int prime1 = pickRandomPrime(); int prime2 = pickRandomPrime(); n = prime1 * prime2; int fi = (prime1 - 1) * (prime2 - 1); int e = 2; while (true) { if (gcd(e, fi) == 1) { break; } e += 1; } public_key = e; int d = 2; while (true) { if ((d * e) % fi == 1) { break; } d += 1; } private_key = d; } public static int encrypt(int message) { int e = public_key; int encrypted_text = 1; while (e > 0) { encrypted_text *= message; encrypted_text %= n; e -= 1; } return encrypted_text; } public static int decrypt(int encrypted_text) { int d = private_key; int decrypted = 1; while (d > 0) { decrypted *= encrypted_text; decrypted %= n; d -= 1; } return decrypted; } public static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } public static List<Integer> encoder(String message) { List<Integer> encoded = new ArrayList<>(); for (char letter : message.toCharArray()) { encoded.add(encrypt((int)letter)); } return encoded; } public static String decoder(List<Integer> encoded) { StringBuilder s = new StringBuilder(); for (int num : encoded) { s.append((char)decrypt(num)); } return s.toString(); }}

import randomimport math# A set will be the collection of prime numbers,# where we can select random primes p and qprime = set()public_key = Noneprivate_key = Nonen = None# We will run the function only once to fill the set of# prime numbersdef primefiller(): # Method used to fill the primes set is Sieve of # Eratosthenes (a method to collect prime numbers) seive = [True] * 250 seive[0] = False seive[1] = False for i in range(2, 250): for j in range(i * 2, 250, i): seive[j] = False # Filling the prime numbers for i in range(len(seive)): if seive[i]: prime.add(i)# Picking a random prime number and erasing that prime# number from list because p!=qdef pickrandomprime(): global prime k = random.randint(0, len(prime) - 1) it = iter(prime) for _ in range(k): next(it) ret = next(it) prime.remove(ret) return retdef setkeys(): global public_key, private_key, n prime1 = pickrandomprime() # First prime number prime2 = pickrandomprime() # Second prime number n = prime1 * prime2 fi = (prime1 - 1) * (prime2 - 1) e = 2 while True: if math.gcd(e, fi) == 1: break e += 1 # d = (k*Φ(n) + 1) / e for some integer k public_key = e d = 2 while True: if (d * e) % fi == 1: break d += 1 private_key = d# To encrypt the given numberdef encrypt(message): global public_key, n e = public_key encrypted_text = 1 while e > 0: encrypted_text *= message encrypted_text %= n e -= 1 return encrypted_text# To decrypt the given numberdef decrypt(encrypted_text): global private_key, n d = private_key decrypted = 1 while d > 0: decrypted *= encrypted_text decrypted %= n d -= 1 return decrypted# First converting each character to its ASCII value and# then encoding it then decoding the number to get the# ASCII and converting it to characterdef encoder(message): encoded = [] # Calling the encrypting function in encoding function for letter in message: encoded.append(encrypt(ord(letter))) return encodeddef decoder(encoded): s = '' # Calling the decrypting function decoding function for num in encoded: s += chr(decrypt(num)) return sif __name__ == '__main__': primefiller() setkeys() message = "Test Message" # Uncomment below for manual input # message = input("Enter the message\n") # Calling the encoding function coded = encoder(message) print("Initial message:") print(message) print("\n\nThe encoded message(encrypted by public key)\n") print(''.join(str(p) for p in coded)) print("\n\nThe decoded message(decrypted by public key)\n") print(''.join(str(p) for p in decoder(coded))) 

using System;using System.Collections.Generic;public class GFG{ private static HashSet<int> prime = new HashSet<int>(); private static int? public_key = null; private static int? private_key = null; private static int? n = null; private static Random random = new Random(); public static void Main() { PrimeFiller(); SetKeys(); string message = "Test Message"; // Uncomment below for manual input // Console.WriteLine("Enter the message:"); // message = Console.ReadLine(); List<int> coded = Encoder(message); Console.WriteLine("Initial message:"); Console.WriteLine(message); Console.WriteLine("\n\nThe encoded message (encrypted by public key)\n"); Console.WriteLine(string.Join("", coded)); Console.WriteLine("\n\nThe decoded message (decrypted by public key)\n"); Console.WriteLine(Decoder(coded)); } public static void PrimeFiller() { bool[] sieve = new bool[250]; for (int i = 0; i < 250; i++) { sieve[i] = true; } sieve[0] = false; sieve[1] = false; for (int i = 2; i < 250; i++) { for (int j = i * 2; j < 250; j += i) { sieve[j] = false; } } for (int i = 0; i < sieve.Length; i++) { if (sieve[i]) { prime.Add(i); } } } public static int PickRandomPrime() { int k = random.Next(0, prime.Count - 1); var enumerator = prime.GetEnumerator(); for (int i = 0; i <= k; i++) { enumerator.MoveNext(); } int ret = enumerator.Current; prime.Remove(ret); return ret; } public static void SetKeys() { int prime1 = PickRandomPrime(); int prime2 = PickRandomPrime(); n = prime1 * prime2; int fi = (prime1 - 1) * (prime2 - 1); int e = 2; while (true) { if (GCD(e, fi) == 1) { break; } e += 1; } public_key = e; int d = 2; while (true) { if ((d * e) % fi == 1) { break; } d += 1; } private_key = d; } public static int Encrypt(int message) { int e = public_key.Value; int encrypted_text = 1; while (e > 0) { encrypted_text *= message; encrypted_text %= n.Value; e -= 1; } return encrypted_text; } public static int Decrypt(int encrypted_text) { int d = private_key.Value; int decrypted = 1; while (d > 0) { decrypted *= encrypted_text; decrypted %= n.Value; d -= 1; } return decrypted; } public static int GCD(int a, int b) { if (b == 0) { return a; } return GCD(b, a % b); } public static List<int> Encoder(string message) { List<int> encoded = new List<int>(); foreach (char letter in message) { encoded.Add(Encrypt((int)letter)); } return encoded; } public static string Decoder(List<int> encoded) { string s = ""; foreach (int num in encoded) { s += (char)Decrypt(num); } return s; } }

#include <iostream>#include <cmath>using namespace std;// calculate phi(n) for a given number nint phi(int n) { int result = n; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { while (n % i == 0) { n /= i; } result -= result / i; } } if (n > 1) { result -= result / n; } return result;}// calculate gcd(a, b) using the Euclidean algorithmint gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b);}// calculate a^b mod m using modular exponentiationint modpow(int a, int b, int m) { int result = 1; while (b > 0) { if (b & 1) { result = (result * a) % m; } a = (a * a) % m; b >>= 1; } return result;}// generate a random primitive root modulo nint generatePrimitiveRoot(int n) { int phiN = phi(n); int factors[phiN], numFactors = 0; int temp = phiN; // get all prime factors of phi(n) for (int i = 2; i <= sqrt(temp); i++) { if (temp % i == 0) { factors[numFactors++] = i; while (temp % i == 0) { temp /= i; } } } if (temp > 1) { factors[numFactors++] = temp; } // test possible primitive roots for (int i = 2; i <= n; i++) { bool isRoot = true; for (int j = 0; j < numFactors; j++) { if (modpow(i, phiN / factors[j], n) == 1) { isRoot = false; break; } } if (isRoot) { return i; } } return -1;}int main() { int p = 11; int q = 13; int n = p * q; int phiN = (p - 1) * (q - 1); // phi(n) = 120 int e = 7; // gcd(7, 120) = 1  int d = 0; while ((d * e) % phiN != 1) { d++; }  cout << "Public key: {" << e << ", " << n << "}" << endl; cout << "Private key: {" << d << ", " << n << "}" << endl; int m = 11; int c = modpow(m, e, n); int decrypted = modpow(c, d, n); cout << "Original message: " << m << endl; cout << "Encrypted message: " << c << endl; cout << "Decrypted message: " << decrypted << endl; return 0;}// This code is modified by Susobhan Akhuli

import java.util.*;public class GFG { // calculate phi(n) for a given number n static int phi(int n) { int result = n; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { while (n % i == 0) { n /= i; } result -= result / i; } } if (n > 1) { result -= result / n; } return result; } // calculate gcd(a, b) using the Euclidean algorithm static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // calculate a^b mod m using modular exponentiation static int modpow(int a, int b, int m) { int result = 1; while (b > 0) { if ((b & 1) == 1) { result = (result * a) % m; } a = (a * a) % m; b >>= 1; } return result; } // generate a random primitive root modulo n static int generatePrimitiveRoot(int n) { int phiN = phi(n); List<Integer> factors = new ArrayList<>(); int temp = phiN; // get all prime factors of phi(n) for (int i = 2; i <= Math.sqrt(temp); i++) { if (temp % i == 0) { factors.add(i); while (temp % i == 0) { temp /= i; } } } if (temp > 1) { factors.add(temp); } // test possible primitive roots for (int i = 2; i <= n; i++) { boolean isRoot = true; for (int factor : factors) { if (modpow(i, phiN / factor, n) == 1) { isRoot = false; break; } } if (isRoot) { return i; } } return -1; } public static void main(String[] args) { int p = 11; int q = 13; int n = p * q; int phiN = (p - 1) * (q - 1); // phi(n) = 120 int e = 7; // gcd(7, 120) = 1  int d = 0; while ((d * e) % phiN != 1) { d++; } System.out.println("Public key: {" + e + ", " + n + "}"); System.out.println("Private key: {" + d + ", " + n + "}"); int m = 11; int c = modpow(m, e, n); int decrypted = modpow(c, d, n); System.out.println("Original message: " + m); System.out.println("Encrypted message: " + c); System.out.println("Decrypted message: " + decrypted); }}// This code is contributed by Susobhan Akhuli