公钥密码学背景

公钥密码学的提出是为了解决对称密码中最困难的两个问题：

  • 密钥分配问题：通信双方要进行加密通信，必须通过一个安全信道共享密钥，然而这种安全信道在现实中难以实现
    其次对于有多个节点的通信网络，通常需要一个密钥分配中心管理密钥，否则整个系统保存的密钥数目会很大。然而公钥密码学提出者Diffie认为，要求用户与密钥分配中心共享密钥，那这些密钥分配中心的泄露也会使得一个不可破的密码体制毫无意义
  • 数字签名问题：即能否设计一个方法对电子消息进行签名，确保消息出自某个特定的人

Diffie和Hellman二人针对上述问题提出了公钥密码学的概念，成为密码学发展的一个里程碑

公钥密码体制及其应用

公钥密码体制中每个用户拥有两个密钥，分别为公钥和私钥，其中公钥是公开的，私钥是保密的

公钥密码的加密/解密算法满足可以用两个密钥中任何一个来加密，而另一个用来解密

根据这些特性，公钥密码体制可以分为三类应用：

  • 消息的加密/解密

假设Alice要给Bob发送加密消息，且Bob产生了公钥$PU_b$和私钥$PR_b$
Alice可以使用Bob的公钥$PU_b$对明文X加密，Bob则使用自己的私钥$PR_b$解密，即

由于只有Bob知道其自身私钥，因此攻击者无法解密出该消息

  • 数字签名

假设Alice要给Bob发送加密消息，且Alice产生了公钥$PU_a$和私钥$PR_a$
Alice可以使用自己的私钥$PR_a$对明文X加密，Bob则使用Alice的公钥$PU_a$解密，即

由于只有Alice知道其自身私钥，因此只有Alice可以加密消息
若Bob用Alice的公钥无法解密，则说明消息Alice不是消息发送方

需要注意的是，这种数字签名方法只能防止消息被修改，而不能防止其他人窃听，因为任何人都能访问Alice的公钥，从而解密出消息

若同时使用公钥密码的加密/解密和数字签名方法，则既可以提供认证，又能保证保密性

  • 密钥交换

即通信双方安全地交换会话密钥，后续会提到有多种方法可以用于密钥交换

需要注意的是并不是所有公钥密码算法都支持这三种应用，下面是一个对比图

public_key_encryption

公钥密码算法的设计要求

  • 产生一个公钥、私钥对在计算上是容易的
  • 已知公钥和明文消息M，产生相应的密文C在计算上是容易的
  • 接收方使用其自身私钥解密接收到的密文在计算上是容易的
  • 攻击者已知公钥，要确定其对应私钥在计算上是不可行的
  • 攻击者已知公钥和密文C，要恢复其明文M在计算上是不可行的
  • 加密、解密函数顺序可以交换，即$M=D(PU_b,E(PR_b,M))=D(PR_b,E(PU_b,M))$

事实上要找到一个满足上述条件的算法并不容易，公钥密码提出的几十年中只有上图中几个算法被广泛接受

Diffie-Hellman密钥交换

Diffie和Hellman在首次提出公钥密码学的论文中给出的算法被称为Diffie-Hellman密钥交换

DH密钥交换需要一个素数$q$和其原根$\alpha$，他们都是公开的

假设A要和B交换密钥，则A选择一个随机整数$X_A<q$，并计算$Y_A=\alpha^{X_A} \mod q$
同理B也独立地选择一个整数$X_B<q$，并计算$Y_B=\alpha^{X_B}\mod q$
其中$X$均为私有的，而$Y$是公开的
用户A、B分别计算$K=(Y_B)^{X_A}\mod q$和$K=(Y_A)^{X_B}\mod q$，至此他们就共享了密钥$K$

DH密钥交换的安全性源于求离散对数的困难性

中间人攻击

DH密钥交换不能抵抗中间人攻击

假设A和B希望交换密钥，而D是攻击者
为了进行攻击，D会生成随机私钥$X{D1}$和$X{D2}$，并计算相应的公钥$Y{D1}$和$Y{D1}$
D将截获$YA,Y_B$的发送，计算$K_2=Y_A^{X{D2}}$和$K1=Y_B^{X{D1}}$
之后D将$Y{D1},Y{D2}$分别发送给B、A，则B会计算$K1=Y{D1}^{XB}$，而A会计算$K_2=Y{D2}^{X_A}$
这样A、D之间共享了密钥$K_2$，B、D之间共享了密钥$K_1$

DH交换协议不能抵抗该攻击是因为通信双方没有进行认证