唠唠闲话

当今互联网传输中，处处可见公钥密码系统的身影，比如 https 协议中， s 代表便是基于公钥系统的 SSL/TLS 协议。

对称加密

对称加密是密码学的一类加密演算法，这类算法在加密和解密时使用相同的密钥，或是使用两个可以简单地相互推算的密钥。

  1. 比如轮盘加密

    apple⟶+12012encodebrqlg⟶−12012decodeappleapple\underset{encode}{\overset{+12012}\longrightarrow}\quad brqlg\quad\underset{decode}{\overset{-12012}\longrightarrow}\quad apple

  2. 对称加密的高级应用：二战时期德国的恩尼格玛密码机(Enigma machine)。受当时算力限制，经其加密的文件很难破译。而盟军能够破译恩尼格玛是因为德国军队犯了一些大的错误，比如没有每月更新密码、机器，使用步骤和密码本被缴获等等。当然，在1944年后英国开发出原始电脑后，即使每月更新也无济于事。

  3. 对称加密有两个缺点：

    • 当密钥被重复使用时，可以用频率分析破解密钥
    • 假设 Alice 要传信息给 Bob，Alice 需事先和 Bob 交换密钥。在互联网中，相隔万里的两人需要先碰面才能传输信息，显然很不方便

  4. 尽管存在诸多限制，但对称加密有个很大的优点：通过一次一密(one-time pad OTP) 能做到“不可破解”。顾名思义，一次一密指密码本用一次就丢弃，比如前边例子中，任意包含5个字母的单词被加密成 brqlg 的概率相同，因而不可能破译原信息。

  5. 假设 Alice 对传输安全性要求很高，她可以先与 Bob 碰面交换长为 N 的随机密钥本，只要密钥本没有泄露，Alice 一共可以给 Bob 发送长为 N 的与密码本等长的数据，在不知道密码本的情况下，窃听者不可能破解这段数据。

对称加密常与非对称加密结合使用，后者解决了密钥交换的问题。

非对称加密

非对称加密基于困难的数论问题，更具体地，可以用单向函数(One-way function)来描述这种加密。

本节用单向函数抽象地讨论加解密过程，这种讨论方式不涉及具体性质，也更容易理解过程以及加密思想，具体加密系统放在下一节介绍。

方便起见，我们将多项式时间内的计算称为容易计算。

单向函数

  1. P,NPP, NP 等概念

    • P 问题：能在在多项式时间内解决的判断问题
    • NP 问题：能在多项式时间内验证的判断问题
    • NP-Hard：所有 NP 问题可以用多项式时间转化为该问题（未必 NP）
    • NP-Complete：NP-Hard 问题与 NP 问题的交集

  2. 单向函数是具有以下性质的单射 ff：对任意输入值 xx，容易计算函数值 f(x)f(x)；但对随机的函数值 yy，很难计算其原像。

  3. 比如哈希函数，在没有哈希冲突的情况下，可以认为是单向函数。

  4. 容易发现，单向函数的存在隐含了 P≠NPP\neq NP。因为 P=NPP=NP 还是开问题，单向函数的存在性也是开问题。尽管如此，密码学家倾向于认为 P≠NPP\neq NP，许多加密算法均基于某类单向函数。

数据加密

  1. 用非对称加密系统加密数据，安全性基于以下性质：

    • 容易生成单向函数 ff 及其逆函数（未必是单向函数） gg，使得 g(f(x))=xg(f(x))=x
    • 将 ff 称为公钥，gg 称为私钥

  2. 假设 Alice 要传输信息 xx 给 Bob，加密过程如下

    • Bob 生成公钥 ff 和私钥 gg
    • Bob 将公钥在公开信道(可能不安全)上传递给 Alice
    • Alice 计算 x′=f(x)x'=f(x)
    • Alice 在公开信道(可能不安全)上传递 x′x' 给 Bob
    • Bob 通过 g(x′)=g(f(x))=xg(x')=g(f(x))= x 解密原始信息 xx
    • 整个过程中，(x,g)(x, g) 为安全信息，(x′,f)(x',f) 为不安全信息

  3. 假设 Eve 为窃听者(eavesdropper)

    • Eve 在公开信道上窃取到来自 Bob 的公钥 ff 以及来自 Alice 的信息 x′x'
    • 由于 ff 为单射，理论上 Eve 总能从 x′x' 反解出原像 x′x'
    • 但由于 ff 为单向函数，反推过程会很困难，可能需要指数时间甚至更高复杂度的时间才能求解原像

  4. 非对称加密的缺点是不能识别中间人攻击：

    • 假设 Bob 生成了密钥对 (f,g)(f,g)，而 Eve 也生成了一对密钥 (f′,g′)(f',g')
    • Eve 在窃听时，偷偷将 Bob 的公钥换成了 f′f'
    • 现 Alice 在公开信道上获取了 f′f' 并传输 f′(x)f'(x) 给 Bob
    • Eve 拦截到 x′x' 并通过 g′(f′(x))=xg'(f'(x))=x 获取原文信息
    • 获取原文后，Eve 再将 f(x)f(x) 传输给 Bob
    • Bob 用 g(f(x))=xg(f(x))=x 正常解码信息，但不知晓中间已被窃听

密钥交换

非对称加密有一个缺点：加密和解密过程的计算复杂度通常较大，尽管时间仍在可执行范围。所以非对称加密一般与对称加密配合使用，用于密钥交换。

  1. 在密钥交换方面，除了上一小节的传输方式，还可以直接生成(伪)随机密码本，安全性基于以下性质：

    • 容易构造函数集合 F\mathfrak{F}，其中函数两两交换

    f,g∈F(a)⇒f(g(x))=g(f(x))f,g\in\mathfrak{F}(a)\Rightarrow f(g(x))=g(f(x))

    • 通过 (F,x,f)(\mathfrak{F},x,f)，计算 f(x)f(x) 很容易
    • 通过 (F,x,f(x))(\mathfrak{F},x,f(x)) 反解出 ff 很困难
    • 上一步困难性是为了确保由 (F,x,f(x),g(x))(\mathfrak{F},x,f(x),g(x)) 求解 f(g(x))f(g(x)) 很难

  2. 此处隐含的单向函数为

    (x,F):F→Ff↦f(x)\begin{align*} (x, \mathfrak{F}):\mathfrak{F}&\rightarrow\mathfrak{F}\\ f&\mapsto f(x) \end{align*}

    这个映射不一定要是单射，但必须确保求原像很困难

  3. 假设 Alice 要和 Bob 共享一段密码本：

    • Alice 和 Bob 在公开信道上约定函数集 F\mathfrak{F} 以及随机数字 xx
    • Alice 随机选取 f∈Ff\in\mathfrak{F}，并在公开信道上将 f(x)f(x) 发送给 Bob
    • Bob 随机选取 g∈Fg\in\mathfrak{F} ，并在公开信道上将 g(x)g(x) 传递给 Alice
    • Alice 手上有私钥 ff 和信息 g(x)g(x)，计算得到密码本 f(g(x))f(g(x))
    • Bob 手上有私钥 gg 和信息 f(x)f(x)，计算得到密码本 g(f(x))g(f(x))
    • 由于 f,gf,g 的交换性，Alice 和 Bob 得到了同一个密码本
    • 整个过程中，(f(x),g(x),x,F)(f(x), g(x), x, \mathfrak{F}) 为不安全信息，(f,g)(f,g) 为安全信息

  4. 假设 Eve 窃听了这个过程：

    • Eve 在公开信道上窃听得到 x,Fx,\mathfrak{F} 和 f(x),g(x)f(x),g(x)
    • 根据假设性质，Eve 很难由这些信息解出密钥本 f(g(x))f(g(x))

两类加密系统的核心都是单向函数，但只有单向性通常是不够的。比如第一类在生成加密映射 ff 时，还要求能一并生成解密映射 gg ；第二类则要求了函数 f,gf,g 的交换性。

一般地，在数论和代数领域更容易碰到这类问题，下边列举几个经典的例子。

常见公钥系统

本节介绍几个常用公钥系统。加密数据方面，介绍基于线性码纠错的 McEliece 加密系统以及基于大整数分解的 RSA 加密系统；密钥交换方面，介绍基于离散对数算法的 Diffie–Hellman 密钥交换以及基于群论的椭圆曲线密钥交换。

McEliece 加密

在密码学中，McEliece 密码系统是由 Robert McEliece 于 1978 年开发的一种非对称加密算法。这是第一个在加密过程中使用随机化的方案，该算法从未在密码学界获得太多认可，但它是“后量子密码学”的候选者，因为它不受使用 Shor 算法的攻击，或者更一般地，不受量子傅里叶采样的影响。

  1. McEliece 密码系统的安全性基于解码一般线性码的困难性（已知为 NP-Hard）

  2. 假设 Alice 要传输信息 x∈Fqkx\in\mathbb{F}_q^{k} 给 Bob

    • Bob 生成一个 (n,k,d)q(n,k,d)_q 线性分组码，以 G∈Fqn×kG\in\mathbb{F}_q^{n\times k} 为生成元矩阵，最大纠错数目 t=⌊d−12⌋t=\lfloor\frac{d-1}{2}\rfloor，且具有高效的纠错解码算法
    • Bob 随机生成 kk 阶可逆矩阵 SS 与 nn 阶置换矩阵 PP，使得以 G^=PGS\hat{G}=PGS 为生成元矩阵的线性码没有高效解码算法
    • Bob 将公钥 G^\hat{G} 在公开信道上发送给 Alice
    • Alice 将 xx 加密为 x′=G^x+zx'=\hat{G}x+z，其中 z∈Fqnz\in\mathbb{F}_q^n 为随机生成的权重为 tt 的扰动(非0元素个数为 tt)
    • Alice 将 x′x' 在公开信道上发送给 Bob
    • Bob 收到 x′x' 后，如下进行解码

    P−1x′=P−1(G^x+z)=P−1(PGSx+z)=G(Sx)+P−1z=Gx^+z^, where x^=Sx, z^=P−1z\begin{align*} P^{-1}x'&=P^{-1}(\hat{G}x+z)\\ &=P^{-1}(PGSx+z)\\ &=G(Sx)+P^{-1}z\\ &=G\hat{x}+\hat{z},\ where\ \hat x=Sx,\ \hat{z}=P^{-1}z \end{align*}

    • 由于 P−1P^{-1} 为置换矩阵，z^\hat{z} 仍然为权重 tt 的向量，根据编码的纠错能力，Bob 能使用高效算法从 Gx^+zG\hat{x}+z 中纠错得到数据 x^\hat{x}，进而得到原始信息 x=S−1x^x=S^{-1}\hat{x}
    • 整个过程中，(x,G,S,P)(x,G,S,P) 为安全信息，(G^,x′)(\hat G,x') 为不安全信息

  3. 现假设 Eve 窃听了这一过程：

    • Eve 窃听得到了 G^x′\hat{G}x'
    • 由于以 G^\hat{G} 为生成元矩阵的线性码没有高效算法，Eve 很难从带有错误的 x′x' 中还原 xx

  4. 由线性代数知识易知，编码 G^\hat{G} 与编码 GG 具有相同的编码距离，理论上总能从 x′=G^x+zx'=\hat{G}x+z 中纠错得到原数据 xx，只是这个过程的计算开销可能极大，约等于不可能。

RSA 加密

RSA(Rivest-Shamir-Adleman) 是一种广泛用于安全数据传输的公钥密码系统。它也是最古老的之一。首字母缩写词 “RSA” 来自 Ron Rivest、Adi Shamir 和 Leonard Adleman 的姓氏，他们在 1977 年公开描述了该算法。实际上，早在 1973 年，英国数学家 Clifford Cocks 便在 GCHQ（英国信号情报机构）秘密开发了一个等效系统，该系统直到 1997 年解密。

概述

  1. RSA 的安全性依赖于分解两个大素数乘积的困难性，即“分解问题”。破解 RSA 加密被称为 RSA 问题。实际上，破解 RSA 是否一定必须经过整数分解也仍然是个悬而未决的问题。当密钥足够大时，目前还没有公开的方法能破解编码。

  2. RSA 是一种相对较慢的算法，正因为如此，它不常用来直接加密用户数据。更多时候，RSA 用于传输对称密钥加密的共享密钥，然后用于批量加密-解密。

  3. P 与 NP 相关

    • 大整数分解属于 NP 问题，假设大整数 N=p⋅qN=p\cdot q，给出 p,qp,q 很快就能验证 N=p⋅qN=p\cdot q；相反，已知 NN 求 p,qp,q 会很困难
    • 大整数分解问题没有被证明是 NPC 问题，所以仍有可能是 P 问题
    • 虽然不清楚整数分解是否是 P 问题，但素性检验已被证明是 P 问题(2002)，即 AKS 素性检验，算法复杂度为 O(log(N)3)O(log(N)^3)。也就是说，给定一个大整数 NN，我们能高效地判断它是否有真因子，但却不能高效的求出来
    • 一般讨论的算法复杂度都是基于经典计算，如果考虑量子计算，由于 shor 算法的出现，大整数分解已被证明是 BQP(Bounded-error Quantum Polynomial time) 问题。即：用量子计算机可在多项式时间内解决，所有实例的错误概率最多为 1/3
    • 为了抵抗量子计算，密码学也在发展后量子密码系统。但在当前，RSA 仍是广泛使用且安全的一种加密

有空打算把大整数分解的常用算法也整理一下（比如和 shor 算法一块介绍）

加密过程

  1. 假设 Alice 需要传输信息给 Bob

  2. Bob 执行以下操作

    • 随机生成两个不同的大素数 p,qp,q，并计算乘积 N=p⋅qN = p\cdot q
    • 计算 NN 的卡迈克尔函数(Carmichael function) λ(N)\lambda(N)

    λ(N)=lcm(λ(p),λ(q))=lcm(p−1,q−1)\begin{align*} \lambda(N) &= lcm(\lambda(p), \lambda(q))\\ &= lcm(p-1, q-1) \end{align*}

    Bob 也可以直接计算欧拉函数 φ(N)=(p−1)(q−1)\varphi(N)=(p-1)(q-1)，但由于 φ(N)≥λ(N)\varphi(N)\geq\lambda(N)，后续解码开销可能会更大

    • 选取整数 ee 使得

    1≤e≤λ(N) and gcd⁡(e,λ(n))=11\leq e\leq \lambda(N)\ and\ \gcd(e,\lambda(n)) = 1

    e 通常取素数 216+1=655372^{16}+1=65537

    • Bob 通过 λ(N)\lambda(N) 计算私钥 dd

    d≡e−1mod  λ(N)d\equiv e^{-1}\mod \lambda(N)

    具体地，由 e,λ(N)e,\lambda(N) 的互素性，Bob 通过辗转相除法，容易得到 u,vu,v 使得

    u⋅e+v⋅λ(N)=1u\cdot e + v\cdot \lambda(N) = 1

    此时取 d≡umod  λ(N)d\equiv u \mod \lambda(N)

  3. Bob 将大整数 NN 以及整数 ee 作为公钥，在公开信道上发送给 Alice

  4. 现假设 Alice 需要传输信息 MM 给 Bob，其中 0≤M<N0\leq M<N，Alice 将信息 MM 加密为 M′M'，并将 M′M' 传递给 Bob

    M′≡Memod  NM' \equiv M^e \mod N

  5. Bob 收到加密信息 M′M' 后，使用私钥 dd 进行解密

    (M′)d≡(Me)d≡Mmod  N(M')^d \equiv (M^e)^d \equiv M \mod N

    式子还原为 MM 是基于欧拉定理（如果这里取了 φ(N)\varphi(N)），或者基于群论的拉格朗日定理：Z/NZ\mathbb{Z}/N\mathbb{Z} 的乘法群为 λ(N)\lambda(N) 阶群

  6. 整个过程中，(N,e,M′)(N,e,M') 为不安全信息；(p,q,λ(N),d,M)(p,q,\lambda(N),d,M) 为安全信息。

  7. 假设 Eve 窃听了这一过程：

    • Eve 窃听得到 N,e,M′N,e,M'
    • Eve 需要求解下边方程才能得到信息 MM

    Me≡M′mod  NM^e\equiv M'\mod N

    然而函数 fe(M)=M′f_e(M)=M' 具有单向性，当 NN 非常大时，Eve 几乎不可能通过 M′M' 反解 MM

离散对数算法

【待补充】
Discrete logarithm

迪菲-赫尔曼密钥交换
Diffie–Hellman key exchange

椭圆曲线算法

【待补充】