逆向工程实验——pre2(RSA密码算法破解)_bugku加密{920139713,19}

4、cipher text

{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

RSA算法描述：

（1）选择一对不同的、足够大的素数p，q。
（2）计算n=pq。
（3）计算f(n)=(p-1)(q-1)，同时对p, q严加保密，不让任何人知道。
（4）找一个与f(n)互质的数e，且1<e<f(n)。
（5）计算d，使得de≡1 mod f(n)。这个公式也可以表达为(d*e-1)% f(n)=0
这里要解释一下，≡是数论中表示同余的符号。公式中，≡符号的左边必须和符号右边同余，也就是两边模运算结果相同。
显而易见，不管f(n)取什么值，符号 右边1 mod f(n)的结果都等于1；符号的左边d与e的乘积做模运算后的结果也必须等于1。
这就需要计算出d的值，让这个同余等式能够成立。
（6）公钥KU=(e,n)，私钥KR=(d,p,q)。
（7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，
则加密过程为：C≡M^e(mod n)。
（8）解密过程为：M≡C^d(mod n)。

上面的题目给出的信息是公钥={n = 920139713,e = 19}，其他的是密文。
所以我们要做的第一步就是分解大整数920139713求出p,q。
然后第二步求出密钥d。
最后第三步解出明文。

源代码：

#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()
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

实验结果截图：

RSA算法解密的明文字符串：flag{13212je2ue28fy71w8u87y31r78eu1e2}