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

Question

作为一名 IT 教师，我想向我的学生展示 RSA 算法的工作原理。我还想向他们展示 'hacking' 它通过遍历所有可能的素数需要永远。

对于小于 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，解密后的消息 =/= 原始消息。

我认为错误在于私有指数的计算"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 的正确解。

还有：

"I would also like to show them that 'hacking' it by iterating over all possible primes takes forever." 让他们破解是件好事，一旦他们感到沮丧并意识到这行不通，那么您可以向他们展示一点数学知识可以提前向他们证明这一点。 prime number theorem 向我们展示了素数的密度。例如，您可以采用 2^1024 数量级的素数，并向他们展示这种大小的数量级为 2^1014.5 的素数。然后问他们每秒可以尝试多少次，并通过这种天真的方法计算他们破解所需的年数（或者您可以采用查看所有素数 table 的存储的方法).然后这可以导致更好的解决方案，如数字字段筛选。哦，太有趣了！

Answer 2

好吧，那是我太蠢了...非常感谢你的想法，我一定会研究这个定理的！

现在它适用于

private static BigInteger ModInverse(BigInteger a, BigInteger n)
    {
        BigInteger t = 0, nt = 1, r = n, nr = a;

        if (n < 0)
        {
            n = -n;
        }

        if (a < 0)
        {
            a = n - (-a % n);
        }

        while (nr != 0)
        {
            var quot = r / nr;

            var tmp = nt; nt = t - quot * nt; t = tmp;
            tmp = nr; nr = r - quot * nr; r = tmp;
        }

        if (r > 1) throw new ArgumentException(nameof(a) + " is not convertible.");
        if (t < 0) t = t + n;
        return t;
    }

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

Decrypting RSA encoded message in C#

c#

encryption

primes

rsa

还有：