Contents

Writeup for Crypto problems in HGAME 2021

Week 1

まひと

古典密码套娃

对称之美

密文是由很短的key(16个字符)循环异或一段很长的明文(FLAG)得到的,这样就会存在多个明文字符被同一个key的字符异或的情况,即key[0]异或了FLAG[0], FLAG[16], FLAG[32]……

又因为明文和key都是可打印字符,所以可以逐个枚举key的字符,然后和对应位置的密文异或,通过判断异或的结果是否可打印,来缩小可能的key的范围。

实现了一下发现,16个字符的key,有12个字符都能通过这个方法唯一确定,其他4个也能将范围缩小,再枚举一下就可以得到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
import string
import itertools
from Crypto.Util.number import  *
cipher=b'R4\x167\x17\\\x05?2aZ$p8\x0b\x11x\x0e\x1cz\rQ\x14#k5[/p<\x15\x005\x02\x01.\t\x19\x1e+kKRj 8\x10\x0b,\x0e\x01=ZV\x03m/3R=97\x1eE:\x06\x03;\x14Z\x14m. P"p6\r\r=\x15OP\x15L\x05ck\x15[##y\x1a\n-\x0b\x0bz\x18\\Q9#$\x13%23\x1c\x06,\x14O.\x12\\\x1c>.-E/#uYo:\x12\x1bz\x13MQ.*/\x13+<*\x16E*\x02\x03;\x0e\\Q9$aP%<6\x0b\x16x\x06\x01>Z3\x1e9#$Aj36\x14\x157\x14\x06.\x13V\x1f,\'aG/31\x17\x0c)\x12\n)T3(">a^+)y\x17\n,G\x1d?\x1bU\x187.aZ>|y\x1b\x10,G\x165\x0fKQ/9 Z$pS\x10\x16x\x05\x1a)\x03\x19\x06"9*Z$7y\x1b\x000\x0e\x01>ZM\x19(k2P/><\nE,\x08O)\x1f\\\x1amA.F>p*\x00\x085\x02\x1b(\x03\x19\x06%./\x133?,Y\t7\x08\x04z\x1bMQ,k1R#>-\x10\x0b?IOP.Q\x14?.aR85y\n\x00.\x02\x1d;\x16\x19\x03(*2\\$#y\x1f\n*G\x1b2\x13J_m\x1f)VjZ?\x10\x17+\x13O3\t\x19\x05%*5\x13=5~\x0b\x00x\x0f\x0e(\x1e\x14\x06$9$Wj$6Y\t7\x08\x04z\x1cV\x03mA(Gdp\x16\x0c\x17x\x06\x019\x13\\\x1f9k ])5*\r\n*\x14O7\x1b@Q#$5\x13"1/\x1cE0\x06\x0bzpXQ#*,Vj66\x0bE1\x13Cz\x18L\x05m?)V3p2\x17\x00/G\x1b2\x1bMQ9#$Z8pS\x16\x126G\r5\x1eP\x14>k6V85y\x1b\x04+\x0e\x0c;\x16U\x08m88^\'5-\x0b\x0c;\x06\x03vZX\x02mA6V85y\r\r7\x14\nz\x15_Q=$5V$$0\x18\tx\x17\x1d?\x1eX\x05"92\x13%"y\t\x17=\x1eAzpm\x19(9$U%"<UE,\x0f\x06)ZZ\x10 .aZ$p1\x18\x0b<\x1eO-\x12\\\x05%.3\x13@31\x16\n+\x0e\x01=ZXQ *5Vfp:\x18\x11;\x0f\x064\x1d\x19\x15$%/V8p6\x0bER\x06\x195\x13]\x18#,aQ/97\x1eE7\tO.\x12\\Q ./Fj??Y\x04x\x14\x01;\x08U\x18#,m\x13@8,\x17\x02*\x1eO*\x1bZ\x1am$\'\x13=?5\x0f\x00+G\x00(Z[\x14,92\x12@\x048\x12\x00x\x06O6\x15V\x1am*5\x133?,\x0bE>\x06\x0c?ZP\x1fm?)Vj=0\x0b\x177\x15OP\x1bW\x15m",R-97\x1cE9G\x033\x14\\Q>?3R#71\rE<\x08\x184ZM\x19(kK^#4=\x15\x00vG65\x0f\x1e\x1d!k2V/p;\x16\x110G\x1c3\x1e\\\x02m$\'\x133?,\x0bER\x01\x0e9\x1f\x19\x10?.aC85-\r\x1cx\x14\x167\x17\\\x05?""R&~y-\r1\x14O3\t\x19{&%.D$p8\nE:\x0e\x03;\x0e\\\x03,\'a@3=4\x1c\x11*\x1eO;\x14]Q$?f@jZ.\x11\x00*\x02O8\x15M\x19m8(W/#y\x1c\x0c,\x0f\n(ZJ\x18).a\\,p-\x11\x0c+Ge>\x13O\x18)"/Tj<0\x17\x00x\x06\x1f*\x1fX\x03m&.A/p6\x0bE4\x02\x1c)ZM\x19(k2R\'5ws67G\x07?\x08\\Q$8aG"5y\x1f\t9\x00UzpQ\x16,&$H\x12`+&\x0cmJ\x0e\x05\x0fjB+\x1ep\x18~>=]\x03\r)\x01#%z@=\x03rA7Z'
TABLE = (string.ascii_letters + string.digits).encode()
printable = b'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \n'

key_list = []
for point in range(16):
    guess = []
    for i in TABLE:
        xor = []
        yes = True
        for j in range(point, len(cipher), 16):
            if long_to_bytes(i^cipher[j]) not in printable:
                yes = False
                break
        if yes:
            guess.append(chr(i))
    key_list.append(guess)

for i in key_list:
    print(i)

for k1 in key_list[1]:
    for k7 in key_list[7]:
        for k10 in key_list[10]:
            for k15 in key_list[15]:
                key = ['X',k1,'o','Z','z','9','q',k7,'K','A',k10,'J','P','Y','y',k15]
                FLAG = bytes([c^ord(k) for c, k in zip(cipher, itertools.cycle(key))])
                if b"flag" in FLAG and b"hgame{" in FLAG:
                    print(FLAG.decode())
                    print(key)


Transformer

可以直接用:https://quipqiup.com/

Week 2

signin

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

a = 142778177166565595452241439755785408785722023435034011865621426392771925402975805391785769311558418640904802907664012210659254889711431409721116078656788939531247711347623009495825137413190179519893307935921658151729942874015415394421836723375850535279723782263357275223549541086676659256262732959547508283051
p = 159478864991647892528478251899516293769724681093913724808035970000092119912231596886680360924994654272732098909098220954729883242929274674168685451217925695768198579747278177210892734464268302577816082807745687409804786684820201814705932743426180728214252063847136815340376864410934225037532093657793966613641
c = 144685907705580660896532903657227210071696408897270047749077961743182805206915282749485343489388619993004501642050635215455005459977479468684818814014546829841108612432004700696476068845222125232274842625159575445601601706277175186052951011316194237821798774357791638650989922632264504432017622879352255640248

print(long_to_bytes(c*inverse(a,p)%p))
# b'hgame{M0du1@r_m4th+1s^th3~ba5is-Of=cRypt0!!}'

gcd or more?

有限域开平方

WhitegiveRSA

N 可以直接分解,确实是“Whitegive”。

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

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 747831491353896780365654517748216624798517769637260742155527
p = 857504083339712752489993810777
q = N//p
m = pow(c,inverse(e,(p-1)*(q-1)),N)
print(long_to_bytes(m))
# b'hgame{w0w~yOU_kNoW+R5@!}'

The Password

 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 *

TABLE = b'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ '

y1, n1 = (15789597796041222200, 14750142427529922)
y2, n2 = (8279663441787235887,  2802568775308984)
y3, n3 = (9666438290109535850,  15697145971486341)
y4, n4 = (10529571502219113153, 9110411034859362)
y5, n5 = (8020289479524135048,  4092084344173014)
y6, n6 = (10914636017953100490, 2242282628961085)
y7, n7 = (4622436850708129231,  10750832281632461)

def right(val, x):
    return val[-x:]+val[:-x]


def left(val, x):
    return val[x:]+val[:x]

flag = b""
y = [y1, y2, y3, y4, y5, y6, y7]
n = [n1, n2, n3, n4, n5, n6, n7]
index = [i for i in range(64)]
index1 = [right(index, i) for i in [7, 4, 2, 6, 8, 5, 2]]
index2 = [left(index, i) for i in [3, 9, 5, 13]] + [right(index, 16), left(index, 7), left(index, 5)]


def try_tr(guess):
    def check():
        for i in range(64):
            if sum([x[i] == -1, x[t1[i]] == -1, x[t2[i]] == -1]) == 1:
                if x[i] == -1:
                    x[i] = x[t1[i]] ^ x[t2[i]] ^ Y[i]
                elif x[t1[i]] == -1:
                    x[t1[i]] = x[i] ^ x[t2[i]] ^ Y[i]
                elif x[t2[i]] == -1:
                    x[t2[i]] = x[i] ^ x[t1[i]] ^ Y[i]
                return True
        return False

    x = [0]*8*padding+guess+[-1 for _ in range(64-(8+padding*8))]
    t1, t2 = index1[K], index2[K]
    while True:
        if check() == False:
            if min(x) == 0:
                if Y == [x[i] ^ x[t1[i]] ^ x[t2[i]] for i in range(64)]:
                    global flag
                    flag += long_to_bytes(int("".join([str(k) for k in x]), 2))
                    print(flag)
            break

for K in range(7):
    Y = [int(i) for i in bin(y[K]^n[K])[2:]]
    Y = [0]*(64-len(Y))+Y
    for guess in TABLE:
        guess = [int(i) for i in ("0"*(8-len(bin(guess)[2:]))+bin(guess)[2:])]
        for padding in range(7):
            try_tr(guess)

# hgame{l1ne0r_a1gebr0&is@1mpor10n1^1n$crypto}

Week 3

LikiPrime

 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 *

def get_prime(bits):
    prime = 1
    for _ in range(bits):
        prime = prime << 1
    return prime - 1

n = 421455057268137623943855130581826670010695787424125483575398783564641774905804241292094489491404078010368108928231613739378723057196150707763465076771136743887645743792429480337282665191759113905477351452687604661932370910619546649016980309127128704196912889482436113968301664065184802718403275566441932610997838594420744542725625369089835898603884842465873796137333422231217780558151579081453050482442480815713888023371806097009026733010675549168891531151463031503487769392933638449687974608310761364013663291522776340420167405179984536987822494653321337710666264607937131444597274723705263700984857724662081511434489432816220704052315794796230167061558323844739991577641137696139034976971120620834491839241524445976160628900208801061487721646073517819705813251737814356857934453635408899953424969351058921296535525652898586206280209211087519688645250498739129308658938793887643661637996930074323463006606640585599948898238215245556143193851301551383887774188493552615734925951375671527105352667838542450376183473659889822337657230288458000424954333331834433907473691512894898086048720146460663598870040517907120196975276637127036440898039790209438552282020873298963230557096195193902471386173063723634310986768157543053601652714130206963511431257764438989910441943467289675619031395812709310167158659929161987322371800772519783732871894602265094632055380313123658370805468895787729810268846662992731442880220367708567278281843728984797991757598241852368778190227221175774287545383420379099242654130282377896190210795413408748016644535143361607704202467109948719631940792634390275040458367000189214605637090341180044461262953283617909526333216836128142485173545881624151994087766224484640246053456234479338867653975606192972308839814170537240390050106021010619105914041749046002023056938838926351260981952851515505853011166663176323135014528257604319991192189816385407590212177524311727412317597062063787864210480343719978961417331119404148767646681957170467643999483804166353759472618987061249
e = 65537
c = 222355810684209810898321418992484158176768114175246273711723211730133586877477229516199462306881664911292528713569328615623289117865819719309117771866695912605159016929621818154754878296929642199154853885099175378170545513337411533093671530219101268277912294188492419865380476927747088199895027963782611920228998477838877058031262695710394801170128352227738953386049885687292897659547503673828307134101228383193631699445635626545356464812072304799332575322143849554658269794456331303610906236928837723190314352165446827809024556818325365351178595165406330507674287782309759596500261492192251157885814858579302578187660248968045343823452508724775792709369582753684932961168005720395899604547343223526941777166095441641005179836245306697244189891878260255633614198297195724657500173125838892339840016334832318158647061021432094471701117877593589966300996882724441161412126441216070214524052003443384883138565684539229608081933177337227713056599835924939406574422835135220969062517048466032178744849711646323986685971577435698825641309667320871937968220321152664888406345498983770639624372368471434171050591221345913052684655953411190576784732606979316226134071064183447313250691475378363755238396177647947358566090184892881980385115755358299169823280303035744069828957505413937236186533551702897060421668892306152749792396283166243185372375461674249538992047898333345288078147345299409741220003358389494286155594689604751762077274649016347290505016608230018871286421974256649767650457447179368349603752028336823209006881694919502246110908210116237302698321805326930248644835294675934739976299293821626330312477272019828308408515198852582592509478514254697033848520164966274193099560130711937051676594226148379079969157844181575671170514039589442819259719916304321927896392420505632176368504042990302827757989676895391809912236128774274283656646762620564562131649030447860685096879791065453280943402105582163943859452786837531830252591373479208304659205040550129303033446111126050926275855093775866

for i in range(2, n.bit_length()):
    if n%get_prime(i)==0:
        p = get_prime(i)
        break
q = n//p
print(isPrime(p))
print(isPrime(q))
m = pow(c,inverse(e,(p-1)*(q-1)),n)
print(long_to_bytes(m))

EncryptedChats

 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
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
import os

M = {'iv': 'd3811beb5cd2a4e1e778207ab541082b', 'encrypted_flag': '059e9c216bcc14e5d6901bcf651bee361d9fe42f225bc0539935671926e6c092'}
S = {'iv': 'b4259ed79d050dabc7eab0c77590a6d0', 'encrypted_flag': 'af3fe410a6927cc227051f587a76132d668187e0de5ebf0608598a870a4bbc89'}

M_iv = bytes.fromhex(M['iv'])
S_iv = bytes.fromhex(S['iv'])
M_flag = bytes.fromhex(M['encrypted_flag'])
S_flag = bytes.fromhex(S['encrypted_flag'])


A = 6407001517522031755461029087358686699246016691953286745456203144289666065160284103094131027888246726980488732095429549592118968601737506427099198442788626223019135982124788211819831979642738635150279126917220901861977041911299607913392143290015904211117118451848822390856596017775995010697100627886929406512483565105588306151304249791558742229557096175320767054998573953728418896571838697779621641522372719890056962681223595931519174265357487072296679757688238385898442549594049002467756836225770565740860731932911280385359763772064721179733418453824127593878917184915316616399071722555609838785743384947882543058635
B = 5522084830673448802472379641008428434072040852768290130448235845195771339187395942646105104638930576247008845820145438300060808178610210847444428530002142556272450436372497461222761977462182452947513887074829637667167313239798703720635138224358712513217604569884276513251617003838008296082768599917178457307640326380587295666291524388123169244965414927588882003753247085026455845320527874258783530744522455308596065597902210653744845305271468086224187208396213207085588031362747352905905343508092625379341493584570041786625506585600322965052668481899375651376670219908567608009443985857358126335247278232020255467723
g = 12602983924735419868428783329859102652072837431735895060811258460532600319539509800915989811879506790207025505003183121812480524033163157114086741486989697
p = 30567260905179651419358486099834315837354102714690253338851161207042846254351374572818884286661092938876675032728700590336029243619773064402923830209873155153338320502164587381848849791304214084993139233581072431814555885408821184652544361671134564827265516331283076223247829980225591857643487356406284913560960657053777612115591241983729716542192518684003840806442329098770424504275465756739925434019460351138273272559738332984560095465809481270198689251655392941966835733947437503158486731906649716026200661065054914445245468517406404904444261196826370252359102324767986314473183183059212009545789665906197844518119

a = (A*inverse(g,p))%p
shared_secret = (a*B)%p



def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data

def decrypt_flag(shared_secret: int, iv: bytes, ciphertext: bytes):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)
    # Prepare data to send
    return plaintext

print(decrypt_flag(shared_secret, M_iv, M_flag))
print(decrypt_flag(shared_secret, S_iv, S_flag))
# hgame{AdD!tiVe-Gr0up~DH_K3y+eXch@nge^4nd=A3S}

HappyNewYear!!

由于需要随机的猜是哪3个人被群发了相同的明文,所以脚本需要多运行几次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from gmpy2 import iroot
from Crypto.Util.number import *
from functools import reduce
from random import choice
def crt(a, m):
    '''Return a solution to a Chinese Remainder Theorem problem.
    '''
    M = reduce(lambda x, y: x*y, m)
    Mi = [M//i for i in m]
    t = [inverse(Mi[i], m[i]) for i in range(len(m))]
    x = sum([a[i]*t[i]*Mi[i] for i in range(len(m))])
    return x % M


messages = list()
data = open("output","r").read().strip("\n").split("\n")
n_list, c_list = list(), list()
for i in data:
    if i == "": continue
    if i[0]=="n": n_list.append(int(i.strip("n = ")))
    if i[0]=="c": c_list.append(int(i.strip("c = ")))

assert len(n_list)==len(c_list)

def get_nums(cnt, length):
    allnums = list(range(length))
    nums = list()
    for i in range(cnt):
        nums.append(choice(allnums))
        allnums.remove(nums[-1])
    return nums
        
NUM = 3
while True:
    choices = get_nums(NUM, len(n_list))
    m3 = crt([c_list[i] for i in choices], [n_list[i] for i in choices])
    root = iroot(m3, 3)
    if root[1]:
        print(long_to_bytes(root[0]).decode())
        break
# hgame{!f+y0u-pl4y_rem@ind3r~YOu^9ot=i7}

Week 4

夺宝大冒险1

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


def solve_1(r):
    a, mod = [int(i) for i in r.recvline().strip().decode()[1:-1].split(", ")]
    states = [int(r.recvline().strip().decode()) for i in range(2)]
    b = (states[1] - states[0]*a) % mod
    r.sendline(str(b).encode())

def solve_2(r):
    mod = int(r.recvline().strip().decode())
    states = [int(r.recvline().strip().decode()) for i in range(3)]
    a = (states[2] - states[1]) * inverse(states[1] - states[0], mod) % mod
    b = (states[1] - states[0]*a) % mod
    r.sendline(str(a).encode())
    r.sendline(str(b).encode())

def solve_3(r):
    states = [123]+[int(r.recvline().strip().decode()) for i in range(7)]
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    mod = abs(reduce(GCD, zeroes))
    r.sendline(str(mod).encode())

def solve_problems(r):
    solve_1(r)
    solve_2(r)
    solve_3(r)
    return "win" in r.recvline().decode()

for i in range(100):
    r = remote("182.92.108.71", 30641)
    if solve_problems(r):
        print(r.recvline().decode())
        r.close()
        break
    r.close()

# hgame{Cracking^prng_Linear)Congruential&Generators}

夺宝大冒险2

 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 task_copy import LXFIQNN
from pwn import *
r = remote("182.92.108.71", 30607)

init = ""
for i in range(10):
    print(r.recvline().strip())
    r.sendafter(b"guess: ", str(16).encode()+b"\n")
    right_num = int(r.recvline().strip().decode().split(" ")[-1])
    right_num = bin(right_num)[2:]
    init += "0"*(4-len(right_num))+right_num
    print(right_num)

mask = "1011001010001010000100001000111011110101"
prng = LXFIQNN(int(init, 2), int(mask, 2), 40)
for i in range(90):
    print(r.recvline().strip())
    guess = prng.random(4)
    r.sendafter(b"guess: ", str(guess).encode()+b"\n")
    r.recvline().strip()
print(r.recvline().strip())
# hgame{lfsr_121a111y^use-in&crypto}