从 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 算法原理(三):补充知识
      • Java 中的 RSA 算法
      • DH 算法
      • 数字签名
      • SSL 和 TLS 协议介绍
    • Java8新特性

    • 网络编程

  • JavaSenior

  • JavaEE

  • JavaWeb

  • Spring

  • 主流框架

  • SpringMVC

  • SpringBoot

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

RSA 算法原理(一):数学知识

# RSA 算法原理(一):数学知识

在学习 RSA 算法原理之前,读者应该有一些基本的数学知识,这里介绍下模运算、质因数和欧拉函数。以下情况如无特别说明,假设讨论的数字都是正整数

# 余数和取模

取模运算是求两个数相除的余数。例如,7÷3 = 2 .... 1,也就是商等于 2,余数为 1。我们也可以称之为 7 对 3 取模,可以写作:7 mod 3 = 1。一般公式:a mod b=c,指的是 a ÷ b 的余数为 c。

由于模运算的英文是 Modular Arithmetic,我们常用 mod 表示取模运算符,也叫求余运算符。在编程语言中,经常使用百分号 % 作为取模运算符。

有时候我们还会见到一个公式:a ≡ b (mod c),这个公式的意思是说,a 和 b 分别对 c 取模,余数是相同的,也读作 a 与 b 同余,mod 为 c ,“≡”是数论中表示同余的符号。例如:7 ≡ 1(mod 3),指的是 7 和 1 分别对 3 取余,余数是相同的。

由于取模其实就是取余数,因此有这样的规律:

设 x mod y = n,则存在一个整数 k,使得 ky + n = x。

这应该不难理解,x mod y 其实就是 x ÷ y,那么结果就是 k(商),余数为 n,也就是 x ÷ y = k.... n

其实我们生活中就有用到取模的例子。

  1. 假设现在是上午 10 点,同事约你说 7 小时后吃饭,也就是 17 点,那么其实也就是下午 5 点(17 mod 12 = 5)。在一些钟表里,只有 1 ~ 12 的数字,可以认为超过 12 的会自动做取模运算
  2. 若 12 月 1 号是周一,很容易就知道 12 月 8 号、15 号、22 号、29 号也是周一。

同时,我们可以推导出以下规律:

  • 自反性:a≡a(mod m)。
  • 对称性:若 a≡b(mod m), 则 b ≡ a(mod m)。
  • 传递性: 若 a≡b(mod m),b≡c(mod m), 则 a≡c(mod m)。

此外,模运算的加减乘除,和基本的四则运算类似:

  • 加法:(a + b) mod p = (a mod p + b mod p) mod p
  • 减法:(a - b) mod p = (a mod p - b mod p ) mod p
  • 乘法:(a * b) mod p = (a mod p * b mod p) mod p
  • 幂运算:(ab) mod p = ((a mod p)b) mod p (这个幂运算的规律后续会经常用到)

另外还有一个公式要了解:(其实就是幂运算的一种情况)

axy mod p = ((ax mod p)y )mod p 证明如下:

axy mod p =(ax * ax .... * ax)mod p (注:y 个 ax 相乘等于 axy)。

            =  (a<sup>x</sup> mod p   * a<sup>x</sup> mod p....  * a<sup>x</sup>mod p )mod p(根据乘法规律可得)

            =   ( (a<sup>x</sup> mod p )<sup>y</sup> )  mod p   ( y 个 a<sup>x</sup>mod p 相乘,也就是(a<sup>x</sup> mod p )<sup>y</sup>)

还有一个公式知道即可:若 a ≡ b(mod m),则 (a - b)mod m = 0。这个很好推导:

  • 假设 a mod m 的余数是 y,则 a mod m = y; 另外,b mod m 也等于 y
  • 假设 a = km + y (k 是正整数),b = zm + y (z 也是整数)
  • 那么 a - b = (km + y )- (zm + y) = (k - z)m,这个数 mod m,余数当然是 0 了。

# 取模运算的用处

在公钥加密算法中,由于公钥是对所有人公开的信息,我们需要保证数据被“公钥”加密之后,不能够被轻易地反推出来。

那什么样的算法单向计算容易,而逆向反推却非常难呢?答案是模运算(Modular Arithmetic),像计算机中的伪随机数,散列(hash)算法都是它的典型应用。

试想下面这个例子:33 mod 7 的值是多少?要计算 3 的 3 次方对 7 取余数,很容易;算出来等于 27 mod 7 = 6;

但如果是这个式子:3x mod 7 = 6。已知余数是 6 的情况下,我们又应当如何去寻找这里的 x 值呢?

由于求余运算并不可逆,我们只能一个数一个数地带进去试:

30 mod 7 = 1

31 mod 7 = 3

32 mod 7 = 2

33 mod 7 = 6

34 mod 7 = 4

35 mod 7 = 5

但如果这里出现的是很大很大的数,例如 3x mod 935654654654651616516498465178135 = 5,再逐个去尝试就不太现实了。

这也是为什么模运算被称作是单向函数,因为对于大数来说,对模运算求逆是根本不现实的。因此也常用在加密算法里,用来生成密文。

# 质数、素数、因子

加密算法中经常会用到几种特别的数字:

  • 质数:只能被自身和 1 整除的数,就是质数,也叫素数。例如 2,3,5,7,11,13,17,19......

  • 合数:比 1 大但不是质数的数字,或者说能被 1 和自身之外的数整除的数字,例如 4 = 2 × 2, 15 = 3 × 5

  • 1 和 0 既非质数也非合数。

  • 因子:也叫因数,约数。设 a × b =c,(a 和 b 都是整数)则 a 和 b 就是 c 的因子,例如:2× 3 = 6,则 2 和 3 是 6 的因子;1 × 6 = 6,则 1 和 6 也是 6 的因子。因此 6 有两组因子

  • 公因子:能同时整除几个整数的整数。例如 4 可以整除 8,也可以整除 12,那么 8 和 12 有一个公因子 4;同理,24 和 12 也有一个公因子 4。公因子可能有多个。例如 8 和 12 的公因子有 1,2,4

  • 质因数:如果一个质数是某个数 n 的因子,我们就称这个质数为 n 的质因数

  • 分解质因数:把一个合数用质因数相乘的形式表现出来,就是分解质因数。例如:

    30=2×3×5,则 2,3,5 就是 30 的质因数。

    12=2×2×3,则 2 和 3 都是 12 的质因数

    分解质因数只针对合数,每个合数都可以写成几个质数相乘的形式。

# 大整数分解质因数

分解质因数,是非常非常困难的。分解没有公式,只能暴力破解(也就是一个个穷举),数字小的时候容易,当数字特别大时,只能靠计算机的计算速度了。

举例来说,你可以对 30 做质因数分解,也可以对 3233 进行质因数分解(61×53),但是如果让你对下面这个整数进行质因数分解呢?:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

这里直接说答案吧,上面的整数是如下两个质数的乘积:

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

比它更大的整数分解,还没有被成功过(至少没有被报到过),因此目前被破解的最长 RSA 密钥就是 768 位。事实上,这大概是人类已经分解的最大整数(232 个十进制位,768 个二进制位)。

质因数分解被认为是指数级增长类型的问题(随着数字的增大,难度指数级增长)。所以,在加密算法里,就是依靠这个特点来保证破解密钥是非常困难的,实际应用中,RSA 密钥一般是 1024 个二进制位,重要场合则为 2048 位,基本不可能被分解成功,因此也破解不了。

假如有人找到一种快速因数分解的算法,那么可能目前的加密体系得颠覆了,但找到这样的算法的可能性是非常小的,也不是本文的重点。

# 互质

互质:如果两个正整数,除了 1 以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15 和 32 没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

由互质关系能得出以下结论:

  • 1 和任意一个自然数是都是互质关系,比如 1 和 99。
  • 任意两个质数构成互质关系,比如 7 和 61。
  • 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如 3 和 10。
  • p 是大于 1 的整数,则 p 和 p-1 构成互质关系,比如 57 和 56。
  • p 是大于 1 的奇数,则 p 和 p-2 构成互质关系,比如 17 和 15。

# 欧拉函数

思考一个问题:任意给定正整数 n,请问在小于等于 n 的正整数之中,有多少个与 n 构成互质关系?(比如,在 1 到 8 之中,有多少个数与 8 构成互质关系?)

有一个计算这个数量的函数,称为欧拉函数。以 φ(n)表示(φ 是希腊字母,读音/fai/)。例如,在 1 到 8 之中,与 8 形成互质关系的是 1、3、5、7,所以 φ(n) = 4。

φ(n) 的计算方法并不复杂,我们分以下情况讨论,最后再得出通用的公式:

  1. 如果 n=1,则 φ(1) = 1 。因为 1 与任何数(包括自身)都构成互质关系。

  2. 如果 n 是质数,则 φ(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如 5 与 1、2、3、4 都构成互质关系。

  3. 如果 n 是质数的某一个次方,即 n = pk(p 是质数,k 是大于或等于 1 的整数),则 φ(pk) = pk- pk-1。比如 φ(8) = φ (23) =23 - 22 = 8 - 4 = 4。怎么推导的呢?

    首先,p 是质数,而 n 是 p 的某一个次方;那么 1×p、2×p、3×p....p(k-1)×p,这几个数都和 n 有一个共同的公因子 p, 把它们减去,剩下的就是与 n 互质的数。可以看出,上面的第二种情况是 k=1 时的特例。

    这个公式也可以写成:φ(pk) = pk- pk-1= pk(1-1/p)

  4. 如果 n 可以分解成两个互质的整数之积,n = p1 × p2,则 φ(n) = φ(p1p2) = φ(p1)φ(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。比如,φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。原理涉及到中国剩余定理,这里不展开了,毕竟本文是计算机系列,不是数学系列 (主要是因为笔者也看不懂了 🙁)

我们来总结下通用的公式是怎么得出的:

  1. 任意一个大于 1 的正整数,都可以写成一系列质数的积(合数可以质因数分解,质数的话则是 1× 本身):n = p1​k1p2​k2p3​k3......pr​kr
  2. 根据第 4 种情况,可以得出:φ (n) =φ (p1​k1) × φ (p2​k) × ...... × φ (pr​kr)
  3. 根据第 3 种情况,可以得到 φ (n) = p1​k1p2​k2p3​k3......pr​kr(1-1/p1)(1-1/p2)...(1-1/pr)
  4. 也就是等于 φ (n) = n (1-1/p1)×(1-1/p2)× ... ×(1-1/pr)。这就是通用公式

我们来测试下这个公式:

  1. φ(8) = φ(23) = 8 × (1 - 1/2) = 4
  2. φ(1323) = φ ( 33 × 72) = 1323 ×(1-1/3 )× (1 - 1/7) =756
  3. 其他的就不一一计算了

以上规律理解即可,不用死记硬背,知道有这个公式即可。

需要注意的是,即使有了这个公式,也并不是说求欧拉函数是一件很容易的事情,因为本身质因数分解是非常困难的。之前我们假设 n = p1​k1p2​k2p3​k3......pr​kr,如果不知道 p1​k1,p2​k2....pr​kr 分别是多少,还是很难计算出来欧拉函数的值的。

# 欧拉定理

欧拉函数的用处,在于欧拉定理:

如果两个正整数 a 和 n 互质,则 n 的欧拉函数 φ(n) 可以让下面的等式成立:

aφ (n)= 1 (mod n)

也就是说,a 的 φ(n)次方被 n 除的余数为 1。或者说,a 的 φ(n)次方减去 1,可以被 n 整除。比如,3 和 7 互质,而 7 的欧拉函数 φ(7)等于 6,所以 3 的 6 次方(729)减去 1,可以被 7 整除(728/7=104)。

欧拉定理的证明比较复杂,这里就省略了。我们只要记住它的结论就行了。

欧拉定理可以大大简化某些运算。比如,7 和 10 互质,根据欧拉定理,7φ (10)= 1 (mod 10),已知 φ(10)=φ( 2 × 5) = φ( 2 ) × φ(5) = 1 × 4,所以马上得到 7 的 4 倍数次方的个位数肯定是 1。因此,7 的任意次方的个位数,能很快就算出来(不用算出整个数是多少)。

欧拉定理是 RSA 算法的核心。理解了这个定理,就可以理解 RSA。

这里说一个欧拉定理的特例,假设正整数 a 与质数 p 互质,因为质数 p 的 φ(p)等于 p-1,则欧拉定理可以写成 ap-1= 1 (mod p),这就是著名的费马小定理。

# 模反元素

最后一个知识点:如果两个正整数 a 和 n 互质,那么一定可以找到整数 b,使得 ab-1 被 n 整除,或者说 ab 被 n 除的余数是 1,公式:ab ≡ 1 (mod n)。这时,b 就叫做 a 的"模反元素"。

比如,3 和 11 互质,那么 3 的模反元素就是 4,因为 ( 3 × 4 ) -1 可以被 11 整除。显然,模反元素不止一个, 4 加减 11 的整数倍都是 3 的模反元素 {...,-18,-7,4,15,26,...},即如果 b 是 a 的模反元素,则 b+kn 都是 a 的模反元素。

欧拉定理可以用来证明模反元素必然存在:aφ (n)= a × aφ (n) -1 ≡ 1(mod n) ,我们设 aφ (n) -1=b,也就是 ab ≡ 1(mod n)

可以看到,b,也就是 a 的 φ(n)-1 次方,就是 a 的模反元素。

# 课后习题

  1. 举一个生活中取模的例子
  2. 理解什么是质数、合数和质因数,并尝试质因数分解 28
  3. 理解什么是欧拉函数,并计算 28 的欧拉函数值
  4. 理解什么是欧拉定理,并计验证 7φ (20)= 1 (mod 20)
  5. 理解什么是模反元素

在往下看答案之前,请先自己计算一遍

# 课后答案

  1. 数字 28 = 2 × 14 = 2 × 2 × 7,28 这个数字很小,可以人肉眼看出质因数
  2. φ(28) = φ(2) × φ(2) × φ(7) = 1 × 1 × 6 = 6。首先是质因数分解,然后计算乘积即可
  3. φ(20) = φ(2) × φ(2) × φ(5) = 1 × 1 × 4 = 4,而 74 = 2401,2401 mod 20 =1. (目前数字都比较小,可以通过电脑自带的计算器运算)
上次更新: 2024/10/1 17:03:07
非对称加密算法介绍
RSA算法原理(二):概述

← 非对称加密算法介绍 RSA算法原理(二):概述→

最近更新
01
吐槽一下《僵尸校园》
05-15
02
2025 年 4 月记
04-30
03
山西大同 “订婚强奸案” 将会给整个社会带来的影响有多严重? - 知乎 转载
04-26
更多文章>
Theme by Vdoing | Copyright © 2022-2025 | 粤 ICP 备 2022067627 号 -1 | 粤公网安备 44011302003646 号 | 点击查看十年之约
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式