RSA 算法原理與大數運算庫 C 語言實現全解析

編輯：關於C語言

大數運算基礎：為什麼需要自定義大數庫？

RSA 依賴 512~4096 位大整數運算，遠超編譯器原生類型（32/64 位）。三種實現路線：

方案	原理	優缺點
十進制字符串模擬豎式	字符數組存十進制，逐位運算	易理解，效率極低（基數小，循環多）
二進制流邏輯操作	位移、邏輯運算模擬加減乘除	代碼複雜、可讀性差、調試難
N 進制數組（推薦）	基數 2^16 或 2^32，數組元素存一「位」	循環少、利用硬件乘法、邏輯清晰

本文採用 基數 2^16 (65536)，元素類型 unsigned short。乘除時擴展為 unsigned long（32 位）計算，避免溢出，兼顧速度與可讀性。1024 位大數 = 64 個 unsigned short。

大數核心運算實現要點

比較：先比符號，再比位數，最後從高位向低位逐位比較。
加減：低位向高位，處理進位/借位。
乘法：模擬豎式乘法，雙重循環，結果低位對齊累加，處理進位。利用 32 位暫存中間積。
除法/取模：高位向低位試商（Knuth Algorithm D），需估算商、修正、借位。
擴展歐幾里得 (exgcd)：求模逆 d ≡ e⁻¹ mod φ(n)，遞歸實現 ax + by = gcd(a,b)。
蒙哥馬利模冪 (ModExp)：c = m^e mod n 核心。掃描指數位，平方乘模，配合蒙哥馬利約減避免大數除法。
最大公約數 (GCD)：輾轉相除法。

RSA 關鍵流程與 API 設計

1. 密鑰生成


// 產生大素數 p, q (Rabin-Miller 測試 + 小素數篩選)
n = p * q;
φ = (p-1)*(q-1);
選擇 e (常用 65537)，gcd(e, φ)=1;
d = exgcd(e, φ) 模 φ;  // d*e ≡ 1 (mod φ)
公鑰 (n, e)，私鑰 (n, d) 或 (p, q, d, dp, dq, qinv) 用於 CRT 加速

2. 加密/解密 (PKCS#1 v1.5 填充)

分塊處理：塊大小 < k 位 (k = n 的位數/8)。填充格式 00 02 [PS] 00 [Data]。
加密：c = m^e mod n (公鑰操作)。
解密：m = c^d mod n (私鑰操作)，可用 CRT (中國剩餘定理) 4 倍加速。

核心 API 簽名示例


// 大數結構
typedef struct { short len; unsigned short d[MAX_DIGITS]; int sign; } BigInt;

// 關鍵函數
char GenKey(BigInt *n, BigInt *e, BigInt *d);
char EncRSA(const unsigned char *in, int inlen, BigInt *e, BigInt *n,
            unsigned char *out, int *outlen, int keytype);
char DecRSA(const unsigned char *in, int inlen, BigInt *d, BigInt *n,
            unsigned char *out, int *outlen, int keytype);

// 輔助
char IsNotPrime(BigInt *p);           // 小素數篩選
char RabinMillerTest(BigInt *p, int t); // 概率素性測試
char GenPrime(BigInt *p);             // 產生大素數
char Str2BigInt(BigInt *a, char *str, int base); // 字符串↔大數
char BigInt2Str(char *str, BigInt *a, int base);

工程化關鍵點

常數時間實現：防止旁路攻擊（時序、功耗、緩存），關鍵路徑（模冪、比較）必須常數時間。
安全隨機數：密鑰生成、填充隨機數必須用 CSPRNG (/dev/urandom, getrandom, BCryptGenRandom)。
填充驗證：解密後嚴格驗證 PKCS#1 結構，防止 Bleichenbacher 攻擊。
內存保護：敏感數據（私鑰、中間值）用後立即清零 (explicit_bzero)，防止內存轉儲洩露。
不要自寫加密庫：生產環境必須使用 OpenSSL (EVP API)、mbedTLS、libsodium 等經過審計的庫。