逆向工程實驗——pre2(RSA密碼演演算法破解)

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

實驗結果截圖：

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