本站消息

站长简介/公众号


站长简介:高级软件工程师,曾在阿里云,每日优鲜从事全栈开发工作,利用周末时间开发出本站,欢迎关注我的微信公众号:程序员总部,程序员的家,探索程序员的人生之路!分享IT最新技术,关注行业最新动向,让你永不落伍。了解同行们的工资,生活工作中的酸甜苦辣,谋求程序员的最终出路!

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

python面试大全(3)

python前言(0)

标签  

python面试(2)

python(0)

日期归档  

2020-12(231)

2021-01(46)

RSA算法与加密解密

发布于2021-10-18 00:19     阅读(389)     评论(0)     点赞(23)     收藏(1)



整理于多篇相关文字和网络资料,参考链接详见于文章末尾。

什么是RSA算法(RSA algorithm)

RSA算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)三人一起提出的一种非对称加密算法,RSA的名字由来就是他们三人姓氏开头字母的拼接。如今,RSA在密码传输方面具有比较大的应用,如京东、百度等,在密码传输上使用了这种算法对明文密码进行加密。

什么是非对称加密算法

非对称加密算法需要两个密钥:公开密钥(publickey:简称公钥)和私有密钥(privatekey:简称私钥)。公钥与私钥是一对,如果用公钥对数据进行加密,只有用对应的私钥才能解密。因为加密和解密使用的是两个不同的密钥,所以这种算法叫作非对称加密算法。而采用单钥密码系统的加密方法,同一个密钥可以同时用作信息的加密和解密,这种加密方法称为对称加密,也称为单密钥加密。
在这里插入图片描述

RSA加密解密原理

序号步骤
1生成两个任意不同的大质数p,q
2n=p*q
3欧拉函数f(n)=(p-1)*(q-1)
4设d与f(n)互质,d∈(1, f(n)),找到任意一个大整数e使得d*e除(p-1)*(q-1)的余数为1
5(n, d)构成公钥,C为密文,M为明文,加密C=M^d mod n
6(n, e)构成私钥,C为密文,M为明文,解密M=C^e mod n

小数据示例:

  1. p = 2 , q = 5;
  2. n = 10;
  3. f(n)=4;
  4. d ∈(2, 3),显然d=3时与f(n)互质(最大公约数为1); 则 e = 7可以满足条件
  5. 明文M=2(加密的范围收到密钥的限制,从mod n就可以很容易看出来了,这也就是n一般取大数的原因), 则密文C=8;
  6. 密文C=8,则密文M=2。

算法攻击和蓝桥杯2018年省赛题目

RSA的小指数攻击

当公钥d取较小的值,虽然会使加密变得易于实现,速度有所提高,但这样做将导致密文容易被破解。RSA的安全性依赖于大数分解,分解n是最显然的攻击方法。因为将n分解成p和q之后,在知道公钥d的情况下,可以知道相应的欧拉函数值,进而得出私钥e。不过,在密钥长度很长的情况下,有限时间内是很难得出结果的。

蓝桥杯2018年省赛题目

这道题目是C++A组和JavaA组的题目,但由于使用C++和Java编写代码会十分复杂,这里面涉及到了高精度(大数)、快速乘、快速幂;而Python拥有天然的大数处理,因此这里使用Python语言编写代码,不过在某些方面,也导致了复杂计算很慢,下面会详细说明。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gglvXsMv-1634177570623)(C:\Users\26797\Desktop\RSA\2.png)]

第一步,分解n求得p和q
import time

n = 1001733993063167141
d = 212353
C = 20190324


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def find_pq():
    i = 3  # 显然n不会被2整除,故而,不可能被偶数整除
    while True:
        if n % i == 0:
            if gcd(i, n//i) == 1:  # 两个数互质,最大公约数为1
                break
        else:
            i += 2
    return i, n//i


start = time.perf_counter()
p, q = find_pq()
end = time.perf_counter()
print('runtime:%s s' % (end-start))
print(p)
print(q)

运行结果是:

运算时间:62.2969663 s
p=891234941
q=1123984201

运算时间长达一分钟,其实是Python语言的原因,而换成“轻巧的”C++,3秒钟内便搞定了。

换回C++

#include <iostream> 
using namespace std;
long long n = 1001733993063167141;
int gcd(long long a, long long b){
    return b==0?a:gcd(b, a%b);
}
void find_pq(){
	long long i = 3;
    while(1){
		if (n%i==0){
			if(gcd(i, n/i)){
				cout<<i<<" "<<n/i;
            	break;
            }	
			}else{
				i += 2;
			}	
		}
}

int main(){
	find_pq();
	return 0;
} 

运算结果:

运算时间:3.676 s
p=891234941
q=1123984201

第二步,求得e

因为 d*e mod fn == 1 则 e = (fn*k+1)/d(k>=1)

n = 1001733993063167141
d = 212353
C = 20190324
p = 891234941
q = 1123984201
fn = (p-1)*(q-1)

i = 1
while True:
    if (fn*i+1) % d == 0:
        e = (fn*i+1)//d
        break
    else:
        i += 1

print(e)

运算结果e = 823816093931522017

第三步,对拍测试

“对拍”就是自己生成一些测验数据来验证代码的准确性。

n = 1001733993063167141
d = 212353
C = 20190324
p = 891234941
q = 1123984201
fn = (p-1)*(q-1)
e = 823816093931522017

# pow(a, b, c) ==> a^b mod c
testM = 2019
testC = pow(testM, d, n)
print(f'{testM}加密成:{testC}')
print(f'{testC}解密成:%s'%pow(testC, e, n))

运行结果:

2019加密成:383690365320020222
383690365320020222解密成:2019

结果正确无误。

第四步,解题

答案是579706994112328949。

n = 1001733993063167141
d = 212353
C = 20190324
p = 891234941
q = 1123984201
fn = (p-1)*(q-1)
e = 823816093931522017


print(pow(C, e, n))

参考链接

[2019第十届蓝桥杯 省赛A组 RSA解密]https://blog.csdn.net/weixin_43107805/article/details/89515994

[RSA 非对称加密原理(小白也能看懂哦~)]https://blog.csdn.net/jijianshuai/article/details/80582187

[RSA 加密算法原理简述]https://blog.csdn.net/gulang03/article/details/81176133

[百度百科]RSA算法、非对称加密算法、对称加密算法

原文链接:https://blog.csdn.net/weixin_45802397/article/details/120758405







所属网站分类: 技术文章 > 博客

作者:骷髅无悔

链接:https://www.pythonheidong.com/blog/article/1060654/983e815886fbcb0f21b6/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

23 0
收藏该文
已收藏

评论内容:(最多支持255个字符)