RSA算法与加密解密

• • 什么是RSA算法（RSA algorithm）
  • 什么是非对称加密算法
  • • RSA加密解密原理
    • 算法攻击和蓝桥杯2018年省赛题目
    • • • RSA的小指数攻击
        • 蓝桥杯2018年省赛题目
        • 第一步，分解n求得p和q
        • 第二步，求得e
        • 第三步，对拍测试
        • 第四步，解题
    • 参考链接

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

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

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

小数据示例：

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。

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

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

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

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  
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< 
运算结果：
 
运算时间: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算法、非对称加密算法、对称加密算法