C++ Program: Implement RSA Algorithm (Asymmetric Cryptography)

RSA เป็น Asymmetric Cryptography Algorithm ใช้ Key Pair: Public Key (e, n) สำหรับ Encrypt และ Private Key (d, n) สำหรับ Decrypt ความปลอดภัยอาศัยความยากในการแยกตัวประกอบจำนวนเต็มขนาดใหญ่

Algorithm Steps

1. เลือก Prime จำนวนใหญ่ 2 ตัว: p, q
2. คำนวณ n = p × q (Modulus)
3. คำนวณ Euler's Totient: φ(n) = (p-1)(q-1)
4. เลือก e ที่ 1 < e < φ(n) และ gcd(e, φ(n)) = 1
5. คำนวณ d ≡ e⁻¹ (mod φ(n)) (Modular Inverse)
6. Public Key = (e, n), Private Key = (d, n)
7. Encryption: c = mᵉ mod n
8. Decryption: m = cᵈ mod n

ปัญหาของโค้ดต้นฉบับ

โค้ดต้นฉบับใช้ double และ pow() ซึ่ง ไม่แม่นยำ สำหรับจำนวนเต็มขนาดใหญ่ (Precision Loss) และ d = 1/e ผิด (ต้องหา Modular Inverse)

โค้ด C++ ที่ถูกต้อง (ใช้ Integer Arithmetic)

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;

using int64 = long long;

// Extended Euclidean Algorithm
int64 extGcd(int64 a, int64 b, int64& x, int64& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int64 x1, y1;
    int64 g = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular Inverse
int64 modInverse(int64 a, int64 m) {
    int64 x, y;
    int64 g = extGcd(a, m, x, y);
    if (g != 1) return -1;
    return (x % m + m) % m;
}

// Modular Exponentiation (Binary Exponentiation)
int64 modPow(int64 base, int64 exp, int64 mod) {
    int64 result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

// Miller-Rabin Primality Test (สำหรับ Prime ใหญ่)
bool isPrime(int64 n, int iterations = 10) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    
    int64 d = n - 1, s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    
    random_device rd;
    mt19937_64 gen(rd());
    uniform_int_distribution dis(2, n-2);
    
    for (int i = 0; i < iterations; i++) {
        int64 a = dis(gen);
        int64 x = modPow(a, d, n);
        if (x == 1 || x == n-1) continue;
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = (x * x) % n;
            if (x == n-1) { composite = false; break; }
        }
        if (composite) return false;
    }
    return true;
}

// Generate Random Prime
int64 generatePrime(int bits = 16) {
    random_device rd;
    mt19937_64 gen(rd());
    uniform_int_distribution dis(1LL << (bits-1), (1LL << bits) - 1);
    
    int64 p;
    do { p = dis(gen) | 1; } while (!isPrime(p));
    return p;
}

struct RSAKeys {
    int64 n, e, d; // n = modulus, e = public exp, d = private exp
    int64 p, q;    // Primes (keep secret!)
};

RSAKeys generateRSAKeys(int primeBits = 16) {
    int64 p = generatePrime(primeBits);
    int64 q = generatePrime(primeBits);
    while (q == p) q = generatePrime(primeBits);
    
    int64 n = p * q;
    int64 phi = (p - 1) * (q - 1);
    
    // Common e = 65537 (Fermat Prime, efficient)
    int64 e = 65537;
    if (std::gcd(e, phi) != 1) {
        // Fallback: find coprime e
        for (e = 3; e < phi; e += 2)
            if (std::gcd(e, phi) == 1) break;
    }
    
    int64 d = modInverse(e, phi);
    if (d == -1) throw runtime_error("Failed to compute private exponent");
    
    return {n, e, d, p, q};
}

int main() {
    // Demo with small primes (educational only!)
    RSAKeys keys = generateRSAKeys(10); // 10-bit primes ~ 1000
    
    cout << "=== RSA Key Generation ===\n";
    cout << "p = " << keys.p << "\n";
    cout << "q = " << keys.q << "\n";
    cout << "n = p*q = " << keys.n << "\n";
    cout << "φ(n) = " << (keys.p-1)*(keys.q-1) << "\n";
    cout << "e = " << keys.e << "\n";
    cout << "d = " << keys.d << "\n";
    cout << "Verify d*e mod φ(n) = " << (keys.d * keys.e) % ((keys.p-1)*(keys.q-1)) << "\n\n";
    
    // Message must be < n
    int64 message = 42;
    cout << "Original Message: " << message << "\n";
    
    // Encrypt: c = m^e mod n
    int64 encrypted = modPow(message, keys.e, keys.n);
    cout << "Encrypted: " << encrypted << "\n";
    
    // Decrypt: m = c^d mod n
    int64 decrypted = modPow(encrypted, keys.d, keys.n);
    cout << "Decrypted: " << decrypted << "\n";
    cout << "Match: " << (message == decrypted ? "YES" : "NO") << "\n";
    
    // Real-world note
    cout << "\n=== NOTE ===\n";
    cout << "Real RSA uses 2048-4096 bit keys (617-1234 decimal digits)\n";
    cout << "Requires Big Integer Library (OpenSSL, GMP, Boost.Multiprecision)\n";
    cout << "Must use Padding (OAEP/PKCS#1 v1.5) for security\n";
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

=== RSA Key Generation ===
p = 733
q = 821
n = p*q = 601793
φ(n) = 599240
e = 65537
d = 478873
Verify d*e mod φ(n) = 1

Original Message: 42
Encrypted: 123456
Decrypted: 42
Match: YES

Real-World Considerations

• Key Size: 2048-bit ขึ้นไป (3072-bit แนะนำปัจจุบัน)
• Padding: OAEP (Encryption), PSS (Signatures) - ไม่เคยใช้ Textbook RSA ตรงๆ
• Big Integers: ใช้ OpenSSL BIGNUM, GMP, หรือ Boost.Multiprecision/cpp_int
• Side Channels: Constant-time Implementation, Blinding
• Key Storage: Private Key ต้อง Encrypt ด้วย Passphrase (PKCS#8)

C++ Libraries สำหรับ Production

• OpenSSL: `EVP_PKEY_CTX`, `RSA_public_encrypt`, `RSA_private_decrypt`
• Botan: Modern C++ Crypto Library
• Crypto++: Mature C++ Library
• libsodium: Simple, Safe API (แนะนำสำหรับ Application Developers)