程序员经验分享-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加密原理详解 的相关文章

  • [CocoaPods]podspec文件中的resource和resource_bundle

    相信基本上所有的iOS开发同学针对于CocoaPods都不陌生 即便没有用过 也是久闻大名如雷贯耳 作为Objective C和Swift中非常流行的依赖管理工具 它拥有超过10000个公有程序库 通过一份Podfile文件和pod ins

  • iOS开发—RunLoop详解

    随着oc语言不断迭代 苹果的API也是逐步完善 RunLoop在实际开发中应用的越来越少 但是在面试中 假如面试官问你RunLoop的相关知识了解 那就相当于面试官在问你从事iOS开发工作的真实年限问题 那么下面我们就详细了解一下RunLo

  • ios屏幕的旋转，Device Orientation

    屏幕旋转 我的理解是ios设备根据重力感应改变屏幕的方向 那么如何在屏幕转动后变换UI 或则保持原样呢 ios设备支持4个方向 UIInterfaceOrientationPortrait UIInterfaceOrientationPor

  • IOS 启动画面和图标设置(适配IOS7 and Xcode5)

    关于IOS程序设置启动画面以及图标的设备目前主要为 IPhone设备 和IPad设备 IPhone启动画面以及图标的设置 目前IPhone的分辨率为 320X480 640X960 640X1136 Default png 320X480

  • iOS内购 - 服务端票据验证及漏单引发的思考

    因业务需要实现了APP内购处理 但在过程中出现了部分不可控的因素 导致部分用户反映有充值不成并漏单的情况 仔细考虑了几个付费安全上的问题 凡是涉及到付费的问题都很敏感 任何一方出现损失都是不能接受的 所以在这里整理一些支付安全的要点分享一下

  • xcodebuild使用

    转自 xcodebuild命令简单使用 简书 流程 build archive IPA teamid xcodebuild命令简单使用 前提准备证书并熟悉xcodebuild介绍 以及官方文档 xcodebuild showsdks查看可用

  • xxx.app已损坏，打不开。 您应该将它移到废纸篓。

    Mac最新的系统打开网上下载的应用程序时 会提示 xxx app已损坏 打不开 您应该将它移到废纸篓 解决方式 1 系统偏好设置 gt 安全性与隐私 gt 修改为任何来源 2 serria里面没有 任何来源 这一项 需要打开终端执行sudo

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

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

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

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

  • Xcode8不能在iOS7上调试,Could not find Developer Disk Image的解决方法

    升级完Xcode8之后 默认情况下 是无法进行iOS7的调试的 因为Xcode8里面不再游iOS7的镜像文件 所以会提示 Could not find Developer Disk Image 解决方法如下 打开finder 应用程序 Xc

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

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

  • 关于目前自己iOS项目使用的第三方开源库

    1 AFNetworking 目前比较推荐的iOS网络请求组件 默认网络请求是异步 通过block回调的方式对返回数据进行处理 2 FMDB 对sqlite数据库操作进行了封装 demo也比较简单 3 MBProgressHUD 也是iOS

  • ad Hoc打包测试

    一 iOS证书 首先介绍一下iOS证书 iOS证书分两种 1 开发证书 用来给你 开发人员 做真机测试 2 发布证书 又分为两种 发布到app store 和发布测试的ad hoc证书 本文就详细讲解 ad hoc证书的创建 二 什么时候用

  • iOS左对齐自动换行collection样式

    前言 想必大家工作中或多或少会遇到下图样式的UI需求吧 像这种cell长度不固定 以此向右对齐排列的样式UI可以说是很常见的 实现方式 一般的实现可能主要是分一下两种 1 一种是用button依次排列实现 动态计算text宽度 记录之前一个

  • iOS App上架流程

    前言 作为一名IOS开发者 把开发出来的App上传到App Store是必须的 下面就来详细介绍下具体流程 1 打开苹果开发者中心 https developer apple com 打开后点击 Member Center 如果你的电脑没有

  • Xcode5.1离线下载安装及使用iOS5模拟器进行开发调试的方法

    Xcode5 1默认不支持iOS5版本的模拟器开发调试 在OS X Mavericks 10 9 x 下默认只能支持iOS6 1及以上版本的模拟器 在OS X Mountain Lion 10 8 x 下默认只能支持iOS6 0及以上版本的

  • iOS下XMPP开发之XMPP开发环境配置（二）mac上搭建openfire服务器

    一 下载并安装openfire 1 到http www igniterealtime org downloads index jsp下载最新openfire for mac版 比如 Openfire 3 8 1 下载后的文件 openfir

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

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

  • linux 环境下 openssl 生成ecdsa公、私钥

    我的个人博客 逐步前行STEP 1 生成ecdsa私钥 openssl ecparam name prime256v1 genkey noout out prime256v1 key pem 2 从ecdsa私钥提取公钥 openssl p

  • IOS开发系列——异步绘制专题

    异步绘制专题 1 图片处理 1 1 编辑图片的几个方法 第一种 先用UIImage对象加载一张图片 然后转化成CGImageRef放到CGContext中去编辑 第二种 用CGImageCreate函数创建CGImageRef 然后把CGI

随机推荐

  • 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加密算法之前 先说下密码学的发展史 其实密码学的诞生 就是为了运用在战场 在公元前 战争之中出现了秘密书信 在

热门标签