RSA

ALGORITHM

By: Mo’men Tamer

ID: 241100
1. Introduction

The RSA (Rivest-Shamir-Adleman) algorithm stands as one of the most significant

cryptographic innovations in modern computing history, forming the backbone of secure
communications across the digital landscape. Named after its inventors Ron Rivest, Adi
Shamir, and Leonard Adleman who introduced it in 1977, RSA represents a landmark
achievement in the field of asymmetric cryptography.

1.1 Historical Context

Before RSA, cryptographic systems primarily relied on symmetric key algorithms, where the
same key was used for both encryption and decryption. This created a "key distribution
problem”, how could parties securely exchange the encryption key before establishing a
secure channel? RSA solved this paradox by introducing a system with mathematically
related yet distinct keys for encryption and decryption.

1.2 Significance in Modern Cryptography

RSA's elegant mathematical solution leverages the computational difficulty of factoring large
composite numbers into their prime components. This creates a system where:

 Encryption and decryption keys are mathematically related

 Deriving the private key from the public key is computationally infeasible
 Information can be securely transferred

This revolutionary approach to cryptography enabled secure digital signatures and

encrypted communications that form the foundation of today's digital security system.

2. Theoretical Foundation
The security and functionality of RSA depend on several fundamental mathematical
concepts that work together to create a solid cryptographic system.

2.1 Mathematical Basis

RSA's security depends on these essential mathematical concepts:

2.1.1 Prime Numbers

Numbers divided only by 1 and themselves (as: 2, 3, 5, 7, 11, etc.). The security of RSA
depends on the selection of two very large prime numbers.

2.1.2 Modular Arithmetic

A system of arithmetic for integers where numbers "wrap around" after reaching a certain
value (the modulus).

2
Example: In clock (modulo 12), 14:00 is represented as 2:00 (14 mod 12 = 2).
For RSA, if we work modulo n, then for any integers a and b:
 a + b (mod n) = [a (mod n) + b (mod n)] mod n
 a × b (mod n) = [a (mod n) × b (mod n)] mod n

2.1.3 Coprime Numbers

Two integers are coprime when their greatest common divisor (gcd) is 1.
For example, 8 and 15 are coprime because gcd(8, 15) = 1.

2.1.4 Euler's Totient Function φ(n)

This function counts the positive integers up to n that are coprime to n.
If p is a prime number, then: φ(p) = p - 1
If p and q are prime numbers, then: φ(p × q) = (p - 1) × (q - 1)

This function is critical for key generation in RSA.

2.1.5 Fermat's Little Theorem

For any prime p and any integer a not divisible by p:
a^(p-1) ≡ 1 (mod p)

2.1.6 Euler's Theorem (Generalization of Fermat's Little Theorem)

For any two coprime integers a and n:
a^φ(n) ≡ a^(n-1) ≡ 1 (mod n)

This theorem provides the theoretical foundation for RSA's operation.

2.2 Core Mathematical Principles

The security of RSA relies on four key mathematical principles:

2.2.1 Prime Multiplication vs. Factorization Asymmetry

While multiplying two large prime numbers is computationally simple O(n²) (because it
comes from two nested loops, each running n times), factoring the resulting product back
into its prime components is exponentially more difficult.

2.2.2 Modular Exponentiation

Computing values of the form ab (mod n), while potentially involving very large exponents,
can be performed efficiently using the square-and-multiply algorithm as O(log b) (because
it’s efficient, as it divides by 2 at each step).

2.2.3 Key Generation Security

The private key is mathematically related to the public key through Euler's totient function.
However, calculating the totient function for a large composite number requires knowing its
prime factorization.

3
2.2.4 Modular Inverse Properties
The relationship between the public exponent e and private exponent d is that they are
modular inverses of each other with respect to φ(n):
e × d ≡ 1 (mod φ(n))

Finding d through a given e is simple if φ(n) is known, but computing φ(n) requires knowing
the prime factorization of n.

3. The RSA Algorithm

The RSA algorithm consists of three main phases: key generation, encryption, and
decryption. Each phase relies on specific mathematical operations.

3.1 Key Generation

The key generation process is the foundation of RSA security and follows these steps:

1. Select two distinct large prime numbers: p and q

 These should be chosen randomly and be of similar bit-length

2. Compute the modulus: n = p × q

 This will be part of both the public and private keys
 The bit-length of n is the key length (typically 2048-4096 bits for modern
applications)

3. Compute Euler's totient function: φ(n) = (p - 1)(q - 1)

 This represents the count of numbers less than n that are coprime to n
 This value must be kept secret as it allows deriving the private key

4. Choose the public exponent: e

 Must satisfy: 1 < e < φ(n)
 Must be coprime to φ(n), where gcd(e, φ(n)) = 1
 The most used public exponent in RSA is 65537 (2¹⁶ + 1), which is prime and
has efficient binary representation

5. Compute the private exponent: d

 d is the modular multiplicative inverse of e modulo φ(n)
 d satisfies the congruence relation: e × d ≡ 1 (mod φ(n))

6. Public key: (n, e)

 Distributed publicly for encryption and signature verification

7. Private key: (n, d)

 Must be kept secret
 Used for decryption and signature generation

4
3.2 Encryption
To encrypt a message M using the public key (n, e):

1. Ensure the message is represented as an integer M, where 0 ≤ M < n

 Messages exceeding this size must be broken into smaller blocks
 Typically involves conversion from characters to numeric representation

2. Compute the ciphertext C:

 C = Me mod n

Using the square-and-multiply algorithm, this can be computed efficiently even with large
values of e.

3.3 Decryption
To decrypt a ciphertext C using the private key (n, d):

1. Compute the original message M:

 M = Cd mod n

3.4 Mathematical Correctness Proof

RSA's correctness follows from Euler's theorem. For message M and encryption/decryption
operations:

 C = Me mod n
 M = Cd mod n = (Me)d mod n = Me × d mod n

Since e × d ≡ 1 (mod φ(n)), we have:

 e × d = (k × φ(n) + 1) for some integer k

Therefore:
 Me × d mod n = M(k × φ(n) + 1) mod n = (Mφ(n)) k × M mod n

By Euler's theorem, if gcd(M, n) = 1:

 Mφ(n) ≡ 1 (mod n)

Therefore:
 M(e × d) mod n = 1k × M mod n = M mod n

This proves that encryption followed by decryption yields the original message.

4. Detailed Example of RSA Encryption and Decryption

5
Let's work through a comprehensive example to illustrate RSA in action:

4.1 Key Generation Example

1. Select two prime numbers:
 p = 61 and q = 53

2. Compute the modulus:

 n = p × q = 61 × 53 = 3233

3. Calculate Euler's totient function:

 φ(n) = (p - 1)(q - 1) = 60 × 52 = 3120

4. Select the public exponent:

 e = 17 (chosen because gcd(17, 3120) = 1)

5. Compute the private exponent:

 We need d where: 17 × d ≡ 1 (mod 3120)
But 1 is not divisible by 17
So, add 3120 for n times to 1 to be divisible by 17
Then, (1 + 3120n) mod 17 = (1 + 9n) mod 17

 Substituting by n:
n = 1: (1 + 1 × 9) mod 17 = 10
n = 2: (1 + 2 × 9) mod 17 = 2
n = 3: (1 + 3 × 9) mod 17 = 11
...and so on, till:
n = 15: (1 + 15 × 9) mod 17 = 0

 Add 3120 for 15 times to 1 to be divisible by 17:

17 × d = 1 + (3120 × 15) mod 3120
17 × d = 46,800 (mod 3120)

 So, d = 2753 (mod 3120)

 Verification: (17 × 2753) mod 3120 = 46801 (mod 3120) = 1 ✓

6. Public key: (n, e) = (3233, 17)

7. Private key: (n, d) = (3233, 2753)

4.2 Encryption Example

6
Let's encrypt the message M = 65:

C = Me mod n = 6517 mod 3233

Using Modular Exponential:

Step 1: 651 = 65 (mod 3233) = 65

Step 2: 652 = 65 × 65 (mod 3233) = 992
Step 3: 653 = 652 × 65 (mod 3233) = 3053
Step 4: 654 = 653 × 65 (mod 3233) = 1232
Step 5: 655 = 654 × 65 (mod 3233) = 2488
and so on… till:
Step 17: 6517 = 6516 × 65 (mod 3233) = 2790

So, C = 2790

4.3 Decryption Example

1. To decrypt C = 2790 using the private key d = 2753:

 M = Cd mod n = 27902753 mod 3233

2. Using Modular Exponential as before:

 M = 65

Which is our original message! The encryption and decryption process are verified.

5. Security Considerations

5.1 Key Size Recommendations

The security of RSA is directly linked to key size. Current recommendations include:

Security level RSA Key Size Recommended Until

112-bit 2048-bit 2030
128-bit 3072-bit 2040
192-bit 7680-bit Post-2040

5.2 Prime Number Generation

7
Secure prime generation is critical, so there should be:

 True Randomness: Use cryptographically secure random number generators

 Prime Testing: Employ probabilistic primality tests like Miller-Rabin
 Size Balance: Primes should be similar in size but not too close

5.3 Common Attack Vectors

1. Factorization Attacks: Attempts to factor the modulus n into its prime components p
and q
2. Side-Channel Attacks: Extracting key information through timing or power analysis
3. Implementation Vulnerabilities: Issues in padding schemes or key handling

5.4 Secure Padding Schemes

Raw RSA is vulnerable to various attacks. Modern implementations use padding schemes:

1. PKCS#1 v1.5: Older standard still in use

2. PKCS#1 v2.1 (OAEP): Optimal Asymmetric Encryption Padding for better security

6. Common Applications for RSA

RSA serves as a cornerstone for many cryptographic applications:

6.1 Secure Web Communications

 SSL/TLS for HTTPS
 Email encryption (PGP, S/MIME)

6.2 Digital Signatures

 Authentication mechanisms
 Non-repudiation
 Code signing

6.3 Hybrid Cryptosystems

RSA is typically used in hybrid systems:
 RSA for key exchange
 Symmetric encryption (like AES) for bulk data

7. Simplified C++ Implementation

Below is a basic C++ implementation for educational purposes:

#include <iostream>
#include <cmath>
#include <random>

8
// Check if a number is prime (simplified)
bool isPrime(unsigned long long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0) return false;

for (unsigned long long i = 3; i <= sqrt(n); i += 2) {

if (n % i == 0) return false;
}
return true;
}

// Find greatest common divisor

unsigned long long gcd(unsigned long long a, unsigned long
long b) {
while (b != 0) {
unsigned long long temp = b;
b = a % b;
a = temp;
}
return a;
}

// Extended Euclidean Algorithm for finding modular inverse

long long modInverse(long long a, long long m) {
long long m0 = m;
long long y = 0, x = 1;

if (m == 1) return 0;

while (a > 1) {
long long q = a / m;
long long t = m;

m = a % m;
a = t;
t = y;

y = x - q * y;
x = t;
}

if (x < 0) x += m0;

return x;
}

// Modular exponentiation
unsigned long long modPow(unsigned long long base, unsigned
long long exponent, unsigned long long modulus) {

9
 if (modulus == 1) return 0;

unsigned long long result = 1;

base = base % modulus;

while (exponent > 0) {

if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
exponent >>= 1;
base = (base * base) % modulus;
}

return result;
}

class RSA {
private:
unsigned long long p, q;
unsigned long long n;
unsigned long long phi;
unsigned long long e;
unsigned long long d;

public:
// Constructor with specified primes (for testing)
RSA(unsigned long long prime1, unsigned long long prime2)
{
if (!isPrime(prime1) || !isPrime(prime2)) {
throw std::invalid_argument("Both inputs must be
prime numbers");
}

p = prime1;
q = prime2;
n = p * q;
phi = (p - 1) * (q - 1);

// Choose e (common value is 65537)

e = 65537;

// If e isn't suitable, find another one

if (e >= phi || gcd(e, phi) != 1) {
e = 3;
while (e < phi) {
if (gcd(e, phi) == 1)
break;
e += 2;
}
}

10
 // Calculate private exponent
d = modInverse(e, phi);
}

std::pair<unsigned long long, unsigned long long>

getPublicKey() const {
return {n, e};
}

std::pair<unsigned long long, unsigned long long>

getPrivateKey() const {
return {n, d}; // Note: In production, private key
should never be exposed
}

// RSA encryption
unsigned long long encrypt(unsigned long long message)
const {
if (message >= n) {
throw std::invalid_argument("Message too large for
this key");
}
return modPow(message, e, n);
}

// RSA decryption
unsigned long long decrypt(unsigned long long ciphertext)
const {
if (ciphertext >= n) {
throw std::invalid_argument("Ciphertext invalid");
}
return modPow(ciphertext, d, n);
}
};

int main() {
try {
// Create RSA instance with example primes
RSA rsa(61, 53);

// Get the public and private keys

auto [n, e] = [Link]();
auto [_, d] = [Link]();

std::cout << "Public key (n,e): (" << n << "," << e <<
")" << std::endl;
std::cout << "Private key (n,d): (" << n << "," << d
<< ")" << std::endl;

// Message to encrypt
unsigned long long message = 65;

11
 std::cout << "Original message: " << message <<
std::endl;

// Encrypt the message

unsigned long long ciphertext = [Link](message);
std::cout << "Encrypted message: " << ciphertext <<
std::endl;

// Decrypt the ciphertext

unsigned long long decrypted =
[Link](ciphertext);
std::cout << "Decrypted message: " << decrypted <<
std::endl;

} catch (const std::exception& e) {

std::cerr << "Error: " << [Link]() << std::endl;
}

return 0;
}

8. Conclusion

RSA remains a foundational algorithm in modern cryptography despite being over four
decades old. Its elegant mathematical structure based on the computational difficulty of
prime factorization continues to provide security for countless applications worldwide.
While newer cryptographic approaches offer advantages in certain contexts, RSA's proven
track record and widespread implementation ensure its continued relevance in securing
digital communications.

Understanding RSA provides insight into not only a specific cryptographic algorithm but also
the broader principles that reinforce secure communication in an untrusted environment.
The core concepts of asymmetric cryptography pioneered by RSA continue to influence the
development of new cryptographic systems and security protocols.

12