推举实验
学习链接：http://www.hetianlab.com/AllExperiments.jsp
一、预备知识
1、費馬小定理： 若p是質數且a是與p互質的整數，則
例如p=3,a=2,则2^(3-1)=4，4==1 （mod 3)，便是这个道理，详细可以拜会数论基本知识。
2、 中国剩余理论（Chinese Remainder Theorem ）
中国有一本数学古书《孙子算经》有这样的记载：
「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」
答曰：「二十三」
术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」
孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人创造得比西方早，以是这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中霸占一席非常主要的地位。它揭示了这样两个别系的同等性：一是模两两互质的一组数的同余方程组，二是模它们的乘积的方程。
中国剩余定理的内容如下：
令n=n1n2...nk，个中ni是两两互质的数，则对0<=a<n与0<=ai<ni且ai=a mod ni，a与(a1,a2...,ak)之间有一种逐一对应的关系，统统对a的操作均可被等价的转换为对对应k元组中的每一元进行同样的操作。因此我们可以将一种表达经由大略的转换后得出另一种表达，个中从a到(a1,a2...,ak)的转换十分随意马虎，而从(a1,a2...,ak)推得对应的a则要轻微繁芜一些。
首先定义mi=n/ni(i=1,2...k)，则mi是除了ni以外的所有nj的乘积，接下来令ci=mi与模n意义下mi的逆元的积，则a为(a1c1+a2c2+...+akck) (mod n)。
例如我们已知a模5余2且模13余3，那么a1=2,n1=m2=5,a2=3,n2=m1=13，则有c1=13(2 mod 5)=26，c2=5(8 mod 13)=40，以是a=(226+340)（mod 65)=42。
二、RSA算法 :
它是第一个既能用于数据加密也能用于数字署名的算法。它易于理解和操作，也很盛行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一贯未能得到理论上的证明。它经历了各种攻击，至今未被完备攻破。
首先, 找出三个数, p, q, r,
个中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数......
p, q, r 这三个数便是 private key
接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1).....
注：意思是rm除以(p-1)(q-1)的余数=1
这个 m 一定存在, 由于 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了.....
再来, 打算 n = pq.......
m, n 这两个数便是 public key
编码过程是, 若资料为 a, 将其算作是一个大整数, 假设 a < n....
如果 a >= n 的话, 就将 a 表成 s 进位 (s <= n, 常日取 s = 2^t),
则每一位数均小於 n, 然後分段编码......
接下来, 打算 b == a^m mod n, (0 <= b < n),
注：^表示次方，不要理解为C#中的XOR
b 便是编码後的资料......
解码的过程是, 打算 c == b^r mod pq (0 <= c < pq),
於是乎, 解码完毕...... 等会会证明 c 和 a 实在是相等的 :)
如果第三者进行窃听时, 他会得到几个数: m, n(=pq), b......
他如果要解码的话, 必须想办法得到 r......
以是, 他必须先对 n 作质因数分解.........
要防止他分解, 最有效的方法是找两个非常的大质数 p, q,
使第三者作因数分解时发生困难.........
<定理>
若 p, q 是相异质数, rm == 1 mod (p-1)(q-1),
a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq,
则 c == a mod pq
证明的过程, 会用到费马小定理, 阐述如下:
m 是任一质数, n 是任一整数, 则 n^m == n mod m
(换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m)
利用一些基本的群论的知识, 就可以很随意马虎地证出费马小定理的........
<证明>
由于 rm == 1 mod (p-1)(q-1), 以是 rm = k(p-1)(q-1) + 1, 个中 k 是整数
由于在 modulo 中是 preserve 乘法的
(x == y mod z and u == v mod z => xu == yv mod z),
以是, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq
1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时,
则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q
以是 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1)+1) == a mod pq
2. 如果 a 是 p 的倍数, 但不是 q 的倍数时,
则 a^(q-1) == 1 mod q (费马小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1)+1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod p
=> p | c - a
以是, pq | c - a => c == a mod pq
3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上
4. 如果 a 同时是 p 和 q 的倍数时,
则 pq | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
Q.E.D.
这个定懂得释 a 经由编码为 b 再经由解码为 c 时, a == c mod n (n = pq)....
但我们在做编码解码时, 限定 0 <= a < n, 0 <= c < n,
以是这便是说 a 等於 c, 以是这个过程确实能做到编码解码的功能.....
三、RSA 的安全性
RSA的安全性依赖于大数分解，但是否等同于大数分解一贯未能得到理论上的证明，由于没有证明破解RSA就一定须要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修正成为大数分解算法。
目前， RSA 的一些变种算法已被证明等价于大数分解。不管若何，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因详细适用情形而定。
四、RSA的速率
由于进行的都是大数打算，使得RSA最快的情形也比DES慢上倍，无论是软件还是硬件实现。速率一贯是RSA的毛病。一样平常来说只用于少量数据加密。
五、RSA的选择密文攻击
RSA在选择密文攻击面前很薄弱。一样平常攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经由打算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法构造：
( XM )^d = X^d M^d mod n
前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特色--每个人都能利用公钥。但从算法上无法办理这一问题，紧张方法有两条：一条是采取好的公钥协议，担保事情过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息署名；另一条是决不对陌生人送来的随机文档署名，署名时首先利用One-WayHashFunction 对文档作HASH处理，或同时利用不同的署名算法。在中提到了几种不同类型的攻击方法。
六 、RSA的公共模数攻击
若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情形是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到规复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：
C1 = P^e1 mod n
C2 = P^e2 mod n
密码剖析者知道n、e1、e2、C1和C2，就能得到P。
由于e1和e2互质，故用Euclidean算法能找到r和s，知足：
r e1 + s e2 = 1
假设r为负数，需再用Euclidean算法打算C1^(-1)，则
( C1^(-1) )^(-r) C2^s = P mod n
其余，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者打算出其它成对的e’和d’，而无需分解模数。办理办法只有一个，那便是不要共享模数n。
RSA的小指数攻击。 有一种提高 RSA速率的建议是使公钥e取较小的值，这样会使加密变得易于实现，速率有所提高。但这样作是不屈安的，对付办法便是e和d都取较大的值。
RSA算法是第一个能同时用于加密和数字署名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的磨练，逐渐为人们接管，普遍认为是目前最精良的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大毛病是无法从理论上把握它的保密性能如何，而且密码学界多数人士方向于因子分解不是NPC问题。
RSA的缺陷紧张有：A)产生密钥很麻烦，受到素数产生技能的限定，因而难以做到一次一密。B)分组长度太大，为担保安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速率较慢，较对称密码算法慢几个数量级；且随着大数分解技能的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET( Secure Electronic Transaction )协议中哀求CA采取比特长的密钥，其他实体利用比特的密钥
出自：博客园
原文链接：http://www.cnblogs.com/midea0978/articles/65244.html
