我正在尝试在 C# 中实现 RSA 算法。下面的代码在 p 和 q 很小时有效,但在尝试复制 RSA-100 或更大时 p 和 q 非常大时无效。
例如,当:
p = 61, q = 53, n = 3233, phi(n) = 3120, e = 17, d = 2753
解密后,我得到正确的原始消息。我从RSA Wikipedia page获得了这些值。该代码也适用于 p 和 q 的其他较小值。
但是,当使用RSA-100或更高版本时,我无法取回原来的消息。我尝试对指数 (e) 使用不同的值,并确保它与 phi(n) 互质,但我无法得到正确的结果。我错过了一些简单/明显的东西吗?
预先感谢您的帮助!
//p and q for RSA-100
//string p = "37975227936943673922808872755445627854565536638199";
//string q = "40094690950920881030683735292761468389214899724061";
string p = "61";
string q = "53";
//Convert string to BigInteger
BigInteger rsa_p = BigInteger.Parse(p);
BigInteger rsa_q = BigInteger.Parse(q);
//n = p * q
BigInteger rsa_n = BigInteger.Multiply(rsa_p, rsa_q);
//phi(n) = (p-1)*(q-1)
BigInteger rsa_fn = BigInteger.Multiply((rsa_p - 1), (rsa_q - 1));
BigInteger rsa_e = 17;
//Compute d
BigInteger rsa_d = BigInteger.ModPow(rsa_e, (rsa_fn - 1), rsa_fn);
//Encrypt the message, in this case 3007
//C = (3007^rsa_e) mod rsa_n
BigInteger C = BigInteger.ModPow(3007, rsa_e, rsa_n);
//Decrypt the message, M should equal 3007
//M = (3007^rsa_d) mod rsa_n
BigInteger M = BigInteger.ModPow(C, rsa_d, rsa_n);