RSA 加密的原理——为什么被公钥加密的可以被私钥解密

本贴最后更新于 2351 天前,其中的信息可能已经渤澥桑田

RSA 加密的原理——为什么被公钥加密的可以被私钥解密?
目录
一,RSA 数学理论基础

二,RSA 实现原理

三,RSA 加密的过程

四,参考文献

引言
在密码学最开始,都是使用的普通加密模式

A 用加密规则加密了字符串 m 然后发给 B

B 用 A 的加密规则来解密,得到原始信息 m

在这个过程中 A 必须把自己的加密规则告诉 B,否则 B 无法解密这段密文,但是如果把加密规则也告诉 B,在传递密钥的过程中,可能就会被拦截获取,这就是最大的问题。

所以,后来又 3 位数学家提供了一种算法,实现非对称加密,后来算法也以他们三个的首字母命名,R(Rivest)S(Shamir )A(Adleman )算法。

最开始,我一直理解不了为什么公钥加密的可以被私钥解密,一直停留在使用层面,直到今天看到一篇博客,才解决了心中的疑惑。

一,RSA 必备数学理论基础
要理解整个 rsa 的流程,需要以下数学基础

1,互质关系
两个正整数,除 1 以外,再没有别的公因子。 比如 2 和 3, 2 和 9。

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

计算上面这个多少个的函数就被成为欧拉函数,以 φ(n)表示。在 1 到 8 之中,与 8 形成互质关系的是 1、3、5、7,所以 φ(n) = 4。

3,欧拉定理
由上面的欧拉函数可以经过一系列的推导,得到欧拉定理

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

4,特殊情况——费马小定理
欧拉定理的特殊情况,当第二个数 n 为质数的情况。

假设正整数 a 与质数 p 互质,因为质数 p 的 φ(p)等于 p-1,

5,模反元素
如果两个正整数 a 和 n 互质,那么一定可以找到整数 b,使得 ab-1 被 n 整除,或者说 ab 被 n 除的余数是 1。

比如 a = 3 ,n = 5,则一定有(a*b)%n =1 ,即 3b -1 = 5y,即一定存在一个数 2,可以满足上式。

6,快速幂取模计算
如果有两个大数 a,b,a^b 可能是一个计算机无法表示的大数,则(a^b)%c 的值如何计算?

这里可以使用快速幂取模算法。

java 代码如下:

/**

  • 快速幂取模 计算 (a^b) %c
  • @param a
  • @param b
  • @param c
  • @return 计算结果
    */
    private static int quick(int a,int b,int c) {
    int ans=1; //记录结果
    a=a%c; //预处理,使得 a 处于 c 的数据范围之下
    while(b!=0)
    {
    if((b&1)==1){ //1 即是 0000000000000001,判断个位是否是 1.如果 b 的二进制位是 1,那么我们的结果是要参与运算的
    ans=(ans*a)%c;
    }
    b>>=1; //二进制的移位操作,相当于每次除以 2,用二进制看,就是我们不断的遍历 b 的二进制位
    a=(a*a)%c; //不断的加倍
    }
    return ans;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    参考了文章

https://blog.csdn.net/ltyqljhwcm/article/details/53043646

二,RSA 实现原理
第一步,选择两个不等质数 p,q(实际密钥一般为 1024 位或 2048 位)
这里我们选择 61 和 53。

第二步,计算乘积 n ####
n = p*q = 3233 (二进制 110010100001,只有 12 位)

第三步,计算 n 的欧拉函数 φ(n)
φ(n) = φ(p)*φ(q)= (p-1)(q-1) = 3120 。一个质数 p 的欧拉函数等于 p-1

第四步,随机选择一个整数 e,条件是 1< e < φ(n),且 e 与 φ(n) 互质。
取 e = 17 (实际应用中,常常选择 65537)。

第五步,计算 e 对于 φ(n)的模反元素 d。
即找出一个 d 满足 ed 互质,且对于 φ(n) 取模为 1 ,即 ed = 1 (mod φ(n))。

即 ed -1 = kφ(n) ,带入上面已知条件:

17d -1 = k3120 即 17x +3120y = 1 (据说可以使用 扩展欧几里得算法求解)

这里直接给出答案 d = 2753。

第六步,将 n 和 e 封装成公钥,n 和 d 封装成私钥。
代入本次的推导过程中的数字,n = 3233,e = 17, d=2753。公钥为(3233,17),私钥为(3233,2723)。

加密使用 (3233,17),解密使用(3233,2723)。

第七步,分析,私钥的获取
由六可以看出来,公钥和私钥的区别其实只是 d,也就是说 d 的推导是否可以在已知 n,e 的情况下推导出来。

由第五步,要得出 d,已知 n,e。需要 φ(n)。

由第三部,要得出 φ(n),需要 p,q。

而已知 n=p*q。而 n 已知,只需要分解 n 因子即可。

结论:只要 n 可以被分解,公私玥加密即可被破解。

第八步,n 可以被分解吗?
在本例中,3233 可以很快被破解,但是实际应用中,两个大质数的积是不容易被分解出来的

例如:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

是以下两个质数的乘积:

a:

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489

b:

36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

人类已经分解的最大整数(232 个十进制位,768 个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长 RSA 密钥就是 768 位。而 RSA 加密一般使用 1024 位或者 2048 位,基本可以理解为不可破解

三,RSA 加密的过程
1,公钥(n,e)加密
所有字符串都可以使用 ascil 码/unicode 值来表示,假设一个字符 m = a,ascii 码为 65,需要满足 m < n 对他进行加密。

m^e ≡ c (mod n),c 为加密字符串

n = 3233,e = 17。 上式可以表示为: (65^17)%3233 = c ,c = 2790。

2,私钥(n,d)解密
(n,d) = (3233,2723) 。在拿到 c = 2790 之后,进行以下操作:

c^d ≡ m (mod n) 即可得到 m 。

推导,m = (2790^2723) %3233 ,在这里使用 必备知识六中的快速幂取模,可以轻松得到答案,m = 65。

3,证明,
略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略。

四,参考文献
1,http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

2,http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

3,https://blog.csdn.net/ltyqljhwcm/article/details/53043646

作者:不会汪汪的猫咪
来源:CSDN
原文:https://blog.csdn.net/doujinlong1/article/details/82051986
版权声明:本文为博主原创文章,转载请附上博文链接!

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Word
    13 引用 • 41 回帖
  • 反馈

    Communication channel for makers and users.

    120 引用 • 906 回帖 • 280 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1708 回帖
  • OpenStack

    OpenStack 是一个云操作系统,通过数据中心可控制大型的计算、存储、网络等资源池。所有的管理通过前端界面管理员就可以完成,同样也可以通过 Web 接口让最终用户部署资源。

    10 引用 • 1 关注
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 269 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    188 引用 • 1057 回帖
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 8 关注
  • 电影

    这是一个不能说的秘密。

    123 引用 • 608 回帖
  • Jenkins

    Jenkins 是一套开源的持续集成工具。它提供了非常丰富的插件,让构建、部署、自动化集成项目变得简单易用。

    54 引用 • 37 回帖
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖 • 1 关注
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    173 引用 • 414 回帖 • 360 关注
  • WordPress

    WordPress 是一个使用 PHP 语言开发的博客平台,用户可以在支持 PHP 和 MySQL 数据库的服务器上架设自己的博客。也可以把 WordPress 当作一个内容管理系统(CMS)来使用。WordPress 是一个免费的开源项目,在 GNU 通用公共许可证(GPLv2)下授权发布。

    46 引用 • 114 回帖 • 166 关注
  • 倾城之链
    23 引用 • 66 回帖 • 169 关注
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    42 引用 • 130 回帖 • 253 关注
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 830 关注
  • OkHttp

    OkHttp 是一款 HTTP & HTTP/2 客户端库,专为 Android 和 Java 应用打造。

    16 引用 • 6 回帖 • 88 关注
  • Webswing

    Webswing 是一个能将任何 Swing 应用通过纯 HTML5 运行在浏览器中的 Web 服务器,详细介绍请看 将 Java Swing 应用变成 Web 应用

    1 引用 • 15 回帖 • 644 关注
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    10185 引用 • 46283 回帖 • 65 关注
  • ZeroNet

    ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。

    1 引用 • 21 回帖 • 649 关注
  • NetBeans

    NetBeans 是一个始于 1997 年的 Xelfi 计划,本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE,直到 1999 年 Sun 买下此公司。Sun 于次年(2000 年)六月将 NetBeans IDE 开源,直到现在 NetBeans 的社群依然持续增长。

    78 引用 • 102 回帖 • 711 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    32 引用 • 108 回帖
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    187 引用 • 832 回帖
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    115 引用 • 319 回帖
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    91 引用 • 59 回帖 • 2 关注
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖 • 9 关注
  • Mac

    Mac 是苹果公司自 1984 年起以“Macintosh”开始开发的个人消费型计算机,如:iMac、Mac mini、Macbook Air、Macbook Pro、Macbook、Mac Pro 等计算机。

    167 引用 • 597 回帖 • 2 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 767 关注