js 出错。如果五秒之后本段文字仍然可见，请使用 firefox 或 chrome，刷新页面。如果仍是不行，请与 [email protected] 联系。

RSA 算法详解

通过本教程，我们将由浅入深地介绍有关 RSA 算法的方方面面的内容。[hr] 1977 年，麻省理工学院的 Ron [b]R[/b]ivest、Adi [b]S[/b]hamir 和 Leonard [b]A[/b]dleman 共同提出了一种[goto=pubkeysec]非对称加密[/goto]算法，用他们三人的姓氏缩写命名为 RSA。从此，最重要的加密算法诞生了。[toggle=off] [title][sup][注][/sup][/title] [content]事实上，早在1973年，英国数学家 Clifford Cocks 就提出了相同的算法，但他的发现被列为政府机密，一直到1997年才公布。[/content][/toggle]。 [toggle=off] [title]一、非对称加密[/title] [content][a=pubkeysec]如果你不了解非对称加密，你会以为加密是件很简单的事。[bird=sec] [table] [tr][td=|align=center|background-color=#98f024]A[/td][td=|align=center|background-color=#f0d124]B[/td][td=|align=center|background-color=#f541fb]C[/td][/tr] [/table] [b]加密要解决两个基本问题[/b] 1、B 能看到 A 发给 C 的内容。 2、B 可以伪造 A 发给 C 的内容。 [/bird] [call=sec]如图[/call]，[size=1][a=situation]A 想和 C 通信，但他们中间总是隔着 B，A 发给 C 的内容必须经 B 传递[/size]。这就带来两个问题： 1、B 能看到 A 发给 C 的内容。[a=pzzl1] 2、B 可以伪造 A 发给 C 的内容。[a=pzzl2] 对于这两个问题，人们首先想到[toggle=off] [title]用对称加密来解决[/title] [content]A 与 C 秘密约定了一套加密算法，A 把原本要发给 C 的内容（明文）通过加密变成密文，经 B 传给 C，C 再通过解密把密文还原成明文。 举个简单的例子，A 要发给 C 的信息是一个数字，而他们事先约定的加密算法是将这个数字加 5。 假如 A 要发 7 给 C，就加密成 12 再发过去，C 收到后将它减去 5，就知道 A 要发的是 7。B 只看到 12，不知道实际应该是 7。 这是一个[b]对称加密[/b]的例子。[a=prisec]为什么叫对称加密？因为 C 知道怎样解密（密文－5＝明文）的同时，也必然知道了 A 是怎样加密（明文＋5＝密文）的。换言之，加密和解密两个算法可以互相推导。 对于上述两个问题： [goto=pzzl1]1[/goto]、B 虽然看到了密文，但不知道怎样解密，因此不知道 A 和 C 在说什么。 [goto=pzzl2]2[/goto]、B 不知道怎样加密，无法制造能够让 C 解密的密文，因此无法伪装成 A。[/content][/toggle]。 看上去问题完美地解决了，对吗？没这么简单。 [toggle=on] [title]对称加密有其局限[/title] [content]对称加密虽然解决了前面的两个问题，却带来新问题： [a=newpzzl1]加解密算法得以实现，依赖于 A 与 C 的单独协商，这与前面说的 [goto=situation]A 与 C 通信必须经过 B[/goto] 的前提矛盾。即使这种单独协商偶尔可以实现，它的机会也必定十分稀缺。如果需要与 C 通信的不止一个 A，而是 A[sub]0[/sub]、A[sub]1[/sub]……A[sub]n[/sub]，每个 A[sub]i[/sub] 都要避开其它所有节点与 C 单独协商，这是不现实的。 如果让这些 A[sub]0[/sub]、A[sub]1[/sub]……A[sub]n[/sub]都使用同样的算法呢？显然，每个 A[sub]i[/sub] 都会知道它不该知道的信息，也可以冒充其它 A[sub]i[/sub] 发送信息[toggle=off] [title][sup][且][/sup][/title] [content]在真实环境中，C 也不是一个 C，而是一组 C[sub]0[/sub]、C[sub]1[/sub]……C[sub]n[/sub]，而且 C[sub]i[/sub] 也要向A[sub]i[/sub] 发送信息。或者说，任意两个节点都有双向通信的需要。[/content][/toggle]。 [a=newpzzl2]所以，每两个节点之间要有一套专用的加解密算法，如果一个网络上有 N 个节点，一共要有 N *（N－1）／2 套算法。对于动辄成千上万个节点的网络，这个数字太大了。 [/content][/toggle]。因此，[toggle=on] [title]非对称加密闪亮登场[/title] [content]人们发现，前述问题的症结在于[goto=prisec]对称[/goto]。如果加密算法和解密算法无法互相推导，事情就好办了： 所有发给 C 的信息都用同样的加密算法，而只有 C 自己才能解密。A[sub]i[/sub] 虽然懂得加密，但并不能从加密算法推导出解密算法来。因此一个 A[sub]i[/sub] 发给 C 的信息不会泄露给其它 A[sub]i[/sub]，就连加密者自己也不会解密。 现在，对于每个节点，只要制作一套加解密算法，解密算法自己留着，将加密算法公布出去：谁想发消息给我就用这个方法加密，加密之后只有我能解密，别人谁也解不出来。 加密算法是公开的，大家都知道，不需要与每个节点单独协商了。（解决了[goto=newpzzl1]一个大问题[/goto]） 而且，在有 N 个节点的网络上，只要有 N 套加解密算法就已足够。（又解决了[goto=newpzzl2]一个大问题[/goto]） [/content][/toggle] [toggle=off] [title]延伸阅读[/title] [content]请看[guide=5642779036221440]飘论坛[/guide]怎样应用非对称加密实现一个安全、健壮的 P2P 论坛。 [/content][/toggle] 非对称加密看上去很美。那么，加密和解密互为逆运算，两种算法却不能互相推导，真有这样的算法吗？谢天谢地，[goto=rsa]这是真的[/goto]。 [/content][/toggle] [toggle=off] [title]二、RSA 算法开始工作[/title] [content][a=rsa]RSA 既不是惟一，也不是最早的非对称加密算法。但它是使用最广泛，因而也是最重要的非对称加密算法。 RSA 算法的实质是三个自然数，一般记作 n, d, e。n 和 d 构成一个密钥，n 和 e 构成另一个密钥。 对于（n, d）与（n, e）这两个密钥，无论用哪个密钥加密出来的密文都可以用另一个密钥解开， 所以不必强调哪个用于加密，哪个用于解密，只要把一个公布出去（称为[b]公钥[/b]），另一个自己藏着（称为[b]私钥[/b]）就行了。 [toggle=off] [title]加解密算法[/title] [content]现在，我告诉你我的公钥是（n = 899，e = 37），如果你想传一个自然数 X（明文）给我，加密算法是求这个数的 37 次幂除以 899 的余数。 [div=#ffffcc][size=1.3]加密：Y＝X[sup]e[/sup] % n＝X[sup]37[/sup] % 899[/size][/div] 把这个余数 Y（密文）告诉我，我就能算出你想传给我的数了。 余数（密文）是 737？明文一定是 12。 密文是 121？明文一定是 100。 你想破了头也不知道我是怎么算出来的吧？其实很简单，在 n, d, e 这三个数里，我告诉了你 n 和 e，还有一个 d 不能让你知道，d 是 613。 解密过程与加密过程相似，只是用 d 代替了 e。把你给我的密文取 613 次幂再除以 899，余数就是明文了。 [div=#ffffcc][size=1.3]解密：X＝Y[sup]d[/sup] % n＝Y[sup]613[/sup] % 899[/size][/div] 别人不知道 d = 613，就没办法解密。 对于所有小于 899 的明文 X，这个算法都是有效的[toggle=off] [title][sup][注][/sup][/title] [content]证明过程在[goto=math]后面[/goto]。[/content][/toggle]。 当然，加密密钥和解密密钥可以互换。比如明文 12 用（n, d）加密： 12[sup]613[/sup] ％ 899 ＝ 389[toggle=off] [title][sup][怎么算？][/sup][/title] [content]12[sup]613[/sup] 肯定是个天文数字。而真实的应用场景中，n 并不能用 899 这样小的数字，这样太容易破解。真实场景中的 n 至少需要 1024 位二进制数，相当于 307 位以上的十进制数。d 和 e 也随之增大，以它们作指数，计算乘方的结果是难以想象的大。 幸好我们有简便算法，计算 12[sup]613[/sup] 并不需要将 12 自乘 613 次。我们可以快速算出 12[sup]2[/sup]，12[sup]4[/sup]，12[sup]8[/sup][toggle=off] [title][sup][注][/sup][/title] [content]12[sup]4[/sup]＝（12[sup]2[/sup]）[sup]2[/sup] 12[sup]8[/sup]＝（12[sup]4[/sup]）[sup]2[/sup] [/content][/toggle]……显然： 12[sup]613[/sup]＝12[sup]512[/sup] * 12[sup]64[/sup] * 12[sup]32[/sup] * 12[sup]4[/sup] * 12 而且，我们不是先算出 12[sup]613[/sup] 的值再对 899 求余数，而是每作一次乘法都将结果除以 899，只留下余数继续作后面的乘法运算。这样就能避免过大的中间结果。[toggle=off] [title][sup][如][/sup][/title] [content]你小时候一定做过这样的数学题： 3[sup]1992[/sup] 的个位数字是____？ 你可以算出它的个位数字是 1，但并不知道 3[sup]1992[/sup] 本身是多少。 [/content][/toggle] 有了上述简便算法，看似直达宇宙热寂的巨数乘方求余就能迅速实现了。 [/content][/toggle]，这是密文。 解密时要用（n, e）： 389[sup]37[/sup] ％ 899 ＝ 12，明文又还原出来了。[/content][/toggle] 读到这里，你一定想[toggle=off] [title]自己动手试一试[/title] [content]如果你的电脑里有 Python[toggle=off] [title][sup][没有？][/sup][/title] [content]可以去[url=http://www.python.org/downloads/]这里[/url]安装。[/content][/toggle]，作这个测试很简单： 1、打开 Python 命令窗口； 2、选择一个比 899 小的明文 X，例如 127； 3、在 Python 命令窗口输入： [div=#ffffcc]>>> pow( 127, [size=1][a=ehere]37[/size], 899 )[toggle=off] [title][sup][注][/sup][/title] [content]pow( a, b, c ) 就是计算 a[sup]b[/sup] % c。[/content][/toggle] 234[/div] 加密时用 [goto=ehere]e[/goto]，得到 234 就是密文 Y。再输入： [div=#ffffcc]>>> pow( 234, [size=1][a=dhere]613[/size], 899 ) 127[/div] 解密时用 [goto=dhere]d[/goto]，明文又回来了。 4、你可以不用（899，37，613）这一组密钥，换成这些试试：（1081，53，401）、（1147，29，149），都可以用。 [/content][/toggle]。 [toggle=off] [title]实际应用概述[/title] [content][toggle=off] [title]实际的加密[/title] [content]从前面的例子可以看出，如果 RSA 密钥中的 n 是 899，它就只能对 899 以下的自然数加密[toggle=off] [title][sup][？][/sup][/title] [content]解密的时候是把密文的 d 次幂除以 n，余数为明文，因此明文必然也必须小于 n。[/content][/toggle]，[a=long]这是非对称加密的一个局限。假如我们要加密的是一大段文字，将它转成数字之后有几百万位，难道要专门构造一个比它还长的密钥吗？即使算出这样大的密钥，用它作乘方运算也必定极其困难。 你可能想到，将这一大段内容分成小段，对每一小段分别加密。这是可行的，但由于 RSA 加密毕竟比较慢，现实中入往往采用对称加密与非对称加密相结合的做法： [div=#ffffcc]1、生成一个随机数 R，用它对这一大段内容作[b]对称加密[/b]。 假设这个算法很简单，就是将明文 X 乘以 R 得到密文 Y。注意，与之前讨论过的简单对称加密不同，这个 R 是临时生成的，并没有事先交给接收方。 2、用接收方的 RSA 公钥对 R 加密，得到密文 S。[/div] 将 S 和 Y 一同传给接收方。接收方收到之后作如下处理： [div=#ffffcc]1、用自己的 RSA 私钥解密 S，得到 R。 2、用 R 解密 Y，得到 X。[/div] 解密完毕。 [/content][/toggle] [toggle=off] [title]签名[/title] [content]前述加密方法解决了[call=sec]两个基本问题[/call]之一，还有一个 B 可能冒充 A 的问题。为了防止冒充，A 需要对自己发出的信息作一个[b]签名[/b]。 非对称加密签名很简单，只要发送方用自己的私钥加密信息，接收方再用发送方的公钥解密，就行了[toggle=off] [title][sup][注][/sup][/title] [content]由于发送方的公钥是公开的，谁都可以解密这段密文，因此，签名过程并不能自然地达到加密的效果。如需加密，[goto=signsec]另做[/goto]。[/content][/toggle]。 因为只有以发送方的私钥加密的信息才能被发送方的公钥解开，所以接收方一旦解密成功，就能确认信息的来源。 当然，信息较长时同样遇到[goto=long]加密不便[/goto]的问题。对此，除了前述加密过程中使用的方法，[toggle=on] [title]签名过程还有更简单的[/title] [content][div=#ffffcc][a=sign]1、发送方 A 对长信息 X 作[wiki=zh]杂凑[/wiki]（md5、sha1 等）运算，得到运算结果 K。 2、A 用发送方的私钥加密 K，得到密文 S。[/div] 将 S 和 X 一同传给接收方 C[toggle=off] [title][sup][需要加密？][/sup][/title] [content][a=signsec]如果发送过程需要加密，就用接收方公钥加密 X，再把密文和 S 一同发出去。[/content][/toggle]。C 收到之后作如下处理： [div=#ffffcc]1、同样对 X 作杂凑运算，得到结果 K‘。 2、用 A 的公钥解密 S，得到 K。 3、检验 K 与 K‘ 是否相同。若相同，即可确认信息来自 A。[/div][/content][/toggle]。 [/content][/toggle] [toggle=off] [title]中间人攻击和 SSL 证书[/title] [content]你可能想到了，前述非对称加密过程有一个弱点，就是传送公钥不安全。 在[call=sec]上图[/call]里，C 要把它的公钥交给 A，也只能经过 B，如果 B 把自己的公钥冒充是 C 的公钥交给 A，就能知道每次 A 发给 C 的信息了。 这就是[wiki=zh]中间人攻击[/wiki]。 为了应对中间人攻击，需要确保 C 发来的公钥的真实性。但在此之前 A 没有 C 的公钥，[goto=sign]前面的签名方法[/goto]不适用。 在 web 访问中，通常用 [b]SSL 证书[/b]做到这一点。 有一个国际数字证书认证机构，叫做 CA，会对每个提供 SSL 加密访问[toggle=off] [title][sup][注][/sup][/title] [content][wiki=zh]SSL[/wiki] （Secure Socket Layer）是非对称加密在 web 上的一种应用。 如果你使用的网站地址前面是 https:// ，就是在通过 SSL 访问了。[/content][/toggle]的网站的公钥作一个签名认证。用户的浏览器事先内置了 CA 的公钥，每次收到目标网站传来的公钥，就用 CA 的公钥检验一下目标网站的公钥是否可靠。如果验证不通过，浏览器会发出警告。 如果你打开的是网上银行、邮箱之类的重要网站，一旦看到这个警告要马上离开。如果你打开的是一些个人小网站，它可能没有向 CA 申请过认证，而即使受到中间人攻击也不会蒙受什么损失，你可以继续访问有警告的网站。 [/content][/toggle] [/content][/toggle] RSA 完美地实现了非对称加密的目标。那么，它的三个数字 n, d, e 是[goto=rsa_nde]怎么计算出来的呢[/goto]？ [/content][/toggle] [toggle=off] [title]三、RSA 获得密钥[/title] [content][a=rsa_nde]要生成一对 RSA 密钥，具体地说就是 n, d, e 这三个数，其实很简单。步骤如下： [div=#ffffcc][a=got_n]1、选择两个质数 p 和 q，它们的乘积就是 n。 我选择 p = 29, q = 31, 则 n = p * q = 899。 [a=got_fi]2、计算 φ = ( p - 1 ) * ( q - 1 )。 即，φ = ( 29 - 1 ) * ( 31 - 1 ) = 840。 3、[a=got_e]再选择一个比 φ 小且与 φ 互质[toggle=off] [title][sup][？][/sup][/title] [content]互质：如果两个自然数，除了 1 没有其它的公约数，称这两个数互质。[/content][/toggle]的数，作为 e。 我选择 e = 37。 4、[a=got_d]找到一个数 d，使 e * d % φ = 1。 我用程序算的，算出来最小的 d 就是 613。[/div] 现在，我得到了 [goto=got_n]n[/goto], [goto=got_d]d[/goto], [goto=got_e]e[/goto] ，把 p 和 q 扔掉，（n, e）作公钥，（n, d）作私钥，就可以执行 RSA 加密运算了。 [toggle=off] [title]RSA 的安全性分析[/title] [content]我把（899, 37）作为公钥发出去了，看到这个公钥的人一定不能算出 d 值吗？ 由[goto=got_d]上面的密钥算法[/goto]可知，要算出 d，必须先知道 φ。 那么由 n 和 e 能算出 φ 来吗？[goto=got_e]e 是随便选的[/goto]，只须考虑 n。 n = p * q φ = ( p - 1 ) * ( q - 1 ) = n - p - q + 1 如果不知道 p 和 q，就不可能从 n 算出 φ。 那么将 n 分解质因数，不就能得到 p 和 q 了吗？幸好，这个运算虽然能够成立，将 899 分解为 29 * 31 也不太难，但对于一个实际使用的 1024 位或者更大的 n，计算的速度会慢到无法实现。[toggle=off] [title][sup][注][/sup][/title] [content]为了不易破解，选择 p, q, e 时还有一些规则，详见[url=http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95#.E5.AF.86.E9.92.A5.E7.94.9F.E6.88.90]维基百科[/url]。 [/content][/toggle] 例如，n = 186506401784256749805468037221367015183 你能分解它吗？这个 n 还只是 128 位的。 2009年12月12日，一个二进制 768 位，十进制 232 位的 n 被成功分解了。这是有公开报道的被分解的最大的 n。所以，现在的 RSA 密钥至少需要 1024 位，重要的密钥最好是 2048 位。只要长度足够，RSA 仍然安全。 [/content][/toggle] RSA 的算法已经很清楚了。如果你还想知道算法背后的数学原理，请看[goto=math]下一节[/goto]。 [/content][/toggle] [toggle=off] [title]四、RSA 算法原理[/title] [content][a=math]RSA 算法是基于[toggle=on] [title]欧拉函数[/title] [content]前面讲[goto=got_fi]生成密钥方法[/goto]的时候，你也许有过疑惑， φ = ( p - 1 ) * ( q - 1 ) 这里为什么要用一个希腊字母呢？ 因为在数学里， φ 表示[wiki=zh]欧拉函数[/wiki]。它的含义并不复杂，φ（N）表示在所有比 N 小的自然数中，与 N 互质的一共有多少个。 例如，φ（9）＝6，比 9 小的数里有 1，2，4，5，7，8 六个与 9 互质。而 φ（8）＝4，φ（7）＝6。 对于 RSA 用到的 [goto=got_n]n = p * q，（p, q 是质数）[/goto]，φ（n） = ( p - 1 ) * ( q - 1 )[toggle=off] [title][sup][证明][/sup][/title] [content]比 n 小的自然数一共是 n - 1 个。先看其中有多少个与 n 不互质。 由于 n 的质因数只有 p, q 两个，如果一个数与它有公约数（不互质），公约数非 p 即 q，则此数或为 p 的倍数，或为 q 的倍数。 在 1 到 n - 1 里，p 的倍数有 p, 2p, 3p……（q - 1）p，共 q - 1 个。 类似地，在 1 到 n - 1 里，q 的倍数有 q, 2q, 3q……（p - 1）q，共 p - 1 个。 由于 p, q 互质，n = pq 是它们的最小公倍数，在比 n 小的数里，p 的倍数和 q 的倍数没有交集。 因此，在比 n 小的数里，与 n 不互质的一共有 （q - 1）+（p - 1）个。 于是，在比 n 小的数里，与 n 互质的一共有 （n - 1）-（q - 1）-（p - 1）= pq - p - q + 1 = （q - 1）*（p - 1）个。 这就是 φ（n）。 [/content][/toggle]。 例如，φ（3）＝2，φ（5）＝4[toggle=off] [title][sup][注][/sup][/title] [content]对于一个质数 p，它的欧拉函数 φ（p）一定是 p - 1，因为比它小的数必然全都与它互质。[/content][/toggle]，则 φ（15）＝8。与它互质的是 1，2，4，7，8，11，13，14。 因此，φ = ( p - 1 ) * ( q - 1 ) 里的 φ 实际是 φ（n），也就是 φ（p * q )。[/content][/toggle]和[toggle=on] [title]欧拉定理[/title] [content][b][a=euler]如果 x 与 n 互质，有 x[sup]φ（n）[/sup]% n = 1[/b] 对它的证明见[url=http://baike.baidu.com/view/48903.htm]百度百科[/url]（费马-欧拉定理）。 [/content][/toggle]设计出来的。 [toggle=off] [title]RSA 加解密的数学证明[/title] [content]设明文为 X，密文为 Y，解密得到的明文为 Z，加密过程为： [size=1.3][a=p0]Y = X[sup]e[/sup] % n （X < n）[/size] 解密过程为： [size=1.3][a=p1]Z = Y[sup]d[/sup] % n[/size] 如果能证明在 [size=1.3]e * d % φ（n）= 1[a=p2][/size] 的前提下，Z ＝ X，就说明加解密的过程正确。[hr] 证明： [bird=mod|display=none][b]定理[/b] 对于自然数 a, b, c, d, e，如果 a % e = b, c % e = d，则 ac % e = bd % e。 [toggle=off] [title]证明[/title] [content]设 a = ke + b, c = me + d，则： ac = kme[sup]2[/sup] + bme + dke + bd ＝ [size=1][a=first]e * （kme + bm + dk）[/size]+ bd [goto=first]前一项[/goto]是 e 的倍数，因此： ac % e = bd % e [/content][/toggle] 由此可得[b]推论一[/b]：对于自然数 a, b, e, k，如果 a % e = b,  则 a[sup]k[/sup] % e = b[sup]k[/sup] % e。 [b]推论二[/b]：对于自然数 a, e, k 和整数 b，有 （a + be）[sup]k[/sup] % e = a [sup]k[/sup] % e。 [/bird] 先引入[call=mod]一个定理[/call]。 [div=#ffffcc]在下面证明过程中，若无特别说明，用到的 g, i, j, k, m, r  等均为整数。[/div] 由[goto=p0]加密过程[/goto]，设 Y + k * n ＝X[sup]e[/sup]，即 [size=1][a=p3]Y = X[sup]e[/sup] - k * n[/size]。 代入[goto=p1]解密过程[/goto]，得到 [size=1][a=p4]Z = （X[sup]e[/sup] - kn）[sup]d[/sup] % n[/size]。 由[call=mod]右面定理[/call]的推论二，（X[sup]e[/sup] - kn）[sup]d[/sup] % n＝（X[sup]e[/sup]）[sup]d[/sup] % n，[goto=p4]上式[/goto]即变为： [size=1.3][a=p5]Z = X[sup]ed[/sup] % n[/size] 由[goto=p2]密钥生成过程[/goto]，设 ed =  k * φ（n）+ 1，[goto=p5]上式[/goto]变为： [size=1.3][a=p6]Z = X[sup]kφ（n）+ 1[/sup] % n[/size] 之后分两种情况考虑： [select=1] [choice=on][title]当 X 与 n 互质[/title][content] 由[goto=euler]欧拉定理[/goto] X[sup]φ（n）[/sup] % n = 1，设 [size=1.3]X[sup]φ（n）[/sup] = m * n + 1[a=p7][/size] ，先将[goto=p6]上式[/goto]变为： [size=1.3][a=p8]Z = （X[sup]φ（n）[/sup]）[sup]k[/sup]  * X % n[/size] 再代入[goto=p7]刚才的假设[/goto]，得到： [size=1.3][a=p9]Z = （m * n + 1）[sup]k[/sup]  * X % n[/size] 再变为： [size=1.3]Z = [size=1]（（m * n + 1）[sup]k[/sup] % n ）[a=p10][/size]* （X % n ）% n[/size] 由[call=mod]右面定理[/call]的推论一，[goto=p10]前一项[/goto]的值是 1。因此，得到： [size=1.3]Z = X % n [/size] 由于 [goto=p0]X < n[/goto]，所以 Z ＝ X。 [/content][/choice] [choice][title]当 X 与 n 不互质[/title][content]由于 n 是两个质数 p, q 的乘积，X 与 n 不互质，则 X 与 n 的公约数不是 p 就是 q。 假定公约数是 p（是 q 的情况与此类似），设 X ＝ k * p，由于 X < n，即 kp < pq，因而 k < q，又由于 q 是质数，因此 k 与 q 互质，X 也与 q 互质。 由[goto=euler]欧拉定理[/goto] X[sup]φ（q）[/sup] % q = 1，而对于质数 q，φ（q）= q - 1，得到 [size=1.3][a=p11]X[sup]q - 1[/sup] % q = 1[/size] 由[call=mod]右面定理[/call]的推论一， [size=1.3][a=p12]（X[sup]q - 1[/sup]）[sup]i[/sup]  % q = 1[/size] 由 [goto=p2]e * d % φ（n）= 1[/goto]，即 e * d % (( p - 1 )( q - 1 ))= 1，设 ed - 1 = m（p - 1）（q - 1），在[goto=p12]上式[/goto]中令 i = m（p - 1），得到： X[sup]m（p - 1）（q - 1）[/sup] % q = 1，即 X[sup]ed - 1[/sup] % q = 1 再变为： [size=1.3]X[sup]ed[/sup] % q = X ％ q[/size] 令 X[sup]ed[/sup] ＝ j * q + X，则 jq = X *（X[sup]ed - 1[/sup] - 1）。由于 X ＝ k * p，故 j 必是 p 的倍数，设 j = r * p，变为： X[sup]ed[/sup] ＝ rpq + X，即 X[sup]ed[/sup] ＝ r * n + X，故： [size=1.3]X[sup]ed[/sup] ％ n = X[/size] 将之代入[goto=p5]前面的式子[/goto] Z = X[sup]ed[/sup] % n，得到： Z = X [/content][/choice] [/select] 证明完毕。 [/content][/toggle] [/content][/toggle]