最后更新: 2023-11-09 19:14 查看: 193 次反馈刷题

大数分解和公开密钥

**二 大数分解和公开密钥**

随着信息时代的到来, 一个人常常要和很多人进行信息传播. 如果任意两个人彼此之间传递的信息需要保密的话, 那么每个人需要保存大量的密钥对 $\{E, D\}$, 而且这些密钥还要经常更换, 否则容易被非法接收者破译. 例如, 若有 2000 个人彼此之间进行信息传递, 并且所有信息均需对第三方保密, 那么共需要 $\mathrm{C}_{2000}^2=1999000$ 对密钥, 每个人需要保存 1999 对密钥. 这样一来, 密钥的保存和保护就成了一个非常严重的问题.
1976 年, 美国斯坦福大学年轻数学家狄菲 (Diffe) 和计算机专家海尔曼 (Hellman)提出了一种新的加密方法, 叫做公开密钥体制, 并且在信息安全领域得到广泛的应用. 在这种体制下, 信息的加密与去密用两个不同的钥, 加密用公钥 (意指此钥可以公开, 无需保密, 任何人都可以得到), 去密用私钥 (意指此钥需严加管理, 只有合法的去密者才有,并不能泄漏).

在前面信息加密传送的例子中, 发送与接收双方公用一对密钥: 加密密钥 $E(k)=k+$ $19(\bmod 31)$ 和去密密钥 $D(k)=k+12(\bmod 31)$, 它们是一对互逆的运算

$$
D E(k)=E D(k)=k \text {. }
$$

不难发现, 加密运算与去密运算都很简单, 并且知道其中一个运算后很容易推出另一个运算. 也就是说, 由其中一个密钥可以得到另一个密钥. 与此不同的是, 在公开密钥体制中, 加密密钥 $E$ 采用所谓的 “单向” 作用. 具体地说, 加密密钥 $E$ 虽然运算简单, 并且是可逆的（即存在某个运算 $D$, 使得 $D E(k)=E D(k)=k$, 对所有 $k$ 都成立), 但是即使知道了 $E$, 要求它的逆运算 $D$ 也是极困难的, 从而保证了第三方无法在保密期限内得到密文的真实信息.

在公开密钥体制下, 每个人只需要自己的一对密钥 $\{E, D\}$, 其中 $E$ 为单向作用, $D$ 为 $E$ 的逆运算. 每个人的加密密钥 $E$ 对外完全公开, 甚至可以编制成册, 供任何人查看, 但去密密钥 $D$ 只有他自己知道, 对其他人保密. 这样一来, 每个人只需保存自己的去密密钥 $D$ 即可.

实现公开密钥体制的关键在于设计单向作用 $E$. 公开密钥体制自 1976 年提出后, 立即引起人们的极大兴趣. 之后的数年里, 人们提出了各种各样设计方案, 但绝大多数方案提出不久便被否定了.
1977 年, 美国麻省理工学院计算机科学实验室的列维斯特 (Rivest) 等人基于大数分解的复杂性给出了一个便于应用的设计方案, 这就是著名的 RSA 方案. 下面简要介绍一下 RSA 方案.

我们知道, 任意大于 1 的整数总可以分解成一些素因数的乘积形式, 但这只不过是理论上的结果. 当整数很大时, 这件事情具体做起来非常困难. 用现代最快速的分解算法,在大型计算机上分解一个大整数所需时间如表 3 所示:
![图片](/uploads/2023-11/image_20231109373e78d.png)
选取两个大约 100 位左右的不同素数 $p$ 和 $q$. 设 $n=p q$, 我们不难计算出 $n$ 的欧拉函数值

$$
\varphi(n)=(p-1)(q-1) .
$$

再取两个正整数 $e$ 和 $d$, 使得 $e d \equiv 1(\bmod \varphi(n))$.
一般地, 对上述正整数 $e, d$ 和任意整数 $x$, 恒有 $x^{a i} \equiv x(\bmod n)$.
证明: 由 $e d \equiv 1(\bmod \varphi(n))$ 知 $e d=1+\varphi(n) k$, 其中 $k$ 为某个整数. 如果 $p \nmid x$, 那么由费马小定理知

$$
x^{e d}=x^{1+\phi(n) k}=x \cdot\left(x^{p-1}\right)^{(q-1) k} \equiv x(\bmod p) .
$$

如果 $p \mid x$, 则 $x^{e d}$ 和 $x$ 模 $p$ 均同余于 0 , 所以对每个整数 $x$, 均有 $x^{e i} \equiv x(\bmod p)$. 类似可证 $x^{a t} \equiv x(\bmod q)$, 因此 $x^{a l} \equiv x(\bmod n)$.
在 RSA 方案中, 把信息 $x$ 用 0 至 $n-1$ 之间的数表示, 分别选取加密密钥和去密密钥为

$$
E(x) \equiv x^e(\bmod n), \quad D(y) \equiv y^d(\bmod n) .
$$

由上述事实知 $E$ 和 $D$ 是互逆的运算. 由于 $\varphi(n)=(p-1)(q-1)$ 是很大的整数, 所以可以求出许多对 $\{e, d\}$, 满足 $e d \equiv 1(\bmod \varphi(n))$. 每个人只需使用其中一对作为自己的密钥对即可.

将 $n$ 和 $e$ 公开 (从而加密密钥是公开的), 每个人保留自己那一个 $d$ 不被别人知道. 别人想通过 $e$ 求出 $d$, 就需要解一个一次同余方程 $e x \equiv 1(\bmod \varphi(n))$.

解一次同余方程并不困难, 但现在的问题是: 别人并不知道模 $\varphi(n)$ 的大小, 因为要得到 $\varphi(n)$ 的值必须先知道 $N$ 的素因素分解式 $p q$. 通过表 3 大家知道, 得到这个分解是极其困难的. 所以别人即使知道 $n$ 和 $e$, 在信息保密期限内也很难得到 $d$ 和去密密码 $D$.

公开密钥体制的提出不仅解决了大量密钥的保存和管理问题, 而且还解决了信息传送中另一个问题: 数字签名和身份认证问题.

设想甲发信息给乙向乙借一笔钱, 那么乙需要确信这条信息来自甲, 以免甲事后否认. 在现实生活中, 人们通常在借条上签名或按手印, 但在如今广泛采用电子通讯中如何确定对方的身份呢? 公开密钥体制提出之前, 身份认证问题一直没有很好的解决方法. 如今采用公开密钥体制做身份认证就变得很简单: 甲向乙传送信息 $x$ 之前, 先用自己的私钥 $D_{\text {甲 }}$ 作用成 $D_{\text {甲 }}(x)=y$ (数字签名), 然后把 $y$ 传送给乙. 乙在公钥本上查到甲的公钥 $E_{\text {甲 }}$,作用于 $y$ 便恢复成明文

$$
x=E_{\text {甲 }}(y)=E_{\text {甲 }} D_{\text {甲 }}(x)=x,
$$

便知此信息来自甲. 由于其他人不知道甲的私钥 $D_{\text {甲 }}$, 所以无法伪装甲进行签名.
在公开密钥体制下, 传送方可以同时对信息进行签名和加密. 例如, 如果甲要向乙传送信息 $x$, 甲可先签名 $D_{\text {甲 }}(x)=y$, 再进行加密 $E_乙(y)=z$, 然后把密文 $z$ 传给乙. 当乙收到密文 $z$ 后, 依次作用私钥 $D_{\text {乙 }}$ 和甲的公钥 $E_{\text {甲 }}$, 便得到明文

$$
E_{\text {甲 }} D_乙(z)=E_{\text {甲 }} D_乙 E_乙(y)=E_{\text {甲 }}(y)=E_{\text {甲 }} D_{\text {甲 }}(x)=x \text {. }
$$

其信息传送的数学模型如图 3 所示:
![图片](/uploads/2023-11/image_20231109b68ce4d.png)
目前, 公开密钥体制已经用于实现愈来愈复杂的信息安全问题.

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：数论在密码中的应用

下一篇：第二部分数论部分问题概述

本文对您是否有用？有用 (0) 无用 (0)