RSA cryptographic algorithm

RSA (Rivest-Shamir-Adleman) is a widely used asymmetric cryptographic algorithm, named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman. It is commonly used for secure communication, digital signatures, and key exchange.

As an asymmetric algorithm, RSA uses a pair of keys: a public key and a private key. The public key is used for encryption and can be freely distributed, while the private key is kept secret and used for decryption.

Here's a simplified overview of how RSA works:

1. Key Generation: First, the RSA algorithm generates a public-private key pair. The private key consists of two large prime numbers, and the public key is derived from these primes.

2. Encryption: To send an encrypted message, the sender uses the recipient's public key. The sender converts the message into numerical form and applies modular exponentiation with the public key to obtain the encrypted ciphertext.

3. Decryption: The recipient, who possesses the corresponding private key, uses it to decrypt the ciphertext. By applying modular exponentiation with the private key, the recipient recovers the original message.

The security of RSA is based on the difficulty of factoring large composite numbers into their prime factors. The larger the key size, the harder it is to factorize and break the encryption. RSA is widely used in various applications where secure communication, data integrity, and authentication are required.

It's worth noting that while RSA is a well-established algorithm, other cryptographic algorithms like elliptic curve cryptography (ECC) are gaining popularity due to their ability to provide equivalent security with smaller key sizes, resulting in more efficient operations.

Let's go through a simplified example of RSA encryption and decryption.

1. Key Generation:

   • Choose two prime numbers, p = 17 and q = 11.

   • Compute the modulus, N = p * q = 17 * 11 = 187.

   • Compute Euler's totient function, φ(N) = (p - 1) * (q - 1) = 16 * 10 = 160

   • Choose a public exponent, e, which is relatively prime to φ(N). Let's choose e = 7.

   • Compute the private exponent, d, such that (d * e) % φ(N) = 1. In this case, d = 23.

2. Encryption:

   • Suppose we want to encrypt the message "HELLO".

   • Convert each character into its corresponding numerical representation, e.g., H = 8, E = 5, L = 12, O = 15.

   • Apply modular exponentiation to each character using the public key (e) and the modulus (N):

     • Encrypted H = 8^7 % 187 = 23.

     • Encrypted E = 5^7 % 187 = 138.

     • Encrypted L = 12^7 % 187 = 71.

     • Encrypted O = 15^7 % 187 = 71.

   • The encrypted message becomes "23 138 71 71".

3. Decryption:

   • The recipient uses the private key (d) and the modulus (N) to decrypt the ciphertext.

   • Apply modular exponentiation to each encrypted character:

     • Decrypted 23 = 23^23 % 187 = 8.

     • Decrypted 138 = 138^23 % 187 = 5.

     • Decrypted 71 = 71^23 % 187 = 12.

     • Decrypted 71 = 71^23 % 187 = 15.

   • Convert the numerical representation back to characters: 8 = H, 5 = E, 12 = L, 15 = O.

   • The decrypted message is "HELLO".

This example demonstrates a basic illustration of RSA encryption and decryption. In practice, larger prime numbers and longer keys are used to ensure stronger security.

The operator "φ" is called Euler's totient function, often denoted as φ (phi). It is a mathematical function that calculates the number of positive integers less than or coprime to a given number.

For a positive integer n, φ(n) represents the count of numbers between 1 and n (inclusive) that are relatively prime to n, meaning they share no common factors with n except for 1. In other words, φ(n) gives the number of integers that are coprime to n.

Euler's totient function is used in various areas of number theory and cryptography, including the RSA algorithm, where it plays a crucial role in key generation. It helps determine the appropriate value for the public exponent and is used to calculate the private exponent in RSA encryption and decryption.