RSA Algorithm Explained

RSA (Rivest–Shamir–Adleman) is a widely used public-key cryptography algorithm. It is based on the mathematical properties of prime numbers and is fundamental for secure communication over the internet. RSA enables encryption of sensitive data and digital signatures, ensuring confidentiality and authenticity.

Algorithm

The RSA algorithm involves the following steps for key generation, encryption, and decryption:

1. Key Generation:

  1. Choose two distinct large prime numbers, p and q.
  2. Compute n \= p \\times q. n is called the modulus.
  3. Compute Euler's totient function \\phi\(n\) \= \(p \- 1\)\(q \- 1\).
  4. Choose an integer e such that 1 < e < \\phi\(n\) and \\gcd\(e, \\phi\(n\)\) \= 1. e is the public exponent.
  5. Compute an integer d such that \(d \\times e\) \\equiv 1 \\pmod\{\\phi\(n\)\}. d is the private exponent. This can be found using the Extended Euclidean Algorithm.
  6. The public key is \(n, e\).
  7. The private key is \(n, d\). Keep p, q, and \\phi\(n\) secret.

2. Encryption:

To encrypt a message M (where 0 \\leq M < n), the sender computes the ciphertext C as:

C \= M^e \\pmod\{n\}

3. Decryption:

To decrypt the ciphertext C, the receiver computes the original message M as:

M \= C^d \\pmod\{n\}

Mathematics

The security and correctness of RSA rely on several fundamental mathematical concepts:

  • Prime Numbers: The algorithm starts by choosing two large prime numbers. The difficulty of factoring a large number into its prime factors is the basis of RSA's security.
  • Modular Arithmetic: All calculations in RSA are performed modulo n. This means we are only concerned with the remainder after division by n. The notation a \\equiv b \\pmod\{m\} means that a and b have the same remainder when divided by m, or equivalently, m divides \(a \- b\).
  • Euler's Totient Function (\\phi\(n\)): For a positive integer n, \\phi\(n\) counts the number of positive integers less than or equal to n that are relatively prime to n (their greatest common divisor is 1). If n \= p \\times q where p and q are distinct primes, then \\phi\(n\) \= \(p \- 1\)\(q \- 1\).
  • Euler's Theorem: If \\gcd\(a, n\) \= 1, then a^\{\\phi\(n\)\} \\equiv 1 \\pmod\{n\}.
  • Modular Inverse: The private exponent d is the modular multiplicative inverse of the public exponent e modulo \\phi\(n\). This means d \\cdot e \\equiv 1 \\pmod\{\\phi\(n\)\}. The Extended Euclidean Algorithm can be used to find d.

Why Decryption Works:

We have d \\cdot e \\equiv 1 \\pmod\{\\phi\(n\)\}, which means d \\cdot e \= 1 \+ k \\cdot \\phi\(n\) for some integer k.

Then, C^d \\equiv \(M^e\)^d \\equiv M^\{ed\} \\equiv M^\{1 \+ k \\phi\(n\)\} \\equiv M \\cdot \(M^\{\\phi\(n\)\}\)^k \\pmod\{n\}.

If \\gcd\(M, n\) \= 1, by Euler's Theorem, M^\{\\phi\(n\)\} \\equiv 1 \\pmod\{n\}, so C^d \\equiv M \\cdot 1^k \\equiv M \\pmod\{n\}.

If \\gcd\(M, n\) \\neq 1, since n \= p \\times q and p, q are prime, M must be a multiple of either p or q (or both). The correctness still holds but requires a slightly more involved argument using the Chinese Remainder Theorem.

Time and Memory Complexity

  • Key Generation:
    • Finding large prime numbers typically involves probabilistic primality tests (e.g., Miller-Rabin), which have a time complexity of roughly O\(k \\log^3 n\), where n is the modulus and k is the number of iterations for the primality test.
    • Computing \\phi\(n\) is O\(1\) once p and q are known.
    • Finding the modular inverse d using the Extended Euclidean Algorithm takes O\(\\log^2 \\phi\(n\)\) or approximately O\(\\log^2 n\) time.
    • Memory complexity is dominated by storing the prime numbers and the keys, which is relatively small.
  • Encryption:
    • Modular exponentiation (M^e \\pmod\{n\}) using the square-and-multiply algorithm takes O\(\\log e \\cdot \(\\log n\)^2\) or approximately O\(\(\\log n\)^3\) time, assuming e is roughly the same size as n in the worst case (though often smaller in practice).
    • Memory complexity is dominated by the size of the message and ciphertext, which are typically of the order of \\log n bits.
  • Decryption:
    • Modular exponentiation (C^d \\pmod\{n\}) using the square-and-multiply algorithm takes O\(\\log d \\cdot \(\\log n\)^2\) or approximately O\(\(\\log n\)^3\) time, as d can be as large as \\phi\(n\).
    • Memory complexity is similar to encryption.

Easy Problems

RSA is primarily used for cryptography and is not typically applied to standard algorithmic problems on platforms like Codeforces in its full form. However, problems might involve understanding basic modular arithmetic and number theory concepts that underpin RSA.

Problem 1: Modular Exponentiation (Core Operation)

Problem Statement: Given integers base, exponent, and modulus, compute base^\{exponent\} \\pmod\{modulus\}.

Input Example:


base = 5
exponent = 11
modulus = 17

Output Example:


13 (5^11 mod 17 = 48828125 mod 17 = 13)

C++ Code:


#include <iostream>

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    long long base, exp, mod;
    std::cin >> base >> exp >> mod;
    std::cout << power(base, exp, mod) << std::endl;
    return 0;
}

Problem 2: Finding Modular Inverse (Key Step)

Problem Statement: Given two integers a and m such that \\gcd\(a, m\) \= 1, find the modular multiplicative inverse of a modulo m. That is, find an integer x such that \(a \\cdot x\) \\equiv 1 \\pmod\{m\}.

Input Example:


a = 17
m = 31

Output Example:


11 (17 * 11 mod 31 = 187 mod 31 = 1)

C++ Code (using Extended Euclidean Algorithm):


#include <iostream>

long long extendedEuclideanAlgorithm(long long a, long long b, long long &x, long long &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1;
    long long gcd = extendedEuclideanAlgorithm(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = extendedEuclideanAlgorithm(a, m, x, y);
    if (g != 1) {
        return -1; // Inverse doesn't exist
    } else {
        return (x % m + m) % m; // Ensure positive result
    }
}

int main() {
    long long a, m;
    std::cin >> a >> m;
    long long inverse = modInverse(a, m);
    std::cout << inverse << std::endl;
    return 0;
}

Intermediate Problems

Problems at this level might involve simulating simplified versions of RSA or using its underlying mathematical principles in more complex scenarios.

Problem 3: Simple RSA Encryption/Decryption

Problem Statement: Given a public key \(n, e\) and a message M, encrypt the message using RSA. Then, given the ciphertext C and a private key d, decrypt the ciphertext to recover the original message. Assume n, e, d, and M are within the range of standard integer types.

Input Example:


n = 3233
e = 17
d = 2753
M = 123

Output Example:


Ciphertext: 855
Decrypted Message: 123

C++ Code:


#include <iostream>

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    long long n = 3233;
    long long e = 17;
    long long d = 2753;
    long long m = 123;

    long long ciphertext = power(m, e, n);
    long long decrypted_message = power(ciphertext, d, n);

    std::cout << "Ciphertext: " << ciphertext << std::endl;
    std::cout << "Decrypted Message: " << decrypted_message << std::endl;

    return 0;
}

Problem 4: Cracking Small RSA

Problem Statement: You are given a small modulus n which is a product of two prime numbers p and q, and a public exponent e. You are also given a ciphertext C. Your task is to find the original message M, assuming the prime factors p and q are small enough that you can find them (e.g., by trial division or a simple factorization method). Once you have p and q, you can compute the private key d and decrypt the message.

Input Example:


n = 91 (7 * 13)
e = 5
C = 12

Output Example:


Message: 8

C++ Code (for cracking small RSA):


#include <iostream>
#include <cmath>

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

long long extendedEuclideanAlgorithm(long long a, long long b, long long &x, long long &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1;
    long long gcd = extendedEuclideanAlgorithm(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = extendedEuclideanAlgorithm(a, m, x, y);
    if (g != 1) {
        return -1;
    } else {
        return (x % m + m) % m;
    }
}

int main() {
    long long n = 91;
    long long e = 5;
    long long c = 12;

    long long p = -1, q = -1;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            p = i;
            q = n / i;
            break;
        }
    }

    if (p != -1 && q != -1) {
        long long phi_n = (p - 1) * (q - 1);
        long long d = modInverse(e, phi_n);
        if (d != -1) {
            long long message = power(c, d, n);
            std::cout << "Message: " << message << std::endl;
        } else {
            std::cout << "Could not find modular inverse." << std::endl;
        }
    } else {
        std::cout << "Could not factor n." << std::endl;
    }

    return 0;
}

Hard Problem

A truly hard problem directly solvable by the core RSA algorithm on competitive programming platforms is unlikely due to the computational intensity of breaking strong RSA encryption (which relies on factoring very large numbers). However, a hard problem might involve advanced number theory related to RSA or vulnerabilities in simplified RSA schemes.

Problem 5: Common Modulus Attack

Problem Statement: Alice sends the same message M to Bob and Charlie. Alice uses the same modulus n for both, but different public exponents e\_1 (for Bob) and e\_2 (for Charlie), such that \\gcd\(e\_1, e\_2\) \= 1. You intercept the ciphertexts C\_1 \= M^\{e\_1\} \\pmod\{n\} and C\_2 \= M^\{e\_2\} \\pmod\{n\}. Your task is to recover the original message M.

Input Example:


n = 3233
e1 = 17
e2 = 23
c1 = 855
c2 = 2278

Output Example:


Message: 123

C++ Code (for Common Modulus Attack):


#include <iostream>
#include <cmath>
#include <vector>
#include <numeric>

long long extendedEuclideanAlgorithm(long long a, long long b, long long &x, long long &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1;
    long long gcd = extendedEuclideanAlgorithm(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp >0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

long long commonModulusAttack(long long n, long long e1, long long c1, long long e2, long long c2) {
    long long s1, s2;
    long long gcd = extendedEuclideanAlgorithm(e1, e2, s1, s2);

    if (gcd != 1) {
        return -1; // Attack not directly applicable
    }

    long long m1 = power(c1, (s1 % (e2 * -1) + (e2 * -1)) % (e2 * -1), n);
    long long m2 = power(c2, (s2 % (e1 * -1) + (e1 * -1)) % (e1 * -1), n);

    long long m = (m1 * m2) % n;
    return m;
}

int main() {
    long long n = 3233;
    long long e1 = 17;
    long long e2 = 23;
    long long c1 = 855;
    long long c2 = 2278;

    long long message = commonModulusAttack(n, e1, c1, e2, c2);

    if (message != -1) {
        std::cout << "Message: " << message << std::endl;
    } else {
        std::cout << "Attack failed or not applicable." << std::endl;
    }

    return 0;
}