Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

RSA 背后的算法

Posted on 11/16/201907/04/2022 by 四火

RSA这篇文章我本来是想写了放到极客时间上我写的专栏里面的,但是专栏的内容是需要仔细斟酌的。这篇文章我认为还是偏难,不适合整个专栏的内容和难度的定位,因此我把它稍微加工了一下,放到我这个博客上。

在专栏中的第 36 讲的选修课堂中,我介绍了 Diffie–Hellman 密钥交换这一算法,它可以说是质数在加密技术中的一个应用,并且是通过其中的 “模幂运算” 来实现的。今天,我来介绍质数的另一个应用,RSA 背后的算法。我在互联网上搜索了一下,我发现基本没有能把它背后的实现原理用浅显的中文叙述讲清楚的,但我还是想试一试,看看能不能尽可能避开那些难懂的术语,用尽量形象和易于理解的方式,把 RSA 背后的原理讲清楚。

在专栏的第 02 讲,我们讲了非对称性加密,比如通过公钥加密的数据,能且只能通过私钥来解密,可是这是怎样实现的呢?这就要讲 RSA 加密技术的原理了。现在,假定我们要通过 RSA 来进行安全的通信,于是你要使用我发布的公钥来对数据加密,加密以后发给我,我拿到加密数据以后使用对应的私钥解密,而攻击者截获了这个加密数据并尝试破解。

模幂等式

我们在介绍 Diffie–Hellman 密钥交换的时候讲到了这个模幂等式:

gᵃ mod p = A

从难度上看它具有如下三个特性:

  • 特性 ①:已知 g、a 和 p,求 A 容易;
  • 特性 ②:已知 g、p 和 A,求 a 困难;
  • 特性 ③:已知 a、p 和 A,求 g 也困难。

再看看上面我们介绍的模幂公式关于离散对数求解的三种难易程度不同的情况吧,我们在 Diffie–Hellman 密钥交换中应用了特性 ① 和特性 ②,而在 RSA 中,我们还要应用特性 ① 和特性 ③。

观察特性 ①,我们可以利用它来设计 RSA 加密,即让 g 代表需要被加密的实际值,而 a、p 可以公开。于是你就求出它的 a 次幂,并取 p 模,得到了 “密文” A,把它发给我。这个过程中,如果 A 被截获,那么根据特性 ③,已知 A、p 和 a,攻击者是很难求解出 g 来的。我们已经说过了,这符合 “正向计算简单,逆向求解困难” 这一特性,这一点很适合用来加密。

但是和前面的 Diffie–Hellman 密钥交换不同的是,我们并不是要让所有人都求解这个 g 困难,因为密文是发给我的,我得很容易求解这个 g 才行啊,要不然就像是用一把没人拥有钥匙的锁来加密,这把锁就失去意义了。

我们再来观察一下这个模幂等式:

gᵃ mod p = A

藉由 Diffie–Hellman 密钥交换带来的灵感,如果我们构造这样一个和上式形式一致,但变量具有一定对称性的等式:

Aᵈ mod p = g

这其实是什么?这不就是将加密的数据 A,经过模幂运算以后,得到了原始的未加密数据 g 了吗?也就是说,既然 a 是公钥,那么这里的 d 就是所谓的 “私钥” 啊。

好,我们把后面这个公式的 A 通过前面那个公式来带入,得到:(gᵃ mod p)ᵈ mod p = g,根据我们前面介绍模幂运算时提到的联等公式,它就可以化简为:

gᵃᵈ mod p = g

因此这个式子,就表示出了公钥、私钥,以及被加密数之间的关系。

接下去,我们来思考怎样生成这个私钥 d。

欧拉函数

为了继续进行后面的分析,我们需要一点知识储备,首先是欧拉函数。欧拉函数 φ(x) 表示,有多少不大于 x 的正整数中,与 x 互质的数目(即公因数只有 1)。

举例来说,要计算 φ(4),你看不大于 4 的正整数包括 1、2、3、4,其中:

  • 1 和 4 互质;
  • 2 不和 4 互质,因为它们有公因数 2;
  • 3 和 4 互质;
  • 4 不和 4 互质,因为它们有公因数 4。

所以 φ(4) = 2。

欧拉函数 φ(x) 一般很难计算,但是如果 x 是质数,情况就不同了,因为质数和任何比它小的正整数互质,比如 φ(5) = 4,这四个数分别是 1、2、3、4,因此,在 x 是质数的情况下:

φ(x) = x – 1

同时,如果 x 是一个可以因式分解的合数,比如 x = m*n,欧拉函数还具备这样的特性:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这个公式我们后面还会用到。

欧拉定理

有了欧拉函数的知识,我们进一步了解欧拉定理。欧拉定理指的是,对于正整数且互质的 g 和 x,有如下性质:

gᵠ⁽ᴾ⁾ ≡ 1 (mod p)

其中的三横线不是表示 “恒等”,而是表示 “同余”,上面的意思是,g 的 φ(p) 次幂,除以 p 所得的余数,和 1 除以 p 所得的余数,二者相同。

举例来说,当 g=3,p=5,根据前面学的欧拉函数有 φ(5)=4,那么 gᵠ⁽ᴾ⁾=81,81 除以 5 余 1;1 除以 5 也余 1,同余关系成立。

密钥生成

由于 1ᵏ ≡ 1 (mod p),我们可以给指数上的欧拉函数赋予正整数系数 k,gᵏᵠ⁽ᴾ⁾ ≡ 1 (mod p),我们再给两边乘以 g,得到 gᵏᵠ⁽ᴾ⁾⁺¹ ≡ g (mod p)。当 g 小于 p 的时候,g 除以 p 的余数就是 g,因此这个同余式可以写成:

gᵏᵠ⁽ᴾ⁾⁺¹ mod p = g

再联想前面的:

gᵃᵈ mod p = g

你看,这两个式子的形式是一样的,这就意味着,kφ(p)+1 = ad。因此,这个私钥就是:

d = (kφ(p)+1)/a

这意味着什么?这意味着如果能够求得 φ(p) 的值,那么这个私钥就求解出来了。但是,怎样求解 φ(p) 呢?这里,我希望:

  • 密钥是我生成的,因此我求解这个 φ(p) 要非常容易,这样我就可以很容易计算出密钥来;
  • p 是公开的,攻击者仅仅知道 p,求解 φ(p) 要非常困难才行,那样才能保证加密的安全性。

你看,这是不是又一个需要 “正向计算简单,逆向求解困难” 特性的问题?

回想一下前面我们学习欧拉函数的时候,我讲到了,如果 m、n 是质数,那么欧拉函数可以这样求得:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这正是我需要的!

你想,如果我选取两个非常非常大的质数 m 和 n,选择 p 的时候,就让它等于 m 和 n 的乘积,那么 φ(p) = φ(m*n) = (m-1) * (n-1),这个正向计算是很简单的,也就是说,因为我知道 m、n,密钥的生成是很容易的一件事情。

可是,攻击者拿不到 m、n,就只能硬生生地尝试去给 p 因式分解才能得到 m、n,而对于这两个因子为超大质数的因式分解,其过程是极其困难的。纵观整个 RSA 的原理,其中涉及到了两个和质数相关的 “正向计算简单,逆向求解困难” 的特性:

  • 一个是前面介绍的模幂等式逆向求底数;
  • 另一个就是这里介绍的超大质数因子的因式分解。

这也就是 RSA 安全性的基本原理。

当然,随着科技发展,计算能力越来越强,特别是量子计算的兴起,我们对超大质数的位数要求也越来越高,512 bit 的 RSA 已经被破解,而 1024 bit 也已经摇摇欲坠,现阶段 2048 bit 长度还是安全的,可是未来,谁又知道呢?

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat

你可能也喜欢看:

  1. Blog 安全问题小记
  2. Dynamo 的实现技术和去中心化
  3. LeetCode 算法题目解答汇总
  4. 谈谈微信的信息流
  5. 近期面试观摩的一些思考

1 thought on “RSA 背后的算法”

  1. abc says:
    12/26/2019 at 10:08 PM

    超大的因式分解

    Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Spark 互联网 亚马逊 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 眼界 程序员 管理 系统设计 缓存 编程范型 美股 英语 西雅图 设计 问题 面向对象 面试

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Machine Learning and Artificial Intelligence (6)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • panshenlian.com on 初涉 ML Workflow 系统:Kubeflow Pipelines、Flyte 和 Metaflow
  • panzhixiang on 关于近期求职的近况和思考
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme