0x01 dp

下载附件得到rsa.txt

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

已知(n,e,dp,c)，可以导致密文被解密的危害。其中dp的意思为：dp≡d mod (p−1)
根据公式m≡c^d mod n想要破解密文，得求出私钥d
根据公式d∗e≡1 mod ϕ(n)，想要求d，得求出ϕ(n),也就是求出p和q

公式推导

已知公式：

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

我们假设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，求的方法也很简单，遍历65537种可能，其中肯定有一个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为整数
        if n%(((dp*e-1)/x)+1)==0: #q为整数
            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))

运行脚本得到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:国密算法，一种对称密钥算法，分组加密， 分组长度为128bit(32字节)， 密钥长度为128bit(32字节)所以需要分段解，注意补位

方法一：手动解密

将key和c转化为16进制

key:0dcc63b1fe29c6a3c9e238d6c0c26268
c:2e30dc9cb8da390df65b013f3c43694095f0d94d6b31de3d9be1e7c4a77909103cb6416527fdfae009cc9a7ace2b613b

使用sm4解密小工具，得到解密后结果

image.png

将解密得到的数据转化为字符串，得到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转换为16进制
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转换为16进制
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字节
key =  0x0dcc63b1fe29c6a3c9e238d6c0c26268
c1 =   0x2e30dc9cb8da390df65b013f3c436940
c2 =   0x95f0d94d6b31de3d9be1e7c4a7790910
c3 =   0x3cb6416527fdfae009cc9a7ace2b613b

clear_num1 = decrypt(c1, key)
clear_num2 = decrypt(c2, key)
clear_num3 = decrypt(c3, key)
# 将10进制明文转化为16进制，再转化为字符串
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')

运行脚本得到flag

image.png

参考：
pysm4