NISACTF2022

2022-03-28

貌似是个新生赛，但是题出的挺好的，做的几道题只有几个解。

xor

题目：

import os
import base64
from Crypto.Util import number, strxor
#from flag import flag

flag='xxxxxxxxxxxxxxxxxx'


def gen_key():
    return [os.urandom(16) for _ in range(8)]

def rnd(b: bytes, k: bytes):
    l = b[:16]
    r = b[16:]
    _r = l
    _l = strxor.strxor(strxor.strxor(r, k), l)
    return _l + _r

def enc(b: bytes, ks):
    c = b
    for i in range(8):
        c = rnd(c, ks[i])
    return c

if __name__ == '__main__':
    a = os.urandom(32)
    ks = gen_key()
    enc_a = enc(a, ks)
    enc_flag = enc(flag.encode(), ks)
    print(base64.b64encode(a).decode())
    print(base64.b64encode(enc_a).decode())
    print(base64.b64encode(enc_flag).decode())

#i03yXzXWe4QTiwJHlUZo6iqEdDkwJVviSOQ7CM3vJmM=
#4EnYOhbivTMP5r4VYLA8cwJBFTXIeeKAoNf/3ctgLLA=
#+qyVMEei1eN3YbV/z2kjcaCKngWc2pW2/e7HwpXKaj0=

加密算法为rn = Ln-1 ，Ln = kn ^ Ln ^ rn；并且会以不同的key连续加密八轮。第一想法是要一轮一轮推导，分别求出八轮密钥。但在推导的过程中发现最后的密钥可以看作一个整体：

r9 = L1 ^ r1 ^ K1

L9 = r1 ^ K2

这里K1，K2都是某几轮密钥的异或值。

那么整个八轮加密就可以看作是第一轮到第九轮结果的一次加密。恢复出K1和K2再对密文求解即可。

import base64
from Crypto.Util import strxor

a = "i03yXzXWe4QTiwJHlUZo6iqEdDkwJVviSOQ7CM3vJmM="
enc_a = '4EnYOhbivTMP5r4VYLA8cwJBFTXIeeKAoNf/3ctgLLA='
a_ = base64.b64decode(a)
enc_a_ = base64.b64decode(enc_a)
c = base64.b64decode('+qyVMEei1eN3YbV/z2kjcaCKngWc2pW2/e7HwpXKaj0=')

r9 = enc_a_[16:]
l9 = enc_a_[:16]
l1 = a_[:16]
r1 = a_[16:]

k1 =strxor.strxor(strxor.strxor(r9,l1),r1)
k2 = strxor.strxor(l9,r1)

r = strxor.strxor(k2,c[:16])
l =strxor.strxor(strxor.strxor(k1,c[16:]),r)
print(l+r)
#3c4e05db6512d51e0a93ae320c0bb69a

rrssaa2

题目：

from Crypto.Util.number import *
import random
import libnum
import gmpy2

def gen():
    p = 1801 * random.getrandbits(1012) + 1
    while not isPrime(p):
        p = 1801 * random.getrandbits(1012) + 1
    return p
p=gen()
q=gen()
e=1801
n=p*q
flag='NSSCTF{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}'
flag=flag+'yhe92871899hihiohh97709ujojl;lhdiwoqu903YE98Y299HDY8W9EYRW8!$$%!$!$FSR@#$@%FSEGDRYERYHRWER@$%^$^DGTW%$^&GRWR@$%@FASFSFQFSTGW#TWGARWQ$@%WGVDSGADQR@%TGVDSFASDATWEGHWE%@$GSDVSFQATY$^#^%@$!RAFSDGDRTW'

c = pow(m, e, n)
print('e=',e)
print('p=',p)
print('q=',q)
print('c=',c)

#e= 1801
#p= 49610229352589717245227429186510630298995334563536199979797365135356894947505595171590737127611751124743823204969291853243936699113293137172961540731655194113111189561603261168928406442577570919901769348742992633428864861175880441682752947688509869668929473479230018031647980097396415380123118521799468844841
#q= 21081926656979729045764441706195868361643779935106260715219328461497406780587336009385210898093496090213306812904410650499587043699660339207567766840318127296396962037273317168795761421233687815992929975284592353117739413561939283754964442896468496199833988666060155459156116345763999855126020972915904618043
#c= 601596145172542477058917394071994325109856881057412872218601643742101914635753765731910337249806643258952637146341530783703613931109366648847232809553067941206928974141651198815184695746636818122414926015513095322872645068410957200062317958684872682628646759817233433643987003499153702624673493727886566639667597997520471371146056861227114668317633291934130573158877960548655006208725827943739971068608175370661619328559766977175575896437656636083179668805135271793023165492681941002853661303072959879197775224449456951125268328000206540965011249895216257583247180682482954741912101069920760903900864428405997751199

直接给了p，q，e，肯定没有那么简单，发现e和phi不互素，准确来说e是p-1和q-1的因子。这就需要用到amm算法：https://www.anquanke.com/post/id/262634

exp：

#sage脚本
import time
from sage.all import *

# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(randint(1, q))
    while p ^ ((q - 1) // r) == 1:
        p = g(randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r ** (t - 1) * s)
    b = o ^ (r * alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r ^ (t - 1 - i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c ^ r) ^ j
        h = h * c ^ j
        c = c ^ r
    result = o ^ alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result


def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(randint(2, p - 1), (p - 1) // e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot


def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert (pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

e= 1801
p= 49610229352589717245227429186510630298995334563536199979797365135356894947505595171590737127611751124743823204969291853243936699113293137172961540731655194113111189561603261168928406442577570919901769348742992633428864861175880441682752947688509869668929473479230018031647980097396415380123118521799468844841
q= 21081926656979729045764441706195868361643779935106260715219328461497406780587336009385210898093496090213306812904410650499587043699660339207567766840318127296396962037273317168795761421233687815992929975284592353117739413561939283754964442896468496199833988666060155459156116345763999855126020972915904618043
c= 601596145172542477058917394071994325109856881057412872218601643742101914635753765731910337249806643258952637146341530783703613931109366648847232809553067941206928974141651198815184695746636818122414926015513095322872645068410957200062317958684872682628646759817233433643987003499153702624673493727886566639667597997520471371146056861227114668317633291934130573158877960548655006208725827943739971068608175370661619328559766977175575896437656636083179668805135271793023165492681941002853661303072959879197775224449456951125268328000206540965011249895216257583247180682482954741912101069920760903900864428405997751199

cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print(mps, mqs)


def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    if bytes.fromhex(h).startswith(b'NSSCTF'):
        print(bytes.fromhex(h))
        return True
    else:
        return False

start = time.time()
print('Start CRT...')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
            print("\n")
            print("\n")
    print(time.time() - start)

end = time.time()
print("Finished in {} seconds.".format(end - start))
#NSSCTF{2he_amm_13_r12lly_hard_f0r_me}

大概需要跑2min得到NSSCTF{2he_amm_13_r12lly_hard_f0r_me}

public

题目：

import os
from Crypto.Util.number import *
flag=b"NSSCTF{xxxxxxxxxxxxxxxxxxx}"
p = getPrime(2048)
q = getPrime(2048)
n = p*q
g = n+1
flag = flag + os.urandom(256)
m = bytes_to_long(flag)
assert m < n
c=(pow(g,p,n*n)*pow(m,n,n*n))%(n*n)
print(f"c={str(c)}")
print(f"n={str(n)}")
print(f"hint={str(pow(m,n,n*n))}")
# c=218076151021560547051903316719541222512040541728274127251955864973204319200312422995983092104505370830336341646283643290975865810979693431665790610118752578450560322701464606111124759353729454729357651736630354926734261137232304018105525402480409214739463624926019853406667257471858400554068936984966255122726345392299611192889869061539625603262461395069803838256649227551122691722958477064737646079234633593322257264277828874899605785719884582898801922036376706945214557655573105936069927519342707813584133447394527727777145289236041783964596526172298751923527410923728437653793368452092818162677292173126395038239746952564824349029187021070624008127312777783389153721156471730690460245726539173442219919067086198412985379251064006364545842890512676104195964096685904104471607447579133813262242889948684214615216415152003486684332654021763372875688811108164167029372542655680239691864011325001804416649090546652965592245015233937378914902555020997254559783431091213187054225512285704706127222748135840936979571164239968858574619878355623067035562073147836429462588372618500946665592533980646179287203705864082701267348885216165672773119373427706470575290690902668785242467233967870570261108990892859880739698792351646244754952340844420919259404502699266393058426943569348443212550646905609608670176752388829848639990144513783071090027192962534454341704209113094332822171724354423757760205937173503650126923081671379294681026909824698111163520911268295889474804858820122835834292711776643387277793548733641809948674628119693459864760337483163877679917119388740268787073315582536101385769332216844206772200893152057186765390268976281904057200764887141067277637744939424349347335952574178492737111320884889894593413406720620482887249419382551684677812936351975305964980443771310389160311391859989139144435489943187361252326617436405569045786172471146825826484820533463066934499480104433398977611810330276369147938097117995654985458513989302241106332776904067311803420489090552556891879767682415265560743407340298578130798877648570926192953127574474259716781135801273211777116319348356510073635809816358623224620898024473581877733194648312939500788032519396047197931401057492369464362250728505049498537131676040902419082386902837490490020207391112191256297932073021141841637862479797419191517126847743253818063471644376196087415026020405982443713386674133996026381008967344619818015476575693412862275373303754013892689230528546297224836909468991043799205998787941893011
# n=508649864931677614732467390772427961758931524996950943172348989353779413500135745017318030372818346445171787306774776609051270954621980771071637593801560166625137373096310055034937710873339570248386417692379532713565448110999149898224125057983565314582568870217037082321220190178702247284057805478222196862321877126877541221804916630403210745798454726695767965708773814502024042373335280648703042654755304969849832318086242798067639199224298659205981289856966590499810461072473369452077687615913217546268362501813809748922922532657782215807173319693469430751556310985767810712372068465527832726893651833030643914873945580271625080157996808574695857605733101549978621472016493582602814890278818563043847095493265778824174731054566468708287724290549925230267719117266452407869862605078436659020887227224470196270187491398217001451889275579626459491632506953638949085966203707446055610214983015428316166700670710716910016807567113694397559364621848368518820842900845963635710936101678917277407976769668789284143702572735353391307624460327339616496606065042109014043456540221432729574605562610831787594345569772727113605355252600129915926507232161710531913156415953128254338208741867773085355435238760994755555830964013004019492562245961
# hint=218453179086923289943807203202770838925178689627774745147232020515098516891161432630028304346664762962142685215503546042472463188085210756898964960254583869432945520650866749585786670220495127010275938757711518963512690357966318771229029024139860779906436335668507703089169058834533472932888386221671186182247869434699020350251916212956639268455849140594527951127570312231046210122761381292092058171708887595484453711631828228850043342993869671675498781490707220852504338423236844200845629493885003815571053367960570828719514793961666314203716137708394529735950110878173175859966298104855781891314256393660478947857997049309347664916363312769426872393903240797057291513182057786294193463281179876929436423970304992964378978343703058273610599094670858299390115880959442514513002687898361714995376183382702580310860520166550246905769724461107221385567718477106980293610194354260662299313387637029454859051754049141731708862005007657254777005078937290648653252057172789665484106225904252249322285164277069353595858401391763857781471982430400812430485462777863701578165740021651239264400111602346875691919587562776319002092593590043298682899772829734368041057265219520645505796166918571599787733464916168997021422429642875880015201743138557239246816614645961943942384226721696842364578221142494114967457346538723563534281835490913459152865031135512888020156712332950698315471031328945767161582387501768383019764191345069522790270253976284543970378444427727423121536104008553289510510497088596599741651012409020454471902200942494893254608355219933431097693790764370965829619433976045850073467615077879096698409574487772631069225578624386542659818683559823001358916184145187794138636007200677181455572920942709512649217555102476437241677652845050079961562071604521307752725300453167225947534296744839161286409625003203181858982730609149419917332043428767843293277924022007390853988328511663307394805322715579362345649842431371200748639996476587970393904239732072852670279076966635546790856059886353247283187091483814130965265452117641315707359747672993447721009270939662160468115475733881984431822454194850017395548046798675473636140217840418467588166347095543815767317284635513061287105795015042775738353765062476084211922890124244419037796630154403434882572164730631883001098922170198642065216541425903144234820480236095640278292837060194123091442480170728800340689332104613912950234195039809087610879082689821270573215009809335626725761798981628604037461376378712686098

因为给了hint，所以c乘hint模n方的逆求出：

$g^p（modn^2)$

关键就在这里，g = n+1，那么g的p次方二项展开很多项mod n 都为0了，只剩下p*n+1。那么我们可以求出p，利用p分解n；这里用hint解m的时候发现运算是在modn^2下，但是题目说明了m<n，这样的话解m在modn下计算即可（和n方同余一定和n同余，并且m<n，那么在modn条件下与modn^2等价）。

$即当m<n时c\equiv m^e (mod)n^2与c\equiv m^e (mod)n的解m相同$

exp：

from gmpy2 import *
from Crypto.Util.number import *

hint = 218453179086923289943807203202770838925178689627774745147232020515098516891161432630028304346664762962142685215503546042472463188085210756898964960254583869432945520650866749585786670220495127010275938757711518963512690357966318771229029024139860779906436335668507703089169058834533472932888386221671186182247869434699020350251916212956639268455849140594527951127570312231046210122761381292092058171708887595484453711631828228850043342993869671675498781490707220852504338423236844200845629493885003815571053367960570828719514793961666314203716137708394529735950110878173175859966298104855781891314256393660478947857997049309347664916363312769426872393903240797057291513182057786294193463281179876929436423970304992964378978343703058273610599094670858299390115880959442514513002687898361714995376183382702580310860520166550246905769724461107221385567718477106980293610194354260662299313387637029454859051754049141731708862005007657254777005078937290648653252057172789665484106225904252249322285164277069353595858401391763857781471982430400812430485462777863701578165740021651239264400111602346875691919587562776319002092593590043298682899772829734368041057265219520645505796166918571599787733464916168997021422429642875880015201743138557239246816614645961943942384226721696842364578221142494114967457346538723563534281835490913459152865031135512888020156712332950698315471031328945767161582387501768383019764191345069522790270253976284543970378444427727423121536104008553289510510497088596599741651012409020454471902200942494893254608355219933431097693790764370965829619433976045850073467615077879096698409574487772631069225578624386542659818683559823001358916184145187794138636007200677181455572920942709512649217555102476437241677652845050079961562071604521307752725300453167225947534296744839161286409625003203181858982730609149419917332043428767843293277924022007390853988328511663307394805322715579362345649842431371200748639996476587970393904239732072852670279076966635546790856059886353247283187091483814130965265452117641315707359747672993447721009270939662160468115475733881984431822454194850017395548046798675473636140217840418467588166347095543815767317284635513061287105795015042775738353765062476084211922890124244419037796630154403434882572164730631883001098922170198642065216541425903144234820480236095640278292837060194123091442480170728800340689332104613912950234195039809087610879082689821270573215009809335626725761798981628604037461376378712686098
n = 508649864931677614732467390772427961758931524996950943172348989353779413500135745017318030372818346445171787306774776609051270954621980771071637593801560166625137373096310055034937710873339570248386417692379532713565448110999149898224125057983565314582568870217037082321220190178702247284057805478222196862321877126877541221804916630403210745798454726695767965708773814502024042373335280648703042654755304969849832318086242798067639199224298659205981289856966590499810461072473369452077687615913217546268362501813809748922922532657782215807173319693469430751556310985767810712372068465527832726893651833030643914873945580271625080157996808574695857605733101549978621472016493582602814890278818563043847095493265778824174731054566468708287724290549925230267719117266452407869862605078436659020887227224470196270187491398217001451889275579626459491632506953638949085966203707446055610214983015428316166700670710716910016807567113694397559364621848368518820842900845963635710936101678917277407976769668789284143702572735353391307624460327339616496606065042109014043456540221432729574605562610831787594345569772727113605355252600129915926507232161710531913156415953128254338208741867773085355435238760994755555830964013004019492562245961
c = 218076151021560547051903316719541222512040541728274127251955864973204319200312422995983092104505370830336341646283643290975865810979693431665790610118752578450560322701464606111124759353729454729357651736630354926734261137232304018105525402480409214739463624926019853406667257471858400554068936984966255122726345392299611192889869061539625603262461395069803838256649227551122691722958477064737646079234633593322257264277828874899605785719884582898801922036376706945214557655573105936069927519342707813584133447394527727777145289236041783964596526172298751923527410923728437653793368452092818162677292173126395038239746952564824349029187021070624008127312777783389153721156471730690460245726539173442219919067086198412985379251064006364545842890512676104195964096685904104471607447579133813262242889948684214615216415152003486684332654021763372875688811108164167029372542655680239691864011325001804416649090546652965592245015233937378914902555020997254559783431091213187054225512285704706127222748135840936979571164239968858574619878355623067035562073147836429462588372618500946665592533980646179287203705864082701267348885216165672773119373427706470575290690902668785242467233967870570261108990892859880739698792351646244754952340844420919259404502699266393058426943569348443212550646905609608670176752388829848639990144513783071090027192962534454341704209113094332822171724354423757760205937173503650126923081671379294681026909824698111163520911268295889474804858820122835834292711776643387277793548733641809948674628119693459864760337483163877679917119388740268787073315582536101385769332216844206772200893152057186765390268976281904057200764887141067277637744939424349347335952574178492737111320884889894593413406720620482887249419382551684677812936351975305964980443771310389160311391859989139144435489943187361252326617436405569045786172471146825826484820533463066934499480104433398977611810330276369147938097117995654985458513989302241106332776904067311803420489090552556891879767682415265560743407340298578130798877648570926192953127574474259716781135801273211777116319348356510073635809816358623224620898024473581877733194648312939500788032519396047197931401057492369464362250728505049498537131676040902419082386902837490490020207391112191256297932073021141841637862479797419191517126847743253818063471644376196087415026020405982443713386674133996026381008967344619818015476575693412862275373303754013892689230528546297224836909468991043799205998787941893011
c1 = invert(hint,n**2) * c % n**2
print(c1)
print(hint<c)
p = (c1-1)//n
q = n//p
phi = (p-1)*(q-1)
d = invert(n,phi)
print(long_to_bytes(pow(hint,d,n)))
#NSSCTF{937dc8be-8348-4925-ad7e-06b91aed8171}