密码学专场Writeup | 公开赛

Posted by Pwnhub on 2018-01-07

2017 年 12 月, Pwnhub 用一场密码学专场送走了最后一个工作周,迎来了 2018 年。

这次密码学专场以公开赛 + 内部赛的形式进行,共发布了 8 道题。十分感谢这次比赛的出题人 @Dr Zhiniang Peng 和 @Kap0k ,帮助我们发现和认识了很多热爱 Crypto 的胖友。(当然也要感谢一下所有参与了此次专场——不管是公开赛还是内部赛的胖友,公开赛邀请码发放数量有限,也对那些认真做题但因为提交顺序没能获得邀请码的胖友表示下遗憾,摸摸脑嗲,再接再厉呀!

接下来,是迟到的公开赛 Writeup ,希望你还需要它。

小小说明一下:Writeup 大部分来自参加公开赛的胖友们提供


asymmetric1

RSA 的低加密指数攻击:

e=3 时,如果明文过小,导致明文的三次方仍然小于 n ,那么通过直接对密文
三次开方,即可得到明文。

脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2
from Crypto.Util.number import long_to_bytes
e = 3
N =
179769313486231590772930519078902473361797697894230657273430081157732675805500963
132708477322407536021120113879871393357658789768814416622492847430639477074095512
480796227391561801824887394139579933613278628104952355769470429079061808809522886
423955917442317693387325171135071792698344550223571732405562649211
c =
826315331619023570333927368402415746375121931530175503997253550521249603484788863
000488498971763172906490538445007322279725379352003051009132296583666591835676940
471026344712455146169609370787877307086577742407351355619892014203721206411825379
081930406716230574277137708287779956941012581L
for i in range(0, 10000):
if gmpy2.iroot(c + i * N, 3)[1]:
print long_to_bytes(gmpy2.iroot(c + i * N, 3)[0])

分享一个参考:公钥指数攻击

polynomial1

主要考察信息安全数学基础。

P.<x>=PolynomialRing(K) 定义了一个多项式环,同时f=x^47 + 12*x + 129是域 GF(131) 上的一个首 1 不可约多项式。

那么R=P.quotient_ring(f)实际上构成了一个阶为p^n的有限域。所以有限域上进行指数求逆操作则变得非常简单了。

求解方法:

1
print c^(e.inverse_mod(p^n-1))

symmetric1

这道题对 AES 加密进行了简单的修改:将 sbox 部分内容进行了适当替换。

用 IDA 反编译 symmetric1,分析程序,一个 AES 加密程序。

密钥扩展前,密钥是 256 位

key[]
1
2
3
4
5
6
7
8
0x00, 0x01, 0x02, 0x03,
0x04, 0x05, 0x06, 0x07,
0x08, 0x09, 0x0a, 0x0b,
0x0c, 0x0d, 0x0e, 0x0f,
0x10, 0x11, 0x12, 0x13,
0x14, 0x15, 0x16, 0x17,
0x18, 0x19, 0x1a, 0x1b,
0x1c, 0x1d, 0x1e, 0x1f};

有一点需要注意,出题者把 S-BOX 第 5 行第 2、3 列的 0x000xed 交换了一下,那么编写解密程序时,需要相对应将 INV-S-BOX 第 0 行第 0 列改成 0x53,第 e 行第 d 列改成 0x52

symmetric3

本题是对 pyDES 做了简单修改,将原来 16 轮 DES 加密变成只有三轮得加密。而且取消了 IP 操作。

本题是对pyDES做了简单修改,将原来16轮DES加密变成只有三轮得加密。而且取消了IP操作。

对字符串

1
38594095175492500138573067507036180364429044573083730664950710851782573016344573567095595234573006323144506605703577573086530918449678044242573007452717351776889978573009628767117493992633573093371651959531258971573075833010077541406980573038191956466640455404573019704587767962973550573006635923963870065548573009748758262639985294573029844598739555555640573038537247222018493410573026196618713447925259573050285422750379444506573081752391536398113387573052731918547834842207573064694994011141811887573052683187086448952327573055350768718169601331573034029843619100215480573009533758469312257545573035920541401174432606573095551388688236109372573093528569264055663960573079597280604434835741573097291087926879721475573067690469656295433595573002859344592155292167573051445674628495732885573036734289564949092636573079414536595495014008573084277700802259719892573002028731189260574729573025674200815148769416573089080909298653947771573069455843797204133299573031809841388746637193573027227351620660103930573071415946226871312203573000582435687349719708573047587870678443224283573082338800643893136802573055651226603937514806573052008260191716578355573055716372799203689894573026552174517329521306573000737958112921903168573010677011278952949385573057208276135209008037573085993073085446551356573019619137179861620524573032992025380456654198573096249115905161507448573000350275197961111283573040173979889250629741573009328418724533766838573017294437581294432655573039153521832507292046573069245795221972053053573020187538633634176140573032210112626896350489573055543227548719795584573060219721058982442695573075235071109330949595573044838228187179323957573039971400749101100850573010133432500535773037573070039178554012168027573065414841113261314361573085111558499600722520573037868241352369378582573089099991314287805586573069794957210800789395573084324486588519817753573038749723448510304909573032523765200239554371573050508535571584860014573062424999836580916226573038765472145644291515573017546975528144419274573013760248636671980782573076336396219625442421573091048466287388656563573076124956426677969568573049790449562829903187573061960306033714917808573016655528404458526866573025536827785780470103573035119988068859737602573086272946604164354767573004856107766954382692573094198443152372703297573071864053326874927149573007743859123032002079573025983304133187040090573054257473939352752920573085417913

进行了加密。

这个字符串有一个特殊的模式,就是 “5730” 这 32bit 会多次重复出现。而且位置都是在某个 block 的右半部分。又由于加密是使用 ECB 模式进行的,所以我们可以使用差分攻击恢复出 48bit 的轮密钥。然后通过暴力搜索,获得剩余 8bit ;然后再通过语义补充,得到 Flag 。

warmup1

这道题还是很简单的,下载后得到⼀个⽂件,发现只有两种字符\x20和\x09,且⼀共256个,考虑替换成 0 和 1 ,之后 ascii 编码即可。

得到以下字符串:

1
2
3
4
5
01110000011101110110111001101000011101010110001001111011011101
11011010000110100101110100011001010111001101110000011000010110
00110110010101011111011100110111010001100101011001110110000101
10111001101111011001110111001001100001011100000110100001111001
01111101

EXP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
a =
'2009090920202020200909092009090920090920090909202009
09200920202020090909200920092009092020200920200909090
92009092009090920090909200909200920202020090920092020
09200909092009202020090920200920092009090920200909200
90909202020202009092020202009200909202020090920090920
20092009200920090909090920090909202009092009090920092
02020090920200920092009092020090909200909202020200920
09092009090920200909200909090920090920200909092009090
92020092020090920202020092009090920202020200909200920
202020090909092020092009090909092009'.decode('hex')
ans = ''
for i in range(0, len(a), 8):
tmp = ''
for j in range(8):
if a[i + j] == '\x20':
tmp += '0'
else:
tmp += '1'
ans += chr(int(tmp, 2))
print ans

warmup2

下载文件,发现是 tar 压缩格式,改后缀解压,得到 public 公钥文件和一个加密文件及一个带密码的 zip 文件。意图明显,RSA 解密得到明文即为 zip 密码。

通过公钥文件得到 n 和 e ,用 yafu 分解得出 p 和 q ,计算出私钥 d ,直接 RSA 解密。部分脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#-*- coding:utf-8 -*-
from Crypto.PublicKey import RSA
import rsa
import gmpy2
pub = RSA.importKey(file('public').read())
n = long(pub.n)
e = long(pub.e)
print n,'\n\r',e
p = 217897987986019837777777868612086707309703990370937064689758730000398748973
0577766666432970948093825098048508432098597439679745967093248509832235872389578
927389754893268956892365896238965823658926374638789572398578932755325250423
q = 217897987986019837777777868612086707309703990370937064689758730000398748973
0577766666432970948093825098048508432098597439679745967093248509832235872389578
927389754893268956892365896238965823658926374638789572398578932755325236147
d = long(gmpy2.invert(e,(p-1)*(q-1)))
key = RSA.construct((n,e,d))
keypem = key.exportKey()
privkey = rsa.PrivateKey.load_pkcs1(keypem )
crypto = file('encrypt','rb').read()
message = rsa.decrypt(crypto,privkey)
print message

解密后得到密码:ABKIDFubodiw724_00922gg

解压zip得到一个文件,还是 tar 压缩包,改后缀直接解压,得到一个 word 和一个说明文件,提示 word 密码是5位以下的纯数字,直接上工具跑。得到密码:00579 ,最后得到 Flag 。


最后,欢迎大家积极来投稿~不管是简单的题目,还是难的题目,我们都接收喔!