您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

RSA 算法實戰：生成 100 位大素數的 C/C++ 實現方案

編輯：程式設計綜合問答

RSA 加密需要大素數（通常 1024/2048 位，即 308/617 十進制位）。教學示例中常見「生成 100 位素數」，但標準 int/long 只能容納 10/19 位，**必須使用大整數庫**。

庫	語言	特點	獲取途徑
OpenSSL (BIGNUM)	C/C++	工業標準、高性能、支持素性測試 (Miller-Rabin)、廣泛用於生產環境	系統包管理器 `apt install libssl-dev` / `brew install openssl`
GMP (mpz_t)	C/C++	通用多精度算術、速度極快、功能全面	`apt install libgmp-dev`
Boost.Multiprecision (cpp_int)	C++	頭文件-only、標準庫風格、C++11+、適合教學/輕量項目	Boost 安裝或 `apt install libboost-all-dev`
Python (內建 int + sympy/gmpy2)	Python	原生支持任意精度整數、`sympy.randprime` 一行生成、快速原型驗證	標準庫 + `pip install sympy gmpy2`

C++ 使用 Boost.Multiprecision 生成 100 位素數示例

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <random>
#include <iostream>

using boost::multiprecision::cpp_int;
using boost::multiprecision::miller_rabin_test;

cpp_int generate_100_digit_prime() {
    std::random_device rd;
    std::mt19937_64 gen(rd());
    // 生成 100 位隨機奇數（約 332 bits）
    cpp_int candidate;
    do {
        candidate = 0;
        for (int i = 0; i < 332; ++i) { // 逐位構建隨機數
            candidate = (candidate << 1) | (gen() & 1);
        }
        candidate |= 1; // 確保為奇數
        candidate |= (cpp_int(1) << 331); // 確保最高位為1，保證位數
    } while (!miller_rabin_test(candidate, 25)); // 25 輪測試，錯誤概率 < 2^-50
    return candidate;
}

int main() {
    for (int i = 0; i < 10; ++i) {
        std::cout << "Prime " << i+1 << ": " << generate_100_digit_prime() << std::endl;
    }
    return 0;
}

關鍵提示

位數換算： 100 位十進制 ≈ 332 位二進制 (log₂10 ≈ 3.3219)。
素性測試： Miller-Rabin 概率測試是標準選擇，25 輪測試足夠安全。確定性測試 (AKS) 太慢不實用。
安全隨機源： 必須使用密碼學安全隨機數生成器 (CSPRNG)，如 /dev/urandom、CryptGenRandom、std::random_device（視實現質量而定）。
工程落地： 實際 RSA 密鑰生成請直接使用 OpenSSL RSA_generate_key_ex 或高層 EVP API，勿自行造輪子。