我很好奇但从未提及的一件事是密码算法如何管理计算在合理的时间内数量如此之多。
这个例子说明了我的意思。如此庞大的数目，以及无数的力量。什么样的算法可以在相当长的时间内处理以
35052111338673026690212423937053328511880760811579981620642802346685810623109850235943049080973386241113784040794704193978215378499765413083646438784740952306932534945195080183861574225226218879827232453912820596886440377536082465681750074417459151485407445862511023472235560823053497791518928820272257787786的能力计算89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713？#1 楼
令人惊讶的是，使用了孩子们在基础学校学习的非常基本的算法。例如：http://www.wikihow.com/Do-Long-Multiplication
可以找到类似的求和，除法和除法算法。尝试向Google询问：“纸上划分”
“权力”有点棘手。在密码学中，您实际上并不需要“的真正力量”。相反，您需要：
（a ^ b）mod c
很容易计算a ^（2的幂）mod c
a * a mod c= a^2 mod c
(a^2)^2 mod c= a^4 mod c
(a^4)^2 mod c= a^8 mod c
...
(a^512)^2 mod c= a^1024 mod c
如果您需要a ^ 5
(a^5) = a^2 * a^2 * a
由于要使用“ mod c”，您可以保持数字不高于c。
例如：
c = 10
2^2 = 4
2^4 mod 10 = (4^2) mod 10 = 16 mod 10 = 6
2^8 mod 10 = ((4^2)^2) mod 10 = (6^2) mod 10 = 36 mod 10 = 6
2^16 mod 10 = (6^2) mod 10 =....
等。
有许多技巧可以使计算更快。例如，通常使用蒙哥马利乘法算法。但是即使没有这些技巧，实现也将足够快。我估计RSA（而不是0.2s）将花费5s左右。
评论
$ \ begingroup $
0.2s vs 5s ！？您大大低估了计算机进行数学运算的速度。差异更接近0.1ms与1ms
$ \ endgroup $
– BlueRaja-Danny Pflughoeft
2015年10月5日在16:26
$ \ begingroup $
注意：如果不执行重复的平方乘运算，您将可能永远无法见证RSA签名操作的完成...
$ \ endgroup $
– SEJPM♦
2015年10月5日在21:02
$ \ begingroup $
486同样快速地开花。
$ \ endgroup $
–轨道轻赛
2015年10月5日23:55
$ \ begingroup $
蒙哥马利乘法没有使事情变得更快，当然也不会降低25倍：基本运算的数量不会渐近变化。它确实简化了商数的估计，并且避免了这种情况出现错误的罕见情况（通常很高兴），并且避免了边信道泄漏。
$ \ endgroup $
–fgrieu♦
2015年10月6日19:16
$ \ begingroup $
请注意有关蒙哥马利的评论是由其他人撰写的。不确定如何做到这一点，但是似乎有些声誉很高的人可以修改其他人的帖子。如果他们明确地指出这一点，那就太好了。
$ \ endgroup $
–smrt28
2015年10月8日在7:34
#2 楼
可以在合理的时间内计算出这样的“巨大”数字有两个原因。第一个原因是我们没有将一个整数x提高到某个大指数d。我们要做的是计算以整数n为模的x的乘幂d。模数意味着我们对最终整数xd并不感兴趣，而仅对xd除以n的欧几里得除数的其余部分感兴趣。这里的好处是所有涉及的数字都将位于0到n-1之间。因此，它们将适合数千个位，而不是变得（比）整个宇宙大得多。
第二个原因是求幂是通过平方和乘法来完成的。例如，为了计算x100（模n），我们不对x乘以99。相反，我们计算：
x2
（x2）2 = x4
（x4）2 = x8
（x8）2 = x16
（x16）2 = x32
（x32）2 = x64
x64x32x4 = x64 + 32 + 4 = x100
因此总共有6个平方和2个乘法，即比朴素算法的99个乘法少得多。一般而言，如果指数拳在k位上（指数值在2k-1和2k之间），则平方乘算法将需要k-1平方和最多k-1乘法（可能远小于
如果您想了解更多有关此类内容的详细信息，请参阅《应用密码学手册》，特别是第14章。
#3 楼
我们可以使用二进制指数方法计算$ m ^ e \ bmod n $。在这种方法中，您应该首先计算$ e $的二进制形式。令$ \ ell $为$ e $中的位数，并让$ e_i $表示$ e $的第ii位，这样$ e = \ sum \ limits_ {i = 0} ^ \ ell e_i \ cdot 2 ^ i $。现在，使用下面的算法，您可以计算$ c $：
$ z：= 1 $
$ \ text {for} i：= \ ell \ text {到} 0 \ text {do} $
$ \ quad z：= z ^ 2 \ cdot m ^ {e_i} \ bmod n $
$ \ text {return} z $
您可以在一秒钟内轻松地在带有
Modexp(m,e,n);的程序中（例如“ MAGMA”）执行此操作。
评论
你做了什么研究？密码学的教科书和课程对此进行了介绍。我们希望您在提出问题之前先做大量研究，然后在问题中加以证明。请参阅security.stackexchange.com/help/how-to-ask：“在提出问题之前，您是否已彻底搜索了答案？共享研究成果对所有人都有帮助。请告诉我们您发现了什么，以及为什么它不满足您的需求。这证明您已花时间尝试自助，这使我们免于重复显而易见的答案，最重要的是，它可以帮助您获得更具体和相关的答案！“另请参阅security.stackexchange.com/q/13674/971
这是一个相关的问题：计算11的“一个”十进制数字，提高到十亿次幂。如果您计算11、1、2、3和4的幂，那么应该很快就会很清楚地知道您不需要执行100亿次乘法即可回答该问题。现在您知道为什么RSA中的计算可行吗？