RSA Algorithm in Cryptography - GeeksforGeeks - The first knowledge sharing application in Vietnam

RSA algorithm is an asymmetric cryptography algorithm. Asymmetric actually means that it works on two different keys i.e. Public Key and Private Key. As the name describes that the Public Key is given to everyone and the Private key is kept private.

An example of asymmetric cryptography:

A client (for example browser) sends its public key to the server and requests some data.
The server encrypts the data using the client’s public key and sends the encrypted data.
The client receives this data and decrypts it.

Since this is asymmetric, nobody else except the browser can decrypt the data even if a third party has the public key of the browser.

The idea! The idea of RSA is based on the fact that it is difficult to factorize a large integer. The public key consists of two numbers where one number is a multiplication of two large prime numbers. And private key is also derived from the same two prime numbers. So if somebody can factorize the large number, the private key is compromised. Therefore encryption strength totally lies on the key size and if we double or triple the key size, the strength of encryption increases exponentially. RSA keys can be typically 1024 or 2048 bits long, but experts believe that 1024-bit keys could be broken in the near future. But till now it seems to be an infeasible task.

Let us learn the mechanism behind the RSA algorithm : >> Generating Public Key:

Select two prime no's. Suppose P = 53 and Q = 59.
Now First part of the Public key  : n = P*Q = 3127.
 We also need a small exponent say e : 
But e Must be 
An integer.
Not be a factor of Φ(n). 
1 < e < Φ(n) [Φ(n) is discussed below], 
Let us now consider it to be equal to 3.
    Our Public Key is made of n and e

>> Generating Private Key:

We need to calculate Φ(n) :
Such that Φ(n) = (P-1)(Q-1)     
      so,  Φ(n) = 3016
    Now calculate Private Key, d : 
d = (k*Φ(n) + 1) / e for some integer k
For k = 2, value of d is 2011.

Now we are ready with our – Public Key ( n = 3127 and e = 3) and Private Key(d = 2011) Now we will encrypt “HI”:

Convert letters to numbers : H  = 8 and I = 9
    Thus Encrypted Data c = 89e mod n. 
Thus our Encrypted Data comes out to be 1394

Now we will decrypt 1394 : 
    Decrypted Data = cd mod n. 
Thus our Encrypted Data comes out to be 89
8 = H and I = 9 i.e. "HI".

Below is the implementation of the RSA algorithm for

Method 1: Encrypting and decrypting small numeral values:

Mục lục bài viết

C++

#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int h)

{

int temp;

while (1) {

temp = a % h;

if (temp == 0)

return h;

a = h;

h = temp;

}

int main()

{

double p = 3;

double q = 7;

double n = p * q;

double e = 2;

double phi = (p - 1) * (q - 1);

while (e < phi) {

if (gcd(e, phi) == 1)

break;

else

e++;

}

int k = 2;

double d = (1 + (k * phi)) / e;

double msg = 12;

printf("Message data = %lf", msg);

double c = pow(msg, e);

c = fmod(c, n);

printf("\nEncrypted data = %lf", c);

double m = pow(c, d);

m = fmod(m, n);

printf("\nOriginal Message Sent = %lf", m);

return 0;

}

Java

import java.io.*;

import java.math.*;

import java.util.*;

public class GFG {

public static double gcd(double a, double h)

{

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;

double n = p * q;

double e = 2;

double phi = (p - 1) * (q - 1);

while (e < phi) {

if (gcd(e, phi) == 1)

break;

else

e++;

}

int k = 2;

double d = (1 + (k * phi)) / e;

double msg = 12;

System.out.println("Message data = " + msg);

double c = Math.pow(msg, e);

c = c % n;

System.out.println("Encrypted data = " + c);

double m = Math.pow(c, d);

m = m % n;

System.out.println("Original Message Sent = " + m);

}

Python3

import math

def gcd(a, h):

temp = 0

while(1):

temp = a % h

if (temp == 0):

return h

a = h

h = temp

p = 3

q = 7

n = p*q

e = 2

phi = (p-1)*(q-1)

while (e < phi):

if(gcd(e, phi) == 1):

break

else:

e = e+1

k = 2

d = (1 + (k*phi))/e

msg = 12.0

print("Message data = ", msg)

c = pow(msg, e)

c = math.fmod(c, n)

print("Encrypted data = ", c)

m = pow(c, d)

m = math.fmod(m, n)

print("Original Message Sent = ", m)

C#

using System;

public class GFG {

public static double gcd(double a, double h)

{

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;

double n = p * q;

double e = 2;

double phi = (p - 1) * (q - 1);

while (e < phi) {

if (gcd(e, phi) == 1)

break;

else

e++;

}

int k = 2;

double d = (1 + (k * phi)) / e;

double msg = 12;

Console.WriteLine("Message data = "

+ String.Format("{0:F6}", msg));

double c = Math.Pow(msg, e);

c = c % n;

Console.WriteLine("Encrypted data = "

+ String.Format("{0:F6}", c));

double m = Math.Pow(c, d);

m = m % n;

Console.WriteLine("Original Message Sent = "

+ String.Format("{0:F6}", m));

}

Javascript

function gcd(a, h) {

let temp;

while (true) {

temp = a % h;

if (temp == 0) return h;

a = h;

h = temp;

}

let p = 3;

let q = 7;

let n = p * q;

let e = 2;

let phi = (p - 1) * (q - 1);

while (e < phi) {

if (gcd(e, phi) == 1) break;

else e++;

}

let k = 2;

let d = (1 + (k * phi)) / e;

let msg = 12;

console.log("Message data = " + msg);

let c = Math.pow(msg, e);

c = c % n;

console.log("Encrypted data = " + c);

let m = Math.pow(c, d);

m = m % n;

console.log("Original Message Sent = " + m);

Output

Message data = 12.000000
Encrypted data = 3.000000
Original Message Sent = 12.000000

Method 2: Encrypting and decrypting plain text messages containing alphabets and numbers using their ASCII value:

C++

#include <bits/stdc++.h>

using namespace std;

set<int>

prime;

int public_key;

int private_key;

int n;

void primefiller()

{

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;

}

for (int i = 0; i < seive.size(); i++) {

if (seive[i])

prime.insert(i);

}

int 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();

int prime2 = pickrandomprime();

n = prime1 * prime2;

int fi = (prime1 - 1) * (prime2 - 1);

int e = 2;

while (1) {

if (__gcd(e, fi) == 1)

break;

e++;

}

public_key = e;

int d = 2;

while (1) {

if ((d * e) % fi == 1)

break;

d++;

}

private_key = d;

}

long 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;

}

long long int decrypt(int encrpyted_text)

{

int d = private_key;

long long int decrypted = 1;

while (d--) {

decrypted *= encrpyted_text;

decrypted %= n;

}

return decrypted;

}

vector<int> encoder(string message)

{

vector<int> form;

for (auto& letter : message)

form.push_back(encrypt((int)letter));

return form;

}

string decoder(vector<int> encoded)

{

string s;

for (auto& num : encoded)

s += decrypt(num);

return s;

}

int main()

{

primefiller();

setkeys();

string message = "Test Message";

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;

}

Python3

import random

import math

prime = set()

public_key = None

private_key = None

n = None

def primefiller():

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

for i in range(len(seive)):

if seive[i]:

prime.add(i)

def 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 ret

def setkeys():

global public_key, private_key, n

prime1 = pickrandomprime()

prime2 = pickrandomprime()

n = prime1 * prime2

fi = (prime1 - 1) * (prime2 - 1)

e = 2

while True:

if math.gcd(e, fi) == 1:

break

e += 1

public_key = e

d = 2

while True:

if (d * e) % fi == 1:

break

d += 1

private_key = d

def 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

def decrypt(encrypted_text):

global private_key, n

d = private_key

decrypted = 1

while d > 0:

decrypted *= encrypted_text

decrypted %= n

d -= 1

return decrypted

def encoder(message):

encoded = []

for letter in message:

encoded.append(encrypt(ord(letter)))

return encoded

def decoder(encoded):

s = ''

for num in encoded:

s += chr(decrypt(num))

return s

if __name__ == '__main__':

primefiller()

setkeys()

message = "Test Message"

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)))

Output

Initial message:
Test Message

The encoded message(encrypted by public key)
863312887135951593413927434912887135951359583051879012887

The decoded message(decrypted by private key)
Test Message

Advantages:

Security: RSA algorithm is considered to be very secure and is widely used for secure data transmission.

Public-key cryptography: RSA algorithm is a public-key cryptography algorithm, which means that it uses two different keys for encryption and decryption. The public key is used to encrypt the data, while the private key is used to decrypt the data.

Key exchange: RSA algorithm can be used for secure key exchange, which means that two parties can exchange a secret key without actually sending the key over the network.

Digital signatures: RSA algorithm can be used for digital signatures, which means that a sender can sign a message using their private key, and the receiver can verify the signature using the sender’s public key.

Disadvantages:

Slow processing speed: RSA algorithm is slow compared to other encryption algorithms, especially when dealing with large amounts of data.

Large key size: RSA algorithm requires large key sizes to be secure, which means that it requires more computational resources and storage space.

Vulnerability to side-channel attacks: RSA algorithm is vulnerable to side-channel attacks, which means that an attacker can use information leaked through side channels such as power consumption, electromagnetic radiation, and timing analysis to extract the private key.

Limited use in some applications: RSA algorithm is not suitable for some applications, such as those that require constant encryption and decryption of large amounts of data, due to its slow processing speed.

This article is contributed by Mohit Gupta_OMG. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

My Personal Notes

RSA Algorithm in Cryptography – GeeksforGeeks

C++

Java

Python3

C#

Javascript

C++

Python3

Advantages:

Disadvantages: