以前写过一个对称加密和攻击案例分析，而对非对称加密，虽然接触时间不长，但一直没有

很系统的记录。所以趁国庆节快要休假的时候，来好好回顾总结一下。

 

 

网站安全序言
 

实际上，从加密定语可以看出，对称加密意味着通信双方具有相同的信息(即信息对称)。资讯可

为预先分享的密钥(PSK)或预先商定的解码方法(例如凯撒密码)。不对称加密技术把信息分成两

个部分，即秘钥A和秘钥B，由秘钥A加密的信息可由秘钥B解密，由秘钥加密的信息也可由秘钥

a解密。这种密钥对一般被称为公钥和私钥，公钥对外公布，私钥自己保留，从而在信息不对称

的情况下实现加密和认证。

 

 

不对称加密有许多实现方法，而且大多依赖于复杂的假设(hardnessassumptions)。在不变的时

间内，根据已知不可解的难题，将问题的答案分成不同的因子，分别构成对应于非对称密码算

法的公钥和私钥。比如RSA基于大素数分解问题，DSA基于离散对数问题，等等。这篇文章主

要讨论RSA不对称加密。

 

 

RSA原则第一批公开密钥加密系统之一应该是RSA，它的名字是三个发明者的首字母缩写名(R

ivest–Shamir–Adleman)。该算法所基于的难题假设是一个质数分解问题，在此之前，先简单

介绍一下所涉及的数学基础。

 

 

Ora函数：φ(n)，表示整数中比n小的正整数中与n互质的数字。若n可以写成乘2个不同质数p和

q的积，则φ(n)=(p-1)(q-1)。验证：略。同余：给定一个正整m，如果a和b的两个整数满足(a-b

)被m整除，则称为a和b的对模m同余，并记作a,b,modm，其中，a,b是同余符号。同余的二数

具有一些有趣的性质，如反身、对称、传递等，详见《数论》。反模式元素：又称为反模式(

模式)。对于整数a，其逆元是整数x，它满足ax=1(modm)，其中m=modulus。Ora公式：如果

a和n是互为质数，那么a^φ(n)=1(modn)，证明：引用拉格朗日定理。lcm:leastcommonmultip

le，公倍数最少。gcd:greatestcommondevisor，公约的最大数目。互质数：co-prime，两个

正整数a,b，互质数表示能同时被其整除的数只有1，也就是gcd(a,b)=1。

 

 

 

密钥的组成。在上述数学基础上，再来看看RSA公私密钥的构成和生成过程。密钥生成主要有

以下几个步骤，实际上每个步骤都有实际的注意事项，下面我们分别来看。发现p和q是两个不

同的质数，可以用它的乘积n=pq来计算φ(n)，因为p和q都是质数，所以根据欧拉定理，选择

了φ(n)=lcm(p-1,q-1)整数e，并且满足1，从以上数字中选取出构造不对称加密的元素：公共密

钥(n,e)私有密钥(n,d)e和d分别是公钥和私钥的核心，两者互为模逆元。通过公钥e推算出私钥

d，需要知道φ(n)；而对于φ(n)=(p-1)(q-1)，则需要知道p和q；公私密钥均已知n=pq，因此这

是难题假设的关键：当n为大时，很难计算出相应的p和q。