应用与计算数学

密码学

利用数论与代数来保护信息安全,从RSA到现代加密方案。

直观给消息上锁,只有对的人才能打开

设想有一把任何人都能扣上、但只有一把特定钥匙才能打开的挂锁。如果每个人都公开自己的挂锁(但对钥匙保密),那么任何人都可以为你锁住一条消息,而只有你才能读出来——无需事先见面,也无需暗号。这正是公钥密码学的核心思想:"上锁"这一操作在一个方向上很容易计算,而在没有密钥的情况下,即便挂锁的设计本身是公开的,在计算上也无法可行地逆转。

\mathbb{Z}/17\mathbb{Z}

上的模乘映射

x \mapsto a x \bmod m

:正向计算轻而易举,而在大模数下逆向求解离散对数或RSA幂映射的困难性正是公钥密码学的基础。

中学模运算:基础构件

定义: 同余与模幂运算

两个整数 $a$ 和 $b$ 在模 $n$ 下同余,记作 $a \equiv b \pmod{n}$ ,当且仅当 $n \mid (a-b)$ 成立:即它们的差恰好是 $n$ 的倍数。模幂运算就是将一个底数对模 $n$ 反复自乘,这正是RSA和Diffie-Hellman等密码方案所依赖的运算,因为它正向计算很快,而反向求解却很困难。

a \equiv b \pmod{n} \iff n \mid (a-b)

这里 $n \mid (a-b)$ 表示 $n$ 整除 $a-b$ ,因此 $a \equiv b \pmod{n}$ 实质上是一个关于余数的陈述: $a$ 和 $b$ 被 $n$ 除时余数相同。下面的欧拉定理推广了费马小定理,正是RSA解密能够还原出原始消息背后的原理。

a^{\phi(n)} \equiv 1 \pmod n \quad \text{whenever} \quad \gcd(a,n)=1

三种密码方案比较
方案	所依赖的困难问题	典型密钥长度(2026年)
RSA	将 $n=pq$ 分解为素因数	2048-4096比特
Diffie-Hellman	模素数的离散对数	2048-3072比特
椭圆曲线密码学(ECC)	椭圆曲线群上的离散对数	256-384比特

大学RSA为何有效,以及Diffie-Hellman如何创建共享密钥

定理: RSA解密的正确性

设 $n = pq$ 是两个不同素数之积,且 $e$ 与 $d$ 满足 $ed \equiv 1 \pmod{\phi(n)}$ 。那么对任意满足 $0 \le m < n$ 的消息 $m$ ,用 $e$ 加密后再用 $d$ 解密可以还原出原始消息: $(m^e)^d \equiv m \pmod n$ 。

为什么成立?

这条定理正是让RSA真正可用的关键:它保证无论发送方用公钥指数加密什么内容,持有私钥指数的人总能解密——对每一个可能的消息都成立,而不仅仅是大多数情形——证明中必须处理消息恰好与模数共享因子的边界情形。

证明

由于 $ed \equiv 1 \pmod{\phi(n)}$ ,根据模同余的定义,存在非负整数 $k$ 使得 $ed = 1 + k\phi(n)$ 成立。

情形一: $\gcd(m,n)=1$ 。由欧拉定理有 $m^{\phi(n)} \equiv 1 \pmod n$ ,将两边同时 $k$ 次幂再乘以 $m$ ,得到 $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$ 。

情形二: $\gcd(m,n) \ne 1$ 。由于 $n = pq$ ,这意味着 $p$ 整除 $m$ 或者 $q$ 整除 $m$ (不会同时成立,因为 $m$ 小于 $n$ )。在模 $p$ 下考虑:若 $p$ 整除 $m$ ,则 $m$ 与 $m^{ed}$ 在模 $p$ 下都同余于 $0$ ;否则 $\gcd(m,p)=1$ ,由费马小定理有 $m^{p-1} \equiv 1 \pmod p$ ,又因为 $(p-1)$ 整除 $\phi(n)$ ,与情形一相同的计算给出 $m^{ed} \equiv m \pmod p$ 。在模 $q$ 下的论证完全相同,给出 $m^{ed} \equiv m \pmod q$ 。

由中国剩余定理,分别在模 $p$ 和模 $q$ 下成立的同余式,在其乘积 $n=pq$ 下也成立,因此 $(m^e)^d \equiv m \pmod n$ 对每一个消息 $m$ 都成立,而不仅仅是那些与 $n$ 互素的消息。

定理: Diffie-Hellman共享密钥协商

固定一个素数 $p$ 和一个底数 $g$ 。若Alice选取秘密值 $a$ 并发送 $A = g^a \bmod p$ ,Bob选取秘密值 $b$ 并发送 $B = g^b \bmod p$ ,那么计算 $B^a \bmod p$ 与 $A^b \bmod p$ 会得到相同的值 $g^{ab} \bmod p$ ,尽管 $a$ 和 $b$ 都从未被传输过。

为什么成立?

这正是使两方能够在被窃听者监视的公开信道上协商出一个密钥的原因:窃听者能看到底数、模数以及双方的公开值,但要从中还原出共享密钥,需要求解离散对数问题,在参数选择恰当的情况下,该问题被认为在计算上是困难的。

证明

根据定义, $A = g^a \bmod p$ 与 $B = g^b \bmod p$ 都是模幂运算的结果,因此Bob收到 $A$ 后计算 $B^a = (g^b)^a \bmod p$ ,而Alice收到 $B$ 后计算 $A^b = (g^a)^b \bmod p$ 。

模幂运算遵循与普通幂运算相同的指数法则,因为在模 $p$ 下的重复相乘,与整数的重复相乘的复合方式完全相同,只是在每一步都对模 $p$ 取约化:作为 $g$ 的指数有 $(g^b)^a = g^{ba} = g^{ab} = (g^a)^b$ ,并且这个等式在每一步取模 $p$ 约化后依然成立。

因此 $B^a \bmod p = g^{ab} \bmod p = A^b \bmod p$ :Alice与Bob各自独立地从自己的秘密指数和对方的公开值计算出相同的量 $g^{ab} \bmod p$ ,而秘密值 $a$ 或 $b$ 从未出现在信道上。

安全性论证与这个正确性论证是分开的:正确性只说明双方得到了同一个数;从 $g$ 、 $p$ 和 $A$ 计算出 $a$ 的困难性(离散对数问题),才是使这个共享数字对观察者保密的原因。

大学实际应用与典型例题

每一次HTTPS连接、每一款安全通讯应用、每一个加密货币钱包都依赖于上述定理:TLS握手使用Diffie-Hellman(或其椭圆曲线变体)来协商会话密钥,银行系统与软件更新使用RSA或ECDSA签名来保证真实性,而区块链钱包利用椭圆曲线上的离散对数,使得从公开地址推导出私钥在计算上不可行。下面两个例子用较小的数字手工演算RSA与Diffie-Hellman,使每一步都可验证。

例题: 用小素数手工计算RSA

使用素数 $p=5$ 和 $q=11$ ,公钥指数为 $e=3$ ,消息为 $m=2$ ,求出密文,并验证解密能还原出该消息。

解答

第一步:计算模数 $n = 5 \times 11 = 55$ 和 $\phi(n) = (5-1)(11-1) = 40$ 。

第二步:检验 $\gcd(3,40)=1$ ,因此 $e=3$ 是合法的公钥指数。

第三步:求满足 $3d \equiv 1 \pmod{40}$ 的私钥指数 $d$ 。取 $d=27$ 得到 $3 \times 27 = 81 = 2 \times 40 + 1$ ,因此 $d=27$ 可行。

第四步:加密 $m=2$ :密文为 $c = 2^3 \bmod 55 = 8 \bmod 55 = 8$ 。

第五步:通过计算 $c^{27} \bmod 55 = 8^{27} \bmod 55$ 来解密。对模55反复平方: $8^2 = 64 \equiv 9$ , $8^4 \equiv 9^2 = 81 \equiv 26$ , $8^8 \equiv 26^2 = 676 \equiv 16$ , $8^{16} \equiv 16^2 = 256 \equiv 36$ 。由于 $27 = 16+8+2+1$ ,计算 $8^{16} \cdot 8^{8} \cdot 8^{2} \cdot 8^{1} \equiv 36 \cdot 16 \cdot 9 \cdot 8 \pmod{55}$ ,逐步化简得到 $2$ 。

第六步:解密得到的值为 $2$ ,正是原始消息,这在这个具体实例上验证了RSA正确性定理。

例题: 手工演算Diffie-Hellman密钥交换

给定素数 $p=23$ 和底数 $g=5$ ,Alice选取秘密值 $a=6$ ,Bob选取秘密值 $b=15$ 。用两种方式分别计算共享密钥,并验证它们相符。

解答

第一步:Alice计算 $A = 5^6 \bmod 23$ 。逐步计算5对23取模的幂: $5^2=25\equiv2$ , $5^3\equiv10$ , $5^4\equiv4$ , $5^5\equiv20$ , $5^6\equiv8$ 。故 $A=8$ 。

第二步:Bob计算 $B = 5^{15} \bmod 23$ 。利用上面的 $5^6\equiv8$ ,有 $5^{12}\equiv8^2=64\equiv18$ ,以及 $5^{15}=5^{12}\cdot5^3\equiv18\cdot10=180\equiv19$ 。故 $B=19$ 。

第三步:Alice计算共享密钥为 $B^a \bmod p = 19^6 \bmod 23$ 。由于 $19\equiv-4$ ,有 $19^6\equiv(-4)^6=4^6=4096$ ,又 $4096 = 178\times23+2$ ,所以该值等于 $2$ 。

第四步:Bob计算共享密钥为 $A^b \bmod p = 8^{15} \bmod 23$ 。写作 $8=2^3$ 得到 $8^{15}=2^{45}$ ;由于 $2^{11}\equiv1 \pmod{23}$ (直接验证: $2^{11}=2048=89\times23+1$ ),且 $45=4\times11+1$ ,该式化简为 $2^{1}=2$ 。

第五步:两种计算都得到 $2$ ,确认Alice与Bob在从未通过信道传输 $a=6$ 或 $b=15$ 的情况下,就共享密钥达成了一致。

研究前沿截至 2026 年

对RSA、Diffie-Hellman和椭圆曲线密码学而言,最大的未解威胁是Shor在1994年提出的量子算法,它能在一台足够大的容错量子计算机上以多项式时间分解整数并计算离散对数——目前尚不存在这样的机器,但这一风险已经推动了一场全球性的转型。2024年,NIST正式确定了首批后量子密码标准(FIPS 203,一种源自CRYSTALS-Kyber、现称为ML-KEM的基于格的密钥封装机制,以及用于数字签名的FIPS 204),其安全性依赖于被认为能抵御量子攻击的格问题的猜想困难性。2022年的一个警示性教训是,并非每个"后量子"候选方案都能经受住审查:基于同源的SIKE方案作为NIST的一个决赛方案,被一种经典(非量子)攻击攻破,这说明该领域仍在被积极检验,而远未尘埃落定。

在 $n=55$ , $\phi(n)=40$ ,公钥指数 $e=3$ 的RSA中,哪个 $d$ 的值满足 $3d \equiv 1 \pmod{40}$ ?

Diffie-Hellman密钥交换的安全性依赖于哪个底层计算问题?

若 $\gcd(a,n)=1$ ,欧拉定理指出 $a^{\phi(n)} \equiv 1 \pmod n$ ,其中 $\phi(n)$ 计数的是以下哪一项?

一家银行想要为软件更新签名,以便客户能够验证更新确实来自该银行且未被篡改。哪种密码工具能直接提供这种保证?

参考文献

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone (1996). Handbook of Applied Cryptography
Peter W. Shor (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring · arXiv:quant-ph/9508027
National Institute of Standards and Technology (2024). Module-Lattice-Based Key-Encapsulation Mechanism Standard (FIPS 203)