RSA 作為非對稱加密基石，其安全性建立在大整數分解困難性之上。工程實現的核心挑戰在於大數（512~4096 位）的高效算術運算。本文系統闡述大數表示策略、核心運算實現、RSA 密鑰生成/加解密流程及關鍵輔助算法。
將大數視為 N 進制數組，每個元素為一個「數位」。
| 基數 N | 元素類型 | 1024 位數組長度 | 優點 | 缺點 |
|---|---|---|---|---|
| 232 (0x100000000) | uint32_t | 32 | 數組最短，循環少 | 乘法中間積溢出 64 位，需手動擴展 |
| 216 (0x10000) | uint16_t | 64 | 乘法擴展到 uint32_t 自然無溢出，調試易讀 | 數組較長，循環開銷大 |
| 104 (10000) | uint16_t | ~78 | 十進制直觀，輸出方便 | 非 2 的冪次，位運算不便 |
工程推薦：基數 216 (65536)，元素類型 uint16_t，乘除時臨時擴展為 uint32_t，平衡了性能、簡潔性與可移植性。
cmp(a, b)從最高位向低位比較，首個差異位決定大小。符號單獨處理。
add(a, b) / 減法 sub(a, b)低位向高位逐位運算，維護 進位/借位 標誌。時間復雜度 O(n)。
mul(a, b)模擬豎式乘法：外層遍歷乘數位，內層遍歷被乘數位，結果位索引 = i + j，累加中間積並處理進位。O(n²)。優化方向：Karatsuba (O(n1.585))、FFT 乘法 (O(n log n))，但 1024 位內 O(n²) 足夠快。
div(a, b) / 取模 mod(a, b)高位向低位試商（長除法）。關鍵是試商估算：用被除數高 2 位 / 除數高 1 位估算商位，再修正。最耗時操作，RSA 中主要用於模運算。
modexp(a, e, n) —— Montgomery 模乘 / 滑動窗口RSA 核心運算 c = me mod n。
二進制平方-乘法：掃描指數位，平方後條件乘法。
Montgomery 模乘：將模除轉換為模加與移位，避免昂貴除法，需預計算 R = 2k mod n。
滑動窗口：預計算 a1..a2w-1，掃描指數時跳過 0 位，減少乘法次數。
exgcd(a, b) —— 求模逆求 d 使 e*d ≡ 1 (mod φ(n))。遞歸實現：
exgcd(a, b) → (g, x, y) s.t. a*x + b*y = g = gcd(a,b)
模逆存在當 g=1，則 x mod b 即為逆元。
gcd(a, b)輾轉相除法，O(log min(a,b))。生成密鑰時驗證 gcd(e, φ(n)) = 1。
k 輪錯誤率 4-k。1024 位素數建議 k ≥ 40。
// 大數結構
typedef struct { uint16_t* digits; int len; int sign; } BigInt;
// 密鑰生成
int GenerateKey(BigInt* n, BigInt* e, BigInt* d); // 產生 p,q → n=pq, 選 e, 算 d≡e⁻¹ mod φ(n)
// 加密：分塊處理，填充 PKCS#1 v1.5 / OAEP
int Encrypt(byte* in, int inLen, BigInt* e, BigInt* n, byte* out, int* outLen, int keyType);
// 解密：同分塊，去填充
int Decrypt(byte* in, int inLen, BigInt* d, BigInt* n, byte* out, int* outLen, int keyType);
// 輔助
int StrToBigInt(BigInt*, char* str, int base); // 10/16 進制字符串互轉
int BigIntToStr(char*, BigInt*, int base);
ceil(inLen/(k-11)) * k；解密輸出 ≤ inLen * k/(k-11)。/dev/urandom, CryptGenRandom, getrandom()）。memset_s/ExplicitZero 清零。RSA 實現的本質是大數模指數運算的高效、安全工程化。從基數選擇、基礎算術、模乘優化、素性測試到填充方案、側信道防禦，每一環都關係最終性能與安全。現代項目強烈建議使用經驗證的庫（OpenSSL、BoringSSL、Libsodium、mbedTLS），而非自行造輪子；但理解其內部機理，對於協議分析、性能調優、漏洞評估不可或缺。
