RSA Definition With an Example of RSA Algorithm

In this article, we’ll take a journey into the world of RSA, exploring its history, definition, and providing an example of RSA algorithm in action. In this digital age, secure communication is a cornerstone of our daily lives. Whether you’re sending a confidential email, making an online purchase, or managing your online banking, a cryptographic superstar known as the RSA algorithm plays a crucial role in safeguarding your digital transactions. So, without any further ado, let’s dive in!

Also Read: Encryption and Decryption Explained in Simple Terms

The Remarkable History of RSA

Before we dive into the inner workings of the RSA algorithm, let’s rewind the clock and appreciate its intriguing history. The acronym RSA stands for Rivest, Shamir, and Adleman, which are the surnames of the brilliant minds behind this cryptographic marvel. Ron Rivest, Adi Shamir, and Leonard Adleman introduced RSA to the world back in 1977, and their creation initiated a revolution in the field of cryptography.

The birth of RSA marked a significant departure from traditional encryption methods, which largely relied on shared secret keys. RSA introduced the concept of a public-key cryptosystem, a fundamental shift that has become the bedrock of secure digital communication and data protection as we know it today.

The RSA Algorithm: A Quick Definition

Now that we have a glimpse of its history, let’s demystify the RSA algorithm itself. At its core, RSA is a public-key cryptosystem. Unlike traditional cryptography, which relies on a single secret key for both encryption and decryption, RSA uses a pair of keys – a public key and a private key.

Public Key: The public key is openly shared with the world and can be known by everyone. It typically consists of two essential components: a modulus (n) and an exponent (e). These values are chosen meticulously during key generation and are used for encryption.

Private Key: The private key, as the name implies, is kept secret. It comprises the same modulus as the public key but includes a different exponent (d). The private key is used to decrypt messages.

The RSA algorithm involves four steps: key generation, key distribution, encryption, and decryption.

Key Generation

Key generation is the foundation of the RSA algorithm. Here’s a brief overview of this critical step:

The process begins by generating a public-private key pair. The public key includes a modulus (n) and an exponent (e), while the private key includes the same modulus and a different exponent (d). These values are carefully selected during key generation.

To generate RSA keys, we follow these steps:

Step 1: Choose Two Large Prime Numbers (p and q)

• To start, we pick two big prime numbers, p and q.
• These numbers should be chosen randomly and should be quite large.
• The reason for choosing large primes is to make it very difficult for someone to figure out your keys by factoring these numbers.
• p and q are kept secret; we don’t share them with anyone.

Step 2: Calculate n = pq

• Now, we multiply these two prime numbers together to get a new number called “n.”
• This n is the key ingredient in both the public and private keys.
• The length of n, usually measured in bits, determines the strength of the RSA key. The longer it is, the more secure the encryption.
• We share n as part of the public key.

Step 3: Compute λ(n) (Carmichael’s Totient Function)

• To find λ(n), we use a special function called Carmichael’s totient function.
• Since n = pq, λ(n) is calculated as the least common multiple of (p – 1) and (q – 1).
• This is done to make sure λ(n) remains a secret.
• We find the least common multiple using a mathematical method called the Euclidean algorithm, but you don’t need to worry about the details.
• The Euler totient function φ(n) = (p − 1)(q − 1) can also be used instead of λ(n) for calculating the private exponent d. For the purpose of this article we will be using φ(n) instead of λ(n) as it is easier to calculate.

Step 4: Select an Integer e

• We choose an integer called “e” such that it meets two conditions:
  1. It should be greater than 2 and less than λ(n).
  2. It should not have any common factors with λ(n) (except for 1).
• Most commonly, e is set to 65537, which is a good balance between security and efficiency. But it can be different.
• e is shared as part of the public key.

Step 5: Calculate d (Private Key)

• Finally, we determine a value called “d” by calculating the modular multiplicative inverse of e modulo λ(n).
• This means we solve the equation de ≡ 1 (mod λ(n)) to find d.
• The extended Euclidean algorithm helps us compute d efficiently.
• d is kept a closely guarded secret and is your private key exponent.

In a nutshell, RSA key generation involves selecting large prime numbers, computing a modulus n, finding the Carmichael’s totient function or Euler totient function, choosing a suitable value for e, and then calculating the corresponding private key exponent, d. The public key consists of n and e, while the private key is comprised of d and other values not mentioned in these steps. This process forms the foundation for secure encryption and decryption in RSA.

Public Key:

• The public key in RSA consists of two main components: the modulus (n) and the public exponent (e).
• The modulus (n) is a product of two large prime numbers, and it’s used in both encryption and decryption processes.
• The public exponent (e) is an integer chosen to ensure the key’s security and efficiency.
• It’s important to understand that the public key is made available to anyone who wants to send you an encrypted message. They need these values to encode the message so that only you, with the private key, can decode it.

Private Key:

• On the other side of the RSA encryption, we have the private key.
• The private key consists primarily of the private exponent (d).
• d is the key to decrypting messages that were encoded using your public key.
• It’s absolutely crucial to keep d a secret. If someone gets hold of your private key, they can decrypt your messages and potentially compromise your data.

Secrecy of p, q, and λ(n):

• In addition to keeping d secret, it’s also vital to keep the prime numbers p and q secret, as well as the value λ(n).
• These numbers can be used to calculate d, and if an attacker figures out any of these values, they might be able to work out your private key.
• After d has been successfully calculated, you can even discard p, q, and λ(n). They’re no longer needed for the RSA process, as your private key (d) is all that’s required to decrypt messages.

In summary, the public key contains the modulus (n) and the public exponent (e), while the private key includes the private exponent (d). It’s imperative to safeguard d, p, q, and λ(n) from prying eyes because any of these pieces of information can be used to compromise the security of your RSA encryption. Once d is computed successfully, you can safely discard the prime numbers and λ(n), further securing your private key.

Key Distribution

The public key is made available to anyone who wishes to send encrypted messages. In contrast, the private key is closely guarded, known only to the key’s owner. This ensures that data encrypted with the public key can only be decrypted by the holder of the private key.

Let’s say David wants to send a coded message to Sophia. If they opt for RSA, David needs Sophia’s public key to encrypt the message, and only Sophia’s secret decryption key can decrypt it.

For David to send his coded messages, Sophia shares her public key (let’s call it modulus n and exponent e) with David through a secure, but not necessarily secret, channel. Sophia keeps her private key (d) strictly to herself, never revealing it to anyone.

Encryption

Let’s imagine David wants to send a secret note to Sophia using RSA encryption. David first turns the message into a number (a padded version of the message) using a reversible process called padding. Then, using Sophia’s public key (let’s call it e), David quickly computes a secret code (ciphertext, c) for the message.

The process involves some math magic, where the ciphertext (c) is calculated using the formula

c = m^e (mod n)

This may sound complex, but it’s done efficiently using modular exponentiation, even for really big numbers.

Finally, David sends this secret code (ciphertext, c) to Sophia for her to decode with her private key. This way, even if someone intercepts the message, only Sophia, with her private key, can unlock and read the original note.

Decryption

Imagine David wants to send a secret code (ciphertext, c) to Sophia using RSA encryption. Once Sophia receives this code, she can uncover the original message (m) using her private key magic.

The process involves some mathematical wizardry, where the ciphertext (c) is calculated using the formula

m = c^d mod n

This might sound like a cryptic incantation, but it ensures that only Sophia, with her special key, can reveal the original message.

Now, Sophia can reverse the padding scheme and voila! She recovers the original message (m) that David sent. It’s like a secret handshake between them, making sure only Sophia, with her private key, can understand the hidden message.

Real World Examples of RSA In Action

Now that we understand the core principles of RSA, let’s explore some practical examples of how this algorithm is applied in the real world:

1. Secure Email Communication

Imagine Alice wants to send a highly confidential email to Bob. In this scenario, Bob generates his own RSA key pair, consisting of a public key (n, e) and a private key (n, d). Bob then shares his public key with Alice. When Alice composes her email, her email client automatically encrypts the message using Bob’s public key. The magic happens when Bob receives the email and decrypts it using his private key. Only Bob, with his private key, can read the message.

2. SSL/TLS Encryption for Secure Websites

Every time you visit a secure website, such as your online bank or a popular e-commerce site, RSA is working its magic in the background. Your web browser and the website’s server engage in an RSA “handshake” to establish a secure connection. This handshake involves the exchange of RSA keys. Once the connection is established, all data transmitted between your browser and the server is encrypted using RSA, ensuring that it can only be decrypted by the server with its private key.

3. Digital Signatures for Document Verification

RSA is not limited to encryption; it’s also used for creating digital signatures, a vital component of document verification. Let’s say you want to digitally sign a PDF document to ensure its authenticity and integrity. Using your private key, you create a unique signature for the document. Others can then verify this signature using your public key, assuring them that the document has not been tampered with and is genuinely from you.

Numerical Example of RSA Algorithm

To truly grasp the inner workings of RSA, let’s walk through a step-by-step numerical example of the RSA algorithm in action.

Step 1: Key Generation

1. Choose two large and distinct prime number (for the purpose of this article we will be using small prime numbers for illustration purposes only and to make calculations easier). Let us say,

p = 37 and q = 43

2. Calculate n = pq,

n = 37*43 = 1591

3. Calculate Euler totient function φ(n) = (p − 1)(q − 1),

φ(1591) = (37 – 1)(43 – 1)

φ(1591) = 36*42 = 1512

4. Choose any number 1 < e < φ(n) that is coprime to φ(n). If we choose a prime number for e then we only need to check that e is not a divisor of φ(n).

Let e = 5

5. Calculate d, which is the modular multiplicative inverse of e(mod φ(n)), giving us

d = 605

as 1 = (5*605) mod 1512

Step 2: Public Key and Private Key

The public key is composed of (n = 1591, e = 5) and private key is composed of (n = 1591, d = 605)

Step 3: Encryption

The encryption function is defined as:

c(m) = m^e mod n

Now, let’s assume that Sophia wants to send a confidential message to David. She encrypts her message, m = 10, using David’s public key (n = 1591, e = 5)

c = 10⁵ mod 1591, which gives us

c = 1358

Step 4: Decryption

The decryption function is defined as:

m(c) = c^d mod n

David, the recipient, receives the ciphertext, c = 1358, and decrypts it using his private key (n = 1591, d = 605):

m = 1358⁶⁰⁵ mod 1591, which gives us

m = 10

In this example, David successfully decrypts Sophia’s message, which was m = 10.

This example showcases the heart of the RSA algorithm: data is encrypted using the recipient’s public key and can only be decrypted by the recipient with their private key. It is the power of this mathematical relationship that ensures secure communication in the digital world.

Conclusion

The RSA algorithm has been an instrumental part of modern cryptography, enabling secure communication, data protection, and digital signatures. Understanding the history, definition, and practical examples of RSA helps us appreciate its significance in our digital world. The example provided sheds light on the inner workings of RSA, showcasing how the algorithm encrypts and decrypts messages.

As we continue to rely on secure online transactions and communications, RSA remains a cornerstone of our digital security. In today’s interconnected world, the RSA algorithm ensures our data remains confidential, our communication is secure, and our digital signatures are reliable.

So, the next time you encounter a secure website, think about the RSA algorithm quietly working in the background, safeguarding your information and ensuring the confidentiality of your online interactions.

In conclusion, the RSA algorithm has truly stood the test of time, and its continued relevance is a testament to the ingenuity of its creators and the enduring importance of secure communication in our digital age. With RSA, our digital lives are a little safer, one encryption at a time.

References

Wikipedia: RSA (cryptosystem)