Trusted answers to developer questions

What is the RSA algorithm?

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

The RSA algorithm is an asymmetric cryptography algorithm; this means that it uses a public key and a private key (i.e two different, mathematically linked keys). As their names suggest, a public key is shared publicly, while a private key is secret and must not be shared with anyone.

The RSA algorithm is named after those who invented it in 1978: Ron Rivest, Adi Shamir, and Leonard Adleman.

The following illustration highlights how asymmetric cryptography works:

svg viewer

How it works

The RSA algorithm ensures that the keys, in the above illustration, are as secure as possible. The following steps highlight how it works:

1. Generating the keys

  1. Select two large prime numbers, xx and yy. The prime numbers need to be large so that they will be difficult for someone to figure out.
  2. Calculate n=xn = x x yy.
  3. Calculate the totient function; ϕ(n)=(x1)(y1)\phi(n) = (x-1)(y-1).
  4. Select an integer ee, such that ee is co-prime to ϕ(n)\phi(n) and 1<e<ϕ(n)1 < e < \phi(n). The pair of numbers (n,e)(n,e) makes up the public key.

Note: Two integers are co-prime if the only positive integer that divides them is 1.

  1. Calculate dd such that e.d=1e.d = 1 modmod ϕ(n)\phi(n).

dd can be found using the extended euclidean algorithm. The pair (n,d)(n,d) makes up the private key.

2. Encryption

Given a plaintext PP, represented as a number, the ciphertext CC is calculated as:

C=PeC = P^{e} modmod nn.

3. Decryption

Using the private key (n,d)(n,d), the plaintext can be found using:

P=CdP = C^{d} modmod nn.

Pseudocode

Consider an example of the RSA algorithm through the following pseudocode:

int x = 61, int y = 53;
int n = x * y;
// n = 3233.

// compute the totient, phi
int phi = (x-1)*(y-1);
// phi = 3120.

int e = findCoprime(phi);
// find an 'e' which is > 1 and is a co-prime of phi.
// e = 17 satisfies the current values.

// Using the extended euclidean algorithm, find 'd' which satisfies 
// this equation:
d = (1 mod (phi))/e;
// d = 2753 for the example values.

public_key = (e=17, n=3233);
private_key = (d=2753, n=3233);

// Given the plaintext P=123, the ciphertext C is :
C = (123^17) % 3233 = 855;
// To decrypt the cypher text C:
P = (855^2753) % 3233 = 123;

RELATED TAGS

rsa
algorithm
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?