0x01 dp

下載附件得到rsa.txt

e=65537
n=9637571466652899741848142654451413405801976834328667418509217149503238513830870985353918314633160277580591819016181785300521866901536670666234046521697590230079161867282389124998093526637796571100147052430445089605759722456767679930869250538932528092292071024877213105462554819256136145385237821098127348787416199401770954567019811050508888349297579329222552491826770225583983899834347983888473219771888063393354348613119521862989609112706536794212028369088219375364362615622092005578099889045473175051574207130932430162265994221914833343534531743589037146933738549770365029230545884239551015472122598634133661853901
dp=81339405704902517676022188908547543689627829453799865550091494842725439570571310071337729038516525539158092247771184675844795891671744082925462138427070614848951224652874430072917346702280925974595608822751382808802457160317381440319175601623719969138918927272712366710634393379149593082774688540571485214097
c=5971372776574706905158546698157178098706187597204981662036310534369575915776950962893790809274833462545672702278129839887482283641996814437707885716134279091994238891294614019371247451378504745748882207694219990495603397913371579808848136183106703158532870472345648247817132700604598385677497138485776569096958910782582696229046024695529762572289705021673895852985396416704278321332667281973074372362761992335826576550161390158761314769544548809326036026461123102509831887999493584436939086255411387879202594399181211724444617225689922628790388129032022982596393215038044861544602046137258904612792518629229736324827

已知(n,e,dp,c)，可以導(dǎo)致密文被解密的危害寂殉。其中dp的意思為：dp≡d mod (p?1)
根據(jù)公式m≡c^d mod n想要破解密文，得求出私鑰d
根據(jù)公式d?e≡1 mod ?(n)，想要求d剑梳，得求出?(n),也就是求出p和q

公式推導(dǎo)

已知公式：

c≡m^e mod n
m≡c^d mod n
?(n)=(p?1)?(q?1)
d?e≡1 mod ?(n)
dp≡d mod (p?1)

將dp≡d mod (p?1)乘以e可以得到

dp?e≡d?e mod (p?1)

因此可以得到

d*e-dp*e=k1*(p-1)----->d?e=k1?(p?1)+dp?e----->k1?(p?1)+dp?e≡1 mod ?(n)

我們將?(n)=(p?1)?(q?1)帶入可以得到

k1?(p?1)+dp?e≡1 mod (p?1)?(q?1)

故此可以得到

k1?(p?1)+dp?e-1=k2*(p?1)?(q?1)----->k2?(p?1)?(q?1)+1=k1?(p?1)+dp?e

變換一下

(p?1)?[k2?(q?1)?k1]+1=dp?e

由dp≡d mod (p?1)推出dp<p?1于是可以得到

e>k2?(q?1)?k1

我們假設(shè)x=k2?(q?1)?k1可以得到x的范圍為(0,e)
將x代入(p?1)?[k2?(q?1)?k1]+1=dp?e得到

x?(p?1)+1=dp?e

那么我們可以遍歷x∈(0,e)
求出p-1，求的方法也很簡(jiǎn)單，遍歷65537種可能班巩，其中肯定有一個(gè)p可以被n整除,那么就可以求出p和q,即求出?(n)

p=(dp*e-1)/x+1
q=n/p
?(n)=(p-1)*(q-1)

從而推出d

d≡e^?1 mod ?(n)

解密腳本

# -*- coding: utf-8 -*-
# python 2
import gmpy2
import libnum
e = 65537
n=9637571466652899741848142654451413405801976834328667418509217149503238513830870985353918314633160277580591819016181785300521866901536670666234046521697590230079161867282389124998093526637796571100147052430445089605759722456767679930869250538932528092292071024877213105462554819256136145385237821098127348787416199401770954567019811050508888349297579329222552491826770225583983899834347983888473219771888063393354348613119521862989609112706536794212028369088219375364362615622092005578099889045473175051574207130932430162265994221914833343534531743589037146933738549770365029230545884239551015472122598634133661853901
dp=81339405704902517676022188908547543689627829453799865550091494842725439570571310071337729038516525539158092247771184675844795891671744082925462138427070614848951224652874430072917346702280925974595608822751382808802457160317381440319175601623719969138918927272712366710634393379149593082774688540571485214097
c=5971372776574706905158546698157178098706187597204981662036310534369575915776950962893790809274833462545672702278129839887482283641996814437707885716134279091994238891294614019371247451378504745748882207694219990495603397913371579808848136183106703158532870472345648247817132700604598385677497138485776569096958910782582696229046024695529762572289705021673895852985396416704278321332667281973074372362761992335826576550161390158761314769544548809326036026461123102509831887999493584436939086255411387879202594399181211724444617225689922628790388129032022982596393215038044861544602046137258904612792518629229736324827


            
for x in range(1,65538):
    if (dp*e-1)%x == 0: #p-1為整數(shù)
        if n%(((dp*e-1)/x)+1)==0: #q為整數(shù)
            p=((dp*e-1)/x)+1
            q=n/p
            phin = (p-1)*(q-1)
            d = gmpy2.invert(e,phin)
            print libnum.n2s(pow(c,d,n))

運(yùn)行腳本得到flag

image.png

0x02 sm4

下載附件得到sm4.txt

key: [13, 204, 99, 177, 254, 41, 198, 163, 201, 226, 56, 214, 192, 194, 98, 104]
c: [46, 48, 220, 156, 184, 218, 57, 13, 246, 91, 1, 63, 60, 67, 105, 64, 149, 240, 217, 77, 107, 49, 222, 61, 155, 225, 231, 196, 167, 121, 9, 16, 60, 182, 65, 101, 39, 253, 250, 224, 9, 204, 154, 122, 206, 43, 97, 59]

SM4:國(guó)密算法渣慕，一種對(duì)稱(chēng)密鑰算法，分組加密抱慌， 分組長(zhǎng)度為128bit(32字節(jié))逊桦， 密鑰長(zhǎng)度為128bit(32字節(jié))所以需要分段解，注意補(bǔ)位

方法一：手動(dòng)解密

將key和c轉(zhuǎn)化為16進(jìn)制

key:0dcc63b1fe29c6a3c9e238d6c0c26268
c:2e30dc9cb8da390df65b013f3c43694095f0d94d6b31de3d9be1e7c4a77909103cb6416527fdfae009cc9a7ace2b613b

使用sm4解密小工具抑进，得到解密后結(jié)果

image.png

將解密得到的數(shù)據(jù)轉(zhuǎn)化為字符串强经，得到flag

image.png

方法二：腳本解密

# -*- coding: utf-8 -*-
# python 2
from pysm4 import encrypt, decrypt
key = [13, 204, 99, 177, 254, 41, 198, 163, 201, 226, 56, 214, 192, 194, 98, 104]
c = [46, 48, 220, 156, 184, 218, 57, 13, 246, 91, 1, 63, 60, 67, 105, 64, 149, 240, 217, 77, 107, 49, 222, 61, 155, 225, 231, 196, 167, 121, 9, 16, 60, 182, 65, 101, 39, 253, 250, 224, 9, 204, 154, 122, 206, 43, 97, 59]

#將key轉(zhuǎn)換為16進(jìn)制
key16 =''
for i in range(len(key)):
    if len(str(hex(key[i])))<4:
        ket16 = key16 + '0'+str(hex(key[i])[2:])
    else:
        key16 =key16  + str(hex(key[i])[2:])
print 'hex(key):'+key16

#將c轉(zhuǎn)換為16進(jìn)制
c16 =''
for i in range(len(c)):
    if len(str(hex(c[i])))<4:
        c16 = c16 + '0'+str(hex(c[i])[2:])
    else:
        c16 =c16  + str(hex(c[i])[2:])
print 'hex(c):'+c16
# 解密 將上述的c分組成32字節(jié)
key =  0x0dcc63b1fe29c6a3c9e238d6c0c26268
c1 =   0x2e30dc9cb8da390df65b013f3c436940
c2 =   0x95f0d94d6b31de3d9be1e7c4a7790910
c3 =   0x3cb6416527fdfae009cc9a7ace2b613b

clear_num1 = decrypt(c1, key)
clear_num2 = decrypt(c2, key)
clear_num3 = decrypt(c3, key)
# 將10進(jìn)制明文轉(zhuǎn)化為16進(jìn)制，再轉(zhuǎn)化為字符串
print str(hex(clear_num1))[2:-1].decode('hex')+str(hex(clear_num2))[2:-1].decode('hex')+str(hex(clear_num3))[2:-1].decode('hex')

運(yùn)行腳本得到flag

image.png

參考：
pysm4