encryption - RSA 指数大小

Question

我正在学习RSA算法。我对非常小的素数执行该算法，并使用在线大整数计算器执行加密和解密，一切正常。

我的问题是关于我们创建的指数的大小，当涉及到更大的数字时，似乎无法计算。

例如，该算法首先选择两个素数 p 和 q。您计算 n=pxq，然后计算 n 的总和。接下来，您选择一个数字“e”，使得 1

然后，要执行加密，您可以使用 ASCII 字符“A”，即 65，然后将其计算为 e 次方。 (65^e)

当 e 大于 100,000(6 位数字)时，在线大整数计算器开始变得非常缓慢且迟缓(计算超过一分钟)

我的问题是，对于工作中的 RSA 算法，该算法选择多大大小(位数)的数字？

我的一个想法是，我使用的在线计算器可能没有使用最佳的指数方法？这是我正在使用的计算器:http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm

Answer 1

比方说M是模数。所以是的，你可以先执行 intermediate = 65^e ，最后计算intermediate mod M 。当然，intermediate将是一个非常非常非常大的整数(如果 e 等于 65537，则 intermediate 的十进制表示包含 118813 位数字!)。

但是，感谢一个非常基本的模算术定理，

(65^e) mod M = ((((65 mod M) * 65) mod M) * 65) mod M [...] (e times)

(定理指出，在商环中，元素所属类别的 n 次方就是该元素的 n 次方类别)

如您所见，这不需要任何非常大的整数库，因为在每个算术乘积之后，您使用 mod M返回 0 之间的整数和M-1 。因此，您只需计算小于 M 的整数的算术乘积。

作为示例，下面是一个简单的 shell 脚本 (bash)，它计算 65^65537 mod 991*997。 如您所见，无需获得大量数字库:

#!/bin/bash

# set RSA parameters
m=65           # message to encode
M=$((991*997)) # modulus (both 991 and 997 are prime numbers)
e=65537        # public exponent (coprime with 990*996, thus compliant with RSA algorithm)

# compute (m^e) mod M
ret=1
for i in {1..$e}
do
  ret=$(((ret*m)%M))
done

# display the result
echo $ret

它立即返回784933 ，因此65^65537 mod 991*997 = 784933

用你的微积分方法计算的最大整数有118813位，但是用这个shell脚本处理的最大整数只有12位或更少((M-1)^2由12位数字组成)。

根据这些解释，我们现在可以回答您的问题:

My question is then, for the working RSA algorithm, what size (number of digits) number does that algorithm pick?

通过上面的解释，您可以看到，您必须操作的整数的十进制表示形式的最大位数是 1+log10((M-1)^2) ，因为您最多将计算 0 之间的两个整数的乘积和M-1 .

请注意1+log10((M-1)^2) = 1+2.log10(M-1) < 2+2.log10(M) = 2.(1+log10(M)) 。另请注意 1+log10(M)是M的位数。

因此，作为结论，这证明您的库必须正确处理的位数是模数位数的两倍(如果您使用整数乘法来计算幂)此处解释)。