跳转至

Lecture 10. 密码学

公钥加密系统 Public-key Crypto-system

公钥加密系统的基本原理是：大素数很容易构造，但是把一个大数分解成两个大素数很难。

公钥加密系统有两个主要用处：

  1. 对通信进行 加密（encrypt）。窃听人员无法 破译（decrypt） 被加密的信息。
  2. 在电子消息的末尾附加 数字签名（digital signature）。消息的任意 bit 发生变化，都将导致签名失效，而签名无法伪造。

在公钥加密系统当中，每个人（比如 Alice、Bob）都拥有一个 公钥（public key） 和 密钥（private key）。每个密钥都是一段信息（对于 RSA，密钥是两个整数）。公钥是可以公之于众的，但是密钥必须保密，仅有自己知道。

函数

使用公钥或密钥可以构造出一个函数，这个函数是 one-to-one 的，定义域和值域都是 $\mathcal{D}$，其中 $\mathcal{D}$ 是指允许表示的信息的集合（比如有限长度的二进制串）。one-to-one 是指，定义域当中的每个 $X$ 都对应值域当中的一个 $Y$，而 $Y$ 只能由定义域当中的一个 $X$ 得到。

设 $P_A$ 和 $S_A$ 分别表示 Alice 的公钥密钥，$P_B$ 和 $S_B$ 分别表示 Bob 的公钥密钥。它们构造的函数用 $P_A()$，$S_A()$，$P_B()$，$S_B()$ 表示。由于这些函数 one-to-one 的性质，这些函数是 $\mathcal{D}$ 的排列。由于密钥只有自己知道，所以在短时间内（可能几十年），$S_A()$ 函数只有 Alice 能够计算，$S_B()$ 只有 Bob 能够计算。

这俩函数还满足一个性质，即 $P_A()$ 与 $S_A()$ 互为反函数，即 $\forall M \in \mathcal{D}$，$S_A(P_A(M)) = P_A(S_A(M)) = M$，这意味着对于任意一个消息 $M$，无论先 $S$ 再 $P$ 还是先 $P$ 再 $S$，都可以回到自身。而公钥是公开的，密钥是保密的，加密系统应当保证，无法从公开的 $P_A()$ 计算出其对应的反函数 $S_A()$。

加密解密过程

对于发送私信

  • 假设 Bob 想要给 Alice 发送一条消息 $M$，不希望被别人知道
  • 那么 Bob 就可以用 Alice 的公钥 $P_A$ 对应的函数 $P_A()$ 来对消息进行加密，通过某种渠道，把 密文（cipher text） 传送给 Alice
  • 可能有人窃听得到了 $P_A(M)$
  • 但是由于从 $P_A(M)$ 解密得到 $M$ 必须要由密钥 $S_A$，所以只有 Alice 能够知道 $M$ 到底是什么

img

对于发布签名

  • 假设 Alice 想要给 Bob 一个带有商业性质的正式承诺的答复，那么 Alice 就需要在消息 $M'$ 的最后附加一个签名 $\sigma$
  • 这个签名就是根据密钥对原始消息的加密信息，即 $\sigma = S_A(M')$
  • 然后 Alice 把 $M'$ 和 $\sigma$ 一起发送给 Bob，注意这里的消息 $M'$ 是明文，所有人都可以看到
  • 即便所有人都能看到这条消息，但是由于签名的存在，可以进行验证，即验证是否 $P_A(\sigma) = M'$。如果不满足，那就意味着消息被篡改了，无效；如果满足，那么就是有效的。
  • $\sigma$ 既包含了发布者对文件内容的确认，也包含了发布者的个人信息，所以类似于现实生活当中的签名

RSA

在 RSA 当中，创建公钥密钥的过程如下：

  1. 随机选取两个不相等的大素数 $p$ 和 $q$
  2. 计算 $n = pq$
  3. 选取一个小的奇数 $e$，要求 $e \perp \phi(n)$；由欧拉函数性质：$\phi(n) = (p-1)(q-1)$
  4. 计算 $e$ 在模 $\phi(n)$ 意义下的逆元 $d$，可以证明 $d$ 唯一存在
  5. 公钥是 $P = (e,n)$，对应函数 $P(M) = M^e \bmod n$
  6. 密钥是 $S = (d,n)$，对应函数 $S(C) = C^d \bmod n$

RSA 时间复杂度分析

假设 RSA 的公钥密钥计算都是用快速幂算法。

  • 由于 $e$ 很小，可以认为 $\lg e = 1$
  • 由于 $d$ 是模 $\phi(n)$ 意义下计算出的逆元，设 $n$ 是 $\beta$ 位的二进制数，那么 $\lg d \leq \beta$
    • 计算 $P(M) = M^e \bmod n$ 的时候，由于指数很小，只需要执行 $\lg e = O(1)$ 次乘法运算，而位操作共有 $O(\beta^2)$ 次
    • 计算 $S(M) = C^d \bmod n$ 的时候，由于指数 $d$ 跟 $n$ 规模差不多，乘法运算需要执行 $O(\beta)$ 次，而位操作还是 $O(\beta^3)$ 次

RSA 的安全性分析

如果可以把这个 $n$ 分解出来，那么就可以得到 $\phi(n)$，于是可以再结合公钥的 $e$ 计算出 $d$，从而得知密钥。

$n$ 越大越难被分解。所以应当尽量找到一千位以上的大质数。

补充：模意义下快速幂

CLRS 4 给出的是递归版

CLRS 3 给出的是二进制形式描述的迭代版

image.png

假设 $a, b, n$ 都是 $\beta$ 位的二进制数，这个过程需要 $O(\beta)$ 次乘法运算，$O(\beta^3)$ 次位操作。