非对称加密（2）非对称加密算法2014-04-24基本流程很简单，那么公钥加密，私钥解密的算法原理到底是什么呢？本节简要阐述RSA算法、DSA算法、ECC算法、Diffie-Hellman算法的基本原理，其中涉及很多数论、离散数学以及解析几何方面的数学知识，感兴趣的读者可以借此加强相关理论基础。RSA算法RSA算法是当前最著名、应用最广泛的公钥系统，1978年由美国麻省理工学院的Ron Rivest、 Adi Shamir 和Leonard Adleman在论文《获得数字签名和公开钥密码系统的方法》中提出的。这是一个基于数论的非对称（公开钥）密码体制，采用分组加密方式。其名称来自于三个发明者的姓名首字母。它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，一个是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接收。为提高保密强度，RSA密钥一般为1024或者2048位。RSA算法的工作原理如下：步骤 1 任意选取两个不同的大质数p和q，计算乘积r=p*q。步骤 2 任意选取一个大整数e，e与（p-1）*（q-1）互质，整数e用做加密密钥。注意：e的选取是很容易的，所有大于p和q的质数都可用。步骤 3 确定解密密钥d： d * e = 1 mod（p - 1）*（q - 1）根据e、p和q可以容易地计算出d。步骤 4 公开整数r和e，但是不公开d。步骤 5 将明文P（P是一个小于r的整数）加密为密文C，计算方法为C = P^e mod r 。步骤 6 将密文C解密为明文P，计算方法为： P = C^d modulo r 。然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。如果你对RSA算法的数学证明感兴趣的话，可以看扩展阅读。扩展阅读 RSA算法的数学证明定理 若 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
易网时代-编程资源站