Article

An Introduction to Cryptography

Math
On this page 4

之前在学习web的时候，对一个流量来回的加密就不是很明白，不过非对称加密中的数学知识似乎还挺有意思的

对称加密

对称加密的过程是比较简单的，加密和解密都使用同一个密钥，也就是通过同一个算法，可以把一串明文变成密文，也可以再反向从密文再推导出这个明文

就好像一个可逆的函数一样，x和y是一一对应的，y=f(x)y=f(x)，x=f−1(y)x=f^{-1}(y)；不会出现一对多/多对一的情况

但是既然是可逆函数，就有一个问题：

比如从A->B发送消息，需要先把这唯一的一把钥匙发送给B，如果在传输中这把钥匙被截获了，那么所有信息都会被暴露

为了不泄露这个信息，需要先建立一个加密好的信道；但是如果传输的信道的加密也是使用对称加密，终究会有一个问题：就是最开始的传输钥匙的过程其实是公开的/不安全的

需要注意的是，在实际中，对称加密的密钥并不是函数本身，而是这个函数的某些参数；而遵循某个标准的对称加密的算法是公开的，只需要填入这个参数就可以得到加密/解密的结果

非对称加密

需求

所以在上面的传输消息的情景下，我们需要一个具有这样性质的加密：

  • 传输的钥匙是”公开“的，这样窃听者即使看到也不能恢复密文
  • 接受者凭借自己拥有的一把钥匙就可以解密，这把钥匙不会被暴露出去

这就是相对比较复杂的非对称加密

这个想法是很好的，但是很自然的一个问题就是什么样的数学结构是能满足这个要求的呢？

这个问题的关键，其实不是寻找一个“不能反向计算”的函数，而是寻找一种具有计算不对称性的数学结构：

x→f(x)x \rightarrow f(x)

正向计算很容易，但是给定 f(x)f(x) 后再反过来寻找 xx，在计算上非常困难。

这种性质通常可以用 One-way Function（单向函数） 来描述。

这里的“单向”并不是说这个函数在数学上绝对不可逆，而是

正向计算可以高效完成，但反向求解没有已知的高效算法。

但是，仅仅有“反向困难”还不能直接用来完成加密，因为如果所有人都无法反向计算，那么接收者自己也无法解密

因此还需要进一步增加一个条件：

存在某种只有接收者知道的秘密信息，使得拥有这份秘密信息的人可以高效完成原本困难的逆向计算。

这份秘密信息就称为 Trapdoor（陷门）。对于某个公开的、正向容易计算但反向计算困难的函数，知道这份秘密信息后，可以高效完成反向计算

于是，一个理想化的结构就变成：

x→公开计算yx \xrightarrow{\text{公开计算}} y

任何人都可以很容易地完成这个方向；

但是：

y→xy \rightarrow x

对于只知道公开信息的人来说很困难。

而如果额外知道一份秘密信息 tt：

(y,t)→x(y,t)\rightarrow x

就可以高效恢复原来的 xx。

这正好对应了非对称加密所需要的两种能力：

  • Public Key（公钥）：提供公开的加密能力；
  • Private Key（私钥）：提供只有接收者拥有的解密能力。

因此，非对称加密的核心不是“用了两把完全无关的钥匙”，而是构造出一对具有数学关联的信息，使得：

公开信息足以完成加密，但不足以完成解密\boxed{ \text{公开信息足以完成加密，但不足以完成解密} }

而：

秘密信息可以补上解密所需要的能力\boxed{ \text{秘密信息可以补上解密所需要的能力} }

接下来的问题就变成了：

数学上到底有没有这样的结构？

答案是有，而且不同的公钥密码系统会利用不同的困难数学问题来实现这种计算不对称性

RSA

到这里这个加密的问题就变成了一个数学问题

例如 RSA 利用模运算和大整数相关的数论结构；Diffie–Hellman 和 ElGamal 利用离散对数问题；椭圆曲线密码学则利用椭圆曲线上的离散对数问题。

也就是说，公钥密码学首先提出的是一种“能力分离”的需求，而 RSA、DH、ECC 等算法只是实现这种需求的不同数学方案

为了直观的来看这个问题，用一个简单的例子，简易版 RSA的流程

1. 先构造一个公开的正向函数

RSA 首先选择两个质数：

p, qp,\ q

然后计算：

n=pqn=pq

例如为了方便手算，这里取：

p=3,q=11p=3,\qquad q=11

那么得到

n=33n=33

接下来选择一个整数 ee，例如：

e=3e=3

于是可以定义一个公开函数：

f(x)=xe mod nf(x)=x^e\bmod n

在这个例子里就是：

f(x)=x3 mod 33\boxed{f(x)=x^3\bmod33}

这里：

  • xx 是输入；
  • ee 是公开指数；
  • nn 是公开模数；
  • f(x)f(x) 是输出。

例如：

x=4x=4

那么：

f(4)=43 mod 33f(4)=4^3\bmod33=64\bmod33=31=31

所以：

4→31\boxed{4\rightarrow31}

任何知道 n=33n=33 和 e=3e=3 的人，都可以完成这样的正向计算。

因此：

(n,e)\boxed{(n,e)}

就可以作为公开信息。

在 RSA 中，这一对信息就是 Public Key（公钥），用来完成正向计算

2. 反向计算

现在假设我们只拿到：

y=31y=31

并且知道：

y=x3 mod 33y=x^3\bmod33

我们希望恢复xx

也就是解决：

x3≡31(mod33)x^3\equiv31\pmod{33}

这里的意思是x3x^3和31属于mod33的同一个余数族

对于这个只有两位数的玩具例子，可以直接一个个枚举尝试（因为同余数组没有什么直接的算法）

但是在现实 RSA 中，nn通常是一个非常大的整数，例如 2048 bit。

这时无法简单枚举所有可能的 xx

所以我们希望构造一份秘密信息，使得知道它的人可以高效完成逆运算。

3. 利用隐藏的质因数构造私钥

最开始生成 nn 的人知道：

p=3,q=11p=3,\qquad q=11

因此他可以计算 Euler’s Totient Function（欧拉函数） φ(n)\varphi(n)

欧拉函数的定义是：在 11 到 nn 之间，小于等于 nn 且与 nn 互质的正整数个数。

对于两个不同质数的乘积n=pqn=pq，有φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)

这里是欧拉函数的两个性质：

  • 欧拉函数乘法的分配律性质 φ(pq)=φ(p)φ(q)\varphi(pq) = \varphi(p) \varphi(q)
  • 欧拉函数对质数的性质φ(n)=n−1\varphi(n) = n - 1

因此φ(33)=(3−1)(11−1)=20\varphi(33) = (3-1)(11-1) = 20

接下来寻找一个整数 dd，满足：

ed≡1(modφ(n))\boxed{ed\equiv1\pmod{\varphi(n)}}

为什么要让ed和1对欧拉函数是同余族，在下一小节里会证明

这里e=3e=3，所以我们要找3d≡1(mod20)3d\equiv1\pmod{20}

取d=7d=7，因为3×7=213\times7=21同时满足21≡1(mod20)21\equiv1\pmod{20}

所以d=7\boxed{d=7} 就可以作为私钥中的核心秘密参数

至此就得到了最终的公钥和私钥

Public Key=(n,e)=(33,3)\boxed{\text{Public Key}=(n,e)=(33,3)}

Private Key=d=7\boxed{\text{Private Key}=d=7}

4. 为什么 dd 可以把结果变回来？

回到这个算法的正向计算公式y=xe mod ny=x^e\bmod n

现在我们定义逆向计算也拥有类似的形式 x′=yd mod nx'=y^d\bmod n

从正向计算的公式，y≡xe(modn)y\equiv x^e\pmod n，左右边取一个幂之后仍然是属于同余数族的：yd≡(xe)d(modn)y^d \equiv (x^e)^d \pmod n

因此得到了yd≡xed(modn)y^d\equiv x^{ed}\pmod n

前面我们故意让 ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}

这意味着存在某个整数 kk，使得ed=1+kφ(n)ed=1+k\varphi(n)

于是：

xed=x1+kφ(n)=x(xφ(n))kx^{ed} = x^{1+k\varphi(n)} = x\left(x^{\varphi(n)}\right)^k

根据欧拉定理，在 xx 与 nn 互质时，有xφ(n)≡1(modn)x^{\varphi(n)} \equiv1\pmod n

[Euler’s Theorem, wikimedia](Euler’s theorem - Wikipedia)

所以xed≡x⋅1k≡x(modn)x^{ed} \equiv x\cdot1^k \equiv x \pmod n

也就是说：

yd mod n=x\boxed{y^d\bmod n=x}

得到 ydy^d和 xedx^{ed}以及 xx对mod n同余之后，如果我们再加上一个额外的限制：0≤x<n0\le x \lt n，就不难得到 yd mod n=xy^d\bmod n=x的结果

所以私钥指数 dd 对应的运算可以撤销公钥指数 ee 对应的运算。

在我们的例子里正向加密的过程是43 mod 33=314^3\bmod33=31

反向解密的过程是 317 mod 33=431^7\bmod33=4

所以：4→31→4\boxed{4\rightarrow31\rightarrow4} 成功完成了这样一次的非对称加密

5. RSA 中的陷门到底是什么？

现在又出现了一个新的问题：

如果 dd 可以求出来，那攻击者为什么不能自己求？

因为要从ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}求出 dd，需要知道φ(n)\varphi(n)

而对于n=pqn=pq，刚刚是利用了性质进行了一个较为方便的计算：φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)

这需要知道秘密质因数p, qp,\ q，which生成密钥的人一开始就知道(定语从句太好用了)

但是最终公开出去的公钥里只有n=pqn=pq，而没有公开其质因数p, qp,\ q

遗憾的是当 p,qp,q 都是非常大的质数时，从nn重新分解得到p, qp,\ q是一个计算上非常困难的问题，目前对经典计算机没有已知的多项式时间算法

所以 RSA 中真正隐藏的数学结构可以理解为知道密钥（质因数）后，p,q→φ(n)→d→高效求逆p,q \rightarrow \varphi(n) \rightarrow d \rightarrow \text{高效求逆}

而普通人只有n,en,e没有已知高效方法完成对应的逆向计算，再面对大数的时候，比如2048bit的，一个cpu core穿行计算的话需要6×10^14 core-years，惊人的数量级

这就是 RSA 中 Trapdoor（陷门） 的具体体现