RSA加密算法实现问题：加解密后无法还原明文

代码中的关键错误点 #

• 质数生成完全错误：generate2048Integer方法当前只生成2位随机数字，既不是质数，也远达不到2048位长度。RSA的核心要求是两个大质数p、q（你代码里的x、y），用普通合数会直接导致加密解密逻辑失效。
• 公钥e未做互质验证：findCoPrime只是随机返回17/257/65537这几个常用e值，但没有验证它们和φ(n)=(x-1)(y-1)是否互质。如果gcd(e, φ(n))≠1，模逆元d不存在，解密必然失败。
• 自定义Pow方法存在严重问题：你实现的循环乘法求幂，当指数是65537这种大数时，计算速度极慢，且中间结果会膨胀到无法想象的大小，即使BigInteger支持，也会引发性能和正确性问题。
• 模逆元未做有效性检查：modInv方法中没有检查扩展欧几里得算法返回的gcd是否为1，直接返回结果。如果e和φ(n)不互质，此时得到的d是无效的，无法正确解密。

修复方案 #

1. 生成符合要求的大质数
   替换generate2048Integer，实现一个生成大质数的方法，比如用米勒-拉宾素性测试（简化版示例）：

   public static BigInteger GenerateBigPrime(int bitLength)
   {
       Random rng = new Random();
       BigInteger candidate;
       do
       {
           byte[] bytes = new byte[bitLength / 8];
           rng.NextBytes(bytes);
           bytes[bytes.Length - 1] |= 0x80; // 确保最高位为1，保证位数
           bytes[0] |= 0x01; // 确保是奇数
           candidate = new BigInteger(bytes);
       } while (!IsPrime(candidate));
       return candidate;
   }
   
   // 简化版米勒-拉宾素性测试
   private static bool IsPrime(BigInteger n)
   {
       if (n <= 1) return false;
       if (n <= 3) return true;
       if (n % 2 == 0) return false;
   
       BigInteger d = n - 1;
       int s = 0;
       while (d % 2 == 0)
       {
           d /= 2;
           s++;
       }
   
       // 测试几个基，这里用2,3,5,7,11
       BigInteger[] bases = {2,3,5,7,11};
       foreach (BigInteger a in bases)
       {
           if (a >= n) continue;
           BigInteger x = BigInteger.ModPow(a, d, n);
           if (x == 1 || x == n - 1) continue;
           for (int j = 1; j < s; j++)
           {
               x = BigInteger.ModPow(x, 2, n);
               if (x == n - 1) break;
           }
           if (x != n - 1) return false;
       }
       return true;
   }
   

2. 正确生成公钥e
   修改findCoPrime，确保返回的e与φ(n)互质：

   public static BigInteger FindCoPrime(BigInteger phi)
   {
       // 优先尝试常用的e值
       BigInteger[] commonEs = {17, 257, 65537};
       foreach (BigInteger e in commonEs)
       {
           if (BigInteger.GreatestCommonDivisor(e, phi) == 1)
           {
               return e;
           }
       }
       // 如果常用值不行，生成随机e
       Random rng = new Random();
       BigInteger e;
       do
       {
           e = RandomIntegerBelow(phi - 1) + 2; // 2 <= e < phi
       } while (BigInteger.GreatestCommonDivisor(e, phi) != 1);
       return e;
   }
   

3. 替换自定义Pow为高效模幂
   直接使用.NET自带的BigInteger.ModPow替换你的Pow方法，同时修改加密解密方法：

   public static BigInteger RSAEncryption(BigInteger plaintext, BigInteger e, BigInteger n)
   {
       return BigInteger.ModPow(plaintext, e, n);
   }
   
   public static BigInteger RSADecryption(BigInteger ciphertext, BigInteger d, BigInteger n)
   {
       return BigInteger.ModPow(ciphertext, d, n);
   }
   

4. 添加模逆元有效性检查
   修改modInv方法，确保只有当gcd为1时才返回逆元：

   public static BigInteger ModInv(BigInteger a, BigInteger b)
   {
       var (g, x, _) = Egcd(a, b);
       if (g != 1)
       {
           throw new ArgumentException("模逆元不存在，a和b不互质");
       }
       return Mod(x, b);
   }
   

修正后的Main方法示例 #

static void Main(string[] args)
{
    BigInteger p = GenerateBigPrime(2048);
    BigInteger q = GenerateBigPrime(2048);
    BigInteger n = p * q;
    BigInteger phi = (p - 1) * (q - 1);
    BigInteger e = FindCoPrime(phi);
    BigInteger d = ModInv(e, phi); 
    
    BigInteger plaintext = 77;
    BigInteger ciphertext = RSAEncryption(plaintext, e, n);
    BigInteger decryptedText = RSADecryption(ciphertext, d, n);
    
    Console.WriteLine($"明文: {plaintext}");
    Console.WriteLine($"解密后: {decryptedText}");
}

内容的提问来源于stack exchange，提问作者Joshua Banks