前言

RSA是一种非对称加密算法。它是由Ronald L. Rivest、Adi Shamir和Leonard Adleman在1977年开发的。RSA算法的核心思想是基于数论中的大质数分解问题和欧拉函数。其加密过程包含公钥和私钥两个密钥，用公钥可以加密信息，只有用私钥才能解密。RSA算法被广泛应用于数字签名、加密通信、安全登陆等领域。

RSA加解密算法是一种公钥加密算法。它的加密和解密过程都需要用到两个密钥：公钥和私钥。公钥可以公开，但私钥必须保密。

下面详细介绍RSA加解密算法的过程：

  1. 密钥生成：

a. 随机选择两个大质数p和q，计算n=p*q

b. 计算欧拉函数φ=(p-1)(q-1)

c. 随机选择一个整数e，1<e<φ，且e与φ互质

d. 计算d，使d满足 (d*e) mod φ = 1

e. 公钥为(n,e)，私钥为(n,d)

  1. 加密过程：

a. 将明文m转换为大数M，使 0<M<n

b. 计算密文 C = M^e mod n

c. 将密文C发送给接收方

  1. 解密过程：

a. 接收方使用私钥 (n,d) 将密文C解密为明文M

b. 计算明文 M = C^d mod n

c. 将明文M还原为原始消息m

RSA算法的安全性基于大质数的质因数分解问题，因此当n的长度很大时，其安全性非常高。在实际应用中，选择的p和q必须足够大（一般都是几百位或上千位），以避免被破解。

总之，RSA加解密算法是一种非常强大的公钥加密算法，可以保证信息的安全性和可靠性，因此被广泛应用于各个领域。

应用场景：

  1. 网络安全：RSA算法可以用来加密数字证书、HTTPS、SSH等网络安全协议，确保数据在传输过程中的安全性。

  2. 电子商务：RSA算法可以用于加密支付信息，保护用户的支付信息不受黑客攻击。

  3. 数字签名：RSA算法可以用于数字签名，保证数字信息的完整性和可信性。

  4. 移动通信：RSA算法可以用于加密移动设备之间的通信，保证信息的机密性和安全性。

RSA算法具有广泛的应用场景，可以保证信息的安全性和可靠性，因此被广泛应用于各个领域。

一、rsa

1.打开题目

在这里插入图片描述

2.解题

下载附加得到字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

给出的信息是公钥={n = 920139713,e = 19}，其他的是密文。

三步走：

  1. 分解大整数920139713求出p,q
  2. 然后第二步求出密钥d
  3. 最后第三步解出明文

相关脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#py -3
#coding=utf-8

import math
# 1、分解小整数的质因子，求出p,q
def dissassemble(n):
    temp = 2
    while temp < math.sqrt(n):
        #找到一个素因子为止,因为RSA算法中n是由两个素数的乘积得来的
        if (n % temp == 0):
            #python中的除法默认为浮点型数，会保留一位小数，如果不加int()的话结果会有一位.0小数
            print("大整数分解的两个素数p,q为：",temp, int(n / temp))
            break
        else:
            #采用的是递加1的方式，如果整数比较大则需要采用大步小步算法或生日悖论概率算法来分解
            temp += 1
    euler = getEuler(temp, int(n / temp))
    print('f(n)欧拉函数值p*q为：',euler)
    return euler

# 2、求欧拉函数f(n)
def getEuler(prime1, prime2):
    return (prime1 - 1) * (prime2 - 1)

# 3、求私钥d  19d - 920071380k= 1
def getDkey(e, eulervalue):  # 也可以用辗转相除法求逆元
    k = 1
    #因为是在mod 欧拉函数值（Eulervalue)的域下，19d = 1,所以只能从1开始一个一个试k
    while True:
        #直到有一个k使得等式成立，即算出私钥d
        if (((eulervalue * k) + 1) % e) == 0:
            #直接用int转换也可以获得一样精度的d
            #x = (eulervalue * k + 1) / e
            #print("失去精度的d",int(x))
            #直接使用库函数计算除法
            (d, m) = divmod(eulervalue * k + 1, e)
            # 避免科学计数法最后转int失去精度
            return d
        k += 1

if __name__ == '__main__':
    #大整数n
    n = 920139713
    print("大整数为：",n)
    #求出欧拉函数值
    euler = dissassemble(n)
    #求私钥
    d = getDkey(19, euler)
    print('私钥为： %d' % d)
    c = [704796792, 752211152, 274704164, 18414022, 368270835, 483295235, 263072905, 459788476, 483295235, 459788476,663551792,475206804, 459788476, 428313374, 475206804, 459788476, 425392137, 704796792, 458265677, 341524652, 483295235, 534149509,425392137, 428313374,425392137, 341524652, 458265677, 263072905, 483295235, 828509797, 341524652, 425392137, 475206804,428313374,483295235, 475206804, 459788476, 306220148]
    L = []
    #求明文对应的ascii码
    for x in c:
        L.append(pow(x, d, n))
    print("明文对应的ascii码:",L)
    # 明文ascii表对应的明文字符
    print("明文ascii表对应的明文字符串：",end='')
    for x in L:
        print(chr(x), end='')
    print()

得到flag：flag{13212je2ue28fy71w8u87y31r78eu1e2}