从数学原理到可视化实现：C#手搓RSA加密算法全解析

1. 项目概述为什么我们要“手搓”RSA在信息安全领域RSA加密算法就像一座基石从HTTPS协议到数字签名无处不在。很多开发者尤其是刚接触C#和加密的朋友可能都只是调用过System.Security.Cryptography.RSACryptoServiceProvider或RSA类传几个参数加密解密就完成了。这当然没问题也是生产环境的标准做法。但时间久了心里总会有点不踏实这黑盒子里到底发生了什么公钥和私钥到底是什么数学关系为什么它这么安全这就是我动手做这个项目的初衷。我想抛开.NET Framework/Core内置的、高度封装的RSA类从最底层的数学原理开始用C#代码一步步“手搓”出RSA的加密和解密过程。这不仅仅是为了学习更是为了建立一种深刻的、直觉性的理解。当你自己实现了大素数的生成、欧拉函数、模逆元计算并亲眼看到用公钥加密的密文能被对应的私钥解开时那种对非对称加密“魔法”的领悟是完全不同的。更进一步我决定用WPFWindows Presentation Foundation来为这个“手搓”的RSA引擎打造一个可视化工具。为什么是WPF因为它的数据绑定和MVVM模式能让我们将复杂的加密过程和数据状态清晰地分离和展示。你可以实时输入明文、点击生成密钥对、观察加密后的密文通常是一串巨大的数字再用私钥解密回来。这个过程的可视化能将抽象的数学概念转化为直观的操作和结果无论是用于教学演示还是自己调试验证算法都极具价值。所以这个项目适合谁呢如果你是C#初学者想深入理解加密和WPF如果你是学生需要完成一个结合算法与界面的课程设计或者你是一位经验丰富的开发者希望重温密码学基础并探索WPF的现代UI开发——那么这个从数学原理到完整可视化工具的旅程都会让你有所收获。接下来我们就从最核心的数学部分开始拆解。2. RSA算法的数学原理与核心步骤拆解要自己实现RSA绕不开它的数学基础。别担心我们不需要成为数学家但必须理解几个关键概念和步骤。RSA的安全性建立在“大数分解难题”之上简单说将两个大质数相乘很容易但想从一个巨大的乘积中倒推出原来的两个质数在现有计算能力下几乎不可能。2.1 密钥生成的五个数学步骤我们自己实现RSA密钥生成需要严格遵循以下流程选择两个大质数 p 和 q这是所有运算的起点。在真实应用中p和q需要非常大通常是1024位或2048位的二进制数以确保安全。对于我们学习和演示可以选择稍小的、可管理的质数比如61和53。关键在于它们必须是质数并且需要一套算法来生成或验证。在C#中我们可以自己实现一个简单的质数测试如米勒-拉宾素性测试或者为了简化从一个预制的质数列表中选取。计算模数 nn p * q。这个n就是之后所有模运算的基数。它的长度二进制位数决定了密钥的强度。在我们的例子中n 61 * 53 3233。计算欧拉函数 φ(n)对于两个质数p和q欧拉函数的值是φ(n) (p-1) * (q-1)。它表示在小于n的正整数中与n互质的数的个数。计算φ(3233) (61-1) * (53-1) 60 * 52 3120。这个 φ(n) 是后续选择公钥指数e和计算私钥指数d的关键。选择公钥指数 e公钥由(e, n)组成。e 需要满足两个条件1 e φ(n)并且e与φ(n)互质即最大公约数 gcd(e, φ(n)) 1。通常为了计算效率我们会选择一个较小的、常见的质数比如 65537 (0x10001)。它满足与大多数 φ(n) 互质且二进制表示中1很少能加速加密运算。在我们的例子中我们检查 65537 是否与 3120 互质。由于 3120 的质因数包括 2, 3, 5, 13而 65537 是质数且远大于这些数所以肯定互质。如果 e 与 φ(n) 不互质就需要重新选择 e。计算私钥指数 d私钥由(d, n)或(d, p, q)组成。d 是 e 对于 φ(n) 的“模逆元”。也就是说d 需要满足(e * d) % φ(n) 1。计算模逆元需要用到“扩展欧几里得算法”。这是手搓RSA中最核心的算法之一。给定 e17我们换个小点的例子假设我们选了17作为eφ(n)3120我们需要找到一个 d使得(17 * d) % 3120 1。通过扩展欧几里得算法我们可以计算出 d2753验证17 * 2753 4680146801 ÷ 3120 15 余 1成立。至此我们得到公钥 (e, n): (17, 3233)私钥 (d, n): (2753, 3233)注意在实际的、安全的RSA实现中私钥通常包含更多信息如p, q, d mod (p-1), d mod (q-1)等以便使用中国剩余定理(CRT)来加速解密过程。我们手搓版本为了聚焦原理可以先使用最基本的 (d, n) 形式。2.2 加密与解密过程有了密钥对加密和解密过程在数学上就非常简洁了。加密假设明文是一个数字m文本需要先转换为数字例如使用ASCII或Unicode编码且m必须小于n。加密过程是计算密文c m^e mod n。这里^表示幂运算mod是取模运算。解密拿到密文c后用私钥解密计算明文m c^d mod n。为什么这样能恢复明文这背后的数学原理是欧拉定理。简单理解因为e和d是关于φ(n)的模逆元所以(m^e)^d mod n m^(e*d) mod n m^(k*φ(n)1) mod n。根据欧拉定理当m与n互质时m^φ(n) mod n 1因此上式等于m。即使m与n不互质利用中国剩余定理也能证明解密成立。一个手工计算的例子 假设明文m 65(ASCII码的 ‘A’)。加密c 65^17 mod 3233。直接计算65的17次方是个天文数字但我们可以用“快速模幂算法”来高效计算。结果是c 2790。解密m 2790^2753 mod 3233。同样用快速模幂算法计算后得到m 65。成功还原这里引出了另一个手搓RSA必须实现的核心算法快速模幂算法。直接计算a^b mod n在指数b很大时如我们的d2753是完全不可行的会溢出且极慢。快速模幂算法通过将指数二进制化并迭代平方、取模将计算复杂度从 O(b) 降低到 O(log b)是工程实现的基石。3. C# 核心算法实现大数运算与关键模块理解了数学原理我们就可以开始用C#编码了。.NET内置的BigInteger结构位于System.Numerics命名空间是我们“手搓”RSA的得力助手它能处理任意大小的整数完美满足我们对大素数和大数模运算的需求。3.1 质数生成与素性测试首先我们需要一种方法来获得大质数p和q。完全随机生成然后测试是最直接的方法。using System.Numerics; public static class PrimeGenerator { private static Random _random new Random(); // 生成一个指定位数的可能质数奇数 public static BigInteger GeneratePossiblePrime(int bitLength) { byte[] bytes new byte[bitLength / 8]; _random.NextBytes(bytes); BigInteger number new BigInteger(bytes); // 确保是正数且是奇数 number BigInteger.Abs(number); if (number.IsEven) number; // 确保位数足够避免前导零导致位数变少 number | (BigInteger.One (bitLength - 1)); return number; } // 米勒-拉宾素性测试概率性测试但精度足够高 public static bool IsProbablePrime(BigInteger source, int certainty 10) { if (source 2 || source 3) return true; if (source 2 || source.IsEven) return false; BigInteger d source - 1; int s 0; while (d.IsEven) { d / 2; s 1; } // 使用一些小质数作为基数进行测试提高效率 BigInteger[] bases { 2, 3, 5, 7, 11, 13, 17 }; for (int i 0; i bases.Length bases[i] source; i) { if (!MillerRabinTest(source, d, s, bases[i])) return false; } // 通过多轮测试可以认为是质数的概率极高 return true; } private static bool MillerRabinTest(BigInteger n, BigInteger d, int s, BigInteger a) { BigInteger x BigInteger.ModPow(a, d, n); if (x 1 || x n - 1) return true; for (int r 1; r s; r) { x BigInteger.ModPow(x, 2, n); if (x n - 1) return true; if (x 1) return false; } return false; } // 生成一个指定位数的质数 public static BigInteger GeneratePrime(int bitLength) { BigInteger candidate; do { candidate GeneratePossiblePrime(bitLength); } while (!IsProbablePrime(candidate)); return candidate; } }实操心得BigInteger.ModPow方法本身就是快速模幂算法的实现我们直接调用即可这大大简化了工作。但在教学意义上你可以尝试自己实现一个ModularExponentiation函数来加深理解。certainty参数控制测试轮数轮数越多误判将合数判为质数的概率越低但耗时也越长。对于演示10轮足够了。真实应用需要更高 certainty。生成大质数是相对耗时的操作。在WPF UI线程中直接调用可能会导致界面卡顿。务必在后台线程如Task.Run中执行并通过Dispatcher更新UI。3.2 扩展欧几里得算法求模逆元这是计算私钥指数d的关键。给定e和φ(n)我们需要解方程e*d ≡ 1 (mod φ(n))即求d e^(-1) mod φ(n)。public static class MathUtils { // 扩展欧几里得算法返回 gcd(a, b), 以及满足 ax by gcd(a, b) 的 x, y public static (BigInteger gcd, BigInteger x, BigInteger y) ExtendedEuclidean(BigInteger a, BigInteger b) { if (b 0) return (a, 1, 0); var (gcd, x1, y1) ExtendedEuclidean(b, a % b); BigInteger x y1; BigInteger y x1 - (a / b) * y1; return (gcd, x, y); } // 计算 a 在模 m 下的模逆元即 a^(-1) mod m // 返回的逆元是正数在模 m 的意义下 public static BigInteger ModInverse(BigInteger a, BigInteger m) { var (gcd, x, _) ExtendedEuclidean(a, m); if (gcd ! 1) throw new ArgumentException($数字 {a} 和模数 {m} 不互质不存在模逆元。); // 确保结果是正数 BigInteger result (x % m m) % m; return result; } }为什么这样算扩展欧几里得算法不仅能求最大公约数还能找到贝祖等式ax by gcd(a,b)的整数解x, y。当a与m互质时gcd(a, m)1等式变为a*x m*y 1。对两边同时取模m得到a*x ≡ 1 (mod m)所以x就是a模m的逆元。最后(x % m m) % m是为了确保结果在0到m-1的正数范围内。3.3 封装RSA核心类现在我们可以把上述模块组合起来形成一个完整的RSA密钥生成和加解密类。public class ManualRSA { public BigInteger ModulusN { get; private set; } public BigInteger PublicExponentE { get; private set; } public BigInteger PrivateExponentD { get; private set; } public BigInteger PhiN { get; private set; } // 仅内部使用不暴露 public int KeySize ModulusN.ToByteArray().Length * 8; // 生成密钥对 public void GenerateKeys(int primeBitLength 512, BigInteger? customE null) { // 1. 生成两个大质数 BigInteger p PrimeGenerator.GeneratePrime(primeBitLength); BigInteger q PrimeGenerator.GeneratePrime(primeBitLength); // 确保 p 和 q 不相等极低概率但需检查 while (p q) { q PrimeGenerator.GeneratePrime(primeBitLength); } // 2. 计算 n 和 φ(n) ModulusN p * q; PhiN (p - 1) * (q - 1); // 3. 选择公钥指数 e PublicExponentE customE ?? new BigInteger(65537); // 常用默认值 65537 // 验证 e 与 φ(n) 互质 if (BigInteger.GreatestCommonDivisor(PublicExponentE, PhiN) ! 1) { throw new InvalidOperationException(选择的公钥指数 e 与 φ(n) 不互质请尝试其他值如 17。); } // 4. 计算私钥指数 d PrivateExponentD MathUtils.ModInverse(PublicExponentE, PhiN); } // 加密将明文数字 m 加密为密文数字 c public BigInteger Encrypt(BigInteger plaintextNumber) { if (plaintextNumber ModulusN) throw new ArgumentException($明文数字必须小于模数 n ({ModulusN})。); // 使用快速模幂算法c m^e mod n return BigInteger.ModPow(plaintextNumber, PublicExponentE, ModulusN); } // 解密将密文数字 c 解密为明文数字 m public BigInteger Decrypt(BigInteger ciphertextNumber) { // 使用快速模幂算法m c^d mod n return BigInteger.ModPow(ciphertextNumber, PrivateExponentD, ModulusN); } // 辅助方法将字符串转换为BigInteger简单使用UTF8编码 public BigInteger StringToBigInteger(string text) { byte[] bytes System.Text.Encoding.UTF8.GetBytes(text); // 注意直接转换可能导致数字过大实际应用中需要对长文本进行分块 return new BigInteger(bytes, isUnsigned: true); } // 辅助方法将BigInteger转换回字符串 public string BigIntegerToString(BigInteger number) { byte[] bytes number.ToByteArray(isUnsigned: true); return System.Text.Encoding.UTF8.GetString(bytes); } }注意事项与常见陷阱文本分块上面的StringToBigInteger方法对于长文本是有问题的。因为RSA要求加密的明文数字m必须小于模数n。如果文本编码后的字节数组代表的数字大于n加密就会失败。真正的RSA加密文本需要结合对称加密如AES或使用OAEP等填充方案并对数据进行分块。我们这里为了演示核心算法假设处理的都是很短的、转换后小于n的字符串。在可视化工具中我们会加入长度检查和提示。密钥存储生成的密钥e, d, n都是BigInteger。为了在UI上显示和交换通常需要转换为Base64或十六进制字符串。注意.NET内置的RSA使用特定的XML或PKCS#1格式我们手搓的密钥格式是自定义的两者不兼容。性能BigInteger.ModPow对于大数运算已经高度优化但解密过程指数d很大仍然比加密指数e较小慢很多。这也是为什么RSA通常只用于加密短数据如对称密钥。4. WPF可视化工具的设计与实现MVVM模式有了RSA核心引擎我们接下来用WPF构建一个用户友好的界面来驱动它。采用MVVMModel-View-ViewModel模式是WPF开发的最佳实践它能将UI逻辑与业务逻辑清晰分离便于测试和维护。4.1 视图模型ViewModel设计ViewModel是连接View界面和Model我们的ManualRSA类的桥梁。它包含属性用于数据绑定和命令用于响应按钮点击。using System; using System.Numerics; using System.Threading.Tasks; using System.Windows.Input; using Microsoft.Toolkit.Mvvm.ComponentModel; using Microsoft.Toolkit.Mvvm.Input; namespace RSATool.ViewModels { public class MainViewModel : ObservableObject { private ManualRSA _rsaEngine new ManualRSA(); // 绑定到UI的属性 private string _primeBitLength 512; public string PrimeBitLength { get _primeBitLength; set SetProperty(ref _primeBitLength, value); } private string _publicKeyE 65537; public string PublicKeyE { get _publicKeyE; set SetProperty(ref _publicKeyE, value); } private string _modulusN ; public string ModulusN { get _modulusN; set SetProperty(ref _modulusN, value); } private string _privateKeyD ; public string PrivateKeyD { get _privateKeyD; set SetProperty(ref _privateKeyD, value); } private string _inputText Hello RSA!; public string InputText { get _inputText; set SetProperty(ref _inputText, value); } private string _encryptedText ; public string EncryptedText { get _encryptedText; set SetProperty(ref _encryptedText, value); } private string _decryptedText ; public string DecryptedText { get _decryptedText; set SetProperty(ref _decryptedText, value); } private bool _isGeneratingKeys; public bool IsGeneratingKeys { get _isGeneratingKeys; set SetProperty(ref _isGeneratingKeys, value); } // 命令 public IAsyncRelayCommand GenerateKeysCommand { get; } public IRelayCommand EncryptCommand { get; } public IRelayCommand DecryptCommand { get; } public MainViewModel() { GenerateKeysCommand new AsyncRelayCommand(GenerateKeysAsync); EncryptCommand new RelayCommand(Encrypt); DecryptCommand new RelayCommand(Decrypt); } private async Task GenerateKeysAsync() { IsGeneratingKeys true; try { // 在后台线程执行耗时的密钥生成 await Task.Run(() { int bitLength int.Parse(PrimeBitLength); BigInteger? customE null; if (BigInteger.TryParse(PublicKeyE, out BigInteger eValue)) { customE eValue; } _rsaEngine.GenerateKeys(bitLength, customE); }); // 更新UI自动回到UI线程 ModulusN _rsaEngine.ModulusN.ToString(X); // 十六进制显示 PrivateKeyD _rsaEngine.PrivateExponentD.ToString(X); } catch (Exception ex) { // 实际项目中应使用日志或更友好的错误提示 System.Diagnostics.Debug.WriteLine($生成密钥失败: {ex.Message}); } finally { IsGeneratingKeys false; } } private void Encrypt() { try { if (string.IsNullOrWhiteSpace(InputText)) return; // 将字符串转换为BigInteger BigInteger plainNumber _rsaEngine.StringToBigInteger(InputText); // 检查明文是否小于模数n if (plainNumber _rsaEngine.ModulusN) { EncryptedText [错误] 明文过长请缩短文本或增大密钥长度。; return; } BigInteger cipherNumber _rsaEngine.Encrypt(plainNumber); EncryptedText cipherNumber.ToString(X); // 十六进制显示密文 } catch (Exception ex) { EncryptedText $[加密错误] {ex.Message}; } } private void Decrypt() { try { if (string.IsNullOrWhiteSpace(EncryptedText)) return; // 将十六进制密文字符串解析回BigInteger if (!BigInteger.TryParse(EncryptedText, System.Globalization.NumberStyles.HexNumber, null, out BigInteger cipherNumber)) { DecryptedText [错误] 密文格式无效。; return; } BigInteger plainNumber _rsaEngine.Decrypt(cipherNumber); DecryptedText _rsaEngine.BigIntegerToString(plainNumber); } catch (Exception ex) { DecryptedText $[解密错误] {ex.Message}; } } } }设计要点异步命令密钥生成是CPU密集型操作会阻塞UI。使用AsyncRelayCommand和Task.Run将其放到后台线程并通过IsGeneratingKeys属性绑定按钮的IsEnabled或显示进度条防止界面卡死。数据绑定所有属性都实现了INotifyPropertyChanged通过ObservableObject当属性值改变时UI会自动更新。错误处理在加解密和转换过程中加入try-catch并将友好错误信息绑定到UI而不是让程序崩溃。显示格式BigInteger直接以十进制显示会非常长使用十六进制ToString(X)更紧凑易读。4.2 视图View设计View是用户直接交互的界面。我们使用XAML来定义布局并利用数据绑定将UI元素与ViewModel的属性连接起来。Window x:ClassRSATool.Views.MainWindow xmlnshttp://schemas.microsoft.com/winfx/2006/xaml/presentation xmlns:xhttp://schemas.microsoft.com/winfx/2006/xaml xmlns:dhttp://schemas.microsoft.com/expression/blend/2008 xmlns:mchttp://schemas.openxmlformats.org/markup-compatibility/2006 xmlns:localclr-namespace:RSATool.ViewModels mc:Ignorabled Title手搓RSA加密解密工具 Height650 Width800 Window.DataContext local:MainViewModel / /Window.DataContext Grid Margin10 Grid.RowDefinitions RowDefinition HeightAuto/ RowDefinition Height*/ RowDefinition HeightAuto/ /Grid.RowDefinitions !-- 密钥生成区域 -- GroupBox Grid.Row0 Header1. 生成RSA密钥对 Margin0,0,0,10 StackPanel StackPanel OrientationHorizontal Margin5 TextBlock Text质数位数: VerticalAlignmentCenter Width80/ TextBox Text{Binding PrimeBitLength, UpdateSourceTriggerPropertyChanged} Width80 Margin5,0/ TextBlock Text(例如: 512, 1024) VerticalAlignmentCenter ForegroundGray Margin5,0/ TextBlock Text公钥指数 e: VerticalAlignmentCenter Width80 Margin20,0,0,0/ TextBox Text{Binding PublicKeyE, UpdateSourceTriggerPropertyChanged} Width120 Margin5,0/ TextBlock Text(常用 65537) VerticalAlignmentCenter ForegroundGray/ /StackPanel Button Content生成密钥对 Command{Binding GenerateKeysCommand} Margin5 Padding20,5 HorizontalAlignmentLeft Button.Style Style TargetTypeButton Setter PropertyIsEnabled ValueTrue/ Style.Triggers DataTrigger Binding{Binding IsGeneratingKeys} ValueTrue Setter PropertyContent Value生成中.../ Setter PropertyIsEnabled ValueFalse/ /DataTrigger /Style.Triggers /Style /Button.Style /Button Grid Margin5 Grid.ColumnDefinitions ColumnDefinition WidthAuto/ ColumnDefinition Width*/ /Grid.ColumnDefinitions TextBlock Text模数 n: VerticalAlignmentTop Grid.Column0/ TextBox Text{Binding ModulusN} IsReadOnlyTrue Grid.Column1 Margin5,0 TextWrappingWrap AcceptsReturnTrue Height60 VerticalScrollBarVisibilityAuto FontFamilyConsolas/ /Grid Grid Margin5 Grid.ColumnDefinitions ColumnDefinition WidthAuto/ ColumnDefinition Width*/ /Grid.ColumnDefinitions TextBlock Text私钥 d: VerticalAlignmentTop Grid.Column0/ TextBox Text{Binding PrivateKeyD} IsReadOnlyTrue Grid.Column1 Margin5,0 TextWrappingWrap AcceptsReturnTrue Height60 VerticalScrollBarVisibilityAuto FontFamilyConsolas/ /Grid /StackPanel /GroupBox !-- 加解密操作区域 -- GroupBox Grid.Row1 Header2. 加密与解密 Margin0,0,0,10 Grid Grid.RowDefinitions RowDefinition Height*/ RowDefinition HeightAuto/ RowDefinition Height*/ /Grid.RowDefinitions Grid.ColumnDefinitions ColumnDefinition Width*/ ColumnDefinition WidthAuto/ ColumnDefinition Width*/ /Grid.ColumnDefinitions !-- 明文输入 -- GroupBox Header明文输入 Grid.Row0 Grid.Column0 Margin5 TextBox Text{Binding InputText, UpdateSourceTriggerPropertyChanged} AcceptsReturnTrue TextWrappingWrap VerticalScrollBarVisibilityAuto FontFamilyConsolas/ /GroupBox !-- 操作按钮 -- StackPanel Grid.Row1 Grid.Column1 VerticalAlignmentCenter HorizontalAlignmentCenter Button Content加密 → Command{Binding EncryptCommand} Margin5 Padding20,5/ Button Content← 解密 Command{Binding DecryptCommand} Margin5 Padding20,5/ /StackPanel !-- 密文显示 -- GroupBox Header密文 (十六进制) Grid.Row0 Grid.Column2 Grid.RowSpan2 Margin5 TextBox Text{Binding EncryptedText} IsReadOnlyTrue TextWrappingWrap VerticalScrollBarVisibilityAuto FontFamilyConsolas/ /GroupBox !-- 解密结果 -- GroupBox Header解密结果 Grid.Row2 Grid.Column0 Grid.ColumnSpan3 Margin5 TextBox Text{Binding DecryptedText} IsReadOnlyTrue TextWrappingWrap VerticalScrollBarVisibilityAuto FontFamilyConsolas/ /GroupBox /Grid /GroupBox !-- 状态栏 -- StatusBar Grid.Row2 StatusBarItem TextBlock Run Text密钥长度:/ Run Text{Binding KeySize, ModeOneWay}/ Run Text bits/ /TextBlock /StatusBarItem Separator/ StatusBarItem TextBlock Text提示首次使用请先生成密钥对。明文不宜过长。 FontStyleItalic ForegroundGray/ /StatusBarItem /StatusBar /Grid /WindowUI设计技巧分组布局使用GroupBox将功能模块密钥生成、加解密清晰分隔提升用户体验。多行文本框对于可能很长的密钥和密文使用TextBox并设置AcceptsReturn、TextWrapping和VerticalScrollBarVisibility使其可以显示多行和滚动。等宽字体对显示数字和十六进制字符串的文本框使用FontFamilyConsolas使字符对齐更易于阅读。数据触发器通过DataTrigger在密钥生成时改变按钮状态显示“生成中...”并禁用提供即时反馈。状态栏显示当前密钥长度等动态信息增强工具的专业感。4.3 应用启动与数据上下文绑定最后在App.xaml中移除StartupUri在App.xaml.cs中手动启动主窗口并设置DataContext。// App.xaml.cs protected override void OnStartup(StartupEventArgs e) { base.OnStartup(e); var mainView new MainWindow(); mainView.DataContext new MainViewModel(); // 实例化ViewModel mainView.Show(); }至此一个完整的、从数学原理到可视化界面的“手搓”RSA工具就完成了。运行程序你可以体验生成密钥、加密一段文字、再解密的完整过程并直观地看到每一步产生的巨大数字。5. 进阶优化、安全考量与常见问题我们的基础版本已经可以工作但距离一个健壮、实用的工具还有距离。这里探讨几个进阶方向和必须注意的安全问题。5.1 性能优化中国剩余定理CRT加速解密我们实现的解密公式m c^d mod n在私钥指数d很大时计算很慢。实际的标准RSA实现如.NET内置的会使用中国剩余定理利用私钥中包含的p和q来大幅加速。原理简述 已知n p * q且p和q互质。分别计算m_p c^(d mod (p-1)) mod pm_q c^(d mod (q-1)) mod q根据费马小定理指数可以模p-1和q-1简化且d mod (p-1)和d mod (q-1)可以预计算并存储在私钥中由于p和q比n小得多这两个模幂运算比直接算mod n快得多。利用CRT由m_p和m_q可以唯一确定m mod n。实现思路在ManualRSA类中密钥生成时保存p,q,dP (d mod (p-1)),dQ (d mod (q-1))和qInv (q^(-1) mod p)。在解密方法中实现CRT版本的计算。这会使解密速度提升数倍。5.2 数据填充Padding与长文本处理我们之前的实现有一个致命缺陷没有使用填充方案并且直接对字符串进行编码加密。这存在两大问题确定性加密同样的明文每次加密产生同样的密文这在语义上是不安全的。长度限制明文必须小于模数n。对于2048位密钥n约等于2^2048能加密的原始数据长度非常有限约256字节。解决方案使用OAEP填充在实际应用中RSA从不直接加密原始数据。而是采用像PKCS#1 OAEP这样的填充方案。它的作用随机化引入随机数使得每次加密相同明文得到不同密文。增强安全性防止特定的数学攻击。编码将任意长度的数据在一定限制内编码为符合RSA加密块长度的格式。对于长文本标准的做法是生成一个随机的对称密钥如AES-256密钥。用这个对称密钥加密你的长文本。用RSA公钥加密这个对称密钥。将RSA加密后的对称密钥和AES加密后的密文一起发送或存储。 解密时先用RSA私钥解出对称密钥再用对称密钥解密文本。在我们的工具中如何改进我们可以引入一个“混合加密”模式。在UI上增加一个选项“使用混合加密RSAAES”。当勾选时加密流程生成随机AES密钥 - 用AES加密明文 - 用RSA公钥加密AES密钥 - 输出[RSA加密的AES密钥][AES密文]的Base64组合。解密流程拆分组合 - 用RSA私钥解密出AES密钥 - 用AES密钥解密密文。5.3 常见问题与排查技巧在开发和测试过程中你可能会遇到以下问题问题现象可能原因排查与解决思路加密时抛出“明文必须小于模数”异常输入的文本太长转换后的BigInteger大于或等于n。1. 检查密钥长度。512位密钥只能加密极短文本几个字符。2. 实现分块加密或切换到“混合加密”模式。3. 在加密前先计算明文数字的大小并给出友好提示。解密结果乱码1. 加密和解密使用的密钥不匹配。2. 密文在传输或显示过程中被篡改如复制丢失字符。3. 文本编码不一致加密用UTF8解密用其他编码。1.务必确保加密用的公钥(e,n)和解密用的私钥(d,n)是同一对密钥生成的。重新生成密钥对后旧的密文无法用新私钥解密。2. 密文十六进制字符串要完整复制。可以增加一个“复制到剪贴板”按钮减少出错。3. 在StringToBigInteger和BigIntegerToString中统一使用Encoding.UTF8。密钥生成非常慢尤其是1024位以上大质数生成和素性测试是计算密集型操作。1. 这是正常现象。在UI上显示进度指示器如ProgressBar。2. 考虑使用更高效的素性测试算法如 Baillie-PSW。3.切勿在UI线程执行必须使用异步。“公钥指数e与φ(n)不互质”错误自定义的公钥指数e与φ(n)有公因数。1.e必须是奇数且通常选质数。最安全省事的选择是固定使用65537。2. 如果自定义e在生成密钥的方法中加入重试逻辑如果选择的e不互质则自动尝试下一个奇数。用其他工具生成的密文无法用本工具解密密钥格式和填充方案不兼容。本工具是自定义的、原始的、无填充的RSA实现。标准工具如OpenSSL使用PKCS#1等标准格式和填充。两者不互通。本工具主要用于教育演示理解算法本质。一个重要的实操心得在调试加解密过程时可以先用很小的、可手算的密钥进行验证。例如使用之前例子中的p61, q53, e17, d2753, n3233。在工具中硬编码这些值然后加密数字65看结果是否为2790。这种“已知答案测试”是验证算法实现是否正确的最有效方法。6. 项目总结与扩展方向走完从数学原理推导、C#算法实现到WPF可视化界面构建的整个流程相信你对RSA不再感到神秘。这个“手搓”的过程强迫我们去关注每一个细节如何生成大素数、如何计算模逆元、快速模幂算法如何工作、以及公钥私钥如何配对。这些知识是单纯调用API所无法给予的。这个项目本身还有很大的扩展空间你可以基于它做更深入的探索实现完整的RSA标准集成PKCS#1 v1.5或OAEP填充方案让你的工具能够与其他标准RSA库如OpenSSL生成的密钥和密文进行互操作。这会涉及到ASN.1编码解码是一个不小的挑战。增加密钥导入/导出功能支持将生成的密钥对以PEM或XML格式保存到文件并从文件加载。这需要你理解这些格式的规范。添加数字签名功能RSA除了加密另一个重要用途是数字签名。尝试实现用私钥“签名”一段数据的哈希值然后用公钥“验证”签名。性能分析与可视化在工具中加入计时功能比较不同密钥长度下加密、解密的速度并用WPF的图表控件如LiveCharts绘制成曲线直观展示RSA性能随密钥长度增长而下降的趋势。移植到 .NET MAUI 或 Avalonia将WPF前端替换为跨平台的UI框架让你手搓的RSA引擎能在macOS或Linux上运行。最后必须再次强调安全警告我们这个用于教育和演示的“手搓”RSA实现绝对不应用于任何真实的生产环境或保护敏感数据。密码学实现中细微的错误都可能导致严重的漏洞。生产环境请务必使用经过严格审计和长期考验的库如 .NET 自带的System.Security.Cryptography.RSA类。这个项目的价值在于照亮黑盒让你在下次使用那些强大、安全的官方API时心中更有底气知道脚下坚实的数学和工程基础究竟是什么。