公钥密码学应用场景
公钥密码体系又称为非对称密码，即加密和解密算法使用不同的密钥：一个是公钥Pu、一个是私钥Pr。公钥密码学的应用场景有：
- 加密和解密 发送方使用接收方的公钥加密，接收方使用对应的私钥解密。这样只有私钥的拥有者能解密，这样就保证了消息的私密性
- 数字签名 发送方使用私钥做签名。消息接收者根据对应的公钥进行签名验证。由于只有消息发送方拥有私钥、生成签名，因此签名验证成功后表明此消息确实由发送方发送过（注意，是发送过，而非消息来源是发送方）。数字签名解决了发送方否认问题。
- 密钥协商 双方能够安全地交换彼此共享的秘密信息，作为后续对称加密所使用的密钥。常用的有基于离散对数的Diffie-Hellman交换和基于椭圆曲线算法的ECDH算法，这里暂时不涉及。
RSA中的数论知识
RSA依赖数论中的一些知识：
- 乘法逆元 对于互素的两个正整数a, n，根据扩展欧几里得算法，总存在正整数b，使得 \(a*b=1(mod n)\)
- 欧拉定理 对于正整数a, n，phi(n)为n的欧拉函数（小于n且与之互素的所有正整数的个数），则有： a^{phi(n)+1}=a(mod n)
- 离散对数难题： 对于正整数a, n, x, y，已知a, n, x，正向求幂y=a^x(mod n)是容易的，反之，求指数x在计算上是困难的；这个性质在RSA签名中得到应用。
- 大素数分解难题，已知两个大素数p,q，求其乘积n=p*q是容易的，而已知n，求其素因子p,q是困难的。
其中计算乘法逆元时的欧几里得算法在计算上是容易的，通常将a对n取模的逆元写成b=a^(-1)(mod n).
此外，根据欧拉定理，还可进一步得到推论：对于正整数a, n, k，phi(n)为n的欧拉函数，有：a^(k*phi(n)+1)=a(mod n)，这一推论可用于RSA加密和解密过程。
RSA密钥生成
RSA算法是基于大素数分解难题，即已知两个大素数p,q，求其乘积n=p*q是容易的，而已知n求其素因子p,q是困难的。基于此，RSA算法按如下过程生成私钥和公钥：
- 选定两个大素数p,q，这两个素数是私密的；
- n = p*q，这个乘积n可以公开；
- 随机选定e满足gcd(phi(n), e) = 1 ，其中phi(n)=(p-1)*(q-1), 为n的欧拉函数。e的选取是公开的；
- 根据欧几里得算法求d = e^(-1) (mod phi(n))，d私密
- 最后一步，销毁大素数p,q
最终生成公钥Pu={e, n}，私钥Pr={d, n}。
RSA加密过程
加密和解密的场景为：对于明文M，Bob使用Alice的公钥加密消息发往Alice；Alice根据自己的私钥解密消息，得到明文。RSA中的过程如下：
- 对于明文M，Bob根据Alice的公钥Pu={e, n}进行加密运算，得到密文C=M^d(\bmod n)
- Alice收到密文后，根据自己的私钥Pr={d, n}进行解密运算，C’=C^d=M^{d*e}(\bmod n)
由于d = e^(-1) (mod phi(n))，则必有de=kphi(n)+1，k为正整数。则根据之前的推论，有： C’=M^(de)(mod n)=M^(k*phi(n)+1)=M(mod n)
至此密文被解密为原来的明文M。值得一提的是，实际中的明文通常为字符串，在应用RSA算法时，需要将字符串映射为整数。
攻击者想得到明文，则必须得到私钥d，这等价于求得phi(n)，无异于想分解n为两个大素数这一大素数分解难题。
RSA签名过程
签名的场景为发送方Alice使用私钥做签名，附带着消息原文M发送。所有的接收者都可以使用Alice公开的公钥对签名进行验证。
Alice生成签名的过程如下：
- Alice对消息原文M进行Hash运算，得到消息的摘要H=Hash(M)
- Alice根据自己的私钥d对消息摘要进行签名S=H^d(mod n)
-
Alice将签名附在消息原文后，一起发送出去，消息为(M S)
接受者Bob收到消息后的签名验证过程如下：
- Bob收到消息后根据Alice的公钥e对签名S进行验证，验证结果为H’=S^e(mod n)
- Bob对接收的消息原文M进行Hash计算，得到消息的摘要H=Hash(M)
- 根据欧拉定理的推论，自然有H’=H，此时可以认定签名来自Alice，且消息M未经篡改
上面的签名过程，事实上解决了发送方否认问题和消息完整性两个问题：
- 消息接受方Bob用Alice分发的公钥确实能够解开签名，Alice无法否认这条消息，这就保证了消息中所声称的身份（Alice）是真实可靠的。
- Hash函数的引入，可以保证消息完整、不被篡改，通常使用HMAC——基于MAC消息验证码的Hash函数
签名发送过程中S=H^d(mod n)和H是公开的，攻击者如果想获取私钥d，则必须解开离散对数难题，这在数学上是困难的。
RSA签名仍然不能解决发送方身份可信问题，因为公钥的来源是没有保障的，这就需要引入CA证书机制。因为和RSA算法本身无关，这里就不再赘述。