最后更新: 2025-10-16 09:54 查看: 262 次纠错评论(0) 课件开VIP

大数质数分解和RSA公开密钥

## 大数分解和公开密钥

随着信息时代的到来, 一个人常常要和很多人进行信息传播. 如果任意两个人彼此之间传递的信息需要保密的话, 那么每个人需要保存大量的密钥对 $\{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 年提出后, 立即引起人们的极大兴趣. 之后的数年里, 人们提出了各种各样设计方案, 但绝大多数方案提出不久便被否定了.

## RSA 加密
1977 年, 美国麻省理工学院计算机科学实验室的列维斯特 (Rivest) 等人基于大数分解的复杂性给出了一个便于应用的设计方案, 这就是著名的 RSA 方案. 下面简要介绍一下 RSA 方案.

我们知道, 任意大于 1 的整数总可以分解成一些素因数的乘积形式, 但这只不过是理论上的结果. 当整数很大时, 这件事情具体做起来非常困难. 用现代最快速的分解算法,在大型计算机上分解一个大整数所需时间如表 3 所示:

![图片](/uploads/2025-06/dee98d.jpg)
 
选取两个大约 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^{ed} \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^{ed} \equiv x(\bmod p)$. 类似可证 $x^{ed} \equiv x(\bmod q)$, 因此 $x^{ed} \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/2025-06/284245.jpg)
目前, 公开密钥体制已经用于实现愈来愈复杂的信息安全问题.

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

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

下一篇：附录1：数论符号与记法

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