Asymmetric cryptography

密钥配送问题

现实世界中使用对称密码时，一定会遇到密钥配送问题（key distribution problem）解决密钥配送问题的方法有以下几种：

  • 通过事先共享密钥来解决
  • 通过密钥分配中心来解决
  • 通过Diffie-Hellman密钥交换来解决
  • 通过公钥密码来解决

1.通过事先共享密钥来解决

密钥配送问题最简单的一种解决方法，就是事先用安全的方式将密钥交给对方，这称为密钥的事先共享。 事先共享的局限性:

  1. 需要一种安全的方式将密钥交给对方。
  2. 即便能够实现事先共享密钥，但在人数很多的情况下，通信所需要的密钥数量也会增大。

2.通过密钥分配中心来解决

如果所有参与加密通信的人都需要事先共享密钥，则密钥的数量会变得巨大，这样额情况下就可以使用密钥分配中心（Key Distribution Center，KDC）来解决密钥配送问题。当需要进行加密通信时，密钥分配中心会生成一个通信密钥，每个人只要和密钥分配中心事先共享密钥就可以了。有多少个人进行通信分配中心就保存了多少密钥。
局限性：

  1. 随着通信人数的增加，密钥分配中心的负荷也会随之增加。如果密钥分配中心计算机发生故障，所有的加密通信就会瘫痪。
  2. 如果主动攻击者入侵了密钥分配中心计算机，并盗取了密钥数据库，所有人的加密通信都会被破译。

3.通过Diffie-Hellman密钥交换来解决

在Diffie-Hellman密钥交换中，进行加密通信的双方需要交换一些信息，而这些信息即便被窃听者听到也没有关系。
根据所交换的信息，双方可以各自生成相同的密钥，而窃听者却无法生成相同的密钥。窃听者虽然能够窃听到双方交换的信息但却无法根据这些信息生成和双方相同的密钥。

4.通过公钥密码来解决

公钥密码（piblic-key cryptography）中，密钥分为加密密钥和解密密钥两种。加密密钥称为公钥，解密密钥称为私钥（private key）。公钥和私钥是一一对应的，一对公钥和一对私钥统称为密钥对（key pair）。

1. 公钥通信的流程： 公钥通信的流程

mod

mod即为除法求余数的运算。27mod12 = 3 （27除以12的余数等于3） mod

RSA

RSA是一种公钥密码算法，可以被用于公钥密码和数字签名。

1. RSA的加密和解密

加密：

密文 = 明文的E次方 mod N    （RSA加密）

解密：

明文 = 密文的D次方 mod N     （RSA解密）

RSA

2. RSA的算法

  1. 求N。选择两个大的质数p和q（p和q不能相差太大），计算乘积：
    N = pq
  2. 求L。L这个数在RSA的加密和解密过程中都不出现，它只出现在生成密钥对的过程中：
    L = lcm(p-1,q-1)         （L是p-1和q-1的最小公倍数）
  3. 求E。选择大于1小于L的随机整数E，且E和L的最大公约数为1，即E和L互质：
    1 < E < L
gcd(E,L) = 1           （E和L的最大公约数为1）
  4. 求D。D是由数E计算得到的，D、E和L之间必须具备下列关系：
    1 < D < L
E x DmodL = 1
    RSA密钥对： RSA密钥对

对于RSA来说，质数p和q不能被密码破译者知道。把p和q交给密码破译者与把私钥交给密码破译者是等价的。因为由N求p和q只能通过将N进行质因数分解来完成，所以一旦发现了对大整数进行质因数分解的高效算法，RSA就能够被破译。

3.中间人攻击（man-in-the-middle attack）
中间人攻击虽然不能破译RSA，但却是一种针对机密性的有效攻击。所谓中间人攻击，就是主动攻击者Mallory混入发送者和接收者的中间，对发送者伪装成接收者，对接收者伪装成发送者的攻击方式，在这里Mallory就是“中间人”。 中间人攻击 要防御中间人的攻击，还需要一种手段来确认所收到的公钥是否真的属于接收者Bob，这种手段称为认证，在这种情况下我们可以使用公钥的证书。

其他公钥密码

除了RSA以外的几种公钥密码：

  • EIGamal方式，RSA利用了质因数分解的难度，而EIGamal方式则利用了modN下求离散对数的难度。缺点就是经过加密的密文长度会变成明文的两倍。
  • Rabin方式，Rabin方式利用了modN下求平方根的困难度。
  • 椭圆曲线密码（Elliptic Curve Cryptosystems，ECC），通过将椭圆上的特点点进行特殊的乘法运算来实现，它的特点是所需的密钥长度比RSA短。