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!!!!!!}

Aegis招新题-crypto-writeup

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

Aegis招新题-crypto-writeup

Ccc

Kinoko的代码 I

源代码：

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
from math import sqrt

def is_prime(n):
    if n < 2:
        return False
    for i in range(3, int(sqrt(n+1)+1), 2):
        if n % i == 0:
            return False
    return True


def next_prime(n):
    while True:
        if is_prime(n):
            print(n)
            return n
        n += 2


seed = 0x5eed
for i in range(64):
    seed <<= 16
    seed += 1
    seed = next_prime(seed)
print("Flag is Aegis{%s}" % (hex(seed)[-32:]))

读完代码后发现是让改进素数判别函数，降低时间复杂度，直接将原函数注释掉，调用gmpy2的is_prime函数即可（偷懒了，题目应该是想考察Miller-Rabin素性检测算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from gmpy2 import is_prime


def next_prime(n):
    while True:
        if is_prime(n):
            print(n)
            return n
        n += 2


seed = 0x5eed
for i in range(64):
    seed <<= 16
    seed += 1
    seed = next_prime(seed)
print("Flag is Aegis{%s}" % (hex(seed)[-32:]))

Kinoko的代码 II

源代码：

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
def phi(n):
	if n <= 1:
		return n
	for i in range(2, n + 1):
		if n % i == 0:
			ans = 1
			while n % i == 0:
				n //= i
				ans *= i
			ans //= i
			ans *= i - 1
			return ans * phi(n)


def common(x, y):
	if x > y:
		x, y = y, x
	i = 2
	ans = 1
	while i <= x:
		while x % i == 0 and y % i == 0:
			x //= i
			y //= i
			ans *= i
		i += 1
	return ans


def check(i, n):
	for j in range(1, phi(n)):
		if pow(i, j, n) == 1:
			return False
	return True


n = 67108934
total = 0
for i in range(n):
	if pow(i, phi(n), n) == 1 and common(i, n) == 1 and check(i, n):
		print(i)
		total += i

print ("Flag is Aegis{%d}" % (total))

首先分析代码：

1
2
3
phi(n)# 计算n的欧拉函数值
common(x, y)# 计算x, y的最大公因数
check(i, n)# 判断i是否是n的原根

分析完代码可以知道题目是让求$n = 67108934$的所有原根的和

这里需要用到原根的数学知识

最小原根是不大于 $\sqrt[4]{m}$ 级别的。

因此，不妨枚举$ [1, \sqrt[4]{m}] $的整数，得到最小原根 g。

再枚举 $g^s$ 的指数 $s$，若 $s$ 与 $φ(m)$ 互质，则$g^smodm$ 为一个原根。

由此可知，如果数 $m$ 存在原根，则原根的个数为 φ(φ(m))

首先枚举求得n最小的原根为7

然后遍历求和即可

1
2
3
4
5
6
7
8
9
from math import gcd

n = 67108934
total = 0
phin = 33554466
for i in range(1, phin):
    if gcd(i, phin) == 1:
        total += pow(7, i, n)
print("Flag is Aegis{%d}" % total)

Kinoko的代码 III

源代码：

1
2
3
4
5
6
7
8
9
P = 0x7fffffff
Q = 0x100
n = 0x100
a = [(i ** (i ** i)) % P for i in range(n)]
res = 0
for x in product(a, repeat=8):
    if reduce(add, x) % Q == 0:
        res += reduce(mul, x)
print("Flag is Aegis{%d}" % (res % (P * Q)))

尝试用快速幂计算出了a，后面的部分就没有思路了，感觉跟 $GF(2^m)$ 有关。

Kinoko的代码 IV

源代码：

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

msg = b'......'
g = 23
p = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
x = bytes_to_long(msg)
h = pow(g,x,p)
print(h)
'''
179956689939799978686596162623009071834749620910632881129570185702597885675366053746660084250822996742213156358846254579536681385720261821941496018561712101559148720253943504890341017743734982584598207516433225345830605843249917382020797858837178839235576965252932584506546764681169682067451758822339982991607788445472451090172187831874941209496749224595861824389402308122683468407022055642183997505151642262281735659513608920324853368172095765041692780083964849712368477052130574239545836322863774186581648844719904538237553913580382934907373884521762228204915991345935021715751152215665694954681931730050491031883519789246541180580522272095192525557554130071875996891173839573092163026966683532806284169788149085982141065261043806380173094680150058915109078775560035635889930619074748416389716690011996098383845646464047453083163083103550738288711630170975733999017234569638947005463854359023927470291784650805324521819096823
'''

考察离散对数求解的知识，直接调用sage中的$discrete_log()$函数求解x，再转换为bytes即可

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

c = 179956689939799978686596162623009071834749620910632881129570185702597885675366053746660084250822996742213156358846254579536681385720261821941496018561712101559148720253943504890341017743734982584598207516433225345830605843249917382020797858837178839235576965252932584506546764681169682067451758822339982991607788445472451090172187831874941209496749224595861824389402308122683468407022055642183997505151642262281735659513608920324853368172095765041692780083964849712368477052130574239545836322863774186581648844719904538237553913580382934907373884521762228204915991345935021715751152215665694954681931730050491031883519789246541180580522272095192525557554130071875996891173839573092163026966683532806284169788149085982141065261043806380173094680150058915109078775560035635889930619074748416389716690011996098383845646464047453083163083103550738288711630170975733999017234569638947005463854359023927470291784650805324521819096823
m = 23
n = 335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
d=discrete_log(c,mod(m,n))
msg = long_to_bytes(d)
print(msg)

notRSA

源代码：

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

p = getPrime(512)
q = getPrime(512)
n = p * q
flag = b'Aegis{......}'
m = bytes_to_long(flag)
c = pow(m, 2, n)
print(p**3+q**3)
print(p*q-p-q)
print(c)

# p = 9294245038014495018370025503838233837842445450717112861530019994089208464544256432365138864858019427603469395634623982915723003321692974199306043896395471
# q = 12342761514228429158263998414220938515337038241757334937761557332062702646597784278541920751268963691194708568191829119140194036616936954532285327408748239
#2683207403901766067825485634185601766409570143649318199140952968037512600470579376068383383524815864039841298998044483348310172352574406995610031363899276749157640097193160488032526253335175497216620520711500711141110234147693948098688349034232723537263489946840300271580577412796742296691684971450119145954769829625063379511509190333209177419150804570514746916533943674944751821667853376532291018641849933876951962902976903371221223111423718945634451076584248030
#114716649959013852657615268840231124447472690710601678501437134218521741792245535933871147569266364478277891322010833300443127314646898434178369690377612566380887447356076682596113975161733897245200003941284379586690945264751249879210669330319947878473291341185035678293547495739763970613403135670992913681859
#23588520303183909632881265716945062770267850520083979450971468612710595466903076931312046174728593508895307445955963477450821781428035995913285067064035796132808196500567866710084350514597397699053074465810242481186367241

读代码后发现 $e=2$, 很明显的 $Rabin$ 加密，利用题目中给出的 $p^3+q^3$ 和 $pq-p-q$ 联立方程解出 $p, q$ 即可

公式推导如下：

求解 $p, q$ 的代码如下：（此处设$a = p^3+q^3,b = pq-p-q$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sympy as sp
a = 2683207403901766067825485634185601766409570143649318199140952968037512600470579376068383383524815864039841298998044483348310172352574406995610031363899276749157640097193160488032526253335175497216620520711500711141110234147693948098688349034232723537263489946840300271580577412796742296691684971450119145954769829625063379511509190333209177419150804570514746916533943674944751821667853376532291018641849933876951962902976903371221223111423718945634451076584248030
b = 114716649959013852657615268840231124447472690710601678501437134218521741792245535933871147569266364478277891322010833300443127314646898434178369690377612566380887447356076682596113975161733897245200003941284379586690945264751249879210669330319947878473291341185035678293547495739763970613403135670992913681859
p = [1, -3, -3*b, -a]

x = sp.Symbol('x')
f = x**3 + p[1]*x**2 + p[2]*x + p[3]
s = sp.solve(f)
# print(s[0])

pq = s[0]+b
q = [1, -s[0], pq]
y = sp.Symbol('y')
g = y**2 + q[1]*y + q[2]
solve = sp.solve(g)
print('p = ' + str(solve[0]))
print('q = ' + str(solve[1]))

运行后解出$p,q$

1
2
p = 9294245038014495018370025503838233837842445450717112861530019994089208464544256432365138864858019427603469395634623982915723003321692974199306043896395471
q = 12342761514228429158263998414220938515337038241757334937761557332062702646597784278541920751268963691194708568191829119140194036616936954532285327408748239

接下来将 $p,q$ 代入进行 $Rabin$ 解密即可

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

e = 2
c = 23588520303183909632881265716945062770267850520083979450971468612710595466903076931312046174728593508895307445955963477450821781428035995913285067064035796132808196500567866710084350514597397699053074465810242481186367241
p = 9294245038014495018370025503838233837842445450717112861530019994089208464544256432365138864858019427603469395634623982915723003321692974199306043896395471
q = 12342761514228429158263998414220938515337038241757334937761557332062702646597784278541920751268963691194708568191829119140194036616936954532285327408748239
n = p*q
u = pow(c, (p+1)//4, p)
v = pow(c, (q+1)//4, q)
#   sp+tq=1
s = gmpy2.invert(p, q)   # (p^-1) mod q
t = gmpy2.invert(q, p)   # (q^-1) mod p
x = (t*q*u+s*p*v) % n
y = (t*q*u-s*p*v) % n

print(b'm1 = ' + long_to_bytes(x % n))
print(b'm2 = ' + long_to_bytes((-x) % n))
print(b'm3 = ' + long_to_bytes(y % n))
print(b'm4 = ' + long_to_bytes((-y) % n))

得到结果如下，m3即为flag

1
2
3
4
b'm1 = kg\xe1\xe8u\x8b\x8b\xda\x04>\xd8z<l\xeby\xd9,1<\x81\xc4\x1d0\x1e\xd8=\x82k\x1cr\x8bzP\x03S\xa1)\xf6\xf2\xdf\x87\xa8\x92\xfd\xf00\xfc\xf5(\xb3\x9e\xa3N\x87~\xf2\xab\xcdr\x1e\x04\xac\xaa\xdc\x90U\x0c\xdeC\x00\xe5oy\xb9\xc9\x1e~\xa5\x01=2\x86O\xbd}\xc4\x1f8\x04g\x8c\xc2\x7f\xae\xf2 wX\xb1\xda#\\\xce\xb0\xde[\xf4\xd0\xe9MN\xb8\x93\xc4\xef\x17%g\xaf\x96I*\xdd\x9a\xc2\x8ec'
b'm2 = 7\xf4\xc5\xad!6\x99\x9dO\xd6\xd6\xce?\x89\x02\xdc\xa8\x11\xb11\xb6Lga\xee\x89\x18n\xd8\x845\xb5\x922\x81\xa3\x01\x81\xbe3X\xd5E*\x1b\xc1o\xe4\x00\x04W\xfe\x88\xb8$\xadO\xd7\x9d\xc4\xcb\xee\xcd\x9a\xf0T\xc4\x18\x10\xc9#\x95f\xb01\xe9}\x0b\x80u\xf4g\xd9\x92\xf0\x1bl\x8bd\xde\xcay\xc2Hj\xdb\x11}[\xa1\xef\x86\xbf\xa2\xd3\xdf\xb5\x99\xe7\x13\rg\xe9\xc0*\xefO~\x87\x84\xf4V6\xef\x04\xbd\x8c\xfe'
b'm3 = Aegis{This_is_RABIN_not_RSA_though_similarity}'
b'm4 = \xa3\\\xa7\x95\x96\xc2%wT\x15\xafH{\xf5\xeeV\x81=\xe2n8\x10\x84\x92\raU\xf1C\xa0\xa8A\x0c\x82\x84\xf6\xa2\xab\xb5&8\\\xed\xbd\x19\xb1\xa0\xe0\xf5-\x0b\x9d,\x06\xac,B\x83k6\xe9\xf3zE\xcc\xe5\x19$\xef\x0c$z\xd6)\xeb\xb2\x9b\x8a%w1\x9a\x1e}F/\xbd/Hz\xc8\x93%^\xa6m\xdf\xb3r\n{J\xae\x02\x10^\xbf;v\x9c\xe6N2\xde\x88v\x070\x85\xc7!3\x00Z6\x0b\xa1\xe4'

LFSR

源代码：

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
flag = b"Aegis{????????????????????????}"
assert(len(flag)) == 31


def parity(x):  # 检验二进制x中1的个数，奇为1，偶为0
    res = 0
    while x:
        x -= x & (-x)
        res ^= 1
    return res


class LFSR:
    def __init__(self, init, mask, length):
        assert((mask & (1 << (length - 1))) != 0)
        self.init = init
        self.length = length
        self.lengthmask = 2 ** length - 1
        self.mask = mask & self.lengthmask

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask
        output = parity(self.init & self.mask)
        nextdata ^= output
        self.init = nextdata
        return output


secret = flag[6:-1]
l = LFSR(int(secret[:12], 16), int(secret[12:], 16), 48)
outstream = 0
for i in range(96):
    outstream <<= 1
    outstream |= l.next()
print(hex(outstream)[2:])  # 9375392d53d805407156b455

常规的LFSR题目，分析代码可知 $init$ 和 $mask$ 均为 $48bit$

而结果所给的 $outstream$ 为 $96bit$ ，恰好为两轮加密的长度

①前 $48bit$ 为 $init$ 加密经过一轮加密所得

②后 $ 48bit$ 为前 $48bit$ 再经过一轮加密所得

利用第②点加密前后均已知我们可以求得 $mask$ ，sage代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def test(outstream):
    s = [int(x) for x in outstream]

    M = matrix(GF(2), 48, 48)
    T = vector(GF(2), 48)

    for i in range(len(s) - 48):
        M[i] = s[i: i + 48]
        T[i] = s[i + 48]
    try:
        mask = M.inverse() * T
        return hex(int(''.join(map(str, (mask))), base=2))
    except:
        return


outstream = 0x9375392d53d805407156b455
mask = test(bin(outstream)[2:])
print('mask = ' + mask)

运行结果：

1
mask = 0xffbeefc0ff3e

解得 $mask$ 后代入第①点即可解出 $init$ ，将 $init$ 和 $mask$ 拼起来即可得到flag，sage代码如下：

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
import itertools, hashlib, numpy as np


def int2bin(a, n):
    assert 0 <= n and a < 2 ** n
    res = np.zeros(n, dtype=int)

    for x in range(n):
        res[n - x - 1] = a % 2
        a = a // 2
    return res.tolist()


def bin2int(a):
    return reduce(lambda x, y: x * 2 + y, a)


def bitAnd(a, b):
    assert len(a) == len(b)
    return list(map(lambda x, y: int(x) & int(y), a, b))


def test(outstream):
    s = [int(x) for x in outstream]

    M = matrix(GF(2), 48, 48)
    T = vector(GF(2), 48)

    for i in range(len(s) - 48):
        M[i] = s[i: i + 48]
        T[i] = s[i + 48]
    try:
        mask = M.inverse() * T
        print('mask = ' + hex(int(''.join(map(str, (mask))), base=2)))
    except:
        return

    suf = []
    for i in range(48):
        if bitAnd([0] + suf + s[0:47 - i], mask).count(1) % 2 == s[47 - i]:
            suf = [0] + suf
        else:
            suf = [1] + suf

    key = hex(bin2int(suf))[2:]

    print('init = ' + key)
    print('The flag is Aegis{' + key + hex(int(''.join(map(str, (mask))), base=2)) + '}')


outstream = 0x9375392d53d805407156b455
test(bin(outstream)[2:])

运行结果：

1
2
3
mask = 0xffbeefc0ff3e
init = a11ceb0bff0f
The flag is Aegis{a11ceb0bff0f0xffbeefc0ff3e}

ezECC

源代码：

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
from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

Point = namedtuple("Point", "x y")

O = 'Origin'

FLAG = b'Aegis{......}'


def check_point(P: tuple):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P: tuple, Q: tuple):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R


def double_and_add(P: tuple, n: int):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def gen_shared_secret(Q: tuple, n: int):
    S = double_and_add(Q, n)
    return S.x


def encrypt_flag(shared_secret: int):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


p = 310717010502520989590157367261876774703
a = 2
b = 3

g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = Point(g_x, g_y)

n = randint(1, p)

public = double_and_add(G, n)
print(public)

b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)

shared_secret = gen_shared_secret(B, n)

ciphertext = encrypt_flag(shared_secret)
print(ciphertext)

分析代码知道这是一道 ECC 加 AES 的题目，首先解决ECC得到 $shared_secret$ ，然后再代入AES解密即可，下面是具体解决步骤

首先利用Pollig_Hellman算法求出n：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
K = (260053855577519367767956057258891222403, 179596564645843970846404853116641598439)
G = (179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
K = E.point(K)
G = E.point(G)

# primes中为点G的阶的质因数分解
primes = [2, 3**7, 139, 165229, 31850531, 270778799, 179317983307]
dlogs = []
for fac in primes:
    t = int(G.order()) // int(fac)
    dlog = discrete_log(t*K, t*G, operation='+')
    dlogs += [dlog]
    print(str(fac) + ',' + str(dlog))
n = crt(dlogs, primes)
print('n = ' + str(n))
1
n = 1735615609077661663789047116578013247

再利用求出的 $ n $ 计算 $nB$ 得到 $shared_secret$ ：

1
2
3
4
5
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)
shared_secret = gen_shared_secret(B, n)
print("shared_secret = " + str(shared_secret))
1
shared_secret = 80834286993107767130878144281867395240

得到 $shared_secret$ 后可以得到AES加密中的key，结合所给的iv，将 $ciphertext$ 解密即可得到 $flag$ ：

1
2
3
4
5
6
7
8
9
10
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]

iv = bytes.fromhex('45879e81ea63153f4dbc94603cbf6ebc')

cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = bytes.fromhex('db9741d44b9d1718bb9e47b7584795e1f09169119a6d5bafe6fe6a6b950e5669f64ec7057f21711c4e896d4a65de20af')
flag = unpad(cipher.decrypt(plaintext), 16)
print(flag)
1
b'Aegis{07e2628b590095a5e332d397b8a59aa7}'

完整代码如下：

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
from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

Point = namedtuple("Point", "x y")

O = 'Origin'

def check_point(P: tuple):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P: tuple, Q: tuple):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R


def double_and_add(P: tuple, n: int):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def gen_shared_secret(Q: tuple, n: int):
    S = double_and_add(Q, n)
    return S.x


p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
K = (260053855577519367767956057258891222403, 179596564645843970846404853116641598439)
G = (179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
K = E.point(K)
G = E.point(G)

primes = [2, 3**7, 139, 165229, 31850531, 270778799, 179317983307]
dlogs = []
for fac in primes:
    t = int(G.order()) // int(fac)
    dlog = discrete_log(t*K, t*G, operation='+')
    dlogs += [dlog]
    print(str(fac) + ',' + str(dlog))
n = crt(dlogs, primes)

b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)
shared_secret = gen_shared_secret(B, n)

sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]

iv = bytes.fromhex('45879e81ea63153f4dbc94603cbf6ebc')

cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = bytes.fromhex('db9741d44b9d1718bb9e47b7584795e1f09169119a6d5bafe6fe6a6b950e5669f64ec7057f21711c4e896d4a65de20af')
flag = unpad(cipher.decrypt(plaintext), 16)
print(flag)

NTRU算法详解

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

NTRU算法详解

算法背景

    NTRU是Hoffstem、Pipher和silverman在1998年提出的一种新的公钥密码体制。该体制是建立在多项式环的基础之上的，其安全性基于格上最短向量问题，可以有效抵抗Shor算法。由于NTRU运算简洁快速，与目前广泛使用的公钥密码系统RSA及椭圆曲线密码系统相比较，在安全要求相同的情况下，NTRU产生密钥对更快，在加密和解密效率上也具有一定的优势。但NTRU的原始方案的安全性一直没有得到严格的证明。

    2011年，Stehle D，SteinfeldR在理想格上基于R-LWE问题构造了选择明文攻击安全的NTRU加密体制。2012年，Ron Steinfeld等人在理想格上提出了选择密文攻击安全的NTRU加密体制。

算法流程

45454f65d2ae336cbc09c4e8178e8769.png

参数选取

N：次数参数，素数

q：大模数，正整数

p：小模数，奇素数或多项式

d：用来限制非0系数的个数，正整数

f(x)：模多项式，N次整系数多项式，将格$Z^N$构造为环$Z[x]/f(x)$

经典参数值：

密钥生成

公钥：$(N, p, q, h(x))
$

私钥：$(f(x), f_{p}^{-1}(x))$

  1. 生成$f(x),f_{q}^{-1}(x),f_{p}^{-1}(x)$

    （1）在格$Z[x]$上选取多项式$f(x)$，满足$f(x)$的次数不超过N-1，系数为$\{-1, 0, 1\}$中的值，且有d+1个系数为1，d个系数为-1，其他系数为0。

    （2）检验$f(x)$在环$Z_q[x]/f(x)$上是否可逆，如果可逆则计算逆元$f_{q}^{-1}(x)$

    （3）检验$f(x)$在环$Z_p[x]/f(x)$上是否可逆，如果可逆则计算逆元$f_{p}^{-1}(x)$

    重复上述步骤，直至得到$(f_{q}^{-1}(x), f_{p}^{-1}(x))$

  2. 生成$g(x)$

    在格Z[x]上选取多项式$f(x)$，满足$f(x)$的次数不超过N-1，系数为$\{-1, 0, 1\}$中的值，且有d+1个系数为1，d个系数为-1，其他系数为0

  3. 计算$h(x)$

加密阶段

  1. 将明文编码为系数属于$\{-1,0,1\}$的多项式$m(x)$，明文空间即为$\mathcal{M}=\{-1,0,1\}^N$；同时，在参数选取为$(p,f(x))=(3,x^N-1)$时，有$\mathcal{M}=Z_p[x]/f(x)$

  2. 随机选取多项式$r(x) \in Z_p[x]/f(x)$

  3. 计算密文

解密阶段

  1. 首先计算：（此处省略了多项式后的(x)）
因为$r(x),g(x),f(x),m(x)$的系数都较小，故上述计算所得到的为恒等式

而非同余式
  1. 接下来计算：

  1. 需要注意的是，1中实际上为概率性算法，概率与q的取值有关，细节见下图：

知识补充

这一部分主要为在代码实现时所要用到的算法

中心化处理取模

中心化处理，即模q运算或模p运算的结果以0为中心。

比如模3运算的结果属于$\{-1，0，1\}$而不是$\{0，1，2\}$,
模256运算的结果属于$\{-127，-126，…，128\}$而不是$\{0，1…，255\}$。

这样的中心化处理在代数上没有任何不同，但使得尺寸变小了。环$Z_q[x]/f(x)$和环$Z_p[x]/f(x)$都经过这样的中心化处理。

将明文编码为多项式

还没找到合适的算法……

判断多项式是否可逆

见NTRU - PamShao - 博客园或论文《NTRU中多项式的逆问题》

多项式卷积计算与快速卷积

设$a(x), b(x), c(x) \in Z^N/f(x)$，其中$c(x)$为a(x)与b(x)的卷积计算结果，记作

将上述多项式表示为向量形式，如下：

由于$X^N \equiv 1 \pmod{X^N -1}$，故乘积后有$X^{N+i} \equiv X^i \pmod{X^N -1}$，进而可以得到：

快速卷积算法

Hello World

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

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment