Soreat_u's Blog

Writeup for Crypto Problems in CISCN 2019

 Writeup

puzzles

question0

四元一次方程组，直接利用numpy解方程得出a1, a2, a3, a4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import numpy as np
A = np.array([
        [13627, 26183, 35897, 48119],
        [23027, 38459, 40351, 19961],
        [36013, 45589, 17029, 27823],
        [43189, 12269, 21587, 33721]
    ])
b = np.array([347561292, 361760202, 397301762, 350830412])
x = np.linalg.solve(A, b)

for i in x:
    print(hex(int(i)))

# a1 = 0xfa6, a2 = 0xbed, a3 = 0x9c6, a4 = 0xa00

question1

给出了3个奇数，猜测为质数，查询质数表

26364809 : 1645834th
Part1    : ???????th
26366033 : 1645908th
26366621 : 1645945th

发现位置相差37个，因此找出第1645871th质数即为Part1 = 26365399 = 0x1924dd7

question2

解定积分，得:

(1+91+7+1) * 77 = 7700 = 0x1e14

因此Part2 = 0x1e14

question3

物理题，求感应电动势，直接带公式:

$$ \epsilon = -\frac{d\psi}{dt} = -2\pi rB\frac{dr}{dt} = -2\times \pi \times 2 \times 4 \times (-5) = 80\pi $$

求得Part3 = 80 * 233 = 0x48d0

question4

计算重积分

$$ \iiint(x^2+y^2){dxdydz} = \int_2^8 {dz} \int_0^{2\pi} {d\theta} \int_0^{\sqrt{2z}} {\rho^3 d\rho} = 2\int_2^8 {\pi}z^2 {dz} = 336\pi$$ Part4 = 336 * 120 = 40320 = 0x9d80

flag

根据格式得到flag：

flag{01924dd7-1e14-48d0-9d80-fa6bed9c7a00}

part_des

Problem

Round n part_encode-> 0x92d915250119e12b
Key map -> 0xe0be661032d5f0b676f82095e4d67623628fe6d376363183aed373a60167af537b46abc2af53d97485591f5bd94b944a3f49d94897ea1f699d1cdc291f2d9d4a5c705f2cad89e938dbacaca15e10d8aeaed90236f0be2e954a8cf0bea6112e84

Recon

DES加密，给出了所有的（16对）子密钥和第n轮的加密结果。

DES是一个对称的加密结构，既然都有了所有的子密钥了，解密不会是问题。

DES的加解密是对称的，解密就是用子密钥倒着加密。

不过这里第n轮中的n未知，可以穷举1~16。

  • 穷举n
  • 解密的时候子密钥要倒着
  • 由于是中间结果，所以没有最后一轮的左右两半轮换和FP，所以解密的时候要注意下

Exploit

 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

# python3
from des import * # https://github.com/soreatu/Cryptography
from Utility import *
from Crypto.Util.number import *

m = Bytes2Block(long_to_bytes(0x92d915250119e12b))
k = long_to_bytes(0xe0be661032d5f0b676f82095e4d67623628fe6d376363183aed373a60167af537b46abc2af53d97485591f5bd94b944a3f49d94897ea1f699d1cdc291f2d9d4a5c705f2cad89e938dbacaca15e10d8aeaed90236f0be2e954a8cf0bea6112e84)
subkey = [ Bytes2Block(k[i:i+6]) for i in range(0,len(k), 6)]
# 子密钥48 bits（6 bytes)一组

# m的右半部是Li-1和F()异或的结果，所以需要用m的右半部作为解密的Li（Feistel网络中Li用来异或）
Ri, Li = m[:32], m[32:]


for n in range(16):
    nn = n
    LLi,RRi=Li,Ri
    while nn > 0:
        LLi,RRi = RRi, BlockXor(LLi, Feistel(RRi,subkey[nn-1]))
        nn-=1
    mm = RRi+LLi
    mm = FP(mm)
    print(Block2Bytes(mm))
# b'\xbfB\x052t\x0b\x18X'
# b'/\xd4\x0f5\xe8B!\xb1'
# b'l\xa71?I}3{'
# b'l\xc7!\x97\x08@\x1c\xe9'
# b'&L\x1b\x9c\x85tT\xae'
# b'5\xa3!P\n\xf4\xcb\xe2'
# b'Bh\xa4~$)\x1e\xa3'
# b'\xd7\xcd\x0e9\xd2\x185S'
# b'\xf2\x1b ;\xf0\xdc\xa4\xdf'
# b'\x93\xc0\xa4Zz\xa2\xbb\x13'
# b'\xc2o\xe3\xaah\x0e\xe1f'
# b')\xc1`r\xfb\xd5\xfb\x9d'
# b'\xb5p^\xdb\xe9=\xb9\x88'
# b'y0ur9Ood'
# b't-\xcfE\xcfx\x90\xa7'
# b'\x8a\x1eD\x9a0\x94\x18/'

可以看到y0ur9Ood,即为flag

Reference

[1] https://ctf-wiki.github.io/ctf-wiki/crypto/blockcipher/des/#2019-ciscn-part_des

warmup

Recon

AES的CTR模式加密。

上网了解了一下什么是AES的CTR。

分析给的脚本的加密过程，发现里面的count是不会变的，加密内容是plaintext+flag，其中Plaintext是自己输入的。

可以通过异或运算的特性，以及count的不变性，得到利用方法：

nc后得到数据：

Exploit

1
2
3
4
5

c1 = '8132124c9092db06f6266d953c73bd36b7bff05387e9995670e088e6224ad04b4204347c7a95d9e436ff46cacd920072'
c2 = 'd66f421ada9ada01f4766e923a6fbe32e7ebec5683b99b4a78b28fb23e4dd3194350677c2fc6dab03eb371fdfaa53745'

for i in range(0, len(c), 2):
    print(chr(int(c[i:i+2], 16) ^ int(m[i:i+2], 16) ^ ord('1')), end="")

flag{9063a267-25ae-45a3-9c6e-62c0eb1db2e9}

Asymmetric

类似于一个RSA的非对称加密。

n是一个大质数的r次方(r∈[2,10])，可以对n求次方根来求得质数p。

利用二分法来求根，经验证第二个p为质数。

现在已知e, n, c, 且 m^e mod n = c, 感觉可以像RSA那样decrypt。即 c^d mod n = m。

关键是要找到d，而 又有ed mod φ(n)=1, 因此只要找到**φ(n)**即可。

根据φ(n)的定义以及n=p^4，可以得到φ(n)=p^4-1-(p^4/p-1)=p^4-p^3。

接下来就是解密了：

 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

import gmpy2
import base64
from Crypto.Util.number import *

# find the xth root of n
def find_xroot(n,x):
    l, r = 1, n
    while l <= r:
        mid = (l + r) / 2
        midx = mid ** x
        if midx > n:
            r = mid - 1
        elif midx < n:
            l = mid + 1
        else:
            #print "find! " + str(mid)
            return mid

e = 58134567416061346246424950552806959952164141873988197038339318172373514096258823300468791726051378264715940131129676561677588167620420173326653609778206847514019727947838555201787320799426605222230914672691109516799571428125187628867529996213312357571123877040878478311539048041218856094075106182505973331343540958942283689866478426396304208219428741602335233702611371265705949787097256178588070830596507292566654989658768800621743910199053418976671932555647943277486556407963532026611905155927444039372549162858720397597240249353233285982136361681173207583516599418613398071006829129512801831381836656333723750840780538831405624097443916290334296178873601780814920445215584052641885068719189673672829046322594471259980936592601952663772403134088200800288081609498310963150240614179242069838645027877593821748402909503021034768609296854733774416318828225610461884703369969948788082261611019699410587591866516317251057371710851269512597271573573054094547368524415495010346641070440768673619729280827372954003276250541274122907588219152496998450489865181536173702554116251973661212376735405818115479880334020160352217975358655472929210184877839964775337545502851880977049299029101466287659419446724781305689536816523774995178046989696610897508786776845460908137698543091418571263630383061605011820139755322231913029643701770497299157169690586232187419462594477116374977216427311975598620616618808494138669546120288334682865354702356192972496556372279363023366842805886601834278434406709218165445335977049796015123909789363819484954615665668979
n = 754600786340927688096652328072061561501667781193760284816393637647032362908189628005150802929636396969230958922073774180726205402897453096041624408154494621307262657492560975357997726055874834308239749992507552325614973631556754707427580134609221878324704469965450463088892083264951442562525825243127575048386573246756312509362222667015490013299327398464802116909245529065994770788125182846841016932803939806558559335886481214931253578226314057242462834149031625361286317307273138514126289052003214703248070256059405676891634792175775697355408418965738663732479622148276007308404691800186837579126431484536836513358124181380166971922188839934522356902295160649189850427580493328509329115798694580347461641487270793993129066433242544366683131231903590153844590595882428219010673818765995719694470668924781499987923250883546686344997580959954960334567874040563037167422839228466141912000421309282727363913908613116739074234989825489075148091144771967111113068647060175231126374070143480727000247378471525286907200601035581143391602569836131345909055708005758380081303860198696570649330092070410465978479841469533490522594827330661914537170063053059393550673731195548189192109328158876774080143171304333338291909598353550442855717204721
enc = 'YXmuOsaD1W4poLAG2wPrJ/nYZCkeOh2igCYKnZA6ecCeJadT6B3ZVTciPN6LJ8AcAsRXNnkC6+9PNJPhmosSG5UGGbpIcg2JaZ1iA8Sm3fGiFacGvQsJOqqIWb01rjaQ3rDBKB331rrNo9QNOfMnjKr0ejGG+dNObTtvnskICbYbNnSxMxLQF57H5JnWZ3LbbKQ493vmZzwvC6iH8blNPAp3dBlVzDqIAmxmUbk0OzFjPoHphD1oxHdzXyQNW+sLxVldrf9xcItq92jN5sqBYrG8wADIqY1/sqhTMZvkIYFMHqoMQuiRSnVrCF2h2RtGDEayLo0evgXI/0W3YveyKCHViOnG6wypcBFm91ZWdjp3fVW/4DyxW6xu9hg/NlXyRP6pT/OyQpcyTqKRuiXJLWgFUJI/8TRgyAjBLLgSd3U0N3VM8kewXw5j+fMUTCW9/Gy4iP8m52Zabx/vEKdwdGZ0QyvgvAWGUFZ96EK0g1BM/LU9Tuu2R+VKcCSCprg283x6NfYxmU26KlQE6ZrrjLmbCOe0327uaW9aDbLxZytPYIE5ZkzhSsD9JpQBKL30dCy3UKDbcuNgB6SrDddrbIuUd0/kLxuwh6kTqNbC4NDrOT4WAuP4se8GGOK8Wz0dL6rE6FkzMnI4Qg501MTSNQZ4Bp7cNf6H9lTa/4DNOl0='

def decrypt():
    c = bytes_to_long(base64.b64decode(enc))

    p = find_xroot(n, 2)
    p = find_xroot(p, 2)

    d = gmpy2.invert(e, p ** 4 - p ** 3)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print flag

if __name__ == "__main__":
    decrypt()

得到flag:flag{ec33f669d2d659e2bc27dbffdfeb0f38}