RSA

RSA was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adelman, hence the name Rivest–Shamir–Adleman (RSA). This type of public key cryptography is based on the integer factorization problem, where the multiplication of two large prime numbers is easy, but it is difficult to factor it (the result of multiplication, product) back to the two original numbers.

The crux of the work involved with the RSA algorithm is during the key generation process. An RSA key pair is generated by performing the following steps:

Modulus generation:

- Select p and q, which are very large prime numbers
- Multiply p and q, n=p.q to generate modulus n

Generate co-prime:

- Assume a number called e.
- e should satisfy a certain condition; that is, it should be greater than 1 and less than (p-1) (q-1). In other words, e must be a number such that no number other than 1 can divide e and (p-1) (q-1). This is called co-prime, that is, e is the co-prime of (p-1) (q-1).

Generate the public key:

The modulus generated in step 1 and co-prime e generated in step 2 is a pair together that is a public key. This part is the public part that can be shared with anyone; however, p and q need to be kept secret.

Generate the private key:

The private key, called d here, is calculated from p, q, and e. The private key is basically the inverse of e modulo (p-1) (q-1). In the equation form, it is this as follows:

ed = 1 mod (p-1) (q-1)

Usually, the extended Euclidean algorithm is used to calculate d. This algorithm takes p, q, and e and calculates d. The key idea in this scheme is that anyone who knows p and q can easily calculate private key d by applying the extended Euclidean algorithm. However, someone who does not know the value of p and q cannot generate d. This also implies that p and q should be large enough for the modulus n to become extremely difficult (computationally impractical) to factor.