2023HECTF

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 2.4k 阅读时长 ≈ 9 分钟

2023HECTF——Crypto方向题解

Crypto

rsarsa

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
from functools import reduce
from Crypto.Util.number import *
import random
from secret import flag,hint

def generate_PQ(bits):
    x = getPrime(bits) >> bits//2 << bits//2
    while True:
        p = x + random.getrandbits(bits//2)
        if isPrime(p):
            break
    while True:
        q = x + random.getrandbits(bits//2)
        if isPrime(q):
            break
    return p,q

m = bytes_to_long(flag)
hint = bytes_to_long(hint)
e = 65537
p,q = generate_PQ(1024)
n = p*q
random.seed(seed)
x = [random.randint(1,seed) for _ in range(2)]
y = [random.randint(1,seed) for _ in range(2)]

print("c =",pow(hint,e,n))
print("n =",n)
print("c1 =",pow(reduce(lambda x, y: x * m + y, x), 17, n))
print("c2 =",pow(reduce(lambda x, y: x * m + y, y), 17, n))

p,q的高512位一样，所以p,q接近，用费马分解，获得hint = Hint{Seed_is_256087_+_396445_-_538018}

有了seed，便有了x,y，然后就是对两个lambda的理解

两个lambda实际上的作用是：c1 = pow(x[0]*m + x[1],17,n)，c2 = pow(y[0]*m + y[1],17,n)

很明显相关消息攻击

exp:

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
# sage
from Crypto.Util.number import *
import random
import gmpy2

c = 
n = 
e = 65537
c1 = 
c2 = 

# a = gmpy2.iroot(n,2)[0]
# while 1:
#     a += 1
#     b2 = pow(a,2)-n
#     if gmpy2.is_square(b2):
#         b = gmpy2.iroot(b2,2)[0]
#         p = a+b
#         q = n // p
#         d = gmpy2.invert(e,(p-1)*(q-1))
#         hint = pow(c,d,n)
#         print(long_to_bytes(hint))
#         break

seed = 256087 + 396445 - 538018
random.seed(seed)
x = [random.randint(1,seed) for _ in range(2)]
y = [random.randint(1,seed) for _ in range(2)]
print(x)
print(y)
def franklinReiter(n,e,c1,c2):
    PR.<m> = PolynomialRing(Zmod(n))
    g1 = (x[0]*m + x[1])^e - c1
    g2 = (y[0]*m + y[1])^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]


m = franklinReiter(n,17,c1,c2)
flag = long_to_bytes(int(m))
print(flag)
# HECTF{r3411y_easy_R4nd0m_And_r3l4ted_m3554ge_att4ck}

我们三

第一层

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

def padding(data):
    return data + b"".join([b'\x00' for _ in range(0, 16 - len(data))])

def execute_program():
    secret_data = padding(flag)
    secret_key = os.urandom(16) * 2
    init_vector = os.urandom(16)
    print(bytes_to_long(secret_key) ^ bytes_to_long(init_vector) ^ 1)
    cipher = AES.new(secret_key, AES.MODE_CBC, init_vector)
    encrypted_flag = cipher.encrypt(secret_data)
    print(encrypted_flag)

if __name__ == "__main__":
    execute_program()
#113271863767201424639329153097952947311122854394813183532903131317262533549675
#b'_1\x16\xc2;\xb1\xddy\x14\xdd\x14\xe5{\x19\x04:'

根据secret_key = os.urandom(16) * 2和init_vector = os.urandom(16)长度不同，导致异或后key的前一半并无影响

可以很容易获得key，接着获得iv。

解密得到信息：RSAKEYISFTCEH，即下一层压缩包密码为FTCEH

exp:

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

hint = 113271863767201424639329153097952947311122854394813183532903131317262533549675
key = long_to_bytes(hint)[:16] * 2

c = b'_1\x16\xc2;\xb1\xddy\x14\xdd\x14\xe5{\x19\x04:'
iv = long_to_bytes(bytes_to_long(key) ^ hint)

aes = AES.new(key, AES.MODE_CBC, iv)
message = aes.decrypt(c)
print(message)

第二层

1
2
3
n=: 17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
c=:7650350848303138131393086727727533413756296838218347123997040508192472569084746342253915001354023303648603939313635106855058934664365503492172
没了 真没了 加油少年

n很容易分解，用sagemath求phi

解密获得信息：keyisEa51stRsA，即下一层压缩包密码为Ea51stRsA

exp:

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

n = 17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
c = 7650350848303138131393086727727533413756296838218347123997040508192472569084746342253915001354023303648603939313635106855058934664365503492172
e = 65537

phi = 1
for p in factor(n):
    phi *= p[0] - 1
    
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

第三层

1
2
3
gIHkeIlRQp1fLeSWEqZJdOTO4aRYRB2OGRcBycHQ1OAdi6UEULYbwIvYh+0alYScSEoN4TOejgTjdPsetrURRlLX6dcifjX6VvLxY7TnMk7c8/xy17mybq/yNQf0vFGh8byC88bUeHian9dA2Qh6rRBYS1I7iNxM62RtCFZ+1OKeaqGIDjf3/VuPlbnCePYIY5FVs6xNXjkGh0m57t2QW4CoGI5lz6OcAAwg4AHP0d8CfeldOF/TogPwOiPaRlDbtHXCh54Bs5ZivV+jDerr0RQvCGYBFHYLJnvyrFtyZC9BxAQ8gQnGlWNDjE1V6BByUvJjpI9DcUyRSNN21rUWouOiLwtKX0BgDQkGH9PhtzhmGYI+R3lZJ4x30l+Xqweu

DES CBC PKCS7 key：hectf iv：0000

DES在线加密解密工具 - MKLab在线工具，网站解密即可

littleblock

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
from Crypto.Util.number import *
import random
from secret import flag

def convert(m):
    m = m ^ m >> 13
    m = m ^ m << 9 & 2029229568
    m = m ^ m << 17 & 2245263360
    m = m ^ m >> 19
    return m


def circular_shift_left(int_value, k, bit=32):
    bin_value = bin(int_value)[2:].zfill(32)
    bin_value = bin_value[k:] + bin_value[:k]
    int_value = int(bin_value, 2)
    return int_value


def enc_block(block):
    block ^= a
    block = circular_shift_left(block, 11)
    block ^= b
    return block


def my_encblock(message):
    assert len(message) % 4 == 0
    new_message = b''
    IV = bytes_to_long(b'retu')
    for i in range(len(message) // 4):
        block = message[i * 4: i * 4 + 4]
        block = bytes_to_long(block)
        block = convert(block)
        block = enc_block(block) ^ IV
        IV = block
        block = long_to_bytes(block, 4)
        new_message += block
    return new_message


a = random.getrandbits(32)
b = random.getrandbits(32)
m = my_encblock(flag)
print('a =', a)
print('b =', b)
print('m =', m)
'''
a = 1909693462
b = 3279553481
m = b'\xa1\x14\xa66\x9c\x88\xe3\xeco?\xe2\x95\xbd\xcd\x1a2)i\xf5_)\x15H\xf2y\xec\x8d\xfc*KU\xefv\xdd\xd0X'
'''

理解代码后逆回去即可

exp:

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

def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp

def inverse_right_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

def inverse_left(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp

def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def recover(y):
    y = inverse_right(y,19)
    y = inverse_left_mask(y,17,2245263360)
    y = inverse_left_mask(y,9,2029229568)
    y = inverse_right(y,13)
    return y&0xffffffff

def circular_shift_left(int_value, k, bit=32):
    bin_value = bin(int_value)[2:].zfill(32)
    bin_value = bin_value[k:] + bin_value[:k]
    int_value = int(bin_value, 2)
    return int_value

def dec_block(block):
    block ^= b
    block = circular_shift_left(block, 32-11)
    block ^= a
    return block

a = 1909693462
b = 3279553481
c = b'\xa1\x14\xa66\x9c\x88\xe3\xeco?\xe2\x95\xbd\xcd\x1a2)i\xf5_)\x15H\xf2y\xec\x8d\xfc*KU\xefv\xdd\xd0X'

cipher = [c[i * 4:i * 4 + 4] for i in range(len(c) // 4)]
cipher = cipher[::-1]

def decrypt(cipher):
    Message = []
    for i in range(1,len(cipher)):
        enc = bytes_to_long(cipher[i]) ^ bytes_to_long(cipher[i-1])
        enc = dec_block(enc)
        m = recover(enc)
        msg = long_to_bytes(m)
        Message.append(msg)
    return Message

message = decrypt(cipher)
message = message[::-1]
flag = b"HECT"

for i in message:
    flag += i
print(flag)
# HECTF{spodjoqw321jp3ij09adfiosofrga}

其中recover(y)是对covert(m)的解密

dec_block(block)是对enc_block(block)的解密

通过前一段和后一段的异或来获得enc_block(block)的密文，然后依次逆回去即可

最后一段是HECT，也可以用iv = b"retu"来求解

Easyecc

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
from Crypto.Util.number import *
from Crypto.PublicKey import ECC
from fastecdsa import curve
from sympy import *
me = bytes_to_long(flag)

key = ECC.generate(curve='NIST P-256')
f = open('pem.txt', 'w').write(key.export_key(format='PEM'))
G = key.public_key()
k = key.d
n = G.order()
p = curve.P256.p
r = randprime(1, n-1)

M = E.random_point()
# M = (mx, my)
e = nextprime(my-mx)
N = n * p
c = pow(me, e, int(N))
print('c =', c)

K = k*G
c1 = M+r*K
c2 = r*G
print(c1)
print(c2)

# c = 340411986008332622492252515156919590702658555525072399052451683041772652474839788525448087771416400264570261404595656046016551644464496921197111421138765
# c1 = (71430232672331113271988412132459391678542075997754159037222774180961171917977 : 62238630405406252154015032808640586594811636815028129383858020738965206372881 : 1)
# c2 = (25742109236464952840117078659367834030129507446418393682693133323915430074859 : 65657711071079869088595294059522027768683424454908946840021611773238453793364 : 1)

pem.txt

1
2
3
4
5
-----BEGIN PRIVATE KEY-----
MIGHAgEAMBMGByqGSM49AgEGCCqGSM49AwEHBG0wawIBAQQgotFz7q/WASYctvjN
Cm4zE7fkywF7jJV0nIME7bsW2i6hRANCAARClk9phO799cZ7E/ZF3ByjzczSz2Wd
fuVuLvrNSK0wlUCXegI/pVSDhvLM9diYBj0hear1pO4tA89Kttmsl4Bf
-----END PRIVATE KEY-----

先把私钥读取了获得k，然后网上找了这条曲线的参数，再自行打印G

解出M之后，获得e，再解RSA即可

exp:

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

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
k = 73644752642842712320035434881783031141060118592034523842277486117853194541614
c = 340411986008332622492252515156919590702658555525072399052451683041772652474839788525448087771416400264570261404595656046016551644464496921197111421138765

E = EllipticCurve(GF(p),[a,b])
point_x = 30118223148967673906925292482929130826457579297516838790778878429125386514581
point_y = 29215658289787473919256744525817443100199549137769452961719426728959931809887
G = E(point_x,point_y)
# n = G.order()
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
N = n * p

c1 = E(71430232672331113271988412132459391678542075997754159037222774180961171917977 ,62238630405406252154015032808640586594811636815028129383858020738965206372881 )
c2 = E(25742109236464952840117078659367834030129507446418393682693133323915430074859 ,65657711071079869088595294059522027768683424454908946840021611773238453793364 )
M = c1 - k*c2

mx = M[0]
my = M[1]

e = gmpy2.next_prime(int(my - mx))
d = gmpy2.invert(e,(p-1)*(n-1))
m = pow(c,d,N)
print(bytes.fromhex(hex(m)[2:]))
# HECTF{Which_one_do_you_prefer?ECC?RSA?}

大帝攻占福岛

1
"zpvepoudbsgcdqwvjgocqg|rxrqo|feviefsyx}szwt|skqfl?NKIZLYZUVfU|jslhyfzmiom…"

找大写字母NKIZL，和HECTF对比发现移位量为6，判断为变异凯撒，每10位移位量加1

exp:

1
2
3
4
5
6
7
8
9
10
11
12
c = "zpvepoudbsgcdqwvjgocqg|rxrqo|feviefsyx}szwt|skqfl?NKIZLYZUVfU|jslhyfzmiom…"
m = ""

for j in range(7):
    temp = c[10*j:10*j+10]
    for i in range(10):
        m += chr(ord(temp[i]) - j-1)

for i in c[70:]:
    m += chr(ord(i) - 8)
print(m)
# youdontcareabouthemandyouonlycareaboutyourownflag:HECTF{STOP_Nuclear_sewage}

nextnext

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
import gmpy2
from sympy import *
from Crypto.Util.number import *
from flag import flag
assert len(flag) == 36


def gen_parameter():
    seed = getPrime(512)
    p = nextprime(seed * 4 + 3)
    q = nextprime(int(str(p)[::-1]))
    a = nextprime(p&(10**6) + 2023)
    b = nextprime(q%(10**6) + 2023)
    g = nextprime(str(a)+str(b))
    return seed, p, q, g, a, b


u, p, q, g, a, b = gen_parameter()
n = p*q
m = []
c = []
t = len(flag)//2
ul = []
for i in range(t):
    mi = bytes_to_long(flag[i*len(flag)//t:(i+1)*len(flag)//t])
    m.append(mi)
    assert mi < g
    ci = pow(b, mi, n)*pow(u, g, n) % n
    c.append(ci)
    u = (a * u + ci) % n
    ul.append(u)

print('g =', g)
print('n =', n)
print('c =', c)
'''
g = 477221908301
n = 3316800027546899796299249900490338525446722616927865256312015775762946188822765432534092050609396978713268788263981158799865606788375214514715320762212090700556505831986082588196853742449073887978094469425136388568791343123156410854535956201512370508501035099259640256718574195902438477533011590110397102848237
c = [1055164913936861759601070681328133050501717812617683016760570306135820467684982411801348559225269987267344307291062260464313087313624260892305321033950481761766023104810722884530078669496273907717111088374157435933600032536778307024663155969024389539729313080850409619343987657232845340152570573522505621491603, 1931851107627113585898872797097407306775031283164577426145463830123237346520365715246429128224516824122830942699000943541489810766548629439116718005359410307932157835115818123572788574134272559866149510231173682996794795999813187683826003192711531187198464750488603425072083209561408438176122711585965417614521, 1551562722871551197414863544414517343879371834887856099644139717728598793747909014883607220057480535681811569818345280038106100034854300913500569380554031238944182867302031941796646079530311570715793289486496649040783388744493532753060611388234228588390324510451593705548122570734602832796634689681202286741231, 1023651876808318489905393236446524875536885683951145279330352918602853853447694302817954906550298552070780962780070361906218334252821218710182511457918223412762333039692689232650733728755517977280988908985889489001184280272980160457616272709308635982633848318896773374734511656916563942512330005914504195635337, 1396728575337462242947982357590285697182930985707363439305151790398230329601135817800702179968308661208157769938994960699547956746505619567144059124531141441467752697367504171971237392789440539834528097734120365895796879328931933526487179744144262805264212389440273880262757867643667487471108998309565898550140, 1453463533504342407605898896519240080022740769794850225555335805482946107024146169859390000606299331075843994897074067237384575978609903446750030301027143895789020930399227882365796877224045827151164458601051146128595023893592012624245622790310841426316026640692999628802961860272538252503655414255518715501760, 1734188098997045370459645852270876699525364972973439165430983746851028049030910755833101537881287022509713394813625855156597027177172650956556060878254135655554674984881391846365166915103188598322747593655410268343252535017545199684952748721388752410634453219588167967135997210093573628009136839331824663153793, 1818406699779534791674336722314603769405956761591677237541492728774856474202640994826261621058081466035202157430270600277311013762985807007932699131075589061444374253409259047428068590023426361125116787756419263498989853608265018899170600671857062729998584244286042946872554751935726176233509343237366515496055, 2110224578372551604599780781500885585255551193387191859255137522510922283309200273861267242416082384430111092429514796837475408585393892870687357616822691388215024614592556325867420126356456409478047036410920404373309285912924997672529275515064192566242865116021386155457310508094958076066460836565160158766663, 2734314898963728479033000142813246259568089815870673472287793041182166446660277754410015225328084515035689551402469914691940245194075232038843006330773963709864978333290609196651422643790161828701709625044405435997758911646361737976981113757530651460202152435735130527785501592575959228161259747235316966996201, 1739471523641202810327265297591577752505734842706360370411736439778091326147544302419672571631359072958736775753021245026170089432144181286585140626235576357003165565365063891892930826430042724988983744805552283272774328426496752194454345137886991083709095834420716211261094791420543983657274033006263000308001, 1633898663983021315880232468128344375973343513831947719034245458394560620764964781139703730328146867688272597377577334096990495217511672495842757422665634041029897836855918503387750125829916880997756237547050115217989501050321312969857782569772685504342333296062699773772524035928647801109780999606286385993828, 2112537678434541983455155438675819752939902315253995877210799994924402130339220301952636880746115003202906732626240880709905450899140386894469798680364428340096308752822463895676369272310594240218523872726432713727923523795670705620796663457058026486698132677105423723912284782467583666496889668277422897855894, 1905547764297991895655464005243291135503915929946223070930193716719353276176299511789743603839518852084522626369746403322782494839655535256374875931989375893727796783477880417388275601342018110420306850519458122983579401421887487157678128437062457898630225923910616082141417945487097104341470017921585005839195, 1630980632175864325821097316033633878432776326284540663613296369228947524580758521174085831270740676902007597921338922338753292569093972749572873894743004276366255450934321127243059265543238264842113465756525410587585432397969103939839156270427669725105700322171323451214990724796618974173901579204785639853134, 1292635594284199143868112145043677901879112026663868813926717849446834212062816627479738463908435329107525807167884054744958110007480513132862178759227531512910666918543220836367082924683127302830131548269436108818466390089950442871095849761612140412791941509938044840002050404927809576689887056237959398977136, 310324905489909024824084121400933825021991800897234790712636396737226585989370791111023225013146436434736093215029815413824844103817159675123939343521545095286530759083380706263972198492435276155154974121163635845407636178909244994128230620536729995377720968956797108798428106425780443422242201889180750288981, 2039664189307611343640813803465995308862030571862749481773985218255689925420739493902877140224067949564556711359387139822248613429228142470315108047060724427423331554137247058128807345703801243735370277897914071996533233891938080869481144515547032970678014987378117344692285321118798540031539132443422486844461]
'''

简单来说就是爆破

先通过爆破分解n得到p,q。参考：Crypto趣题-剪枝 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

然后求a,b,u

因为加密是两个字符两个字符进行加密，所以有了u以后还是爆破得到flag

exp:

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
from Crypto.Util.number import *
import sys
from tqdm import *
sys.setrecursionlimit(100000)

def find(ph,qh,pl,ql):
    #check1
    padding0 = (dec_len-len(ph)-len(pl))*"0"
    padding9 = (dec_len-len(ph)-len(pl))*"9"
    if(int(qh+padding0+ql)*int(ph+padding0+pl) > n or int(qh+padding9+ql)*int(ph+padding9+pl) < n):
        return

    #check2
    mask = 10**len(pl)
    if(int(ql)*int(pl) % mask != n % mask):
        return
    
    #return(因为p、q长度为奇数，才这样，否则可以直接判断)
    if(len(ph+pl) == dec_len-1):
        for i in range(10):
            if(n % int(ph+str(i)+pl) == 0):
                p = int(ph+str(i)+pl)
                q = n // p
                print("p =",p)
                print("q =",q)
                exit()

    #search  
    for i in range(10):
        for j in range(10):
            find(ph + str(i), qh + str(j), str(j) + pl, str(i) + ql)

n = 3316800027546899796299249900490338525446722616927865256312015775762946188822765432534092050609396978713268788263981158799865606788375214514715320762212090700556505831986082588196853742449073887978094469425136388568791343123156410854535956201512370508501035099259640256718574195902438477533011590110397102848237
dec_len = 155

#find plow
for b in trange(10000):
    try:
        qlow = str(b).zfill(4)
        for i in range(10000):
            if(i*b % (10**4) == n % (10**4)):
                plow = str(i).zfill(4)

        qhigh = plow[::-1].zfill(4)

        #find phigh
        for i in range(4023):
            if b - i < 0:
                phigh = str(b - i + 10000)[::-1].zfill(4)
            if b - i > 0:
                phigh = str(b - i)[::-1].zfill(4)
            if b - i == 0:
                phigh = "0000"
                
            if(int(phigh + "0" * (dec_len-4)) * int(qhigh + "0" * (dec_len-4)) < n and int(phigh + "9" * (dec_len-4)) * int(qhigh + "9" * (dec_len-4)) > n):
                break
        
        find(phigh,qhigh,plow,qlow)
    except:
        pass

得到p

然后对u，通过第一个明文HE来验证u是否正确

exp:

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

n = 3316800027546899796299249900490338525446722616927865256312015775762946188822765432534092050609396978713268788263981158799865606788375214514715320762212090700556505831986082588196853742449073887978094469425136388568791343123156410854535956201512370508501035099259640256718574195902438477533011590110397102848237
c = [1055164913936861759601070681328133050501717812617683016760570306135820467684982411801348559225269987267344307291062260464313087313624260892305321033950481761766023104810722884530078669496273907717111088374157435933600032536778307024663155969024389539729313080850409619343987657232845340152570573522505621491603, 1931851107627113585898872797097407306775031283164577426145463830123237346520365715246429128224516824122830942699000943541489810766548629439116718005359410307932157835115818123572788574134272559866149510231173682996794795999813187683826003192711531187198464750488603425072083209561408438176122711585965417614521, 1551562722871551197414863544414517343879371834887856099644139717728598793747909014883607220057480535681811569818345280038106100034854300913500569380554031238944182867302031941796646079530311570715793289486496649040783388744493532753060611388234228588390324510451593705548122570734602832796634689681202286741231, 1023651876808318489905393236446524875536885683951145279330352918602853853447694302817954906550298552070780962780070361906218334252821218710182511457918223412762333039692689232650733728755517977280988908985889489001184280272980160457616272709308635982633848318896773374734511656916563942512330005914504195635337, 1396728575337462242947982357590285697182930985707363439305151790398230329601135817800702179968308661208157769938994960699547956746505619567144059124531141441467752697367504171971237392789440539834528097734120365895796879328931933526487179744144262805264212389440273880262757867643667487471108998309565898550140, 1453463533504342407605898896519240080022740769794850225555335805482946107024146169859390000606299331075843994897074067237384575978609903446750030301027143895789020930399227882365796877224045827151164458601051146128595023893592012624245622790310841426316026640692999628802961860272538252503655414255518715501760, 1734188098997045370459645852270876699525364972973439165430983746851028049030910755833101537881287022509713394813625855156597027177172650956556060878254135655554674984881391846365166915103188598322747593655410268343252535017545199684952748721388752410634453219588167967135997210093573628009136839331824663153793, 1818406699779534791674336722314603769405956761591677237541492728774856474202640994826261621058081466035202157430270600277311013762985807007932699131075589061444374253409259047428068590023426361125116787756419263498989853608265018899170600671857062729998584244286042946872554751935726176233509343237366515496055, 2110224578372551604599780781500885585255551193387191859255137522510922283309200273861267242416082384430111092429514796837475408585393892870687357616822691388215024614592556325867420126356456409478047036410920404373309285912924997672529275515064192566242865116021386155457310508094958076066460836565160158766663, 2734314898963728479033000142813246259568089815870673472287793041182166446660277754410015225328084515035689551402469914691940245194075232038843006330773963709864978333290609196651422643790161828701709625044405435997758911646361737976981113757530651460202152435735130527785501592575959228161259747235316966996201, 1739471523641202810327265297591577752505734842706360370411736439778091326147544302419672571631359072958736775753021245026170089432144181286585140626235576357003165565365063891892930826430042724988983744805552283272774328426496752194454345137886991083709095834420716211261094791420543983657274033006263000308001, 1633898663983021315880232468128344375973343513831947719034245458394560620764964781139703730328146867688272597377577334096990495217511672495842757422665634041029897836855918503387750125829916880997756237547050115217989501050321312969857782569772685504342333296062699773772524035928647801109780999606286385993828, 2112537678434541983455155438675819752939902315253995877210799994924402130339220301952636880746115003202906732626240880709905450899140386894469798680364428340096308752822463895676369272310594240218523872726432713727923523795670705620796663457058026486698132677105423723912284782467583666496889668277422897855894, 1905547764297991895655464005243291135503915929946223070930193716719353276176299511789743603839518852084522626369746403322782494839655535256374875931989375893727796783477880417388275601342018110420306850519458122983579401421887487157678128437062457898630225923910616082141417945487097104341470017921585005839195, 1630980632175864325821097316033633878432776326284540663613296369228947524580758521174085831270740676902007597921338922338753292569093972749572873894743004276366255450934321127243059265543238264842113465756525410587585432397969103939839156270427669725105700322171323451214990724796618974173901579204785639853134, 1292635594284199143868112145043677901879112026663868813926717849446834212062816627479738463908435329107525807167884054744958110007480513132862178759227531512910666918543220836367082924683127302830131548269436108818466390089950442871095849761612140412791941509938044840002050404927809576689887056237959398977136, 310324905489909024824084121400933825021991800897234790712636396737226585989370791111023225013146436434736093215029815413824844103817159675123939343521545095286530759083380706263972198492435276155154974121163635845407636178909244994128230620536729995377720968956797108798428106425780443422242201889180750288981, 2039664189307611343640813803465995308862030571862749481773985218255689925420739493902877140224067949564556711359387139822248613429228142470315108047060724427423331554137247058128807345703801243735370277897914071996533233891938080869481144515547032970678014987378117344692285321118798540031539132443422486844461]
p = 46060946081700475998019330950462361323376131758358942279882592756596585429914462101036196106577809589925330011092448105798640311237611630449649590724980027
q = n // p
a = nextprime(p&(10**6) + 2023)
b = nextprime(q%(10**6) + 2023)
g = nextprime(str(a)+str(b))

# U = []
# for i in range(2000):
#     seed = ((p - i) - 3) // 4
#     if seed.bit_length() == 512 and isprime(seed):
#         u = seed
#         U.append(u)

u = 11515236520425118999504832737615590330844032939589735569970648189149146357478615525259049026644452397481332502773112026449660077809402907612412397681244723

flag = b""
for i in trange(18):
    for j in range(32,128):
        for k in range(32,128):
            m = (chr(j) + chr(k)).encode()
            mi = bytes_to_long(m)
            for index in range(len(c)):
                if c[index] == pow(b, mi, n)*pow(u, g, n) % n:
                    flag += m
                    u = (a * u + c[index]) % n
                    continue
    print(flag)
print(flag)
# HECTF{jasdjeifhiew2983rji3hr4hi32df}

HE

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


def bin_expansion(c, p):
    row = c.nrows()
    col = c.ncols()
    log_p = row // col
    Ec = Matrix(ZZ, row, row)
    for i in range(row):
        for j in range(col):
            bits = bin(c[i, j] % p)[2:].rjust(log_p, '0')[::-1]
            for index in range(log_p):
                Ec[i, j * log_p + index] = int(bits[index])
    return Ec


def encryp(A,e,s,G,message,p):
    message = bin(message)[2:]
    Cipher = []
    for i in message:
        ci = block_matrix([A, A*s+e],ncols=2,subdivide=False)+ int(i) * G
        ci = bin_expansion(ci, p)
        Cipher.append(ci)
    return ' '.join([str(i.list()) for i in Cipher])


column = 7
prime = 4097
t = round(log(prime, 2))
m = t*column
G = Matrix(ZZ, t*column, column)
for i in range(t):
    for j in range(column):
        G[j*t+i, j] = 2 ** i
A = random_matrix(ZZ, m, column-1, x=0, y=prime)
e = random_matrix(ZZ, m, 1, x=0, y=prime//64)
s = random_matrix(ZZ, column-1, 1, x=prime//4, y=4*prime//3)
decrypt_key = Matrix(s.list() + [-1]).transpose()
encrypt_key = s

message = bytes_to_long(flag)
cipher = encryp(A,e,s,G,message,prime)
with open('cipher.txt', 'w') as f:
    f.write(cipher)

理解一下encryp，发现block_matrix([A, A*s+e],ncols=2,subdivide=False)是固定的

而且i 的取值只有0和1

所以，ci = block_matrix([A, A*s+e],ncols=2,subdivide=False) + int(i) * G只有两种可能

稍微猜测一下就行了

exp:

1
2
3
4
5
6
7
8
9
data = open("cipher.txt",'r').read().split(' ') # 这里我把数据中的逗号间的空格删掉了
m = ""
for line in data:
    if line == data[0]:
        m += "1"
    if line == data[1]:
        m += "0"
print(bytes.fromhex(hex(int(m,2))[2:]))   
# HECTF{Fu1ly_Hom0morp4ic_En3ryption}

写在最后

星盟安全团队纳新！

欢迎师傅们加群（346014666）学习、讨论！

-------------已经到底啦！-------------