Cài đặt thuật toán RSA trong C++

RSA (Rivest-Shamir-Adleman, 1977) là thuật toán mật mã khóa công khai (asymmetric) phổ biến nhất. Dựa trên độ khó của bài toán phân tích thừa số nguyên lớn.

Quy trình toán học

1. Chọn 2 số nguyên tố lớn p, q.
2. Tính n = p * q (modulus).
3. Tính φ(n) = (p-1)(q-1) (Euler's totient).
4. Chọn e (public exponent): 1 < e < φ(n) và gcd(e, φ(n)) = 1. Thường dùng e = 65537.
5. Tính d (private exponent): d ≡ e⁻¹ (mod φ(n)) — nghịch đảo modulo.
6. Khóa công khai: (n, e). Khóa riêng: (n, d).
7. Mã hóa: c = m^e mod n.
8. Giải mã: m = c^d mod n.

Chương trình minh họa (số nhỏ, dùng double - CHỈ DẠY)

#include <iostream>
#include <cmath>

using namespace std;

// GCD đệ quy
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Lũy thừa modulo nhanh (binary exponentiation)
long long modPow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

// Nghịch đảo modulo bằng Extended Euclid
long long modInverse(long long a, long long m) {
    long long m0 = m, x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1) {
        long long q = a / m;
        long long t = m;
        m = a % m; a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}

int main() {
    // ⚠️ CHỈ DÙNG SỐ NHỎ DEMO — THỰC TẾ p,q 1024-2048 BIT
    long long p = 61, q = 53;           // Số nguyên tố
    long long n = p * q;                // 3233
    long long phi = (p-1) * (q-1);      // 3120
    
    long long e = 17;                   // Public exponent (gcd(17,3120)=1)
    long long d = modInverse(e, phi);   // Private exponent = 2753
    
    cout << "p = " << p << ", q = " << q << '\n';
    cout << "n = " << n << ", phi = " << phi << '\n';
    cout << "Public key:  (n=" << n << ", e=" << e << ")\n";
    cout << "Private key: (n=" << n << ", d=" << d << ")\n";
    
    long long message = 123; // Bản rõ (số nguyên < n)
    cout << "\nBan ro (m): " << message << '\n';
    
    long long cipher = modPow(message, e, n);
    cout << "Ban ma (c = m^e mod n): " << cipher << '\n';
    
    long long decrypted = modPow(cipher, d, n);
    cout << "Giai ma (m = c^d mod n): " << decrypted << '\n';
    
    // Ký số (Digital Signature)
    long long signature = modPow(message, d, n);
    cout << "\nChu ky so (sign = m^d mod n): " << signature << '\n';
    long long verified = modPow(signature, e, n);
    cout << "Xac thuc (verify = sign^e mod n): " << verified 
         << (verified == message ? " [HOP LE]" : " [SAI]") << '\n';
    
    return 0;
}

Kết quả

p = 61, q = 53
n = 3233, phi = 3120
Public key:  (n=3233, e=17)
Private key: (n=3233, d=2753)

Ban ro (m): 123
Ban ma (c = m^e mod n): 855
Giai ma (m = c^d mod n): 123

Chu ky so (sign = m^d mod n): 123
Xac thuc (verify = sign^e mod n): 123 [HOP LE]

⚠️ Cảnh báo quan trọng

• Code trên chỉ để minh họa toán học — dùng long long và số nhỏ.
• RSA thực tế yêu cầu:
  • Số nguyên tố p, q 1024-2048 bit (khoảng 300-600 chữ số thập phân).
  • Thư viện bignum: OpenSSL (BIGNUM), GMP, Botan, Crypto++.
  • Padding: OAEP (mã hóa), PSS (ký số) — không bao giờ dùng raw RSA (textbook RSA không an toàn).
  • Bảo vệ side-channel (timing attack, power analysis).
• Không tự triển khai crypto cho production — dùng thư viện đã được kiểm chứng (OpenSSL, libsodium, NaCl).

Ứng dụng thực tế

• TLS/HTTPS (trao đổi khóa, chứng chỉ số).
• Chữ ký số (PGP, S/MIME, blockchain).
• Mã hóa email, file, VPN.

RSA là nền tảng của PKI (Public Key Infrastructure) và an ninh mạng hiện đại. Hiểu toán học cốt lõi giúp sử dụng đúng và an toàn các thư viện crypto.