公钥密码体制

提出背景

对称密码体制满足不了保密通信的需求

  • 网络中用户数量多就需要更多密钥，密钥管理很困难
  • 互不认识的网络用户间通信要求密钥共享双方相互信任，不能解决陌生人之间的密钥传递问题
  • 堆成密码难以提供数字签名功能

于是因为对称密码体制的局限性，非对称密码体制应运而生。

公钥密码的基本思想

每个用户都有一个公钥和私钥。

公钥用于其他人向自己发送信息时进行加密。

私钥用于自己解密他人向自己发的信息。

单项陷门函数

  • 对任意明文加密是容易的
  • 已知解密密钥，解密密文是容易的
  • 不知道解密密钥，即使知道其他一切信息，解密也是困难的

满足以上性质的函数称为单向陷门函数。

常见的单项陷门函数问题

  • 大整数的分解问题（rsa）
  • 有限域上的离散对数问题（ELGamal）
  • 椭圆曲线上的离散对数问题（ECC）

公钥密码的应用

  • 机密性的实现（公钥加密私钥解密）
  • 数字签名（发送方用自己私钥签名，接收方用对应公钥鉴别）
  • 密钥分发和协商

公钥密码的局限

公钥密码体制虽然很安全，但是运算代价较大。当传送大量数据时，常采用公钥和对称密钥的混合密码体制。

RSA公钥密码体制

RSA由Rivest、Shamir、Adleman在1987年提出。

RSA方案是被最广泛接受并实现的通用公开密钥密码算法。

算法的数学基础是欧拉定理，安全性建立在大整数因子分解的困难性之上。

密钥生成

选择两个随机的大素数p、q

计算公钥的一部分：

  • n = p*q

  • 欧拉函数 (p-1)(q-1)

    欧拉函数的实际含义：欧拉函数是小于n的正整数中与n互质的数的数目

从1到(p-1)(q-1)里找到一个e，这个e和(p-1)(q-1)互质

再找到一个d （e的逆元）

d=e^-1 mod(欧拉函数)

这时候，公钥为（e，n），私钥为（d，n）

解密

m = c^d mod n

加密

c = m^e mod n