c# - 在 C# 中解密 RSA 编码的消息

Question

作为一名 IT 教师，我想向我的学生展示 RSA 算法的工作原理。我还想向他们展示，通过遍历所有可能的素数来“破解”它需要很长时间。

对于 < 1000 的素数，加密和解密工作得很好。当我用稍大的素数执行相同的算法时，解密结果是错误的。

Eg:
p, q are primes  
n = p * q  
phi = (p-1) * (q -1)  
d = (1 + (k * phi)) / e;  
**encryption:**  
c = (msg ^ e) % n  
**decryption**  
message = c ^ d % n;  

对于 p = 563 和 q = 569，解密工作正常。
另一方面，对于 p = 1009 和 q = 1013，解密后的消息 =/= 原始消息。

我认为错误在于私有(private)指数“d”的计算。我用 BigIntegers 替换了所有 int，但这并没有改变任何事情。有人有想法吗？

class RSA
{
    private BigInteger primeOne;
    private BigInteger primeTwo;
    private BigInteger exp;
    private BigInteger phi;
    private BigInteger n;
    private BigInteger d;
    private BigInteger k;


    private void calculateParameters(){
        // First part of public key:
        this.n = this.primeOne * this.primeTwo;
        // Finding other part of public key.
        this.phi = (this.primeOne - 1) * (this.primeTwo - 1);
        //Some integer k
        this.k = 2;
        this.exp = 2;

        while (this.exp < (int) this.phi)
        {
            // e must be co-prime to phi and
            // smaller than phi.

            if (gcd(exp, phi) == 1)
                break;
            else
                this.exp++;
        }

        this.d = (BigInteger) (1 + (this.k * this.phi)) / this.exp; ;
    }

    // Return greatest common divisors
    private static BigInteger gcd(BigInteger a, BigInteger b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    //Encryption algorithm RSA
    public string Encrypt(string msg)
    {
        calculateParameters();
        BigInteger encryptedNumber = BigInteger.Pow(BigInteger.Parse(msg),(int) this.exp) % this.n;
        // Encryption c = (msg ^ e) % n
        return Convert.ToString(encryptedNumber);

    }

    public string Decrypt(string encrypted)
    {

        BigInteger intAlphaNumber = BigInteger.Parse(encrypted);
        BigInteger decryptedAlphaNumber = BigInteger.Pow(intAlphaNumber,(int) this.d) % n;
        return Convert.ToString(decryptedAlphaNumber);

    }

}

Answer 1

你的问题出在数学上。

回想一下 e*d == 1 mod phi(n)，这意味着 e*d = 1 + k*phi(n)。在您的实现中，您假设 k 始终为 2。该假设是错误的。

为了证明，请考虑您的错误情况 p = 1009 和 q = 1013。在这种情况下，exp 是 5，根据您的选择它的算法。 k 对应的正确值为 4，所以 d 应该是 816077。但是，您的算法错误地将 d 计算为 408038。

如果您在代码中放置一个断言来检查 exp*d = 1 + k*phi(n)，那么您将很容易地看到您的 k 工作时和不工作时。

使用扩展欧几里德算法得到d的正确解。

还有:

“我还想向他们展示，通过遍历所有可能的素数来‘破解’它需要很长时间。”让他们破解是件好事，一旦他们感到沮丧并意识到这行不通，那么您可以向他们展示一点数学知识可以提前向他们证明这一点。 prime number theorem向我们展示了素数的密度。例如，您可以采用 2^1024 数量级的素数，并向他们展示这种大小的数量级为 2^1014.5 的素数。然后询问他们每秒可以尝试多少次，并通过这种天真的方法计算他们破解所需的年数(或者您可以采用查看所有素数表的存储方式)。然后这可以导致更好的解决方案，如数字字段筛选。哦，太有趣了!