程序员经验分享-hwhale

非对称加密算法--RSA加密原理详解

2023-11-04

密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。

密码学发展史

在说RSA加密算法之前， 先说下密码学的发展史。其实密码学的诞生，就是为了运用在战场，在公元前，战争之中出现了秘密书信。在中国历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。在遥远的西方，在希罗多德（Herodotus）的《历史》中记载了公元前五世纪，希腊城邦和波斯帝国的战争中，广泛使用了移位法进行加密处理战争通讯信息。

相传凯撒大帝为了防止敌人窃取信息，就使用加密的方式传递信息。那么当时的加密方式非常的简单，就是对二十几个罗马字母建立一张对照表，将明文对应成为密文。那么这种方式其实持续了很久。甚至在二战时期，日本的电报加密就是采用的这种原始加密方式。
凯撒密码对照表

早期的密码学一直没有什么改进，几乎都是根据经验慢慢发展的。直到20世纪中叶，由香农发表的《秘密体制的通信理论》一文，标志着加密算法的重心转移往应用数学上的转移。于是，逐渐衍生出了当今重要的三类加密算法：非对称加密、对称加密以及哈希算法（HASH严格说不是加密算法，但由于其不可逆性，已成为加密算法中的一个重要构成部分）。

1976年以前，所有的加密方法都是同一种模式：加密和解密使用同样规则（简称"密钥"），这被称为"对称加密算法"，使用相同的密钥，两次连续的对等加密运算后会回复原始文字，也有很大的安全隐患。

1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。也正是因为这个算法的产生，人类终于可以实现非对称加密了：A给B发送信息

  1. B要先生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
  2. A获取B的公钥，然后用它对信息加密。
  3. B得到加密后的信息，用私钥解密。
    理论上如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是232个十进制位，也就是768个二进制位，因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全，当然量子计算机除外。

RSA算法的原理

下面进入正题，解释RSA算法的原理，其实RSA算法并不难，只需要一点数论知识就可以理解。

  1. 素数：又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。
  2. 互质，又称互素。若N个整数的最大公因子是1，则称这N个整数互质。
  3. 模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。
欧拉函数

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以φ(n)表示。

  • 计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8
    φ(8) = 4
    如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则φ(n) = φ(p^k) = p^k - p^(k-1)。也就是φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4
  • 计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7
    φ(7) = 6
    如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
  • 计算56的欧拉函数
    φ(56) = φ(8) * φ(7) = 4 * 6 = 24
    如果n可以分解成两个互质的整数之积，即 n = p * k ，则φ(n) = φ(p * k) = φ(p1)*φ(p2)

欧拉定理：如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。
欧拉定理.png

费马小定理：欧拉定理的特殊情况，如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。
费马小定理.png

模反元素

还剩下最后一个概念，模反元素：如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除，或者说ed被x除的余数是1。
那么d就是e相对于x的模反元素。
d是模反元素

等式转换

  1. 根据欧拉定理
    等式转换1

  2. 由于1^k ≡ 1，等号左右两边都来个k次方
    等式转换

  3. 由于1* m ≡ m，等号左右两边都乘上m
    等式转换3.png

根据模反元素，因为e*d 一定是x的倍数加1。所以如下：
等式转换

通过多次的等式转换。终于可以将这两个等式进行合并了！如下：
最终等式转换

这个等式成立有一个前提！就是关于模反元素的，就是当整数e和φ(n)互质！一定有一个整数d是e相对于φ(n)的模反元素。
我们可以测试一下。
m取值为4
n取值为15
φ(n)取值为8
e 如果取值为3
d 可以为 11、19…(模反元素很明显不止一个，其实就是解二元一次方程)
如果你测试了，那么你可以改变m的值试一下，其实这个等式不需要m和n 互质。只要m小于n 等式依然成立。
这里需要注意的是，我们可以看做 m 通过一系列运算得到结果仍然是 m。这一系列运算中，分别出现了多个参数n、φ(n)、e还有d。

m 的 e乘上d 次方为加密运算，得到结果 c
c 模以 n 为解密运算，得到结果 m
这似乎可以用于加密和解密。但这样，加密的结果会非常大。明文数据将非常小（虽然RSA用于加密的数据也很小，但是没这么大悬殊），真正的RSA要更加强大，那么RSA是怎么演变来的呢？？
早期很多数学家也停留在了这一步！直到1967年迪菲赫尔曼密钥交换打破了僵局！

迪菲赫尔曼密钥交换

这个密钥交换当时轰动了整个数学界！而且对人类密码学的发展非常重要，因为这个伟大的算法能够拆分刚才的等式。当非对称加密算法没有出现以前，人类都是用的对称加密。所以密钥的传递，就必须要非常小心。
迪菲赫尔曼密钥交换 就是解决了密钥传递的保密性，我们来看一下
迪菲赫尔曼密钥交换
假设一个传递密钥的场景。算法就是用3 的次方去模以17。 三个角色

  • 服务器 随机数 15
    这个15只有服务器才知道。通过算法得到结果 6 因为 3的15次方 mod 17 = 6 。然后将结果 6 公开发送出去，拿到客户端的 12 ，然后用12^15 mod 17 得到结果10(10就是交换得到的密钥)
  • 客户端 随机数13
    客户端用3 的 13次方 mod 17 = 12 然后将得到的结果12公布出去。
    拿到服务器的 6 ，然后用6^13 mod 17 得到结果10(10就是交换得到的密钥)
  • 第三者
    第三者只能拿到6 和 12 ，因为没有私密数据13、15，所以它没法得到结果10。

为什么 6的13次方会和12的15次方得到一样的结果呢?因为这就是规律，我们可以用小一点的数字测试一下3^3 mod 17 = 10和10 ^ 2 mod 17 ； 3 ^ 2 mod 17 = 9和9^3 mod 17结果都是15。迪菲赫尔曼密钥交换最核心的地方就在于这个规律
迪菲赫尔曼密钥交换转换

RSA的诞生

RSA原理

现在我们知道了m^e % n = c是加密，c^d % n = m是解密，m就是原始数据，c是密文，公钥是n和e，私钥是n和d，所以只有n和e是公开的。加密时我们也要知道φ(n)的值，最简单的方式是用两个质数之积得到，别人想破解RSA也要知道φ(n)的值，只能对n进行因数分解，那么我们不想m被破解，n的值就要非常大，就是我们之前说的，长度一般为1024个二进制位，这样就很安全了。但是据说量子计算机(用于科研，尚未普及)可以破解，理论上量子计算机的运行速度无穷快，大家可以了解一下。

以上就是RSA的数学原理

检验RSA加密算法

我们用终端命令演示下这个加密、解密过程。
假设m = 12(随便取值，只要比n小就OK)，n = 15(还是随机取一个值)，φ(n) = 8，e = 3(只要和φ(n)互质就可以)，d = 19（3d - 1 = 8，d也可以为3,11等等，也就是d = (8k + 1)/3 ）
终端分别以m=12，7输入结果
终端演示

OpenSSL进行RSA的命令运行

Mac可以直接使用OpenSSL，首先进入相应文件夹

  • 生成公私钥
// 生成RSA私钥，文件名为private.pem，长度为1024bit
openssl genrsa -out private.pem 1024

// 从私钥中提取公钥
openssl rsa -in private.pem -pubout -out publick.pem

生成私钥

// 查看刚刚生成好的私钥
cat private.pem

// 查看刚刚生成好的公钥
cat publick.pem

查看公私钥

我们可以看到base64编码，明显私钥二进制很大，公钥就小了很多。
这时候我们的文件夹内已经多了刚刚生成好的公私钥文件了

公私钥文件

// 将私钥转换为明文
openssl rsa -in private.pem -text -out private.txt

96111F25-0954-4854-9B36-75413A439AFD.png

里面就是P1、P2还有KEY等信息。

  • 对文件进行加密、解密
// 编辑文件message内容为hello Vincent!!!
// 刚刚的public.pem写成了publick.pem(哎。。。)
 $ vi message.txt
 $ cat message.txt
 hello Vincent!!!
// 通过公钥加密数据时，使用encrypt对文件进行加密
 $ openssl rsautl -encrypt -in message.txt -inkey publick.pem -pubin -out enc.txt
// 此时查看该文件内容为乱码
 $ cat enc.txt
j��E]֌a��d�kUE�&<
                 ��I*��V/��pL[���ˋ�O�+�-�M��K�ܱ�&⪅ծO��2���o34�:�$���6��C�L��,b�'M�S�k�0���A��3%�[I���1�����ps"%
// 通过私钥解密数据
 $ openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
// 已成功解密，正确显示文件内容
 $ cat dec.txt
  hello Vincent!!!

// 通过私钥加密数据时，要使用sign对文件进行重签名
$ openssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin
// 此时查看该文件内容同样为乱码
$ cat enc.bin
{���Ew�3�1E��,8-OA2�Is�:���:�ԅ@MU����؜
                                      �i1B���#��6���ׂm�D(�t#/���	�ہ�������ݬ>(�>�^@�C��3�ӸMQт�O%
// 通过公钥解密数据
$ openssl rsautl -verify -in enc.bin -inkey publick.pem -pubin -out dec.bin
// 已成功解密，正确显示文件内容
$ cat dec.bin
 hello Vincent!!!
RSA用途及特点

到这里，大家都知道RSA通过数学算法来加密和解密，效率比较低，所以一般RSA的主战场是加密比较小的数据，比如对大数据进行对称加密，再用RSA给对称加密的KEY进行加密，或者加密Hash值，也就是数字签名。

关于RSA数字签名后面再慢慢阐述。该文章为记录本人的学习路程，希望能够帮助大家，也欢迎大家点赞留言交流！！！https://mp.csdn.net/mdeditor/85228078#

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

iOS开发

非对称加密

RSA加密原理

非对称加密算法--RSA加密原理详解 的相关文章

  • iOS下XMPP开发之xmppFramework框架的导入步骤和介绍

    一个将要开发xmpp的项目 建议在项目刚创建就导入框架 这样可以避免一些自己操作失误造成不必要的损失 xmpp中最常用的框架就是 xmppFrameWork 第一种方法直接拖 1 gt 拖入文件夹 在网盘链接的xmppFramework文件

  • NSTextAttachment实现图文混排

    苹果在iOS7中推出了一个新的类NSTextAttachment 它是做图文混排的利器 本文就是用这个类 只用50行代码实现文字与表情混排 当然也可以实现段落中的图文混排 首先说一下文字和表情的混排 先来做点儿准备工作 搞一个存放表情信息的

  • OC使用cocoapods导入swift库注意

    首先就是在 targets gt Build Setting gt Packaging 中设置 Defines Module为YES 然后创建swift文件时会生成 文件名 Bridging Header h 这样一个桥接文件 怎样使用co

  • 将APP程序发布到iPhone或iPad上去测试

    转载至 http www appshare cn thread 3123 1 1 html 图文的介绍版本 http fstoke me blog tag apple 绝大多数iPhone Developer Distribution 的代

  • 2022最新苹果开发者账号注册、付款流程图解【图文并茂】

    更新日期 2022 07 22 每年续费就有一个坑 文章末尾已注明 1 申请一个邮箱 用于注册苹果开发者账号 我的邮箱 密码 2 注册开发者账号 1 注册官网 官网地址 Apple Developer Program Apple Devel

  • 非对称加密算法--RSA加密原理详解

    密码学是在编码与破译的斗争实践中逐步发展起来的 并随着先进科学技术的应用 已成为一门综合性的尖端技术科学 密码学发展史 在说RSA加密算法之前 先说下密码学的发展史 其实密码学的诞生 就是为了运用在战场 在公元前 战争之中出现了秘密书信 在

  • iOS开发之第三方支付支付宝支付教程，史上最新最全第三方支付宝支付方式实现、支付宝集成教程，支付宝实现流程

    本章项目demo https github com zhonggaorong alipayDemo 支付宝支付大致流程为 1 公司与支付宝进行签约 获得商户ID partner 和账号ID seller 和私钥 privateKey 开发中

  • ios-常见的命令行工具

    pwd 查看当前目录 cat 在命令行中查看文件 ls 查看文件 ls l 就是以列表的形式展开 touch 创建文件 open 打开文件 more 分页查看文件内容 f是下一页 b是上一页 当你命令行有很多东西你写错了的时候不想去一一删除

  • ios10.3之CoreData的详细教程

    首先如果要使用CoreData可以选择在初创项目时选择添加coredata 也可以选择自己添加coredata文件 系统添加coredata后会在Appdelegate类中自动添加一个persistentContainer属性 和一个sav

  • 使用FTP（IOS FTP客户端开发教程）

    本文翻译自新近Wrox出版社出版的 由Peter van de Put所著的 Professional iOS Programming 该书题材比较新颖 结构合理 是一本不错的IOS开发书籍 本文译自该书第八章 Using FTP 本文开放

  • iOS 应用获取最上层全屏 Window 的正确方法

    有时候 我们需要将View添加到最上层的Window上 比如 弹出框 Loading等 经常有同学直接通过 UIApplication sharedApplication windows lastObject 来获取 这种方法是非常不严谨的

  • 一个奇怪的GCD内存不释放的问题

    这个问题是我的同学提出来的 原帖在http bbs csdn net topics 390933411 大概是这样 pre class objc IBAction touchToCreateThread id sender int i 10

  • iOS开发实战之app获取通讯录（iOS 9）

    在做通讯类APP的时候 时常会访问到手机的通讯录 来获取联系人的各种属性 那么本文就来讨论一下怎么获取通讯录 注意 iOS 9 版本上可以行 其他版本未试 第一步 先导入系统库 Contacts framework 然后在 h上导入头文件

  • iOS内购-防越狱破解刷单

    2018 10 16更新 最近我们公司丢单率上涨 尤其是10月份比9月份来说丢单率翻了3倍 和一些同行交流了一下 发现他们也是丢单量增加 初步推断可能是苹果iOS12的原因 某些情况下会有用户内购成功后 却返回的是订单失败 错误类型为SKE

  • APNS编程----iOS真机测试消息推送

    一 准备工作 1 拥有一台iOS为操作系统的苹果设备 iPhone iPad iPod都可以 2 拥有苹果开发者账号 需要真机调试 最好是是付费开发者 后面的步骤将会更顺利 3 需要一台PC做推送服务器 如果是台拥有MAC OS系统 将会更

  • iOS Cookies.binarycookies（俗称63数据）存取

    iOS 系统会自动将Safari或APP中网络请求的cookie保存为文件 APP的cookie保存路径为APP的沙盒路径 var mobile Containers Data Application x x x Library Cooki

  • 分布式环境下使用RSA算法实现登录密码的加密传输

    目录 效果 RSA介绍 实现思路 服务端实现 RSAService RSA算法的相关操作 RedisService 公钥和密钥的存储和获取 获取公钥的接口 客户端使用公钥加密 服务端使用私钥解密 效果 RSA介绍 RSA是一种非对称加密算法

  • Appstore审核被拒-[4. DESIGN: PREAMBLE]

    Appstore审核被拒原文如下 原因是设置里有一个版本信息可以响应点击事件进入一个版本详情页 苹果要求版本更新必须使用iOS版本更新内置更新机制 4 DESIGN PREAMBLE Design Preamble The version

  • CocoaPods创建管理类库的步骤

    用到的命令 1 git clone https github com jackLeong MySDK git 克隆一份远程仓库 2 git add fileName 把文件纳入git的缓存区 可使用 代替目录下的所有文件 3 git sta

  • iOS App打包上架详细流程

    一 前言 作为一名iOS开发者 把辛辛苦苦开发出来的App上传到App Store是件必要的事 但是很多人还是不知道该怎么上传到App Store上 下面就来详细讲解一下具体流程步骤 二 准备 一个已付费的开发者账号 可分为 账号类型分为个

随机推荐

  • P2524 Uim的情人节礼物·其之弐【康托展开模板题】

    题目链接 我在这里加了树状数组来优化康托展开 但是这道题的数据其实很小 不需要加也是可以的 include

  • 27 类深度学习主要神经网络

    1 感知器 Perceptron P 感知器模型也称为单层神经网络 这个神经网络只包含两层 输入层 输出层 这种类型的神经网络没有隐藏层 它接受输入并计算每个节点的加权 然后 它使用激活函数 大多数是Sigmoid函数 进行分类 应用 分类

  • 49 题目 1431: [蓝桥杯][2014年第五届真题]分糖果

    题目 1431 蓝桥杯 2014年第五届真题 分糖果 时间限制 1Sec 内存限制 128MB 提交 5807 解决 2969 题目描述 问题描述 有n个小朋友围坐成一圈 老师给每个小朋友随机发偶数个糖果 然后进行下面的游戏 每个小朋友都把

  • Python中Requests模块的异常值处理

    在我们用Python的requests模块进行爬虫时 一个简单高效的模块就是requests模块 利用get 或者post 函数 发送请求 但是在真正的实际使用过程中 我们可能会遇到网络的各种变化 可能会导致请求过程发生各种未知的错误导致程

  • Vue中的路由以及默认路由跳转

    文章目录 官方网址 Vue路由配置 安装 引入并使用 配置路由 官方网址 https router vuejs org Vue路由配置 安装 npm install vue router save 或者 cnpm install vue r

  • SpringBoot集成XxlJob分布式任务调度中心（超详细之手把手教学）

    一 前言 废话就不多说了 介绍Xxl Job的网上已经有很多 本文就不多加复制粘贴了 直接步入第二步 PS 本文包括Xxl Job分布式定时任务调度中心的搭建 以及SpringBoot集成XxlJob的全过程 如果不想了解搭建的小伙伴可以直

  • 判断加密方式

    如何判断密文的加密方式 1 如果密文是十进制 字符范围是 0 9 可以猜测是ASCII编码 2 如果密文由 a z A Z 和 构成 特别是末尾有 那么判断可能是Base64编码 Base64在线解码网址 BASE64加密解密 3 如果密文

  • Docker 部署 RocketMQ

    文章目录 安装nameserver 拉取镜像 运行容器 出现问题卸载 安装broker 创建配置文件 运行容器 出现问题卸载 安装控制台 拉取镜像 运行容器 出现问题卸载 安装nameserver 拉取镜像 docker pull rock

  • 时序预测

    时序预测 MATLAB实现ARIMA时间序列预测 armax函数 本程序基于MATLAB的armax函数实现arima时间序列预测 实现了模型趋势分析 序列差分 序列平稳化 AIC准则模型参数识别与定阶 预测结果与误差分析过程 逻辑清晰 数

  • 【NLP实践】使用Pytorch进行文本分类——BILSTM+ATTENTION

    目录 网络结构 代码实现 Attention计算 模型效果 调参 相关文章 网络结构 代码实现 class TextBILSTM nn Module def init self config TRNNConfig char size 500

  • 学习Vue 之 创建一个 Vue 应用

    文章目录 Vue js 概述 了解 Vue 创建一个 Vue 应用 参考 Vue js 概述 计划学习前端 已有一些HTML js CSS的基础知识 下一步学习Vue js 以下是一些适合新手的Vue js教程 你可以根据自己的实际情况和需

  • Python提示 TypeError: super(type, obj): obj must be an instance or subtype of type问题

    Python提示 TypeError super type obj obj must be an instance or subtype of type问题 简述问题 在工作中有一天将debug下正常工作的python代码编译之后运行却抛出

  • 奇迹mu修改服务器名,奇迹MU 红名设置调整方案说明

    尊敬的用户 经过与游戏制作方的沟通 已经确认本次游戏版本中红名设置突然调整的原因 由于韩国奇迹MU之外的所有服务器 国际服 日服 中国服务器等 将对红名设置进行统一设置 红名设置将恢复成为Season 8版本期间的模式 红名2阶段之后可以继

  • 使用JAVA连接MySQL，储存歌曲，图片，影片文件

    MySQL中创建数据表 存放歌曲等文件字节流 使用longblob字段类型 我这个只是演示所以就一个字段 如果想比较好的管理文件 不要这么搞 create dadabase ttest use ttest create table musi

  • 【stm32单片机基础】按键状态机实现长按和短按

    stm32单片机基础 按键状态机 文章目录 stm32单片机基础 按键状态机 前言 一 按键的消抖 二 按键状态机实现 0 状态机模式 1 单个按键检测 2 单个按键实现长按和短按 三 长按和短按测试示例 四 多按键检测 按键处理经典例程

  • openEuler20.03如何安装图形化界面

    需求描述 需要安装图形界面方便操作 详细步骤 1 安装ukui图形界面 字体库 root localhost yum install ukui y root localhost local yum groupinstall fonts y

  • 2021白盒测试常用工具介绍【建议收藏】

    白盒测试工具一般是针对代码进行测试 测试中发现的缺陷可以定位到代码级 根据测试工具原理的不同 又可以分为静态测试工具和动态测试工具 1 Jtest 是一个代码分析和动态类 组件测试工具 是一个集成的 易于使用和自动化的Java单元测试工具

  • js 在数组对象中模糊搜索（直接上代码）

    1 测试数据 学生对象数组 var students id 1 name 张三 age 14 id 2 name 李四 age 15 id 3 name 王五 age 17 id 4 name 赵六 age 18 2 查询操作 根据下标查询

  • 写论文的开源免费神器汇总

    科研办公学习的开源免费神器汇总 一 公式 1 Mathtype 是一款专业的数学公式编辑工具 理科生专用的工具 mathtype公式编辑器能够帮助用户在各种文档中插入复杂的数学公式和符号 2 Mathpix Mathpix可以将图片 PDF

  • 非对称加密算法--RSA加密原理详解

    密码学是在编码与破译的斗争实践中逐步发展起来的 并随着先进科学技术的应用 已成为一门综合性的尖端技术科学 密码学发展史 在说RSA加密算法之前 先说下密码学的发展史 其实密码学的诞生 就是为了运用在战场 在公元前 战争之中出现了秘密书信 在

热门标签