RSA加密算法详细解说[通俗易懂]

RSA加密算法详细解说[通俗易懂]RSA加密算法是一种非对称加密算法,于1977年由罗纳德·李维斯特(RonRivest)阿迪·萨莫尔(AdiShamir)伦纳德·阿德曼(LeonardAdleman)一起提出的。RSA的优势:对极大整数做因数分解的难度决定了RSA算法的可靠性,对一极大整数做因数分解愈困难,RSA算法愈可靠加密由公钥,私钥,明文,密文,四部分组成。质数与互质数一个大于1的自然数,除了1和它本身…

大家好,又见面了,我是你们的朋友全栈君。

RSA加密算法是一种非对称加密算法,于1977年由
罗纳德·李维斯特(Ron Rivest)
阿迪·萨莫尔(Adi Shamir)
伦纳德·阿德曼(Leonard Adleman)一起提出的。

RSA的优势:对极大整数做因数分解的难度决定了RSA算法的可靠性,对一极大整数做因数分解愈困难,RSA算法愈可靠

加密由公钥,私钥,明文,密文,四部分组成。

质数与互质数

一个大于1的自然数,除了1和它本身外,不能被其他自然数整除(除0以外)的数称之为质数(素数);否则称为合数。

例如,15=3×5,所以15不是素数
13除了等于13×1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数
1不是质数,也不是合数
公约数只有1的两个数,叫做互质数

取模运算

也就是求余数
例如,10 mod 3 = 1(10%3=1) 、26 mod 6 = 2 、28 mod 2 = 0

同余定理

“≡”是数论中表示同余的符号
同余的定义如下:
给定一个正整数m,如果两个整数a和b满足a – b能被m整除,即(a – b)modm=0,
那么就称整数a与b对模m同余,记作a ≡ b ( mod m),同时可成立a mod m = b
注意,同余与模运算是不同的
显然,有如下事实
(1)若a≡0(mod m),则m|a;
(2)a≡b(mod m)等价于a与b分别用m去除,余数相同。

欧拉函数

任意给定正整数n,计算在小于等于n的正整数之中,有多少个与n构成互质关系?计算这个值的方法就叫做欧拉函数,以φ(n)表示.

例如,在1到8之中,与8形成互质关系的是1、3、5、7,所以φ(n)=4

在RSA算法中,欧拉函数对以下定理成立
1.如果n可以分解成两个互质的整数之积,即n=p×q,则有:φ(n)=φ(pq)=φ( p )φ( q );
2.当p为质数,φ( p )=p-1

所以有φ(n)=(p-1)(q-1)

欧拉定理与模反元素

欧拉函数的用处,在于欧拉定理
“欧拉定理”指的是:
如果两个正整数a和n互质,则n的欧拉函数φ(n)可以让下面的等式成立:
a^φ(n)≡1(modn)
也就是说,a的φ(n)次方被n除的余数为1

模反元素的推导过程如下:
根据欧拉定理,有:
a^φ(n) = a × a^(φ(n)−1)≡1(modn)

b=a^(φ(n)−1),得:

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

所以求私钥d的公式:d*e≡1mod[(p-1)(q-1)]

其中{φ(n) = (p-1)(q-1),φ(n) 与e互质,k为正整数}
可化为:d= (k*φ(n)+1)/e

推导公式:d*e≡1mod φ(n)

可得:(d*e-1) / φ(n) =k

即:d = (k*φ(n)+1) / e

在这里插入图片描述

RSA密钥一般是1024位(安全)

由p,q,dp,dq,c求明文的算法

代码如下:

import gmpy2
I = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)               #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq       #求明文公式

print(hex(m))          #转为十六进制

一切以解题为目的的抄代码都是没有灵魂的,我们还是要从数学理论上去分析解决它,再去写代码。
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130540.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • java软件开发工程师面试题_软件开发工程师面试题

    java软件开发工程师面试题_软件开发工程师面试题Java软件高级工程师笔试题【智力部分】(30分)1.烧一根不均匀的绳要用一个小时,如何用它来判断半个小时?(5分)两头同时烧2.4,4,10,10,加减乘除,怎么出24点?四个数字分别

  • Python 学习笔记 列表 range() xxx XXX

    Python 学习笔记 列表 range() xxx XXXPython学习笔记列表range()xxxXXXprint(“-“*30)forvalueinrange(1,5): print(value)numbers=list(range(1,6))print(numbers)even_numbers=list(range(2,11,2))print(even_numbers)squares=[]forvalueinr…

  • C++函数指针、指针函数、返回值为函数指针的函数浅谈

    C++函数指针、指针函数、返回值为函数指针的函数浅谈C++函数指针、指针函数、返回值为函数指针的函数浅谈引言函数指针、指针函数是C中重要而容易混淆的概念,博主将通过两个实例来说明这两个截然不同的概念。而返回值为函数指针的指针函数就更难理解了,放在文章的最后来介绍。函数指针函数指针是一种特殊的指针,它指向函数的入口。例如int(*add)(int,int);定义了一个函数指针add,用于指向返回值为int,并且有两个int参数的函数…

  • win10系统中pdf不显示缩略图及预览图

    win10系统中pdf不显示缩略图及预览图试试这个,我的取消了复选框反而出现了预览图:https://helpx.adobe.com/cn/acrobat/using/enable-pdf-thumbnail-preview-windows-explorer.html

  • icon矢量图标库_阿里ceo

    icon矢量图标库_阿里ceo啦啦啦啦啦

    2022年10月24日
  • PostgreSQL-模糊查询

    PostgreSQL-模糊查询!/bin/bash1模糊查询时,大多数情况下首先想到的是like‘%关键字%’或基于gin索引的正则表达式,gin至少需要三个字符才会使用索引,对于汉语来说十分不方便;2在海量数据的情况下,基于like和gin索引的正则表达式均不理想时,一般采用分词后进行查询.3分词存在两个弊端3.1词库的维护是比较繁重的工作.当词库中没有的关键词会导致查询结果不正确.3.2历史数据的维护工作不好处理

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号