学习《图解密码技术》补充密码学相关基础知识过程中所做的简单学习笔记，只记录要点，所用图例的来源均为《图解密码技术》一书。
本篇主要参考本书第五章——公钥密码
公钥密码也称非对称加密。
在对称密码中，加密与解密使用的是相同的密钥，所以在传递秘文之外，还需要向接收者传输密钥，这就引入了一个密钥配送的问题。
而如果使用公钥密码，则无需向接收者传输密钥，解决了密钥配送的问题。可以说公钥密码是密码学历史上最伟大的发明。
公钥密码
在公钥密码（public-key cryptography）中，密钥分为加密密钥和解谜密钥两种。加密密钥是发送者加密时使用的，解密密钥则是接受者解密时使用的。
加密密钥一般是公开的，也称为公钥（public key），解密密钥是不公开的，称为私钥（private key）。一对公钥与私钥成为密钥对（key pair）。密钥对中的两个密钥在数学上是有紧密相关的，是不能分别单独生成的。
由于加密时使用的密钥和解密时使用的密钥不一样，相对于对称密码的加解密使用同一对密钥来说，公钥密码也称为“非对称密码”。
公钥通信的流程如下：
可以看到，私钥并没有出现在通信内容中，因此窃听者无法对密文进行解密。
公钥密码的局限性
公钥密码也是面临着一些问题的，比如，需要判断所得到的公钥是否正确合法，这个问题被称为“公钥认证”问题，此外，公钥密码的处理速度只有对称密码的几百分之一。
RSA
现在最常用的公钥密码算法是RSA，但除了RSA外，还有很多其他的公钥密码。比如ElGamal方式、Rabin方式以及椭圆曲线密码等。这里我们重点介绍RSA密码。
RSA是现在使用最广泛的公钥密码算法。RSA可以被用于公钥密码和数字签名。
RSA加解密算法
RSA的加密过程： RSA的加密就是“求明文E次方的modN”（明文E次方以N为模求余），这里{E, N}就称为公钥。
RSA的解密过程： RSA的解密就是“求密文D次方的modN”（密文D次方以N为模求余），这里{D, N}就称为私钥，由于N也是公钥的一部分，也是公开的，所以也可以单独地把D称为私钥。
整理一下，RSA的加密和解密如下：
RSA密钥对的生成
现在可以看到，在RSA中，加密和解密的形式是相同的，而作为解密密钥的D，和数字E有着相当紧密的数学联系，才能实现用E加密的结果可以用D来解密的机制。
那么，在RSA加密算法中用到的E、D和N到底应该如何生成呢？
RSA密钥对的生成过程如下：
- 求N
- 求L（L是仅在生成密钥对过程中使用的数）
- 求E
- 求D
下面分步说明RSA密钥对的生成：
求N 首先准备两个很大的质数p和q，p和q太小的话，密码会变得容易被破译，太大的话计算时间又会变得很长。生成大质数的是要用到伪随机数生成器来生成的，如果生成的不是质数，就要用伪随机数重新生成另外一个数，然后再判断。 准备好着两个很大的质数之后，将其相乘，其结果就是数N。
$$
N=p×q
\
(p、q为大质数)
$$求L L这个数载RSA的加密和解密过程中都不出现，只出现在生成密钥对的过程中。 L是p-1和q-1的最小公倍数（least common multiple, lcm）。
$$
L=lcm(p−1,q−1)
\（L是p−1和q−1的最小公倍数）
$$求E E是一个比1大，比L小的数。此外，E和L的最大公约数（greatest common divisor, gcd）必须为1，也就是说，E和L互质。生成E也是要使用到伪随机数生成器的，先用伪随机数生成器生成大于1小于L的候选E，然后再判断其是否满足E与L互质的条件。求最大公约数可以使用欧几里得的辗转相除法。
$$
1<E<L\
gcd(E,L)=1（E和L的最大公约数为1，E和L互质）
$$求D
D是由E计算得到的，D、E和L之间必须具备下列关系：
$$
1<D<L\
E×DmodL=1
$$
要保证存在这样的D，就要求E和L必须得互质，否则是不存在满足公式的D的，这也正是第3步求E时的要求。 只要D满足上述条件，那么用E和N进行加密的密文，就可以通过D和N进行解密了。
经过上面四个步骤，已经求出了N和E、D，也就是生成了RSA的密钥对。整理一下以上生成密钥对的过程：
还需要注意的是，加密的明文必须是小于N的数，因为解密时最终要求mod N，算出的结果是一定小于N的，因此如果明文本身大于N，则解密后无法得到正确的明文。
RSA的机密性
相对于对称密码通过将明文转换为复杂形式来保证其机密性，公钥密码则是基于数学上的困难问题来保证机密性的。
可以看到，RSA主要是利用了离散对数求解的数学困难、以及大整数的质因数分解问题的数学困难来保证其机密性的。
- 密文 = 明文的E次方 mod N，得到密文，想要求解明文的问题实际上就变成了一个求离散对数的问题，这是非常困难的，因为人类还没有发现求离散对数的高效算法。
- 对于RSA来说，有一点非常重要，那就是大质数p和q不能被密码破译者知道，把p和q交给破译者与把私钥交给破译者是等价的。 由于N = p*q，而且N是公开的，要想通过N求出p和q，这里就存在一个对N进行质因数分解求p与q的问题。 因此可以说，一旦发现了对大整数进行质因数分解的高效算法，RSA就能够被破译。然而，目前还没有发现对大整数进行质因数分解的高效算法，而且也尚未证明质因数分解是否真的是非常困难的问题，甚至也不知道是否存在一种分解质因数的简单方法。
中间人攻击
中间人攻击虽然不能破译RSA，但却是一种针对机密性的有效攻击。
所谓中间人攻击，就是说攻击者混入到发送者和接受者中间，对发送者伪装接受者，对接受者伪装发送者的攻击方式。
假设存在这样一个场景，A和B使用公钥密码来加密通信，而他们之间的通信可以被主动攻击者C拦截，那么C就可以对A和B的加密通信进行中间人攻击：
- A向B发送邮件：我要和你通信，把你的公钥发给我。
- C通过窃听知道了A正在向B索取公钥。
- B向A回复邮件：这是我的公钥！
- C拦截了B对A的回复邮件，并获得了B的公钥。然后，C生成了自己的公钥和私钥，然后伪装成B将自己的C公钥发送给A，而把B的公钥保存好。
- A收到了C伪装B发送的回复邮件，获得了C的公钥，当然了，A以为这是B的公钥，然后开始进行加密通信！
- A将明文通过C的公钥加密后发送给B。
- C拦截了A发送给B的密文，然后使用自己的私钥对密文解密（注意，A不知道自己得到的公钥是C的，以为是B的呢），得到了明文，然后将明文保存好，再将明文用B的公钥加密后，伪装成A将密文发送给B。
- B收到了用自己的公钥加密的密文，然后用自己的私钥解密，正常读取到了明文内容。
在这个中间人攻击的过程中，非对称加密算法正常工作，而消息原本的发送者和接受者也能“正常地”发送接收信息，并不会意识到中间人的存在！因为中间人通过劫持信息和伪造信息，把两头都给欺骗了，成功截取了双方通信的内容，并且随时可以对信息内容进行篡改等进一步的恶意行为。
用一个图例更清晰地说明中间人攻击的过程：
这种中间人攻击的方法不只是针对RSA，而是可以针对任何公钥密码，可以看到，仅靠公钥密码本身，是无法防御中间人攻击的。
要防御中间人攻击，还需要一种手段来确认收到的公钥是否真的属于消息的接受者，而不是中间人攻击的攻击者，这种手段我们称之为“认证”，在这种情况下，我们可以使用公钥的证书。