糖醋小鸡块的blog
0%

2023-HECTF-wp-crypto

发表于 分类于 Valine：

没有参加这个比赛，赛后从其他师傅那里要到了题目附件于是写个题解。

大帝攻占福岛

题目描述：

1
大帝攻占了福岛，并与他的士兵一起在海边痛饮海水，于是大帝发生了奇妙的变化，每十秒增长1厘米

题目：

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

大帝指的是凯撒，那么这题目的加密应该基于移位密码，放进cyberchef里看看 ：

image-20231120085226648

可以看到移动一位时，前十个字符变成了有意义的英文串。对应于题目提示”每十秒增长1厘米”，那就是每10个字符多移一位。

exp：

1
2
3
4
5
6
7
8
9
c = "zpvepoudbsgcdqwvjgocqg|rxrqo|feviefsyx}szwt|skqfl?NKIZLYZUVfU|jslhyfzmiom…"
flag = "HECTF{"

for j in range(8):
    temp = c[10*j:10*j+10]
    for i in range(10):
        print(chr(ord(temp[i]) - j-1),end = "")

#HECTF{STOP_Nuclear_sewage}



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))

output.txt：

1
2
3
4
c = 23001012057110779471190091625946693776382380529397302126337301229214301450335125076016991835054198112255974220434689958104931664098817350134656616154892781885504255726632558690544057380195511404078662094726952602350250840712610362029824982069179543810686494204685887486972937880502875441232004432323308734978847464589775857815430854038396134952486665687531579988133729365443247597395131516449487146786214227230853061720614077115599878358089377114269765796099004940883513036567103436154122335792598432012140232905658895014924069330265282364249236142072335363164451294973492092043110680377767954710822286121195290921259
n = 25797576442752368834409243494498462987370374608513814739930733437032797864549696772439769896270235017474841764016848627149724764584643408544417890463920153063835758878658712790547466715525246861709503145754424896044647787146006099053059124466248594151765065039034244830614724509092882854620642569723528913880146979990993657935598837645247839225413889995373643109990149255485373119338024345925311643249141660177285328457994476509430988280481564046398593906405870633323621548853838399385539924067139236445142933316057900841508972844270649504321178274091144241788883353514769368447833090379142367062327674855735832181241
c1 = 5702553209026762891130621254037294747819864952568824327221430749829654552175171307151888953348659971422228556686092434932000213695492351602755144510029319044193567051613888876933660356756790444392278614143455408803808095980542751023095024106689759843322130186219560734082292015929006937318400901378373771587448471762923415750064340829545587346927358411518874090282598069394946985795177419501659425500481799157093068337225389827654860680897913114945871197415129055139716514884716404289565297854681809258375973195355836553939670482515484347869258398517276876478311544109924573128946617113822561968330536525876279165313
c2 = 17562619948191690401152271053920025392401205523418067246455197241332062181407775133406742024747779181762812656501246379566147855594504112107873162350649668441267907193889705868572309785100582281795380779594946422800722070311908572538672508371123334385630310655242811756206073131919770939609347021343765434127086363844595938894714892990053114153402729297796655717510572619694559203260762574159375142757462082162882775921182437134358375300674547217425590072112733480640372328934982979603312597484512120618223179217692002851194538130349201457319160001114007059615596355221194709809437500052122684989302563103918409825040

首先由题目知道p、q高512位相等，因此p-q较小，可以用费马分解。分解后得到hint：

1
Hint{Seed_is_256087_+_396445_-_538018}

也就是说我们有了seed，就有了x和y，又由于对于明文m有如下等式：

两个多项式均有根(x-m)，所以相关明文攻击就好。

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

def fermat(num):
    x = iroot(num, 2)[0]
    if x * x < num:
        x += 1

    while (True):
        y2 = x * x - num
        y = iroot(y2, 2)[0]
        if y * y == y2:
            break
        x += 1

    result = [int(x + y), int(x - y)]
    return result[0]

c = 23001012057110779471190091625946693776382380529397302126337301229214301450335125076016991835054198112255974220434689958104931664098817350134656616154892781885504255726632558690544057380195511404078662094726952602350250840712610362029824982069179543810686494204685887486972937880502875441232004432323308734978847464589775857815430854038396134952486665687531579988133729365443247597395131516449487146786214227230853061720614077115599878358089377114269765796099004940883513036567103436154122335792598432012140232905658895014924069330265282364249236142072335363164451294973492092043110680377767954710822286121195290921259
n = 25797576442752368834409243494498462987370374608513814739930733437032797864549696772439769896270235017474841764016848627149724764584643408544417890463920153063835758878658712790547466715525246861709503145754424896044647787146006099053059124466248594151765065039034244830614724509092882854620642569723528913880146979990993657935598837645247839225413889995373643109990149255485373119338024345925311643249141660177285328457994476509430988280481564046398593906405870633323621548853838399385539924067139236445142933316057900841508972844270649504321178274091144241788883353514769368447833090379142367062327674855735832181241
c1 = 5702553209026762891130621254037294747819864952568824327221430749829654552175171307151888953348659971422228556686092434932000213695492351602755144510029319044193567051613888876933660356756790444392278614143455408803808095980542751023095024106689759843322130186219560734082292015929006937318400901378373771587448471762923415750064340829545587346927358411518874090282598069394946985795177419501659425500481799157093068337225389827654860680897913114945871197415129055139716514884716404289565297854681809258375973195355836553939670482515484347869258398517276876478311544109924573128946617113822561968330536525876279165313
c2 = 17562619948191690401152271053920025392401205523418067246455197241332062181407775133406742024747779181762812656501246379566147855594504112107873162350649668441267907193889705868572309785100582281795380779594946422800722070311908572538672508371123334385630310655242811756206073131919770939609347021343765434127086363844595938894714892990053114153402729297796655717510572619694559203260762574159375142757462082162882775921182437134358375300674547217425590072112733480640372328934982979603312597484512120618223179217692002851194538130349201457319160001114007059615596355221194709809437500052122684989302563103918409825040
e = 65537

#part1 fermat
p = fermat(n)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)

#part2 hint
hint = pow(c,d,n)
#print(long_to_bytes(hint))
#Hint{Seed_is_256087_+_396445_-_538018}

#part3 getflag
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)]

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

PR.<m> = PolynomialRing(Zmod(n))
f1 = (x[0]*m+x[1])^17-c1
f2 = (y[0]*m+y[1])^17-c2
flag = -gcd(f1, f2)[0]
print(long_to_bytes(int(flag)))

#HECTF{r3411y_easy_R4nd0m_And_r3l4ted_m3554ge_att4ck}



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]
'''

题目分为两部分，第一部分是十进制逆序剪枝，第二部分对flag每两字节进行加密并给出密文。

而第一部分应该是对一道原题进行的微调改编，但是实际上和没改区别不大，这是因为+2023这个操作无非是增大了一些偏移量。同时，我们依然是可以完全不用g这个信息就能分解出p、q的，详细思路可以看我另一篇文章的nextprime剪枝一题：

Crypto趣题-剪枝 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

而分解出p、q后，我们就能获得准确的a、b，并且也可以由p往前推出可能的512bit的素数u。然后由于加密是每两字节对flag进行加密，那么我们只需要爆破两字节的2^16种可能性，检查哪一个与密文相等即可。这一部分用gmpy2的powmod会显著加快速度。

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


def dec(p,q,c,n):
    phi = (p-1)*(q-1)
    d = inverse(65537,phi)
    print(long_to_bytes(pow(c,d,n)))

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)
                print(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
if(0):
    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]

            #find phigh
            for i in range(4000):
                if(b-i < 0):
                    phigh = str(10000+(b-i))[::-1].zfill(4)
                else:
                    phigh = str(b-i)[::-1].zfill(4)
                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 = 46060946081700475998019330950462361323376131758358942279882592756596585429914462101036196106577809589925330011092448105798640311237611630449649590724980027
q = 72008942709594694403611673211304689750184429011003352998590877560169163010126441992458569565729528897224985385713167332316326405903391089957400718064906231
a = nextprime(p&(10**6) + 2023)
b = nextprime(q%(10**6) + 2023)

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

possible_u = []
for i in range(2000):
    temp = ((p-i)-3) // 4
    if(isPrime(temp) and temp not in possible_u and nextprime(4*temp+3) == p and len(bin(temp)) == 514):
        possible_u.append(temp)

for i in possible_u:
    u = i
    flag = b""
    for j in trange(18):
        for k in range(2**16):
            mi = k
            ci = powmod(b, k, n)*powmod(u, g, n) % n
            if(ci == c[j]):
                flag += long_to_bytes(mi)
                u = (a * u + ci) % n
    print(flag)

#HECTF{jasdjeifhiew2983rji3hr4hi32df}



little_block

题目：

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'
'''

看到这个convert函数很自然就会想到MT19937，事实上确实也就是改了MT的几个参数而已，把对应参数调整为题目中的值，然后逆回去就能得到m。

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

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 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 reconvert(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 dec_block(block):
    block ^=b
    block = circular_shift_left(block, 21)
    block ^= a
    return block

def my_decblock(message):
    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 = block ^ IV
        IV = bytes_to_long(message[i * 4 : i * 4 +4])
        block = dec_block(block)
        block = reconvert(block)
        block = long_to_bytes(block, 4)
        new_message += block
    return new_message

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'
print(my_decblock(m))

#HECTF{spodjoqw321jp3ij09adfiosofrga}



我们仨

题目分为三部分，每一部分需要前一部分的值作为压缩包密码。

第一部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from 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:'

可以注意到key和iv的长度不同，并且key是由重复的两部分拼接而成，因此异或后高16字节其实就是key，得到key后再异或就可以得到iv，然后AES解密就好。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
#part1 AES
hint1 = 113271863767201424639329153097952947311122854394813183532903131317262533549675
c1 = b'_1\x16\xc2;\xb1\xddy\x14\xdd\x14\xe5{\x19\x04:'
key1 = hint1 >> (16*8)
key1 = (key1 << (16*8)) + key1
iv1 = hint1 ^ key1 ^ 1

key1 = long_to_bytes(key1)
iv1 = long_to_bytes(iv1)
aes1 = AES.new(key1, AES.MODE_CBC, iv1)
m1 = aes1.decrypt(c1)
print(m1)
#RSAKEYISFTCEH

第二部分：

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

没有其他信息的话，挂factordb肯定可以分解出来，直接解密。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#part2 RSA
e=65537
n=17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
c=7650350848303138131393086727727533413756296838218347123997040508192472569084746342253915001354023303648603939313635106855058934664365503492172
f = FactorDB(n)
f.connect()
fs = f.get_factor_list()

phi = 1
for i in fs:
    phi *= (i-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))
#keyisEa51stRsA

第三部分：

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

DES CBC PKCS7 key：hectf iv：0000

DES的key和iv都告诉了，直接解密就好，注意key和iv要以b”\x00”填充至长度8。

完整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
from Crypto.Cipher import AES,DES
from Crypto.Util.number import *
from factordb.factordb import FactorDB
from base64 import *

#part1 AES
hint1 = 113271863767201424639329153097952947311122854394813183532903131317262533549675
c1 = b'_1\x16\xc2;\xb1\xddy\x14\xdd\x14\xe5{\x19\x04:'
key1 = hint1 >> (16*8)
key1 = (key1 << (16*8)) + key1
iv1 = hint1 ^ key1 ^ 1

key1 = long_to_bytes(key1)
iv1 = long_to_bytes(iv1)
aes1 = AES.new(key1, AES.MODE_CBC, iv1)
m1 = aes1.decrypt(c1)
print(m1)
#RSAKEYISFTCEH

#part2 RSA
e=65537
n=17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
c=7650350848303138131393086727727533413756296838218347123997040508192472569084746342253915001354023303648603939313635106855058934664365503492172
f = FactorDB(n)
f.connect()
fs = f.get_factor_list()

phi = 1
for i in fs:
    phi *= (i-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))
#keyisEa51stRsA

#part3 DES
c3 = "gIHkeIlRQp1fLeSWEqZJdOTO4aRYRB2OGRcBycHQ1OAdi6UEULYbwIvYh+0alYScSEoN4TOejgTjdPsetrURRlLX6dcifjX6VvLxY7TnMk7c8/xy17mybq/yNQf0vFGh8byC88bUeHian9dA2Qh6rRBYS1I7iNxM62RtCFZ+1OKeaqGIDjf3/VuPlbnCePYIY5FVs6xNXjkGh0m57t2QW4CoGI5lz6OcAAwg4AHP0d8CfeldOF/TogPwOiPaRlDbtHXCh54Bs5ZivV+jDerr0RQvCGYBFHYLJnvyrFtyZC9BxAQ8gQnGlWNDjE1V6BByUvJjpI9DcUyRSNN21rUWouOiLwtKX0BgDQkGH9PhtzhmGYI+R3lZJ4x30l+Xqweu"
c3 = b64decode(c3)

key3 = b"hectf"+b"\x00"*3
iv3 = b"0000"+b"\x00"*4
des3 = DES.new(key3, DES.MODE_CBC, iv3)
m3 = des3.decrypt(c3)
print(m3.decode())

#HECTF{DES_RSA_AES_WOMENSA_ZHENQIANG}



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
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)

题目基于GSW的FHE系统实现，具体过程可以见：

初探全同态加密之三：构建GSW全同态加密系统 - 知乎 (zhihu.com)

总的来说，s是我们需要的解密密钥，如果有s我们就可以用如下方式解密：

image-20231120090555239

image-20231120090606879

但是题目并没有给出s，所以正常说来我们是解密不了的(看出题人的wp可以知道能构造CVP问题规约出密钥s)，所以题目肯定有别的漏洞。

然后就仔细看加密函数，会发现他对每个flag的比特位加密均用的是同一个噪声，那么题目就简单很多，既然噪声相同，那么对flag中的所有为0的比特位和所有为1的比特位，其加密密文均相同。我们用这个对cipher进行统计就可以还原flag串了。

然后我这里是对cipher.txt作了一些小处理才能像下面的exp一样做，具体是：

  • 文件名改为cipher.py，并放在exp同目录下
  • 把”]”全局替换为”],”，然后微调一下使c变成二维数组

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from cipher import c

t = c[0]

flag = ""
for i in c:
    if(i == t):
        flag += "1"
    else:
        flag += "0"
print(long_to_bytes(int(flag,2)))

#HECTF{Fu1ly_Hom0morp4ic_En3ryption}



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

可以看到，题目基于一条NIST P-256的标准曲线，生成了一组签名的密钥：

1
key = ECC.generate(curve='NIST P-256')

并且他直接将私钥写入了pem.txt，那么就可以直接从pem中导入私钥k，有了k后就可以解出M点从而获得e。并且曲线是固定的，所以n和p等曲线相关的参数我们都可以直接获得，所以最后解一个RSA就能得到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
from Crypto.Util.number import *
from Crypto.PublicKey import ECC
from sympy import *

if(0):
    key = open(r'E:\题\历届赛题\HECTF 2023\easyecc\pem.txt','r').read()
    ec = ECC.import_key(key)
    k = int(ec.d)
    print(k)

    p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
    a = -3
    b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
    n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    E = EllipticCurve(GF(p), [a, b])

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

M = (2372011614198472883933948212291055165634847441796295478646240666272503588335 , 107224829709217890598399116795814898856363625796608443578148128103651983835541)
e = nextprime(M[1]-M[0])
phi = (p-1)*(n-1)
d = inverse(e,phi)
print(long_to_bytes(int(pow(c,d,n*p))))

#HECTF{Which_one_do_you_prefer?ECC?RSA?}