写教程,改变世界


3 推荐

作者:远山
2015-05-17 06:25:01
标签:RSA, 加密
有效阅读:1192
点击量:13870

免责声明:本站(guideep)之内的所有教程概由作者自由创作并承担全部责任。教程的内容和观点未经 guideep 审核。读者在阅读过程中应自行鉴别其是否真确、有效或安全。
特别地,如果教程内容涉及化学、生物、高压电气、放射性、医疗、气功、宗教、运动等可能造成严重后果的领域,请读者慎重鉴别,切勿盲目学习。
本站不对学习造成的后果承担任何责任。

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]
uu

对本段内容的讨论

点击书签可编辑,清空即删除。