从 01 开始 从 01 开始
首页
  • 📚 计算机基础

    • 计算机简史
    • 数字电路
    • 计算机组成原理
    • 操作系统
    • Linux
    • 计算机网络
    • 数据库
    • 编程工具
    • 装机
  • 🎨 前端

    • Node
  • JavaSE
  • Java 高级
  • JavaEE

    • 构建、依赖管理
    • Ant
    • Maven
    • 日志框架
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • 环境管理和配置管理-科普篇
    • Servlet
  • Spring

    • Spring基础
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC

    • SpringMVC 基础
  • SpringBoot

    • SpringBoot 基础
  • Windows 使用技巧
  • 手机相关技巧
  • 最全面的输入法教程
  • 最全面的浏览器教程
  • Office
  • 图片类工具
  • 效率类工具
  • 最全面的 RSS 教程
  • 码字工具
  • 各大平台
  • 校招
  • 五险一金
  • 职场规划
  • 关于离职
  • 杂谈
  • 自媒体
  • 📖 读书

    • 读书工具
    • 走进科学
  • 🌍 英语

    • 从零开始学英语
    • 英语兔的相关视频
    • Larry 想做技术大佬的相关视频
  • 🏛️ 政治

    • 反腐
    • GFW
    • 404 内容
    • 审查与自我审查
    • 互联网
    • 战争
    • 读书笔记
  • 💰 经济

    • 关于税
    • 理财
  • 💪 健身

    • 睡眠
    • 皮肤
    • 口腔健康
    • 学会呼吸
    • 健身日志
  • 🏠 其他

    • 驾驶技能
    • 租房与买房
    • 厨艺
  • 电影

    • 电影推荐
  • 电视剧
  • 漫画

    • 漫画软件
    • 漫画推荐
  • 游戏

    • Steam
    • 三国杀
    • 求生之路
  • 小说
  • 关于本站
  • 关于博主
  • 打赏
  • 网站动态
  • 友人帐
  • 从零开始搭建博客
  • 搭建邮件服务器
  • 本站分享
  • 🌈 生活

    • 2022
    • 2023
    • 2024
    • 2025
  • 📇 文章索引

    • 文章分类
    • 文章归档

晓林

程序猿,自由职业者,博主,英语爱好者,健身达人
首页
  • 📚 计算机基础

    • 计算机简史
    • 数字电路
    • 计算机组成原理
    • 操作系统
    • Linux
    • 计算机网络
    • 数据库
    • 编程工具
    • 装机
  • 🎨 前端

    • Node
  • JavaSE
  • Java 高级
  • JavaEE

    • 构建、依赖管理
    • Ant
    • Maven
    • 日志框架
    • Junit
    • JDBC
    • XML-JSON
  • JavaWeb

    • 服务器软件
    • 环境管理和配置管理-科普篇
    • Servlet
  • Spring

    • Spring基础
  • 主流框架

    • Redis
    • Mybatis
    • Lucene
    • Elasticsearch
    • RabbitMQ
    • MyCat
    • Lombok
  • SpringMVC

    • SpringMVC 基础
  • SpringBoot

    • SpringBoot 基础
  • Windows 使用技巧
  • 手机相关技巧
  • 最全面的输入法教程
  • 最全面的浏览器教程
  • Office
  • 图片类工具
  • 效率类工具
  • 最全面的 RSS 教程
  • 码字工具
  • 各大平台
  • 校招
  • 五险一金
  • 职场规划
  • 关于离职
  • 杂谈
  • 自媒体
  • 📖 读书

    • 读书工具
    • 走进科学
  • 🌍 英语

    • 从零开始学英语
    • 英语兔的相关视频
    • Larry 想做技术大佬的相关视频
  • 🏛️ 政治

    • 反腐
    • GFW
    • 404 内容
    • 审查与自我审查
    • 互联网
    • 战争
    • 读书笔记
  • 💰 经济

    • 关于税
    • 理财
  • 💪 健身

    • 睡眠
    • 皮肤
    • 口腔健康
    • 学会呼吸
    • 健身日志
  • 🏠 其他

    • 驾驶技能
    • 租房与买房
    • 厨艺
  • 电影

    • 电影推荐
  • 电视剧
  • 漫画

    • 漫画软件
    • 漫画推荐
  • 游戏

    • Steam
    • 三国杀
    • 求生之路
  • 小说
  • 关于本站
  • 关于博主
  • 打赏
  • 网站动态
  • 友人帐
  • 从零开始搭建博客
  • 搭建邮件服务器
  • 本站分享
  • 🌈 生活

    • 2022
    • 2023
    • 2024
    • 2025
  • 📇 文章索引

    • 文章分类
    • 文章归档
  • JavaSE

    • 我的 Java 学习路线
    • 安装 Java
    • Java 数据类型

    • Java 多版本配置
    • 面向对象

    • Java 核心类

    • IO

    • Java 与时间

    • 异常处理

    • 哈希和加密算法

      • 什么是哈希算法
      • 第三方库的哈希算法
      • MAC 算法
      • 加密算法介绍
      • 对称加密算法
      • 口令加密算法
      • 非对称加密算法介绍
      • RSA 算法原理(一):数学知识
      • RSA算法原理(二):概述
      • RSA 算法原理(三):补充知识
        • RSA 算法:公钥指数的选取
        • RSA 算法的一个例子
        • RSA 的一个漏洞
        • 公钥的传输
        • 量子计算机
        • 总结
      • Java 中的 RSA 算法
      • DH 算法
      • 数字签名
      • SSL 和 TLS 协议介绍
    • Java8 新特性

    • 网络编程

  • JavaSenior

  • JavaEE

  • JavaWeb

  • Spring

  • 主流框架

  • SpringMVC

  • SpringBoot

  • Java
  • JavaSE
  • 哈希和加密算法
2023-03-20
目录

RSA 算法原理(三):补充知识

# RSA算法原理(三):补充知识

补充下关于 RSA 的更多细节

# RSA 算法:公钥指数的选取

我们回顾下公私玥的生成

  1. 首先,Alice 选择一对不相等且足够大的质数,记为 p 和 q
  2. 计算 pq 的乘积,记为 n,也就是 p × q = n
  3. 计算 n 的欧拉函数,φ(n) = φ(p×q) = φ(p) × φ(q) = (p -1 ) × (q - 1)
  4. 随机选取一个与 φ(n) 互质的数 e,并且 1 < e < φ(n)
  5. 计算出一个 e 对于 φ(n)的模反元素 d,也就是说 ed mod φ(n) = 1

公钥:(n,e) 私钥:(d,n)

加密公式: me mod n = c

解密公式:cd mod n = m

关于 e :

第 4 步,e 到底是怎么选取呢?其实,是可以随机的,但是为了提高 RSA 的加密速度实际使用中公钥指数最长用的三个值是 3、17、65537(65536 = 216 +1)。这样选取主要是为了性能,将公钥指数选小一点,这样计算密文就方便一点;

但是这样会导致解密会麻烦一点。因为正常使用中都是用公钥加密,所以需要节约大部分人的时间。而极少部分人也会选用私钥解密,那么就只能少数服从多数了。

在选用公钥指数时,人们普遍会认为 3 和 17 没有 65537 安全。然而这种想法并没有合理的依据。实际上采用这三个值中的任何一个都不存在安全问题。前提是使用正确的填充方案。

关于 d 是怎么计算出来的:

  1. 我们知道 ed mod φ(n) = 1
  2. 那么也就是说,存在一个整数 k,使得 ed ÷ φ(n) = k....1 (商为 k,余数为 1)
  3. 也就是 ed - 1 = kφ(n), 变化一下就是 ed + kφ(n) = 1.
  4. 我们已知 e 和 φ(n)的值,d 和 k 的值未知。其实,以上公式就是对这个二元一次方程求解:ex + φ(n)y = 1
  5. 这个方程可以用扩展欧几里得算法 (opens new window)求解,此处省略具体过程

# RSA 算法的一个例子

我们来举个例子,具体演示下算法的运作过程。本例子用到的数字都特别小,实际应用中,一般会成百上千位的数字进行计算。

第一步,选取 p = 61, q=53

第二步,计算 pq 乘积:n = pq = 3233。 n 的长度就是密钥长度。3233 写成二进制是 110010100001,一共有 12 位,所以这个密钥就是 12 位。实际应用中,RSA 密钥一般是 1024 位,重要场合则为 2048 位。

第三步:计算 n 的欧拉函数:φ(n) = (p-1)(q-1) = 3120

第四步:随机选取一个整数 e,这里选择 17

第五步:计算 e 对于 φ(n)的模反元素 d,使得 ed mod φ(n) = 1. 上一小节我们说过 ed + kφ(n) = 1,代入 e 和 φ(n),也就是 17d + 3120k = 1,可以根据扩展欧几里得算法 (opens new window)算得一组整数 d = 2753, k=-15。

因此,公钥就是(3233,17),私钥就是(3233,2753)

假设我们要加密字符 ‘A’,其 ASCII 码为 65; 根据加密公式可得 6517 mod 3233 = 2790,因此密文 c 就是 2790

解密:通过解密公式 cd ≡ m (mod n),可得 27902753 mod 3233 = 65。

至此,"加密--解密"的整个过程全部完成。

# RSA 的一个漏洞

Rambus 公司曾发现了 RSA 的一个小漏洞:如果 N 的两个质数 p 和 q 很接近,那么很可能被硬猜出来!其实这个方法是大数学家费马之前就发现过的:如果两个数很接近,意味着他们的差很小,因此可能破解出来。

具体怎么破解呢?首先,假设质数 p 和 q 是用来生成公钥的,我们设 a,b 为两个整数,并且 a = (p+q)/2, b = (p-q)/ 2

那么就有 p = a + b, q = a - b

则有 n = (pq) = (a+b)(a-b) = a2 - b2 (初中的平方差公式)

因此 a2= n +b2。 我们可以知道,任何数的平方都是正数,因此 a2= n +b > n。而费马说过,如果两个数很接近,意味着他们的差很小,而 b 是作为他们的差的一半,即使算上了平方,也还是很小的!那么 a2 应该就约等于 n。

又因为 p 和 q 是质数(也是奇数),所以 a 和 b 必定是整数(奇数加减后是偶数,除以 2,是能被整除的,所以 a 和 b 不是小数),然后我们就可以从 n 的平方根开始,一个个试,总有可能试出来。

举个粒子:

假设有个公钥 n = 27263 = a2 - b2

我们将 n 开平方,并用 a 表示:a ≈ ,也就是 a ≈ 165.12

假设 a = 166,则 b2 = 293,则 b 不是整数,pass❌

假设 a = 167,则 b2 = 626,则 b 不是整数,pass❌

假设 a = 168,则 b2 = 961,则 b=31☑

因此,就破解出了 a 和 b,然后就可以计算出 p=a+b=199,q=a-b=137,因此可以破解出密钥 d。

当然,现实生活中会极力避免出现这样的情况的,并且这个漏洞已经上报公开了,目前 RSA 算法还是很安全的。

数学家们认为,判断 RSA 算法密钥是否安全的标准为:| p - q | < ,也就是 p-q 的绝对值,是否小于 n 的四次方根。

# 公钥的传输

其实,使用公钥传输还是有一个问题:万一用户收到的是攻击者的公钥怎么办?

假设 Bob 要和 Alice 通信,需要 Alice 的公钥,那么 Alice 将公钥发送给了 Bob;但如果在发送公钥的过程中,Peter 截胡了,将自己生成的公钥发给了 Bob!

然后 Bob 收到公钥后,加密数据,并发送给 Alice,但不幸的是,也被 Peter 截胡了,然后 Peter 就可以解密了。。。

最后,我们还是回到最初的问题:密钥怎么发送给使用者?其实我们电脑(准确来说是操作系统)一开始就装了很多证书。

以 Windows 为例,在 cmd 命令行中执行 certmgr.msc 命令,可以查看操作系统已经安装的证书列表。

# 量子计算机

1994 年,美国数学家秀儿(Peter Shor),曾经提出了一种逆天的量子计算算法,对于一般的计算机而言,RSA 算法的公钥 N 位数每增加一位,破解 RSA 的难度都会呈指数上升;而这个逆天算法可以把“指数上升”的难度,降低到跟 N 位数的平方成正比!

图片来自麻省理工学院官网 (opens new window)

量子算法是厉害,但现在的量子计算机性能实在太渣。2001 年 IBM 曾经在自己的量子计算机上,用秀儿算法搞了次因数分解,成功把 15 分解成了 3×5;2019 年的时候 BM 想用自己最新的量子计算机,尝试分解 35,但失败了.....

IBM_Q_system_Fraunhofer_2

图片来自:Quantum computing- 维基百科 (opens new window)

目前的密钥长度基本都是成百上千的,要想分解,至少需要 600 个量子比特的量子计算机。然而谷歌最新的量子计算机,也不过 53 个量子比特。因此在可见的未来里。RSA 加密都会继续保持安全。

# 总结

本文作为 RSA 原理系列的最后一篇,相信大家通过之前的讲解,对于 RSA 都有一定的认知了。

RSA 从提出到现在,这么多年过去了,经历了各种攻击的考验,注解为人们接受,普遍认为是目前最优秀的公钥方案之一。

本文参考了非常多的博客和文章,非常感谢他们:

深入理解 RSA 算法 - 简书 (opens new window)

RSA 中 底数 m 和模数 n 不互素是仍然成立_rsa 的 m_Zetaa 的博客-CSDN 博客 (opens new window)

密码学笔记 - 阮一峰的网络日志 (opens new window)

RSA 算法原理(一) - 阮一峰的网络日志 (opens new window)

RSA 算法原理(二) - 阮一峰的网络日志 (opens new window)

密钥交换算法 - 廖雪峰的官方网站 (opens new window)

五年级数学“分解质因数”难题详解 (opens new window)

为什么大整数分解质因数很困难? - 知乎 (opens new window)

质因数分解与量子计算机 - 知乎 (opens new window)

分解质因数_百度百科 (opens new window)

欧拉函数 - 天殇梦璃 - 博客园 (opens new window)

Diffie-Hellman 密钥交换算法 | 公钥加密 | DH 算法 | 密码学 | 信息安全_哔哩哔哩_bilibili (opens new window)

【不懂数学没关系】DH 算法 | 迪菲-赫尔曼 Diffie–Hellman 密钥交换_哔哩哔哩_bilibili (opens new window)

用小学数学,看懂支付宝微信都在用的“最强加密”_哔哩哔哩_bilibili (opens new window)

【RSA 加密算法】| RSA 加密过程详解 | 公钥加密 | 密码学 | 信息安全 |_哔哩哔哩_bilibili (opens new window)

模运算_百度百科 (opens new window)

上次更新: 2025/6/3 09:31:54
RSA算法原理(二):概述
Java 中的 RSA 算法

← RSA算法原理(二):概述 Java 中的 RSA 算法→

最近更新
01
学点统计学:轻松识破一本正经的胡说八道
06-05
02
2025 年 5 月记
05-31
03
《贫穷的本质》很棒,但可能不适合你
05-27
更多文章>
Theme by Vdoing | Copyright © 2022-2025 | 粤 ICP 备 2022067627 号 -1 | 粤公网安备 44011302003646 号 | 点击查看十年之约
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式