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:
The RSA algorithm ensures that the keys, in the above illustration, are as secure as possible. The following steps highlight how it works:
Note: Two integers are co-prime if the only positive integer that divides them is 1.
can be found using the extended euclidean algorithm. The pair makes up the private key.
Given a plaintext , represented as a number, the ciphertext is calculated as:
Using the private key , the plaintext can be found using:
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;
View all Courses