RSA Algorithm

 RSA (cryptosystem) algorithm

The RSA algorithm is used for both public key encryption and digital signatures. It is the most widely used public key encryption algorithm. The basis of the security of the RSA algorithm is that it is mathematically infeasible to factor sufficiently large integers. The RSA algorithm is believed to be secure if its keys have a length of at least 1024-bits. RSA is one of the first practicable public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem.

This algorithm was given by Ron Rivest, Adi Shamir and Len Adleman. It is named after the initials of their surnames.

Key generation

RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way:

1. Choose two distinct prime numbers p and q.
• For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
2. Compute n = pq.
• n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function.
4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are co prime.
• e is released as the public key exponent.
• e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 2¹⁶ + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.
5. Determine d as d ≡ e⁻¹ (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)).

·         This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod φ(n))

·         This is often computed using the extended Euclidean algorithm. Using the pseudocode in the Modular integers section, inputs a and n correspond to e and φ(n), respectively.

·         d is kept as the private key exponent.

  

Encryption ,Decryption will be discussed later .