如何在C＃中创建非对称密钥，因为指数大小有限？

Question

我正在创建一个使用非对称密钥加密和解密数据的软件。

问题是，我在C＃编码，即使我使用：

 BigInteger.Pow(BigIntenger myNumber, int myExponent);

指数是一个“int”，我的值对于int来说是大的。

只是为了快速解释并确保我没有犯任何错误，你必须使用大数字来使解密更加困难而不需要私钥。

所以我有

• N = P * Q.
• P和Q都是素数。
• M =（P-1）+（Q-1）
• C是带M的素数
• 然后找到U：C×U + M×V = 1

公钥（N，C）。

私钥（U，N）。

例如，您想要加密：“Bonjour！”到UTF8。

你将会有 ：

B⇔66/o⇔111/n⇔110/j⇔106/o⇔111/u⇔117/r⇔114/(spaces）⇔32/！⇔33

然后将每个数字提升到C的幂并以N为模。

例如：valueOfB =（66 ^ C）％N。

现在您的邮件已加密。

如果要解密它，则必须将每个值乘以指数U和模N.

例如：（valueOfB ^ U）％N

所以我只能在使用较小的数字时才这样做，因为我会有一个小的U值，它适合“int”，但是它不安全，我怎么能用像BigInteger这样的大U而不是int呢？

Answer 1

BigInteger的BigInteger.Pow将是一个非常复杂的数字。

二进制乘法具有（粗略地说）将n位数乘以m位数的特性产生近似(n+m)位的答案。

10 * 4096 = 0b1010 * 0b1_0000_0000_0000  (4 bits, 13 bits)
40960 = 0b1010_0000_0000_0000 (16 bits)

16 * 4096 = 0b1_0000 * 0b1_0000_0000_0000  (5 bits, 13 bits)
65536 = 0b1_0000_0000_0000_0000 (17 bits)

15 * 4095 = 0b1111 * 0b1111_1111_1111 (4 bits, 12 bits)
61425 = 0b1110_1111_1111_0001 (16 bits)

由于求幂是重复乘法，并且乘法重复加法，我们可以看到将1024位数提高到512位数的幂将在1024 * 512位（524288位，65536字节）的范围内产生答案。

但是你要用模数运算来跟进它，把它带回到1024位数的领域。那太浪费了。

值得庆幸的是，存在用于执行有效modular exponentiation的算法。感谢你们，.NET继续为你写下这个。

你在寻找什么

valueOfB = BigInteger.ModPow(66, U, N);