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

你的代码存在几个核心问题，导致加密解密后无法还原明文：

1. 密钥生成的致命错误：p和q不是大素数 #

RSA的核心要求是p和q必须是互不相同的大素数，但你的generate2048Integer方法只是生成了INTLIMIT位的十进制随机数字字符串，既不是素数，也不符合2048位二进制数的要求（注释标注的是bit value，但代码逻辑是生成十进制位数）。

修复方法：

• 实现大数素性检测算法（比如米勒-拉宾素性测试，适合大整数素性验证）
• 生成真正的2048位二进制随机大整数，再检测是否为素数，直到找到符合要求的素数p和q

示例素数生成逻辑框架：

public static BigInteger GenerateBigPrime(int bitLength)
{
    Random rng = new Random();
    BigInteger prime;
    do
    {
        // 生成bitLength位的随机大数，确保最高位为1（保证位数）、最低位为1（排除偶数）
        byte[] bytes = new byte[bitLength / 8];
        rng.NextBytes(bytes);
        bytes[bytes.Length - 1] |= 0x01;
        bytes[0] |= 0x80;
        prime = new BigInteger(bytes);
    } while (!IsPrime(prime));
    return prime;
}

// 简化版米勒-拉宾素性测试，足够验证2048位素数
public static bool IsPrime(BigInteger n)
{
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;

    // 将n-1分解为d*2^s
    BigInteger d = n - 1;
    int s = 0;
    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }

    // 测试多个底数，确保素数准确性
    BigInteger[] bases = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
    foreach (BigInteger a in bases)
    {
        if (a >= n) continue;
        BigInteger x = BigInteger.ModPow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool isComposite = true;
        for (int j = 1; j < s; j++)
        {
            x = BigInteger.ModPow(x, 2, n);
            if (x == n - 1)
            {
                isComposite = false;
                break;
            }
        }
        if (isComposite) return false;
    }
    return true;
}

2. 幂运算未使用模幂优化，效率与正确性双失 #

你的Pow方法是普通逐次乘法，当指数为65537时，需要执行65536次乘法，不仅耗时极久，还会生成天文数字级的中间值，可能引发计算异常。RSA加密解密必须使用模幂运算，即直接计算(底数^指数) mod 模数，可以直接调用BigInteger.ModPow（内部实现了快速幂+模运算，高效且正确）。

修复加密解密方法：

public static BigInteger RSAEncryption(BigInteger plaintext, BigInteger e, BigInteger n)
{
    // RSA要求明文必须小于模数n
    if (plaintext >= n)
        throw new ArgumentException("明文必须小于模数n");
    return BigInteger.ModPow(plaintext, e, n);
}

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

删除你自行实现的Pow方法，直接使用系统内置的BigInteger.ModPow。

3. φ(n)计算逻辑错误 #

当p和q为互不相同的素数时，欧拉函数φ(n)的正确值是(p-1)*(q-1)，你的代码中BigInteger.Abs(a * b) / dgcd(a, b)是计算两个数的最小公倍数，完全不符合φ(n)的计算规则。当然这个错误的根源还是p和q不是素数，即使公式正确也无法得到有效结果。

4. 模逆元有效性未做检查 #

在newModInv方法中，若r > 1说明e和φ(n)不互质，此时模逆元不存在，方法会返回0。你的代码直接使用这个无效的d进行解密，必然无法得到正确明文。需要在生成d后添加检查：

BigInteger d = newModInv(e, phi);
if (d == 0)
{
    Console.WriteLine("错误：公钥指数e与φ(n)不互质，无法生成私钥");
    return;
}

修复后的主函数示例 #

static void Main(string[] args)
{
    // 生成2048位大素数p和q，确保二者不相等
    BigInteger p = GenerateBigPrime(2048);
    BigInteger q = GenerateBigPrime(2048);
    while (p == q)
    {
        q = GenerateBigPrime(2048);
    }

    BigInteger n = p * q;
    BigInteger phi = (p - 1) * (q - 1);
    BigInteger e = 65537; // 常用公钥指数，默认与φ(n)互质

    BigInteger d = newModInv(e, phi);
    if (d == 0)
    {
        Console.WriteLine("私钥生成失败：e与φ(n)不互质");
        return;
    }

    BigInteger plaintext = 77;
    if (plaintext >= n)
    {
        Console.WriteLine("明文长度超过模数范围");
        return;
    }

    BigInteger ciphertext = RSAEncryption(plaintext, e, n);
    BigInteger decryptedText = RSADecryption(ciphertext, d, n);

    Console.WriteLine($"明文: {plaintext}");
    Console.WriteLine($"密文: {ciphertext}");
    Console.WriteLine($"解密后明文: {decryptedText}");
}

其他细节优化 #

• 删除或修正INTLIMIT的注释（当前注释与代码逻辑完全不符）
• dgcd方法的功能与BigInteger.GreatestCommonDivisor一致，可以直接用系统方法简化代码

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