Introduction

In today's digital world, the security of our online communications is paramount. Whether you're shopping online, sending an email, or accessing your bank account, encryption ensures that your data remains private and secure. One of the most widely used encryption techniques is RSA (Rivest-Shamir-Adleman). Developed in 1977, RSA is a public-key cryptosystem that relies on the mathematical properties of prime numbers to secure data. In this three-part series, we'll explore the RSA process in detail, using simple prime numbers to illustrate how it works.

What is RSA?

RSA is named after its inventors, Ron Rivest, Adi Shamir, and Leonard Adleman. It is a type of asymmetric encryption, meaning it uses two different keys for encryption and decryption. These keys are:

• Public Key: Used to encrypt the data. This key can be shared openly.

• Private Key: Used to decrypt the data. This key is kept secret by the owner.

The security of RSA is based on the difficulty of factoring large numbers into their prime factors. Let's dive into the process of generating RSA keys and see how encryption and decryption work.

The RSA Process: Generating Keys and Ensuring Security

Step 1: Choose Two Prime Numbers

The first step in RSA is selecting two distinct prime numbers, 𝑝 and 𝑞. These primes should be kept secret.

For our example, let's choose:

• 𝑝=17

• 𝑞=23

Step 2: Compute 𝑛

Next, we compute 𝑛, the product of 𝑝 and 𝑞:

n= p × q
𝑛= 17 × 23
𝑛= 391

Step 3: Compute the Totient Function 𝜙(𝑛)

The totient function, 𝜙(𝑛), is calculated as:

ϕ(n)= (p−1) × (q−1)
ϕ(n)= (17−1) × (23−1)
ϕ(n)= 16 × 22
ϕ(n)= 352

Step 4: Choose an Integer 𝑒

We select an integer 𝑒 such that 1<𝑒<𝜙(𝑛) and gcd⁡(𝑒,𝜙(𝑛))=1. A common choice is 𝑒=3: gcd⁡(3,352)=1

Step 5: Compute 𝑑

The final step is determining 𝑑d, the modular multiplicative inverse of 𝑒e modulo 𝜙(𝑛):

d × e = 1 (mod ϕ(n))
# Using the Extended Euclidean Algorithm, we find:
d=235

RSA Keys Summary:

Public Key: (e,n)=(3,391)
Private Key: (d,n)=(235,391)

With the keys generated, we're ready to see RSA in action with an example of encryption and decryption.

Example in Action - Encrypting a Message

Let's encrypt a message 𝑀=42 using the public key (3,391).

Step 1: Encryption

The encryption formula is: 𝐶=𝑀^𝑒 (mod 𝑛)
For 𝑀=42:

𝐶=42^3 (mod 391)
𝐶=74088 (mod 391)
𝐶=74

Our encrypted message (ciphertext) is 𝐶=74

Step 2: Decryption

Now, let's decrypt the ciphertext 𝐶=74 using the private key (235,391).
The decryption formula is 𝑀=𝐶^𝑑 (mod 𝑛)
For 𝐶=74:

𝑀=74^235 (mod 391)
M=42

By calculating, we retrieve the original message: 𝑀=42

Conclusion

We've explored the RSA encryption and decryption process. From generating keys using prime numbers to encrypting and decrypting messages, RSA plays a crucial role in securing our digital communications. Understanding this process helps us appreciate the complexities and importance of modern encryption methods in protecting our data. Whether you're a student, a professional, or just a curious learner, grasping the basics of RSA provides valuable insight into the world of cryptography.