关键词：对称加密算法，RSA算法，素数（质数），素数分布，数论。
历史
1976年以前，所有的加密方法都是同一种模式：
（1）甲方选择某一种加密规则，对信息进行加密；
（2）乙方使用同一种规则，对信息进行解密。
由于加密和解密使用同样规则（简称"密钥"），这被称为“对称加密算法”（Symmetric-key algorithm）
这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。
1976年，两位美国计算机学家Whitfield Diffie 和Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。意味着加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。
这种新的加密模式被称为"非对称加密算法"。
（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
RSA算法相关
1977年，三位数学家Rivest、Shamir 和Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA，RSA加密算法，是一种非对称加密算法，在公开密钥加密和电子商业活动中被广泛应用。
因数分解决定了RSA算法的可靠性，到目前为止，世界上还没有任何可靠的攻击RSA算法的方式，只有短的RSA钥匙才可能被强力方式解破。长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。同时RSA算法也是素数的经典运用。
因素分解：一个整数分解成多个约数（因数），根据算术基本定理结果是唯一的。如：12=2*3*2；
素数：又称质数，在大于1的自然数中，除了1和它本身以外不再有其他因数，质数的个数是无穷的；
互质：互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形
扩展欧几里得算法：是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
乘法逆元：是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a'=a'×a=e，其中e为该群的单位元。
RSA算法原理
生成公钥和私钥步骤。
1）选择相异素数P、Q，并得到乘积N ，既「N=P*Q」。
2）将P、Q各减1，再互乘，得到数值，既「
=（P-1）（Q-1）」。
3）选择整数E为密钥，使E和互质，且E小于。
4）根据公式DE mod =1，计算出D的值 ，作为另外一个密钥
5）通过以上步骤计算出，N，E，D3个数，N、E为公钥，N、D为私钥。
简单实例
P=3 Q=11
N=P*Q
N=33
=（P-1)(Q-1）=2*10=20
E=7（7<8）
DE mod =1
D*7=1（mod 20）
D=3
公钥（33，7）， 私钥（33，3）
公钥加密
明文 ：M=5
加密：C=（）mod 33=14
密文 ：C=14
私钥解密
密文：C=14
解密 ：M=（）mod 33
M=5
参考：「百度文库」、「RSA算法详解」、「几何原本」「程序员的数学思维修炼」、「RSA算法原理阮一峰」
网友评论