What is the procedure for key generation using RSA?

The standard procedure for creating a Secure Shell public/private key pair follows. For information on additional options, see ssh-keygen(1).

myLocalHost% ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key(/home/johndoe/.ssh/id_rsa): 

Enter file in which to save the key(/home/johndoe/.ssh/id_rsa): 

Enter passphrase(empty for no passphrase):  

Enter same passphrase again: 
Your identification has been saved in /home/johndoe/.ssh/id_rsa.
Your public key has been saved in /home/johndoe/.ssh/id_rsa.pub.
The key fingerprint is:
0e:fb:3d:57:71:73:bf:58:b8:eb:f3:a3:aa:df:e0:d1 johndoe@myLocalHost

Educative Answers Team

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:

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)=(x−1)(y−1)\phi(n) = (x-1)(y-1).
4. Select an integer ee, such that e e 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;

Copyright ©2022 Educative, Inc. All rights reserved

How are RSA keys generated?

What are three steps for RSA algorithm?

What is RSA key generator?

How is RSA used for key exchange?