公钥密钥学

公钥算法基于数学函数，而不是“替换”与“置换”，不像传统对称加密使用同一密钥，公钥密码使用非对称密钥。

公钥密码需要两个密钥，一个是公开密钥，另一个是私有密钥；公钥用作加密，私钥则用作解密，反过来：私钥加密，需要公钥解密。

不同于加密和解密都使用同一个密钥的对称加密。公钥可以公开，可任意向外发布；私钥不可以公开，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供，也不会透露给被信任的要通信的另一方。

对公钥密码的要求

已经公钥无法确实私钥
只知道公钥与密文，无法恢复出明文
使用公钥加密可以用私钥解密；使用私钥加密可以用公钥解密

公钥密钥学的两个用处：加密与数字签名

加密

如果任何人使用公钥加密明文，得到的密文可以透过不安全的途径（如网络）发送，只有对应的私钥持有者才可以解密得到明文；

在数学上，d(c(x))=x，使用典型的爱丽丝与鲍伯假设来解释：

爱丽丝与鲍伯事先互不认识，也没有可靠安全的沟通渠道，但爱丽丝现在却要透过不安全的互联网向鲍伯发送信息
爱丽丝撰写好原文，原文在未加密的状态下称之为明文x
鲍伯使用密码学安全伪随机数生成器产生一对密钥，其中一个作为公钥为c，另一个作为私钥d
鲍伯可以用任何方法发送公钥c给爱丽丝，即使伊夫在中间窃听到c也没问题
爱丽丝用公钥c把明文x进行加密，得到密文c(x)
爱丽丝可以用任何方法传输密文c(x)给鲍伯，即使伊夫在中间窃听到密文c(x)也没问题
鲍伯收到密文，用私钥d对密文进行解密d(x)，得到爱丽丝撰写的明文x
由于伊夫没有得到鲍伯的私钥d，所以无法得知明文x
如果爱丽丝丢失了她自己撰写的原文x，在没有得到鲍伯的私钥d的情况下，她的处境将等同伊夫，即无法透过鲍伯的公钥c和密文c(x)重新得到原文x

数字签名

由于私钥只由该用户自己持有，故可以肯定该文件必定出自于该用户；

公众可以使用对应的公钥验证该用户发布的数据或文件是否完整、中途有否曾被篡改，接收者可信赖这些数据、文件确实来自于该用户，这被称作数字签名

例如，从网上下载的安装程序，大部分都带有程序制作者的数字签名，可以证明该程序的确是该作者（公司）发布的而不是第三方伪造的且未被篡改过（身份认证/验证）。

数字签名实现了“数据完整性”与“认证源”，它往往使用hash值来作为“认证符”，任何对原内容的修改，都会让认证符发生变化。数字签名不具有保密性，但具有认证性

公钥密码的缺点

公钥加密在计算上相当复杂，性能远远不比对称加密；因此，在一般实际情况下，往往通过公钥加密来随机创建临时的对称秘钥，亦即对话键，然后才通过对称加密来传输大量、主体的数据。

公钥密码与传统密码不能直接比较优劣，因为公钥密码需要的计算量大，所以很难直接取缔传统密码，但公钥密码学常用于“密钥管理”和“数字签名”。

公钥密码用来传输对称加密的密钥或数字签名

公钥密码的攻击

虽然公钥密码常用来作传输对称加密的密钥的工具，但有种攻击方式，是公钥密码独有的

假如现在要发送的内容是“56位DES密钥”，攻击者知道公钥，他可以用公钥将全部有可能的DES密钥进行加密，再将加密结果与发送的密文进行比较。

对于这种穷举攻击，不论公钥密钥有多长（虽然密钥越长，抗穷举攻击性越好），都无效。解决方法是，在要发送的消息后面附加一个随机数再进行加密

RSA加密

RSA使用的公钥密码学

特点：

非对称加密，即：PK与SK不是同一个

PK用于加密，SK用于解密

PK决定SK，但是PK很难算出SK（数学原理：两个大质数相乘，积很难因式分解）

速度慢，只对少量数据加密

加密过程

这几步的目的：产生公钥和私钥

RSA产生密钥过程

第3步是欧拉函数，不考证明
第4步的选择e（公钥），是在1~φ(n)这个范围内即可
第5步的选择d（私钥），是e的模反元素；使得e*d-1能被φ(n)整除【或e*d mod φ(n) =1】
公钥是e与n
私钥是d与n

产生公钥与私钥后，加密与解密如下：

加密解密过程

加密：明文M（将M理解为一个字符），M^e^ mod n =C ，C就是密文

解密：密文C（也是个字符），C^d^ mod n=M

举例

步骤1：p=3,q=11

步骤2：n=p*q=33

步骤3：φ(n)=(p-1)*(q-1)=2*10=20

步骤4：e=3【因为方便计算，1~φ(n)即可】

步骤5：d=7【因为要满足：e*d mod n =1 ,3*d mod n =1】

步骤6：KU=(e,n)=(3,33)

步骤7：KR=(d,n)=(7,33)

得到公钥与私钥，下面进行加解密过程

假如M=20

加密：C=M^e^ mod n=14

解密：M=C^d^ mod n=20

Diffie–Hellman密钥交换

功能：让通信双方创建一个共享密钥，这个密钥用来给后续通讯进行加密

适合用作密钥交换的原因：它使用离散对数正向计算简单，逆向计算困难的特点。当选择的素数较大时，使用穷举攻击几乎不可能

下面展示这个算法，粗体表示非秘密信息，红色表示秘密信息：

爱丽丝与鲍伯协定使用 p=23以及 g=5【其中的p是个素数；g是个小于p的整数，p和g都能公开】
爱丽丝选择一个【私钥a】秘密整数a=6，计算A = $g^a mod p$ $g^{a} m o d p$ 并发送给鲍伯【A可以公开】
- A = $5^6 mod 23$ = 8.
鲍伯选择一个【私钥b】秘密整数b=15，计算B = $g^b mod p$ $g^{b} m o d p$ 并发送给爱丽丝。【B可以公开】
- B = $5^15 mod 23$ = 19.
爱丽丝得到鲍伯的B=19，爱丽丝计算res= $B^a mod p$ $B^{a} m o d p$
- res= $19^6 mod 23$ =2
鲍伯得到爱丽丝的A=8，鲍伯计算res = A^b^ mod p
- res= $8^15 mod 23$ =2

最终得到res=2就是共享密钥，一旦爱丽丝和鲍伯得出了公共秘密，他们就可以把它用作对称密钥，以进行双方的加密通讯，因为这个密钥只有他们才能得到。当然，为了使这个例子变得安全，必须使用非常大的a, b 以及 p

针对上面的DH密钥交换，很快就有了对应的攻击手段，叫“中间人攻击”

中间人攻击

用来对DH密钥交换进行攻击

中间人攻击的关键：篡改【安全攻击形式之一】

篡改包括了中断和伪造

核心

中间人攻击的关键在于，中间人要同时维护与Alice的共享密钥k1，还要维护和Bob的共享密钥k2。

中间人有两套自己的公钥与私钥，分别与Alice交换密钥时使用、与Bob交换密钥时使用

举例

假设爱丽丝（Alice）希望与鲍伯（Bob）通信。同时，马洛里（Mallory）希望拦截窃会话以进行窃听并可能在某些时候传送给鲍伯一个虚假的消息。

Mallory提前准备了两套密钥

私钥Xmb对应公钥Ymb，用来Mallory与Bob通信
私钥Xma对应公钥Yma，用来Mallory与Alice通信

篡改过程

Alice将自己的公钥【Ya】给Bob
但【Ya】被Mallory截获，Mallory将自己公钥【Yma】回复给Alice，同时Mallory用【Ya】计算出Mallory与Alice的共享密钥K2
- Mallory得到K2
- K2=(Ya)^Xma^ mod q 【q是公开的素数，Xma是Mallory与Alice通信时，Mallory保留的私钥】
Mallory再将自己的公钥【Ymb】传给了Bob
Bob得到【Ymb】，Bob计算共享密钥K1【实际是Mallory和Bob的共享密钥K1】
- Bob得到K1
- K1=(Ymb)^Xb^ mod q 【Xb是Bob的私钥】
Bob将自己公钥【Yb】发送给Alice
但【Yb】也被Mallory截获，Mallory用【Yb】计算出与Bob共享密钥K1
- Mallory得到K1
- K1=(Yb)^Xmb^ mod q 【Xmb是Mallory与Bob通信时，Mallory保留的私钥】
Alice收到了【Yma】，Alice计算出共享密钥K2【实际是Mallory和Alice的共享密钥K2】
- Alice得到K2
- K2=(Yma)^Xa^ mod q

可以观察到Mallory同时得到了K1与K2，而Alice和Bob各自得到一个共享密钥

通信模拟

Alice用K2对消息加密
被Marrlory截获，并用Xma解密，得到信息。
Marrlory再用K1对消息加密发送给Bob【Marrlory此时可以只监听，不修改消息……当然也可以修改消息】
Bob收到消息后解密，得到信息

防御中间人攻击

利用物理时间判断是否是真的对方

延迟测试，例如使用复杂加密哈希函数进行计算以造成数十秒的延迟；如果双方通常情况下都要花费20秒来计算，并且整个通讯花费了60秒计算才到达对方，这就能表明存在第三方中间人。

因为中间人攻击中，Alice和Bob无条件的信任了Marrlory的公钥，所以需要对收到的公钥进行认证

公钥体系的完整性通常必须以某种方式得到保障，但不需要进行保密。密码和共享密钥有额外的保密需求。公钥可以由证书颁发机构验证，这些公钥通过安全的渠道（例如，随Web浏览器或操作系统安装）分发。公共密钥也可以经由Web在线信任进行在线验证，可以通过安全的途径分发公钥（例如，通过面对面的途径分发公钥）。