CNSS招新题-2021-crypto-writeup

发表于2022-04-10更新于2022-04-10

CNSS招新题-crypto-writeup

Ccc

[😋] 大大超人的代码 I

先贴代码

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import long_to_bytes

a = 10499958999037877045860819145654592139531258013786800315952660437695953206118177802362538707257147839843929607571065996701775308516344320494492623326535070933404552245238889019529867495706219558537483959855018656456767601472852530792072968424254995263689863458109858200434368660199825370006622972172615283000225895986795432100524830372657448639751748649746517567275491877758341825114165092719349624453145256163927226959292249202574111889453838454722039
n = 24482146465492008075985247474612414320648047425785643838292024343856484727961531014143038475016832753633643464040872815615028679515938203288641456487330618969964445990607887042678786725649115551121279019558561466028015891949399125083811735238746137986294864917479675168130071009961552443914582290960081092498541343026165888900247802180370535720495152921978143267961988522304615862013752399728187062523671938698800778472385717512452760615330027345844283
b = 13974352443151
for i in range(n):
	if(a*i%n==b):
		break
flag = b'cnss{'+long_to_bytes(i)+'}'

求逆，利用扩展欧几里得算法求解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import long_to_bytes

def ext_gcd(a, b):  # 扩展欧几里得算法
    if b == 0:
        return 1, 0, a
    else:
        x, y, gcd = ext_gcd(b, a % b)  # 递归直至余数等于0(需多递归一层用来判断)
        x, y = y, (x - (a // b) * y)  # 辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立
        return x, y, gcd

a = 10499958999037877045860819145654592139531258013786800315952660437695953206118177802362538707257147839843929607571065996701775308516344320494492623326535070933404552245238889019529867495706219558537483959855018656456767601472852530792072968424254995263689863458109858200434368660199825370006622972172615283000225895986795432100524830372657448639751748649746517567275491877758341825114165092719349624453145256163927226959292249202574111889453838454722039
n = 24482146465492008075985247474612414320648047425785643838292024343856484727961531014143038475016832753633643464040872815615028679515938203288641456487330618969964445990607887042678786725649115551121279019558561466028015891949399125083811735238746137986294864917479675168130071009961552443914582290960081092498541343026165888900247802180370535720495152921978143267961988522304615862013752399728187062523671938698800778472385717512452760615330027345844283
b = 13974352443151

d = ext_gcd(a, n)[0]
i = b*d % n
print("cnss{" + long_to_bytes(i).decode() + "}")

得到flag

1
cnss{you yi ge ren qian lai mai gua. lue lue lue lue lue. sa ri lang, sa ri lang. ei, hua qiang, hua qiang}

[😋] 大大超人的代码 II

先贴代码

1
2
3
4
5
6
7
8
9
10
11
from hashlib import md5
from math import gcd

num = 42884020547169390364057708512857160494285905714049130207174574321294001570717794624065180823944268300615872241601579039570417514768021539120794827687319577302185669966605784385135475359835440522138098740956869698753641542827169807498060060203204623056652296548672193678604201527271552258183411014527366217548194668469156210293296924920396661175084847772705813725399053734267798263155285086152337660486536186646844672457165552673635686438518233777750910982014487846162409685706645584022613739678475494110418588076015804320630926293482802728176941310074063709832881421592093809601385355979927053037564815022569532301725889642648753691270079271760325794402609541247330395378653665694056501747438163292250560881807911461231726101015329450977148586716650828721964825603783645451441758913032780302842678209454303821607654073090650401139540242325808963472494771631432989047762098809264580664019379523293624441137658106554812934798531301113822034790852090529061101693937747989599304386879458074169786212163676139153571980665024887827190167719665028793495590181448050849517686984259984456749798664352548534304800162670309538117876068852938462001997080070145586746296815514664296506732662997084432462415745714170644890474456380187175650685331337577272850596655499330349676234958852437039128355237654047269
cnt = 0
for i in range(1,num):
	if gcd(i,num) == 1:
		cnt += 1

flag = md5(str(cnt).encode()).hexdigest()
print('Flag is cnss{' + flag '}')

求 $1$ 到 $num-1$ 中与 $num$ 互素的元素的和，也就是求 $num$ 的欧拉函数值，将 $num$ 质因数分解后利用公式求解即可

对 $num$ 进行质因数时 $factordb$ 不管用了，利用一下代码分解

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import math
import random
import time

start = time.perf_counter()


# 判断输入是否为素数
def prime(n):
    if n in {2, 3, 5, 7, 11}:
        return True
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False
    t = 0
    u = n - 1
    while u % 2 == 0:
        t += 1
        u //= 2
    a = random.randint(2, n - 1)
    r = pow(a, u, n)
    if r != 1:
        while t > 1 and r != n - 1:
            r = (r * r) % n
            t -= 1
        if r != n - 1:
            return False
    return True


# 寻找输入的一个因数
def find(n, a):
    def f(x):
        return (x * x + a) % n

    # 补上因子为2的判定
    if n % 2 == 0:
        return 2

    x1 = random.randint(0, n)
    x2 = x1
    while True:
        x1 = f(x1)
        x2 = f(f(x2))
        p = math.gcd(abs(x2 - x1), n)
        if p > 1:
            return p
        if x1 == x2:
            return n


def factor_n(num):
    prime_list = []

    while num != 1:
        if prime(num):
            prime_list.append(num)
            break
        else:
            c = find(num, random.randint(0, num - 1))
            if prime(c):
                prime_list.append(c)
                num //= c
    prime_list.sort()
    return prime_list


if __name__ == '__main__':
    num = 42884020547169390364057708512857160494285905714049130207174574321294001570717794624065180823944268300615872241601579039570417514768021539120794827687319577302185669966605784385135475359835440522138098740956869698753641542827169807498060060203204623056652296548672193678604201527271552258183411014527366217548194668469156210293296924920396661175084847772705813725399053734267798263155285086152337660486536186646844672457165552673635686438518233777750910982014487846162409685706645584022613739678475494110418588076015804320630926293482802728176941310074063709832881421592093809601385355979927053037564815022569532301725889642648753691270079271760325794402609541247330395378653665694056501747438163292250560881807911461231726101015329450977148586716650828721964825603783645451441758913032780302842678209454303821607654073090650401139540242325808963472494771631432989047762098809264580664019379523293624441137658106554812934798531301113822034790852090529061101693937747989599304386879458074169786212163676139153571980665024887827190167719665028793495590181448050849517686984259984456749798664352548534304800162670309538117876068852938462001997080070145586746296815514664296506732662997084432462415745714170644890474456380187175650685331337577272850596655499330349676234958852437039128355237654047269
    print(f'{num}=')
    prime_list = factor_n(num)
    print(prime_list)
    print('*'.join(map(str, prime_list)))

    end = time.process_time()
    print(f'Running time: {end - start} Seconds')

得到分解结果如下

1
[726469, 726469, 726469, 726469, 726469, 1248059, 1248059, 1248059, 1248059, 1248059, 1248059, 3488777, 3488777, 3488777, 3488777, 3488777, 3488777, 4003333, 4003333, 4003333, 4003333, 4003333, 4003333, 4003333, 7324349, 7324349, 7324349, 7324349, 7324349, 7324349, 7324349, 7324349, 7324349, 13943177, 13943177, 13943177, 13943177, 13943177, 13943177, 14429917, 14429917, 14429917, 14429917, 14429917, 14429917, 14429917, 14429917, 14429917, 14429917, 40264613, 40264613, 40264613, 40264613, 40264613, 40264613, 40264613, 40264613, 40264613, 40264613, 117077309, 117077309, 117077309, 117077309, 117077309, 416211353, 416211353, 416211353, 416211353, 416211353, 416211353, 416211353, 416211353, 416211353, 925020799, 925020799, 925020799, 925020799, 925020799, 925020799, 925020799, 925020799, 925020799, 1291513693, 1291513693, 1291513693, 1291513693, 1291513693, 1291513693, 1291513693, 1291513693, 1291513693, 1291513693, 4297172359, 4297172359, 4297172359, 4297172359, 4297172359, 4297172359, 4297172359, 6945055903, 6945055903, 6945055903, 6945055903, 6945055903, 6945055903, 6945055903, 6945055903, 14980192757, 14980192757, 14980192757, 14980192757, 14980192757, 14980192757, 31896490931, 31896490931, 31896490931, 31896490931, 31896490931, 31896490931, 31896490931, 31896490931, 34448261957, 34448261957, 34448261957, 34448261957, 34448261957, 34448261957, 34448261957, 34448261957, 34448261957, 42273263297, 42273263297, 42273263297, 42273263297, 42273263297, 334972370143, 334972370143, 334972370143, 334972370143, 334972370143, 334972370143, 409576292549, 409576292549, 409576292549, 409576292549, 409576292549, 409576292549, 409576292549, 409576292549]

接下来利用欧拉函数求解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from hashlib import md5

list = ['726469', '726469', '726469', '726469', '726469', '1248059', '1248059', '1248059', '1248059', '1248059', '1248059', '3488777', '3488777', '3488777', '3488777', '3488777', '3488777', '4003333', '4003333', '4003333', '4003333', '4003333', '4003333', '4003333', '7324349', '7324349', '7324349', '7324349', '7324349', '7324349', '7324349', '7324349', '7324349', '13943177', '13943177', '13943177', '13943177', '13943177', '13943177', '14429917', '14429917', '14429917', '14429917', '14429917', '14429917', '14429917', '14429917', '14429917', '14429917', '40264613', '40264613', '40264613', '40264613', '40264613', '40264613', '40264613', '40264613', '40264613', '40264613', '117077309', '117077309', '117077309', '117077309', '117077309', '416211353', '416211353', '416211353', '416211353', '416211353', '416211353', '416211353', '416211353', '416211353', '925020799', '925020799', '925020799', '925020799', '925020799', '925020799', '925020799', '925020799', '925020799', '1291513693', '1291513693', '1291513693', '1291513693', '1291513693', '1291513693', '1291513693', '1291513693', '1291513693', '1291513693', '4297172359', '4297172359', '4297172359', '4297172359', '4297172359', '4297172359', '4297172359', '6945055903', '6945055903', '6945055903', '6945055903', '6945055903', '6945055903', '6945055903', '6945055903', '14980192757', '14980192757', '14980192757', '14980192757', '14980192757', '14980192757', '31896490931', '31896490931', '31896490931', '31896490931', '31896490931', '31896490931', '31896490931', '31896490931', '34448261957', '34448261957', '34448261957', '34448261957', '34448261957', '34448261957', '34448261957', '34448261957', '34448261957', '42273263297', '42273263297', '42273263297', '42273263297', '42273263297', '334972370143', '334972370143', '334972370143', '334972370143', '334972370143', '334972370143', '409576292549', '409576292549', '409576292549', '409576292549', '409576292549', '409576292549', '409576292549', '409576292549']
s = 1
n = 42884020547169390364057708512857160494285905714049130207174574321294001570717794624065180823944268300615872241601579039570417514768021539120794827687319577302185669966605784385135475359835440522138098740956869698753641542827169807498060060203204623056652296548672193678604201527271552258183411014527366217548194668469156210293296924920396661175084847772705813725399053734267798263155285086152337660486536186646844672457165552673635686438518233777750910982014487846162409685706645584022613739678475494110418588076015804320630926293482802728176941310074063709832881421592093809601385355979927053037564815022569532301725889642648753691270079271760325794402609541247330395378653665694056501747438163292250560881807911461231726101015329450977148586716650828721964825603783645451441758913032780302842678209454303821607654073090650401139540242325808963472494771631432989047762098809264580664019379523293624441137658106554812934798531301113822034790852090529061101693937747989599304386879458074169786212163676139153571980665024887827190167719665028793495590181448050849517686984259984456749798664352548534304800162670309538117876068852938462001997080070145586746296815514664296506732662997084432462415745714170644890474456380187175650685331337577272850596655499330349676234958852437039128355237654047269
for i in list:
    s *= int(i)

nb = []
for i in list:
    if i not in nb:
        nb.append(i)
print(nb)

phi = 1
for i in nb:
    phi *= n - n//int(i)

phi = phi//(n**(len(nb)-1))
flag = "cnss{" + md5(str(phi).encode()).hexdigest() + "}"
print(phi)
print(flag)
print(s == n)

得到flag

1
cnss{7b4a23cf05fc166e2f5e6798d737cb83}

[😋] EZRSA

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import bytes_to_long,getPrime

flag = u'xxxxxx'
m = bytes_to_long(flag.encode())
p = getPrime(1024)
q = getPrime(1024)
e = 3
n = p*q
c = pow(m,e,n)
print(n)
print(c)

#17122915166265113628936084259612311876364779252333817653908064563012403283413723801149226058776045562431863561527598029708484050735340376592692944196636066937254842628374596659520832392883941088961925998112268354069528298108259950738233300271339429579172788606259082714089126140552788081701431773946954101521880287079138683872063436125499187482930254182605546821908768554127091588674102227605591868183216588952297634056187432224500652151699978753316630287127751214117068167697654397115835061787620207935678045116272234790320727737354518224845334305441037073149880267837099939565780539222758100209016162314144630920799
#16926458617386458077637050106018850896006879092288192701331681605474802210713231004923465605065133301881405183688853792875133217926741592214428875953305593414362683885848278980412814134018268287018200015497631362139676275057736654215717198437649465165438442373537289011460247398965575656801213891887710880496787600356785377725103473390014610976378061619695088235473509

注意到加密指数 $e=3$ ，直接尝试对 $c+kn$ 开立方，尝试发现 $ k=0 $ 时就可以得到flag

解密代码如下

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import long_to_bytes
import gmpy2

c = 16926458617386458077637050106018850896006879092288192701331681605474802210713231004923465605065133301881405183688853792875133217926741592214428875953305593414362683885848278980412814134018268287018200015497631362139676275057736654215717198437649465165438442373537289011460247398965575656801213891887710880496787600356785377725103473390014610976378061619695088235473509
n = 17122915166265113628936084259612311876364779252333817653908064563012403283413723801149226058776045562431863561527598029708484050735340376592692944196636066937254842628374596659520832392883941088961925998112268354069528298108259950738233300271339429579172788606259082714089126140552788081701431773946954101521880287079138683872063436125499187482930254182605546821908768554127091588674102227605591868183216588952297634056187432224500652151699978753316630287127751214117068167697654397115835061787620207935678045116272234790320727737354518224845334305441037073149880267837099939565780539222758100209016162314144630920799

status = gmpy2.iroot(c, 3)[1] #status为1表示改数能被开立方成整数
rootnumber = gmpy2.iroot(c, 3)[0] #开立方后的结果
print(rootnumber)
print(long_to_bytes(rootnumber).decode())

得到flag：

1
cnss{面对恐惧的最好办法就是消除恐惧}

[😋] True Random

代码如下

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
import random

flag = 'cnss{......}'

seeds = []
for i in range(0, len(flag)):
    seeds.append(random.randint(0, 10000))

res = [0]
for i in range(0, len(flag)):
    random.seed(seeds[i])
    rands = []
    for j in range(0, 4):
        rands.append(random.randint(0, 255))

    res.append(ord(flag[i]) ^ rands[i % 4] ^ res[i])
    del rands[i % 4]
    print(str(rands))

print(seeds)
print(res[1:])

#[6756, 949, 8167, 2246, 9307, 4748, 9651, 1460, 3867, 5744, 5815, 713, 1057, 5614, 4024, 8075, 3862, 732, 279, 5308, 7815, 2251, 5533, 6324, 6786, 8549, 4421, 6651, 7409, 4880, 6246, 1249, 192, 4099, 1704, 3678, 7520, 1378, 2642, 9154, 5690, 8621, 1717, 4992, 8903, 1608, 3214, 2565, 3146, 2521, 2070, 1047, 5784, 8682, 1057, 1091, 8655, 2957, 8591, 1284, 9162, 2974, 9395]
#[8, 221, 50, 176, 21, 79, 19, 208, 117, 8, 51, 171, 156, 247, 101, 60, 46, 152, 162, 182, 29, 16, 102, 154, 22, 117, 65, 21, 121, 197, 170, 2, 217, 118, 201, 15, 132, 246, 21, 1, 250, 7, 45, 130, 124, 231, 200, 103, 7, 63, 86, 159, 211, 168, 82, 11, 60, 173, 209, 168, 191, 255, 101]
#[245, 9, 243] [172, 160, 136] [23, 160, 158] [22, 128, 253] [43, 4, 130] [99, 42, 16] [171, 168, 108] [196, 148, 162] [229, 40, 88] [131, 92, 63] [194, 214, 44] [199, 145, 186] [210, 183, 113] [53, 244, 60] [177, 17, 151] [138, 188, 113] [129, 43, 241] [61, 127, 37] [210, 181, 250] [42, 226, 165] [104, 249, 247] [23, 153, 232] [156, 114, 5] [134, 65, 64] [225, 236, 36] [88, 14, 254] [232, 68, 58] [37, 197, 70] [126, 199, 207] [73, 0, 249] [91, 228, 182] [117, 81, 89] [153, 44, 238] [192, 12, 184] [116, 53, 67] [137, 25, 136] [83, 179, 128] [6, 225, 201] [89, 151, 47] [103, 173, 16] [160, 247, 223] [83, 63, 83] [88, 117, 59] [124, 121, 180] [160, 239, 98] [92, 189, 95] [157, 245, 5] [53, 164, 247] [223, 174, 68] [129, 4, 226] [199, 51, 42] [40, 132, 192] [217, 209, 235] [90, 192, 239] [82, 210, 113] [184, 18, 139] [232, 133, 100] [14, 90, 39] [180, 28, 252] [254, 247, 77] [21, 183, 150] [18, 222, 6] [27, 22, 247]

考察随机数种子与异或运算，利用 $seeds$ 和 $ res$ 生成完整的 $rands$ 后再异或运算即可得到flag。解密时记得把 $res$ 首位的 $0$ 加上

解密代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random

seeds = [6756, 949, 8167, 2246, 9307, 4748, 9651, 1460, 3867, 5744, 5815, 713, 1057, 5614, 4024, 8075, 3862, 732, 279, 5308, 7815, 2251, 5533, 6324, 6786, 8549, 4421, 6651, 7409, 4880, 6246, 1249, 192, 4099, 1704, 3678, 7520, 1378, 2642, 9154, 5690, 8621, 1717, 4992, 8903, 1608, 3214, 2565, 3146, 2521, 2070, 1047, 5784, 8682, 1057, 1091, 8655, 2957, 8591, 1284, 9162, 2974, 9395]
res = [0, 8, 221, 50, 176, 21, 79, 19, 208, 117, 8, 51, 171, 156, 247, 101, 60, 46, 152, 162, 182, 29, 16, 102, 154, 22, 117, 65, 21, 121, 197, 170, 2, 217, 118, 201, 15, 132, 246, 21, 1, 250, 7, 45, 130, 124, 231, 200, 103, 7, 63, 86, 159, 211, 168, 82, 11, 60, 173, 209, 168, 191, 255, 101]
length = 63
flag1 = []
for i in range(length):
    seed = seeds[i]
    random.seed(seed)
    rands = []
    for j in range(0, 4):
        rands.append(random.randint(0, 255))
    flag1.append(chr(res[i+1] ^ rands[i % 4] ^ res[i]))

flag = ''.join(i for i in flag1)
print(flag)

得到flag：

1
cnss{Trust me!This is turely random!!!!TURELY RANDOMMMMMM!!!!!}

[😋] 基地遭到攻击

先贴代码

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
msg = ''
dic = '0987654321qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM!@#$%^&*-=+:;(){}<>'


def dec_to_ter(num):
    l = []
    while True:
        num, reminder = divmod(num, 3)
        l.append(str(reminder))
        if num == 0:
            return "".join(l[::-1]).zfill(5)


def ter_to_dec(st):
    num = 0
    for i in range(len(st)):
        num += 3**(len(st) - i - 1) * int(st[i])
    return num


cy = ''

for i in range(len(msg) // 3):
    st = '0' + dec_to_ter(ord(msg[3 * i])) + dec_to_ter(ord(
        msg[3 * i + 1])) + dec_to_ter(ord(msg[3 * i + 2]))
    cy += dic[ter_to_dec(st[:4])] + dic[ter_to_dec(st[4:8])] + dic[ter_to_dec(
        st[8:12])] + dic[ter_to_dec(st[12:16])]
res = '0' + ''.join([dec_to_ter(ord(msg[i])) for i in st[len(msg) // 3 * 3:]])
res += '0' * ((len(res) // 4 + 1) * 4 - len(res))
for i in range(len(res) // 4):
    cy += dic[4 * i:4 * i + 4]
print(cy)

#eJ:zwWufwZuYwHsvelcawj9le^jxwCMb7HjhwZuYwJMz7JVl7Hugq^3j7Zob1)qQeZuke7Hj7J:n4RZze^jU1x-ge%Ige%IuqHjmeCHzwRMte^nge(ZhqHqkqKWue%MO0987

忘了怎么做了，先把解题代码放上来，后面再看

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
def dec_to_ter(num):  # 十进制转三进制（保留4位）
    l = []
    while True:
        num, reminder = divmod(num, 3)
        l.append(str(reminder))
        if num == 0:
            return "".join(l[::-1]).zfill(4)


def ter_to_dec(st):  # 三进制转十进制（输入字符串）
    num = 0
    for i in range(len(st)):
        num += 3**(len(st) - i - 1) * int(st[i])
    return num


dic = '0987654321qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM!@#$%^&*-=+:;(){}<>'
cy = 'eJ:zwWufwZuYwHsvelcawj9le^jxwCMb7HjhwZuYwJMz7JVl7Hugq^3j7Zob1)qQeZuke7Hj7J:n4RZze^jU1x-ge%Ige%IuqHjmeCHzwRMte^nge(ZhqHqkqKWue%MO0987'
msgs = ''
for i in range(len(cy)//4):
    s = cy[i*4:i*4+4]
    st = ''
    for n in s:
        st += str(dec_to_ter(dic.index(n)))
        
    msgs += st[1::]

msg = ''
for i in range(len(msgs)//5):
    pd = msgs[i*5:i*5+5]
    msg += chr(ter_to_dec(pd))
print(msg)

运行结果：

1
qing ji zhu n@melessoier shi zhen de qiang!!!Your flag is:cnss{This_is_a_strange_switch_of_Base} ¥

[(😋+😗)/2] Smooth Criminal

代码

1
2
3
4
5
6
7
8
9
msg = b''
g = 23
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
x = bytes_to_long(msg)
h = pow(g,x,p)
print(h)
'''
284807206758690260674168635652206676153199531206012399963212250117387237611215360933500261515214683228087961018802214033227875404285999805861378064908267139553648162291537289278610803697593790816897557638428568100928359466319989545031886032567685512341977270979526717345142165708163150135333252686395591140161831940144432170025393466325742577593887920556316984992847396283579269633262200726954355227038902620716137491876506054110491178240133590849734496335712064335802238492192883394892712228203054091984354156897863240197296165162563130406991577815765695750522464228829570550025932368633890216042941018677666517405480771960616480812214562091924764071878808127451559388368257581409875583275118825609722046677620382418300990385176438231226653889407671404650316193783984038250699566770765090427892884433879512806495203724706133916982135893710559405918247360707377685182171666477087313942829242876879340985182675501598869126412636
'''

离散对数问题，题目已经暗示 $p-1$ 是一个光滑数，显然是想考察 $Pohilg_Hellman$ 算法。

直接扔进 $sage$ 求解偷一波懒。 sage yyds! (bushi

1
2
3
4
5
h = 284807206758690260674168635652206676153199531206012399963212250117387237611215360933500261515214683228087961018802214033227875404285999805861378064908267139553648162291537289278610803697593790816897557638428568100928359466319989545031886032567685512341977270979526717345142165708163150135333252686395591140161831940144432170025393466325742577593887920556316984992847396283579269633262200726954355227038902620716137491876506054110491178240133590849734496335712064335802238492192883394892712228203054091984354156897863240197296165162563130406991577815765695750522464228829570550025932368633890216042941018677666517405480771960616480812214562091924764071878808127451559388368257581409875583275118825609722046677620382418300990385176438231226653889407671404650316193783984038250699566770765090427892884433879512806495203724706133916982135893710559405918247360707377685182171666477087313942829242876879340985182675501598869126412636
g = 23
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
d = discrete_log(h,mod(g, p))
print(d)

得到flag：

1
cnss{You_have_got_Pohilg_Hellman!}

[😗] ECDLP

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import bytes_to_long
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030
P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
key = b'fake_key'
flag = b'cnss{'+ key +b'}'
key = bytes_to_long(key)
assert(len(bin(key))<100)
Q = key * P
print(Q)

一道简单的ECDLP问题，考察 $Pohlig_Hellman$ 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030
P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
Q = (45327498586483906413153672412174634093375862785049326580296250293031012757729, 92851637248675027432500221064266708706584869653830467154078497414427393871661)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
factors, exponents = zip(*factor(P.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-2]
dlogs = []
for fac in primes:
    t = int(P.order()) // int(fac)
    dlog = discrete_log(t*Q,t*P,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order

key = crt(dlogs,primes)
print(key)

求出key后扔进IDLE转回bytes类型得到flag：

1
cnss{S4G3&P0h1i9}

[😗] 那个男人！！！

万恶的纯猜题/(ㄒoㄒ)/~~

先看代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
from Crypto.Util.number import bytes_to_long, getPrime
from hashlib import sha256
import random
import string
import signal
import socketserver
from os import urandom

flag = 'cnss{......}'
Bits = 256

banner = br'''[+] Big hacker MMonster is cracking a communications system.
[+] Can you help him decrypt the secret?
[+] MMonster will give you a flag in return.
'''

menu = br'''[+] 1.Get your gift
[+] 2.Give me the secret
[+] Give me your choice:'''


class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(8))
        proof = ''.join([
            random.choice(string.ascii_letters + string.digits)
            for _ in range(20)
        ])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend(
            str.encode(("[+] sha256(XXXX + %s) == %s" % (proof[4:], digest))))
        self.send(str.encode('[+] Give me XXXX:'))
        x = self.request.recv(10)
        x = (x.strip()).decode("utf-8")
        if len(x) != 4 or sha256(
            (x + proof[4:]).encode()).hexdigest() != digest:
            return False
        return True

    def dosend(self, msg):
        try:
            self.request.sendall(msg + b'\n')
        except:
            pass

    def send(self, msg):
        try:
            self.request.sendall(msg)
        except:
            pass

    def read_line(self):
        body = b""
        while True:
            ch = self.request.recv(1)
            if ch == b"\n":
                break
            body = body + ch
        return body

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def handle(self):
        try:
            signal.alarm(120)
            if not self.proof_of_work():
                self.dosend(b'[!] You must pass the PoW!')
                self.request.close()
            t = len(flag) * random.randint(4, 8)
            Con = [getPrime(Bits // 2) for i in range(t)]
            secret = getPrime(Bits)
            p = getPrime(Bits)
            self.send(banner)
            self.dosend(f"[+] p = {p}".encode())

            while True:
                self.send(menu)
                choice = self.read_line()
                if (choice == b"1"):
                    try:
                        num = random.randint(1, p)
                        result = secret
                        for i in range(t):
                            result += Con[i] * pow(num, i + 1, p) % p
                        result = result % p
                        self.dosend(b"[+] Here is your gift:")
                        self.dosend(f"[+] ({num}, {result})".encode())
                    except:
                        self.dosend(b'[!] ERROR')
                elif (choice == b'2'):
                    try:
                        self.send(b'[+] The secret: ')
                        ans = self.read_line()
                        if (int(ans) == secret):
                            self.dosend(
                                b'[+] Congratulations! You successfully cracked the system'
                            )
                            self.dosend(
                                f'[+] Here is your flag: {flag}'.encode())
                        else:
                            self.dosend(b'[+] You are wrong')
                        break
                    except:
                        self.dosend(b'[!] ERROR')
                else:
                    self.dosend(b'[!] Please follow the rule!')
                    break

        except TimeoutError:
            self.dosend(b'[!] Timeout!')
            self.request.close()
        except:
            self.dosend(b'[!] Whats wrong???')
            self.request.close()


class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 9999
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()
1
nc 101.32.29.195 9999

首先是常规的 $proof_of_work$ ，暴力破解即可

进入系统后有两种操作可选

1
2
3
[+] 1.Get your gift
[+] 2.Give me the secret
[+] Give me your choice:

操作 $2$ 后发送正确的 $secret$ 就可以得到 $flag$

操作 $1$ 后系统会生成一个随机的 $num$ 代入一个 $t$ 次同余多项式进行运算得到 $result$，然后给出 $num$ 和 $result$，其中多项式的常数项就是我们要求的 $secret$

其中选择 $1$ 可以重复选择，由此可以通过不断地选择操作 $1$ 来得到 $t$ 组$num$ 和 $result$，然后构建出一个 $t$ 维的线性方程组来求解得到 $secret$

最后需要解决的问题就是这个 $t$，$len(flag)$ 未知且每次运行还会生成随机数。。。

1
t = len(flag) * random.randint(4, 8)

刚开始脑子抽了在手动猜，失败无数次后心态发生了亿点点变化（

后面利用python里的os包来进行自动运行，尝试到 $len(flag)=45$ 时得到flag

对于求解 $flag$，最初手写了一个模条件下的简易高斯消元来求解，得到flag后发现好像想要考察的是拉格朗日插值法

完整解题代码如下：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
# coding:utf-8
from pwn import *
import hashlib
import string
from functools import reduce
from math import gcd


def ext_gcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, d = ext_gcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, d


def set_matrix(nums, results, t, q):
    matrix = []
    for i in range(t + 1):
        rows = []
        num = nums[i]
        result = results[i]
        for k in range(t):
            rows.append(pow(num, k + 1, q))
        rows.append(1)
        rows.append(result)
        matrix.append(rows)
    return matrix


def find_secret(matrix, t, q):
    for i in range(t):
        if matrix[i][i] != 1:
            s1 = ext_gcd(matrix[i][i], q)[0]
            for j in range(i, t + 2):
                matrix[i][j] = (matrix[i][j] * s1) % q
        for k in range(i + 1, t + 1):
            s2 = matrix[k][i]
            for l in range(i, t + 2):
                matrix[k][l] = (matrix[k][l] - matrix[i][l] * s2) % q
    d = ext_gcd(matrix[t][t], q)[0]
    return (matrix[t][t + 1] * d) % q


p = remote("101.32.29.195", 9999)
TOTAL = 20


def myhash(text):
    mysha = hashlib.sha256()
    mysha.update(text)
    return mysha.hexdigest()


def passPoW(plain, cipher):
    dic = string.digits+string.ascii_letters
    for a0 in dic:
        for a1 in dic:
            for a2 in dic:
                for a3 in dic:
                    tmp = (a0+a1+a2+a3+plain).encode()
                    if myhash(tmp) == cipher:
                        return a0+a1+a2+a3


def main():
    # pass the PoW
    recv = p.recvline().decode()
    print(recv.strip())
    plain = recv[18:34]
    cipher = recv[39:-1]
    print(plain, cipher)
    res = passPoW(plain, cipher)
    print(p.recvuntil("Give me XXXX:".encode()))
    p.sendline(res.encode())
    print(res + plain)

    for i in range(4):
        recv = p.recvline().decode()
        print(recv.strip())
    q = int(recv[8:-1])
    print('q = ' + str(q))

    for i in range(2):
        recv = p.recvline().decode()
        # print(recv.strip())

    t = 45 * 5
    nums = []
    results = []
    for i in range(t+1):
        p.sendline(b'1')
        for j in range(2):
            recv = p.recvline().decode()
            # print(recv.strip())
        gift = recv[5:-2].split(', ')
        nums.append(int(gift[0]))
        results.append(int(gift[1]))
        # print('num = ' + gift[0], '\nresult = ' + gift[1])
        for j in range(2):
            recv = p.recvline().decode()
            # print(recv.strip())

    matrix = set_matrix(nums, results, t, q)
    secret = find_secret(matrix, t, q)
    print(secret)
    p.sendline(b'2')
    p.sendline(str(secret).encode())
    recv = p.recvline().decode()
    print(recv.strip())
    print(recv.strip())
    print(recv.strip())
    print(recv.strip())
    recv = p.recvline().decode()
    print(recv.strip())


if __name__ == '__main__':
    main()
1
2
3
4
5
6
7
8
import os

for i in range(20):
    run = 'python p7_writeup.py'
    a = os.system(run)
    print(a)
    if a != 1:
        break

flag：

1
cnss{Lagrange_i5_one_of_My_favour1te}

[😗] RSA I

事RSA！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p * q

e = 65537
print(n)
print(pow(bytes_to_long(flag) , e , n))

_p = int(bin(p)[2:258]+bin(p)[258:][::-1],2) 
_q = int(bin(q)[258:][::-1]+bin(q)[2:258],2) 

print(_p ^ _q)

'''
128966867931621017951402141152350515585922701101703171805286229280649080647456092995914584397246443887423499663793458719282451496996613304284219288980124348105720917541598445131650977064828807037484823828553004028415721038165820372738002173903655842610359239877763360519229606532878770232406532771135170997013
5690662746178266479325698709275119693770487802124577299826695176054941202523665055025450322208031101907866334556059314241344084994180738805538046733994924313334723193790887926979826447385190012967272407294079552678501721130119836521906772578870744755554658825724748264427246566006927477363674507384245147796
5334584593664858319670147545831540027620360712512679965236952968664258458326815898964419736009663358894095508398927605649898980377954463431300198964796146
'''

难点在于通过 $p*q$ 和 $_p\bigoplus_q$ 来分解 $p,q$

观察发现，把 $_p\bigoplus_q$ 的后256位反向后可以得到 $p\bigoplus q_f$，个人感觉应该是要利用异或限制来暴力分解 $p,q$，但是思考后没能实现算法

刚开始在CTFtime上找到一道类似的rsa题目PlaidCTF 2021 / xorsa，但是这道题中的限制条件是 $p\bigoplus q$ ，尝试类比，无果

后面单独寻找异或分解终于找到GKCTF 2021 / XOR，利用脚本分解 $p,q$ 后常规求解rsa得到flag

不过最后还是没有搞懂原理，招新结束后找个师傅问一哈

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
from Crypto.Util.number import *
from tqdm import tqdm


class Solver:
    def __init__(self, x, n):
        self.x = x
        self.n = n
        self.pq = [(0, 0)]

    def add(self, b, p, q):
        if p * q <= n and (p | (b - 1)) * (q | (b - 1)) >= n:
            self.pq.append((p, q))

    def solve(self):
        for shift in tqdm(range(4095, -1, -1)):
            b = 1 << shift
            pq, self.pq = self.pq, []
            for p, q in pq:
                if self.x & b:
                    self.add(b, p | b, q)
                    self.add(b, p, q | b)
                else:
                    self.add(b, p, q)
                    self.add(b, p | b, q | b)
        return self.pq[0]


if __name__ == '__main__':
    x = 5334584593664858319670147545831540027620360712512679965236952968664258458326815898964419736009663358894095508398927605649898980377954463431300198964796146
    n = 128966867931621017951402141152350515585922701101703171805286229280649080647456092995914584397246443887423499663793458719282451496996613304284219288980124348105720917541598445131650977064828807037484823828553004028415721038165820372738002173903655842610359239877763360519229606532878770232406532771135170997013
    solver = Solver(x, n)
    p, q = solver.solve()
    print(p, q)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes

def ext_gcd(a, b):  # 扩展欧几里得算法
    if b == 0:
        return 1, 0, a
    else:
        x, y, gcd = ext_gcd(b, a % b)  # 递归直至余数等于0(需多递归一层用来判断)
        x, y = y, (x - (a // b) * y)  # 辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立
        return x, y, gcd


p = 12948472548502855475796108830280319241339751876644203406728117021144556144383328664200964459933613907132679575664273588175268439115295754485162100467976557
q = 9960006282480985513480885672444211883767328748705584719471703464167670477391828270868899276906078628248865861165369352288036643194313864072301868155144009
m = 5690662746178266479325698709275119693770487802124577299826695176054941202523665055025450322208031101907866334556059314241344084994180738805538046733994924313334723193790887926979826447385190012967272407294079552678501721130119836521906772578870744755554658825724748264427246566006927477363674507384245147796
n = p * q
e = 65537
phi = (p-1)*(q-1)
d = ext_gcd(e, phi)[0]
flag = long_to_bytes(pow(m, d, n))
print(flag.decode())

得到flag：

1
cnss{st0_Mmons7er_Or2_ajfwiclskjd}

[😯] RSA II

1
2
3
n = 97814568264814384858194701955408461509880555772006698372422205341758322175891474378211599333051180365254844248340812534463000531890490435018379585036704801177155418066770861143206836558793774360498040810255823235715535487716966004194143204900564413879660115112965484824906920141847149888933004740523449213441
e = 93943500165298065499950418373429723509334252629406924973909070866091749987346174290549648466771963135864917881154270768788129489671486923171733460927672763251885052132144244633336183737015936611716827476566876619327956203686756399730968768494676888428137426449681845021696056187478027217734766494935085365973
c = 94824506238324647310189440118275905630079991117300404682731742667903989141279243563467739363969077465823348334409761663544741888528986945132364537746094780678318967503662858734042718154696328032759064617107207652499854549294495304943140505861316519905693752269944653247754307028004160249127852813312325931155

题目只给了 $n,e,c$ 三个数据，刚开始看 $e$ 的大小觉得是 $Wiener’s Attack$ 或者 $Boneh and Durfee attack$，尝试失败后陷入了迷茫，然后直接扔factordb发现分解出来了。。。超，大意了

常规解密后得到一个网址

1
https://files.catbox.moe/eami99.py

打开后发现套了一层啊这是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from secret import flag,padding
from gmpy2 import *

m = bytes_to_long(flag)
e = 7 

p = getPrime(512)
q = getPrime(512)
n = p * q

c1 = pow(m,e,n)
c2 = pow(m+padding,e,n)

print(c1)
print(c2)
print(n)

'''
25273007066020189408109545229904933542261476876009872439710113415858837573395525630415777935344105797142851844145072854811848998350900372253971849285971326186079657861753281055419024685971559366012439288855412385839773710368571132729119276524681516954047015289030441158082956015073955156160324687579087140475
59742662912819263048476842525911792774606722595876218353030983190479211608519746735628199156539097538888609903705813533259650335449835222582640654777700444326609516992455668845647841850293730999545553827474883338490920161461753350303815384773788647536170704446255770720919964851226435888665577313224159779663
67530919003139966773553200011128742490294797009276982165948531486788511785120120505106383097675618844859048245902703407886773958024692000896590916622934616822563863757961613349221514066937957870378716994349709221655837122691033725689519576287720351954630419028668871186060611604084354574970069046834491765983
'''

看完代码后发现是一道 $Short_padding_attack$ 结合 $Related_message_attack$ 的题目，考察对 $Coppersmith$ 算法的使用

首先利用 $Short_padding_attack$ 求出 $padding$ ，然后代入 $padding$ 利用 $Related_message_attack$ 求解并转回bytes即可得到flag

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
40
41
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff
 
 
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

c1 = 25273007066020189408109545229904933542261476876009872439710113415858837573395525630415777935344105797142851844145072854811848998350900372253971849285971326186079657861753281055419024685971559366012439288855412385839773710368571132729119276524681516954047015289030441158082956015073955156160324687579087140475
c2 = 59742662912819263048476842525911792774606722595876218353030983190479211608519746735628199156539097538888609903705813533259650335449835222582640654777700444326609516992455668845647841850293730999545553827474883338490920161461753350303815384773788647536170704446255770720919964851226435888665577313224159779663
n = 67530919003139966773553200011128742490294797009276982165948531486788511785120120505106383097675618844859048245902703407886773958024692000896590916622934616822563863757961613349221514066937957870378716994349709221655837122691033725689519576287720351954630419028668871186060611604084354574970069046834491765983
e = 7
diff = short_pad_attack(c1, c2, e, n)
flag = related_message_attack(c1, c2, diff, e, n)
print(flag)
1
flag = bytes_to_long(59780862049663373465799351334364799719350413972042289550369773853093462961495194111494470756664785207187307066237).decode

flag:

1
cnss{0x10001_getPrime_invert_pow_long_to_bytes}

[😗] 大大超人的代码Ⅲ & [😯] 大大超人的代码Ⅳ

同一道题的两个不同难度，考察的核心是下面这个函数的计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# p is a prime number, 2 <= a,b < p
def f(a, b):
    S = set()
    prod = b
    while(prod not in S):
        S.add(prod)
        prod = prod * b % p

    ret = 1
    prod = a 
    while(prod not in S):
        ret = ret + 1
        prod = prod * a % p
    
    return ret

题目翻译过来就是找到最小的 $i$ 满足：

一道纯数学题，用到的是数论中阶相关的知识，刚开始做的无比艰难，后面通过举例尝试得(cai)到了结果，但是还没能得到严谨证明

得到公式后只需要解决求阶的问题就可以了，刚开始用的是暴力遍历 $\phi(p)$ 因数的方式来求阶，但是速度太慢了，第一题足足跑了两个小时

但是第二题有时间限制，就不能再用这么暴力的方法了，后面从判断原根的算法中得到启发，通过筛选去除质因数的方法来求阶：

遍历 $\phi(p)$ 的质因数 $p_i$ ，若 $a^\frac{\phi(p)}{p_i}\not=1$ ，则 $p_i$ 不是 $ord_p(a)$ 的质因数，将 $\phi(p)$ 其从中除去，最后剩下的就是 $ord_p(a)$ . 具体代码实现如下：

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
def find(a, lst, p):
    # start = time.perf_counter()
    order = p - 1
    order_list = []
    for k in lst:
        order_list.append(k)
    for j in range(len(order_list)):
        if not order_list:
            break
        for i in order_list:
            if pow(a, order // i, p) == 1:
                order = order // i
                del order_list[0]
                break
            else:
                order_list.remove(i)
    # end = time.process_time()
    # print(f'Running time: {end - start} Seconds')
    return order


def f(a, b, order_list, p):
    a1 = find(a, order_list, p)
    b1 = find(b, order_list, p)
    ret = a1 // gcd(a1, b1)
    print(ret)
    return ret

经测试，代码平均用时在0.01-0.02s左右，成果解决第二题

不过好像还存在一点小bug😢，因为我解决掉第二题之后用这个算法去解决第一题时最后结果不太对劲，而且跑出来的结果有时候还不一样，但是由于时间问题还没仔细找问题出在哪，后面有时间了再看一看，找师傅要证明的时候可以问一问

最后给出两道题的flag

1
cnss{490340709191995056161967738}
1
cnss{ACM_L1mit5_My_Im@ginati0n}

[👿]CNSS Crypto Service

BOSS题来辣！

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#!/usr/bin/env python3
from ocb import OCB
from os import urandom
import socketserver

from Crypto.Cipher import AES
from Crypto.Util.number import *
from hashlib import md5
from Crypto import Random

BS = 16
FLAG=b'cnss{..........................................}'
assert(len(FLAG) == 48)

BANNER=br"""
Welcome to CNSS Crypto Service! 
  ____ _   _ ____ ____ 
 / ___| \ | / ___/ ___| 
| |   |  \| \___ \___ \ 
| |___| |\  |___) |__) |
 \____|_| \_|____/____/ 

All the string variables you send/recieve should/would be in hex form and be n * 16 bytes.
For example, 65392825175610104412735799271089255734
"""
MENU = br"""
[1] Encrypt
[2] Decrypt
[3] Show Encryption History
[4] Exit
"""

def pad(s):
    return s + (BS - len(s) % BS) * long_to_bytes(BS - len(s) % BS) 
def unpad(s):
    return s[0:-s[-1]]
def col(a, c):
    return [a[i][c] for i in range(len(a))]

class Scheme:
    def __init__(self,key):
        self.key = key

    def encrypt(self,raw):
        raw = pad(raw)
        raw = md5(raw).digest() + raw

        iv = Random.new().read(BS)
        cipher = AES.new(self.key,AES.MODE_CBC,iv)
        return (iv + cipher.encrypt(raw)).hex().encode()

    def decrypt(self,enc):
        enc = bytes.fromhex(enc.decode())

        iv = enc[:BS]
        enc = enc[BS:]

        cipher = AES.new(self.key,AES.MODE_CBC,iv)
        blob = cipher.decrypt(enc)

        checksum = blob[:BS]
        data = blob[BS:]

        if md5(data).digest() == checksum:
            return unpad(data)
        else:
            return

class Task(socketserver.BaseRequestHandler):
    encrypt_history = []
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if type(msg)==str: msg=msg.encode()
            if newline: msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, text, prompt=b'> '):
        self.send(text, newline=False)
        self.send(prompt, newline=False)
        return self._recvall()

    def recvhex(self, text, prompt=b'> '):
        return bytes.fromhex(self.recv(text, prompt=prompt).decode('latin-1'))

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def encrypt(self, ocb):
        N = self.recvhex(b'nonce')
        M = self.recvhex(b'plain')
        if N in col(self.encrypt_history, 0) or M in col(self.encrypt_history, 0) or N==M:
            self.send('Illegal Encryption Request!')
            return()
        
        C, T = ocb.encrypt(N, M)
        self.encrypt_history.append([N, C, T])
        self.send(f'cipher: {C.hex()}')
        self.send(f'tag: {T.hex()}')

    def decrypt(self, ocb):
        N = self.recvhex(b'nonce')
        C = self.recvhex(b'cipher')
        T = self.recvhex(b'tag')
        if C in col(self.encrypt_history, 1):
            self.send('Illegal Decryption Request!')
            return()
        auth, M = ocb.decrypt(N, C, T)
        self.send(f'auth: {auth}')
        if auth:
            self.send(f'plain: {M.hex()}')

    def serve(self, isAdmin = False):
        while True:
            self.send(MENU, newline = False)
            option = int(self.recv(''))
            if option == 1:
                self.encrypt(self.ocb)
            elif option == 2:
                self.decrypt(self.ocb)
            elif option == 3:
                if isAdmin:
                    for record in self.encrypt_history:
                        self.send("#"*20)
                        self.send(f'nonce: {record[0].hex()}')
                        self.send(f'cipher: {record[1].hex()}')
                        self.send(f'tag: {record[2].hex()}')
                else:
                    self.send("Permission Denied! Only admin can use this option.")
            else:
                return
        

    def login(self):
        key = Random.new().read(BS)
        scheme = Scheme(key)
        self.ocb = OCB(urandom(16))
        N = urandom(16)
        C, T = self.ocb.encrypt(N, FLAG)
        self.encrypt_history.append([N, C, T])
        while True:
            self.send("Please [r]egister or [l]ogin")
            cmd = self.recv('')
            if cmd == b'r':
                name = self.recv("username")
                if(len(name) > 32):
                    self.send(b'Username too long!')
                    continue
                if pad(name) == pad(b'admin'):
                    self.send(b'You cannot use this name!')
                    continue
                else:
                    self.send(b'Here is your token:')
                    self.send(scheme.encrypt(name))
            elif cmd == b'l':
                data = self.recv("token")
                try: 
                    name = scheme.decrypt(data)
                except: 
                    self.send("Illegal Token!")
                    continue
                if name == b'admin':
                    self.send(b'Welcome admin!')
                    self.serve(True)
                else:
                    self.send(f'Welcome {name.decode()}!')
                    self.serve()
            else:
                self.send(b'Unknown cmd!')
                continue

    def handle(self):
        try:
            self.send(BANNER)
            self.login()
        except:
            self.send(b'What\'s wrong???')
            self.request.close()

class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

HOST, PORT = '47.113.199.200', 20000
server = ThreadedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()

题目有两个考察点

第一个是利用 $AES-CBC$ 翻转攻击来伪造 $token$ 登录 $admin$ ，进而获取 $flag$ 经过 $OCB2$ 加密后得到的 $nonce、cipher、tag$

第二个是 $OCB2$ 的 $Plaintext\ Recovery$ ，因为我们并不能直接利用系统的 $decrypt$ 来进行解密，所以就需要通过一系列构造来绕过限制条件进行解密

首先是 $AES-CBC$ 翻转攻击

在0CTF2017找到了一道类似的题目，大致思想就是利用 $AES-CBC$ 分组加密并且每一组的加密依靠的是上一组密文的特性来进行伪造

以 $admin$ 身份登录后取得 $nonce、cipher、tag$

接下来就要用到 $OCB2$ 的 $Plaintext\ Recovery$

最初找到了一篇论文Plaintext Recovery Attack of OCB2和一道类似的题Cryptography: Attacking OCB2 – react0r blog，看完后基本上已经有了思路，然后利用github上找到的代码成功解决

最后的解题代码有点小bug，sendline发的太快容易导致顺序错乱，还没来得及解决，暂时用调试顶替了一下。

完整代码如下：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
from pwn import *
from Crypto.Util.number import *
from hashlib import md5
from block import *


def pad(s):
    return s + (BS - len(s) % BS) * long_to_bytes(BS - len(s) % BS)


def bxor(b1, b2): # use xor for bytes
    parts = []
    for b1, b2 in zip(b1, b2):
        parts.append(bytes([b1 ^ b2]))
    return b''.join(parts)


def login_as_admin():
    # login as admin
    p.sendline(b'r')
    p.sendline(md5(pad(b'admin')).digest() + b'admin')
    print(md5(pad(b'admin')).digest() + b'admin')

    recv = p.recvline().decode()
    print(recv.strip())
    recv = p.recvline().decode()
    print(recv.strip())
    token = recv.strip()
    print(token.encode())
    mytoken = token[32:]
    print(len(mytoken), type(mytoken))
    recv = p.recvline().decode()
    print(recv.strip())

    p.sendline(b'l')
    p.sendline(mytoken.encode())
    recv = p.recvline().decode()
    print(recv.strip())


def get_NCT():
    p.sendline(b'3')
    recv = p.recvline().decode()
    print(recv.strip())
    recv = p.recvline().decode()
    print(recv.strip())
    nonce = Block(bytes.fromhex(recv[7:]))
    recv = p.recvline().decode()
    print(recv.strip())
    cipher = Block(bytes.fromhex(recv[8:]))
    recv = p.recvline().decode()
    print(recv.strip())
    tag = Block(bytes.fromhex(recv[5:]))
    return nonce, cipher, tag


def encrypt(nonce, message):
    for i in range(5):
        recv = p.recvline().decode()
        print(recv.strip())
    p.sendline(b'1')
    p.sendline(nonce.encode())
    p.sendline(message.encode())
    recv = p.recvline().decode()
    print(recv.strip())
    print(recv[24:])
    cipher = Block(bytes.fromhex(recv[24:]))
    recv = p.recvline().decode()
    print(recv.strip())
    print('tag = ' + recv[5:])
    tag = Block(bytes.fromhex(recv[5:]))
    return cipher, tag


def decrypt(nonce, cipher, tag):
    print('begin decrypt')
    for i in range(5):
        recv = p.recvline().decode()
        print(recv.strip())
    p.sendline(b'2')
    p.sendline(nonce.encode())
    p.sendline(cipher.encode())
    p.sendline(tag.encode())
    recv = p.recvline().decode()
    print(recv.strip())
    recv = p.recvline().decode()
    print(recv.strip())
    plain = Block(bytes.fromhex(recv[7:]))
    return plain


def randomMapping(n):
    N = Block.random(16)
    M = Block.random(n * 16) + Block.len(16) + Block.random(16)
    C, T = encrypt(N.hex(), M.hex())

    S = Block.zero()
    C_ = Block()
    T_ = M[n + 1] ^ C[n + 1]
    for i in range(n):
        C_ += C[i]
        S ^= M[i]
    C_ += (S ^ C[n] ^ Block.len(16))
    M_ = decrypt(N.hex(), C_.hex(), T_.hex())
    # assert auth

    S = Block.zero()
    for i in range(n):
        S ^= M[i]
    L = (S ^ M_[n] ^ Block.len(16)).half(n + 1)

    mappings = []
    for i in range(n):
        mappings.append((M[i] ^ L.double(i + 1), C[i] ^ L.double(i + 1)))

    return mappings


def specificMapping(Is):
    N, L = randomMapping(1)[0]

    n = len(Is)
    M = Block()
    for i in range(n):
        M += (Is[i] ^ L.double(i + 1))
    M += Block.zero()
    C, T = encrypt(N.hex(), M.hex())

    Os = []
    for i in range(n):
        Os.append(C[i] ^ L.double(i + 1))

    return Os


def recovery(N, C, T):
    L = specificMapping([N])[0]

    n = C.blocksize()
    if n == 1:
        Y = specificMapping([Block.len(16) ^ L.double()])
        M_ = Y[0] ^ C[0]
    elif n == 2:
        Y = specificMappingInv([C[0] ^ L.double()])
        M_ = Y[0] ^ L.double()
        Y = specificMapping([Block.len(16) ^ L.double(2)])
        M_ += Y[0] ^ C[1]
    else:
        L_ = L.double() ^ L.double(2)
        C[0], C[1] = C[1] ^ L_, C[0] ^ L_
        M_ = decrypt(N.hex(), C.hex(), T.hex())
        M_[0], M_[1] = M_[1] ^ L_, M_[0] ^ L_
    return M_

p = remote('47.113.199.200', 20000)
BS = 16

# receive BANNER
for i in range(12):
    recv = p.recvline().decode()
    print(recv.strip())

login_as_admin()

for i in range(5):
    recv = p.recvline().decode()
    print(recv.strip())

N, C, T = get_NCT()

flag = recovery(N, C, T)
print(bytes.fromhex(flag.hex()).decode())

最后得到flag:

1
cnss{0CB2_1S_N0t_S3cUR3__US3_OcB3_1NST34D!!!!!!}