随缘刷题(二)

​ 一些四月做的杂题，尽量记录一下，保持良好习惯。

贵阳大数据及网络安全精英对抗赛-解题赛

math

首先需要通过POW：

from pwn import *
from hashlib import *
import string
import itertools


table = string.ascii_uppercase + string.ascii_lowercase + string.digits

io = remote('39.107.81.36',65241)
def proof():
    s1 = io.recvline()
    print(s1)
    p1 = s1.find(b'X+')
    p2 = s1.find(b')')
    p3 = s1.find(b'== ')
    s = s1[p1+2:p2]
    h = s1[p3+3:-1]
    h = h.decode()
    print(h)
    print(s)
    for i in itertools.product(table, repeat=4):
        d = ''.join(i).encode()
        dd = d + s
        #print(dd)
        if sha256(dd).hexdigest() == h:
            print(d)
            io.sendline(d)
            #io.interactive()
            break

后面部分解法不唯一，可以用两个式子建立方程，sagemath直接求解求p和q，也可以通过推导式子的关系来做，这里记录方法二。

已知$p^9+q^9…(1)$和$p^3+q^3…(2)$，把（2）式进行三次方和（1）式做差即可得到$3p^3q^3(p^3+q^3)$，这里除以一个（2）式可以求出pq，再利用$p^3+q^3=(p+q)(p^2-pq+q^2)=(p+q)[(p+q)^2-3pq]$和sagemath求解p+q。最后把pq%(p+q)发送到server获得flag。

from gmpy2 import *

s9 = 2824822169624626054661488626925458420744715781080646942074253083493110409304139573698331220638806746185475842194119961243645804370254606328869920018072689414438851986763034645626556982418990163940800474549193470898195538208390077574728861492183878546810890489530709875694439708304188836872775133284206949916525601873082688977829638863138990316027434787047769932507784217745872371234159638863412009751336370516261263894787945468938670587885217215533551430379370918887017578135901512047635699889591590644728268209911213837545954673959103136577695532350503753325666353616999846273454813736702876968828262577312436890164868139215146941181825104314265142027185641195497429436701158821466597436322426101818844710031297488336024894303790150460476458932731090576824660354020881969224935848618388008509287249786048287099709905361669995934683044400119527112547308946141798312531702089592589519108535371095268166661526029944144811749355534331341058531140340843830280132820250819782775604064279338833095450886869781021370514423225666663969097910935332887127861068226704314810075641777615479058315604743490070494698514916318640565210625873112244649996112730726083223048152494260522865824835075057025248755461487069699219010214934196309822790800505679440651281428272245964425847552725070324370935048163205674057942566606069023173193117188785459966877961255640155226356782264373613291491124970651673222
s3 = 2170975452570130427181048521695873973135933481372313804498232310176782170227124595928130478815483294370924323759914604172695746976894120890757779825855362817255229290661676271054758017616180660951572648811631474401996380573736869074007533444837272191850638568203334900550339868176862783180156627459202829081595794230688694799962290853974633400675886602057846186352130394606371882689934371132063210289099864922945499792531454940004181032574377548535600071749073142
sub = (pow(s3,3) - s9)//(3*s3)
pq = iroot(sub,3)[0]
print(pq)
pq = 104382446543490642967811678517220436436716778415457395457593714868883339184762950121395070723630584112101307457040293771100904440354905920406281214367055888699798428085190446368682575243053002296287183024620331778956869409649373650981057783610236974465359326825472347978830890939849109024750348290567119465481
P.<x> = PolynomialRing(ZZ)
f = x * (x ^ 2 - 3 * pq) - s3
pplusq = f.roots()[0][0]
print(pq % pplusq)

childrsa

前一半给了P+Q的高位gift，可以把gift直接当作P+Q来用，解方程得到P的高位，然后再来一次P高位的copper恢复P，解出hint：

import gmpy2
from Crypto.Util.number import *

gift = 112012823249741273956420414320152024086394551241563686416444057368708038459572554871491781707278127933195689073127882065060125127295041489653572915729848455155059117821290550157606860744547
N = 19913283586978731272870374837854045562790864804312115658302463830117436116219931849180682454814957654994095500743161455669517742683196683945049694888375426558735311269294662060482717191409995553476857418604462748567614908456839975140435522714312533340013676955820372105156740228641356206825881138276471973278761948406726062399175269553184359236859175084438349221553915085882218661560890322526503741457647907788204833926214096369428913779871365689037671018942683561649187089844083798834324075157252488088496084629641115161544547506935703532950490109236586524242732310854674446718076810611730874295399180178401471353663
enc_hint = 13605762329549698957586626266580933128225639142810971158632386694900212152297364700673906983331081843360581227221052403163762155206266035280442283924005142717129467351643173282810669982201476798388553001056498736307588260706475327062302787323877507524036357644241120006072323797778327893834792299939570334886948188364597473931268889437417695532862093912649528155151390080600081199337965649892379699786628095487656690228838497716512853509768997296826487263776776447496125752546322173589223915740715451543895861668143819159937998988611022766833424669076863898157258297885102980961819003128529680884480390557024888414518
n = 98394377912970161077976095071716071520245470884522650898371541866651139965831581427336428521179335097560338145643418890363050369233502530295868251106114979969844387393758147627569985743852463470545138002189902685566590889175140517151122304528973863485700142820829052897139853465497289644064298161242772703289
c = 73440769815335471983607426365687905918721184275652299429416892828899873930224614597826204961136670712832234285387297735959592122505613951335959593105045789810808172640134939607018894726831927984520480432707238536268054572649912957275921796939059679116900910403261478040783178268712136617053467195749630152736
e = 65537
RF = RealField(2048)
# 设一个2048比特的未知数
X = polygen(RF)
f =X*((gift<<400)-X) - N
P = int(f.roots()[1][0])
P_high = (P<<430)>>430
PR.<x> = PolynomialRing(Zmod(N))
f1 = x + P_high
x0 =f1.small_roots(X=2^430, beta=0.4)[0]
P1 = P_high+x0
print(f"P = {P1}")
Q =N//int(P1)
print(f"Q = {Q}")
phi = (P1-1)*(Q-1)
d = gmpy2.invert(e,gmpy2.mpz(phi))
hint = pow(enc_hint,d,N)
print(f"hint = {hint}")

后一半是已知p低位攻击，但最右端5位未知，考虑爆破并构造copper：

for low in range(2 ^ 5):
    try:
        PR.<x> = PolynomialRing(Zmod(n))
        f = x * (2^350) + hint * 2 ^ 5 + low
        f = f.monic()
        k = 512 - 350
        root = int(f.small_roots(X=2^k, beta=0.4)[0])
        p = root * 2^350 + hint * 2 ^ 5 + low
        if gcd(n,p) > 1:
            print(p)
            break
    except:
        continue

求出p以后分解n解密即可。

还有一种解法是需要利用论文里的结论：

这里的条件很容易被满足，因此先求P的大致值再做一次高位copper攻击即可，注意卡了下界。

from Crypto.Util.number import *
import gmpy2

N = 19913283586978731272870374837854045562790864804312115658302463830117436116219931849180682454814957654994095500743161455669517742683196683945049694888375426558735311269294662060482717191409995553476857418604462748567614908456839975140435522714312533340013676955820372105156740228641356206825881138276471973278761948406726062399175269553184359236859175084438349221553915085882218661560890322526503741457647907788204833926214096369428913779871365689037671018942683561649187089844083798834324075157252488088496084629641115161544547506935703532950490109236586524242732310854674446718076810611730874295399180178401471353663
n = 98394377912970161077976095071716071520245470884522650898371541866651139965831581427336428521179335097560338145643418890363050369233502530295868251106114979969844387393758147627569985743852463470545138002189902685566590889175140517151122304528973863485700142820829052897139853465497289644064298161242772703289
gift = 112012823249741273956420414320152024086394551241563686416444057368708038459572554871491781707278127933195689073127882065060125127295041489653572915729848455155059117821290550157606860744547
enc_hint = 13605762329549698957586626266580933128225639142810971158632386694900212152297364700673906983331081843360581227221052403163762155206266035280442283924005142717129467351643173282810669982201476798388553001056498736307588260706475327062302787323877507524036357644241120006072323797778327893834792299939570334886948188364597473931268889437417695532862093912649528155151390080600081199337965649892379699786628095487656690228838497716512853509768997296826487263776776447496125752546322173589223915740715451543895861668143819159937998988611022766833424669076863898157258297885102980961819003128529680884480390557024888414518
c = 46814170527248885168246756812210153119486966489687247805498130392493821903069671992391504575922384362815525403472565575725937709774229597491391051813804042471442431633524349982475366135612679353929043843989912068628511038187760032595582149371542884316315767726222944205184200050316281081588507579737917836748
e = 65537

s=int(gift<<400)
p_=int((s+gmpy2.iroot(s^2-4*N,2)[0])//2)
PR.<x>=PolynomialRing(Zmod(N))
f2=p_+x
root=f2.small_roots(X=2^450,beta=0.45,epsilon=0.05)
P=int(p_+root[0])
Q = N//P
assert N == P * Q
phi1 = (P-1) * (Q-1)
d1 = inverse(e,phi1)
hint = pow(enc_hint,d1,N)
print(hint)

hint = 52025683076044044599992400773221280746229263847635117575567345877303750178218448109638198217351426116857
for low in range(2 ^ 5):
    try:
        PR.<x> = PolynomialRing(Zmod(n))
        f = x * (2^350) + hint * 2 ^ 5 + low
        f = f.monic()
        k = 512 - 350
        root = int(f.small_roots(X=2^k, beta=0.4)[0])
        p = root * 2^350 + hint * 2 ^ 5 + low
        if gcd(n,p) > 1:
            print(p)
            break
    except:
        continue
        
p = 12875389203118258668614951298149797909799840999471786801115807021855220020135243368328555419081024867855094746702504569598236375581106125211941848589901621
q = n//p
phi2 = (p-1)*(q-1)
d2 = inverse(e,phi2)
print(long_to_bytes(int(pow(c,d2,n))))

线性代数

已知S=L.U，那么$L^{-1} S^2 L (LU*L)^{-1}=U$，求出U以后通过另一个代换关系可求出R。利用U和R就可恢复A了，具体地：

$$A = X- R = S^{-1}Y-R = U^{-1}E - R$$

利用A和encrypt的逻辑倒回去即可恢复flag，exp：

p = 71
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'

def decode_(M):
    m = ['*' for _ in range(24)]
    for k in range(24):
        i, j = 5 * k // 11, 5 * k % 11
        m[k] = alphabet[M[i, j]]
    return ''.join(m)

f = open('out.txt','r')
E = []
for i in range(11):
    tmp = f.readline().strip()[1:-1].split(' ')
    lis = []
    for j in tmp:
        try:
            lis.append(int(j))
        except:
            continue
    E.append(lis)

LUL = []
f.readline()
for i in range(11):
    tmp = f.readline().strip()[1:-1].split(' ')
    lis = []
    for j in tmp:
        try:
            lis.append(int(j))
        except:
            continue
    LUL.append(lis)

LS2L = []
f.readline()
for i in range(11):
    tmp = f.readline().strip()[1:-1].split(' ')
    lis = []
    for j in tmp:
        try:
            lis.append(int(j))
        except:
            continue
    LS2L.append(lis)
    
RS8 = []
f.readline()
for i in range(11):
    tmp = f.readline().strip()[1:-1].split(' ')
    lis = []
    for j in tmp:
        try:
            lis.append(int(j))
        except:
            continue
    RS8.append(lis)

E = matrix(Zmod(p),E)
LUL = matrix(Zmod(p),LUL)
LS2L = matrix(Zmod(p),LS2L)
RS8 = matrix(Zmod(p),RS8)

U = LS2L * LUL.inverse()
print(U)
LULU = LUL * U
R_ = RS8 * (LULU ^ 4).inverse()
R  = R_.inverse()

A = U.inverse() * E - R
print('flag{%s}' % decode_(A))

eezzrrssaa

利用tmp = prng2.next() * q + prng1.next()除以q可以恢复prng2的序列，模q则可以得到prng1的序列，但由于get_prime函数存在if判断，序列的两个输出之间可能跳过很多个非素数。发现prng1给了a和b，通过序列1可以计算每两个数据之间间隔的个数，再利用序列2的关系建立方程，grobner basis求解恢复prng2的a和b，然后利用get_prime再跑几轮得到rsa的私钥解密。exp：

from sage.all import *

q = 863666614243448299685073534539782091614466038667659466359664255833879357401208752356758391473753149783695523347
ps = [488430779430824599064935338391249442829022539899115535143196485163487049206340136142789020350176476554441378462595965038290365842362034176672340569719593003574222248527447206361459719954322885881075726676950555671635007363, 707157149197462658139117084378634522562212403870035237598970809858394732217372944239689355077884840011520921058759306333833289658731807522052892377679354636501446734633867023331470805974187027036109531714774435994689042891, 476172773176400166870512700278283739900716339392176146031791100542596627419155254113738721222559386964568077259931246639803960023216418997484355347182274626554844693011339867671881591249587444088969603398209425951467440211, 479577456885290037281759580853233626951314430312455485422558946021203602708559915552877926123425413442096439066002524196474514162220000152373758925097140843218665566655451970747063255562540421337155353658793225970423042099]
n = 98507292107212647629392277192521724876575060525397166586602724341772322834661685719879043139101436908036967520130509456130010632959287915661915441539615555345261656834100254232656609022587219863738542204349757544278313022268849986380405350778976502504598388632375506019980481343421510001650112826277323670706717869878490374078543128198589764240329950804782453481144228576858436696625100959717702337809834581369797601972108713612318371100605389
c = 57773774305129316009141892175661507569534831447382854914588401185097291538023184369651537398951570363918970263297625149448254614479110835192103043721312687685309489008584881189077640538284919592229456061921760452134520765924458040140450750863491592935761079322474155890093610865852109521471075002695928101302724254321097314555582345987979625286958861654447780330651520542323214097640450289283886871665487690407096815701340627706657525543320274
pr1 = []
pr2 = []
a1 = 202320232023
b1 = 320232023202

for i in ps:
    pr1.append(i%q)
    pr2.append(i//q)

count = []
tmp = pr1[0]
test = []
for i in range(1000):
    tmp = (a1 * tmp + b1)%q
    test.append(tmp)

for i in pr1:
    if i in test:
        print(test.index(i))

F = []
s = pr2[0]
R.<a,b>=PolynomialRing(Zmod(q))
for i in range(78):
    s = a * s + b
F.append(s - pr2[1])
s1 = pr2[1]
for i in range(103-78):
    s1 = a * s1 + b
F.append(s1-pr2[2])

s2 = pr2[2]
for i in range(672-103):
    s2 = a * s2 + b

F.append(s2-pr2[3])
res=Ideal(F).groebner_basis()
print(res)

a = -721474313686950040760456718395855289332361081440581115357964297160374075412604063880198191814907640385556239775 % q
b = - 42522514490869169124681320640539356074221591805568832332992800925663834398026485545017374651679305179842368739 % q

from Crypto.Util.number import *
import random

class PRNG:
    def __init__(self, a, x, b ):
        self.a = a
        self.x = x
        self.b = b

    def next(self):
        ret = self.x
        self.x = (self.a * self.x + self.b) % q
        return ret


def get_prime(prng1,prng2,q):
    while 1:
        tmp = prng2.next() * q + prng1.next()
        if isPrime(tmp):
            return tmp

q = 863666614243448299685073534539782091614466038667659466359664255833879357401208752356758391473753149783695523347
ps = [488430779430824599064935338391249442829022539899115535143196485163487049206340136142789020350176476554441378462595965038290365842362034176672340569719593003574222248527447206361459719954322885881075726676950555671635007363, 707157149197462658139117084378634522562212403870035237598970809858394732217372944239689355077884840011520921058759306333833289658731807522052892377679354636501446734633867023331470805974187027036109531714774435994689042891, 476172773176400166870512700278283739900716339392176146031791100542596627419155254113738721222559386964568077259931246639803960023216418997484355347182274626554844693011339867671881591249587444088969603398209425951467440211, 479577456885290037281759580853233626951314430312455485422558946021203602708559915552877926123425413442096439066002524196474514162220000152373758925097140843218665566655451970747063255562540421337155353658793225970423042099]
n = 98507292107212647629392277192521724876575060525397166586602724341772322834661685719879043139101436908036967520130509456130010632959287915661915441539615555345261656834100254232656609022587219863738542204349757544278313022268849986380405350778976502504598388632375506019980481343421510001650112826277323670706717869878490374078543128198589764240329950804782453481144228576858436696625100959717702337809834581369797601972108713612318371100605389
c = 57773774305129316009141892175661507569534831447382854914588401185097291538023184369651537398951570363918970263297625149448254614479110835192103043721312687685309489008584881189077640538284919592229456061921760452134520765924458040140450750863491592935761079322474155890093610865852109521471075002695928101302724254321097314555582345987979625286958861654447780330651520542323214097640450289283886871665487690407096815701340627706657525543320274

print(len(ps))
pr1 = []
pr2 = []
a1 = 202320232023
b1 = 320232023202
a = -721474313686950040760456718395855289332361081440581115357964297160374075412604063880198191814907640385556239775 % q
b = - 42522514490869169124681320640539356074221591805568832332992800925663834398026485545017374651679305179842368739 % q

print(a)
print(b)

for i in ps:
    pr1.append(i%q)
    pr2.append(i//q)

prng1 = PRNG(202320232023,pr1[3],320232023202)
prng2 = PRNG(a, pr2[3], b)

p_ = [get_prime(prng1,prng2,q) for _ in range(4)]
pp = p_[-1]
qq = p_[-2]
assert pp * qq == n
e = 0x10001

phi = (pp-1)*(qq-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

某不知名小比赛

task6

from Crypto.Util.number import *
from hashlib import md5

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
e = 2023
a = pow(p+q,e,p*q)
b = pow(p+r,e,p*r)
o = pow(q+e,p,p*q)
s = pow(r+e,p,p*r)

flag = "flag{%s}"%md5(str(p+q+r).encode()).hexdigest()
flag_md5 = md5(str(flag).encode()).hexdigest()

print("flag_md5 = ",flag_md5)
print('a =',a)
print('b =',b)
print('o =',o)
print('s =',s)

'''
flag_md5 =  a6e1f5c86223607ab196d5ed36cb1eb8
a = 33022028261473232777495374489369984051173051765914698583738518002899904080523156837934749116742046277602367384435566675571554308103705904368259935553616909439053270303487771097937681411464233154789299798806729983958502682142190437300710333776343215351258409122741296694039365121701417931039351706449620933965
b = 81094699539404597343145361125240498679809760332244536460451475832258379562399932681242912311485592104271252217309012830898060896041053659829385735202726553288600509493460180497835520339585127754273226762440611089795375598402111645618656148576588630597445547241467407938373779128315636192164727397109721371821
o = 84271446189918339833844652348525276763886039158109929437916837238145526361383913885452712470249189911870483017509012824863702488719752612973997881394827167428837538802085223497834025041680433523842549305188960285145390142799963207261252716937469861672320881012026095221908641651584348583973984309599037601834
s = 15123960887720641582473419411098607262340676763761583670149167561153634913307686118729176007021398862293975304379052309333724796000639317958549447559668843718134962233429595288688678289005300880495334503517799794958574524554067587882588738019194484329080120346211069604574355250202792739546620819511246051563
'''

根据已知算式推导有：

$(o-2023)^e\;mod\;p=q^e$,$a\;mod\;p=q^e$,$(s-2023)^e\;mod\;p=r^e$,$b\;mod\;p=r^e$

因此只要把$q^e和r^e$消去就能用gcd求出p，然后利用p再去求q和r，注意需要用md5值爆破一下。exp：

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

flag_md = 'a6e1f5c86223607ab196d5ed36cb1eb8'
a = 33022028261473232777495374489369984051173051765914698583738518002899904080523156837934749116742046277602367384435566675571554308103705904368259935553616909439053270303487771097937681411464233154789299798806729983958502682142190437300710333776343215351258409122741296694039365121701417931039351706449620933965
b = 81094699539404597343145361125240498679809760332244536460451475832258379562399932681242912311485592104271252217309012830898060896041053659829385735202726553288600509493460180497835520339585127754273226762440611089795375598402111645618656148576588630597445547241467407938373779128315636192164727397109721371821
o = 84271446189918339833844652348525276763886039158109929437916837238145526361383913885452712470249189911870483017509012824863702488719752612973997881394827167428837538802085223497834025041680433523842549305188960285145390142799963207261252716937469861672320881012026095221908641651584348583973984309599037601834
s = 15123960887720641582473419411098607262340676763761583670149167561153634913307686118729176007021398862293975304379052309333724796000639317958549447559668843718134962233429595288688678289005300880495334503517799794958574524554067587882588738019194484329080120346211069604574355250202792739546620819511246051563

t1 = pow(o-2023,2023) - a
t2 = pow(s-2023,2023) - b
p = gcd(t1,t2)
print(p)

q = (o-2023) % p
r = (s-2023) % p

for i in range(100):
    for j in range(100):
        q_ = q + p * i
        r_ = r + p * i

        flag = "flag{%s}"%md5(str(p+q_+r_).encode()).hexdigest()
        flag_md5 = md5(str(flag).encode()).hexdigest()
        if flag_md5 == flag_md:
            print(flag)
            print(flag_md5)
            break

task14

from Crypto.Util.number import *
from hashlib import md5
p = getPrime(1024)
q = getPrime(1024)
e = 0x1000000001
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
info = p+q+d
flag = "flag{%s}"%(md5(str(p).encode()+str(q).encode()).hexdigest())
print("info = %d"%info)
print("n = %d"%n)
print("e = %d"%e)
print("flag_md5 = %s"%md5(flag.encode()).hexdigest())
'''
info = 8624427976171269462118041236131860880353185724611115567769031391985212205334299206262416050893790496280487822633821896510164798860649610314643858720250778483148210218901983626065047187632632798657803619845039340275071550929875181405670087477995477977547400586054837874496784983655506143028794707073522709491957889389497112122398129617977201085938125308438851338856122300458905698778054527484342442183812543835926984418962888390266572594876953921925983459356710496966798344822306906157437194702449649080264101152002664874120624149638832121202508620869036457251193215517734116478672807574868697528296087842179376581201
n = 14646253358612854593317963725110988740491254060490903007910848037596846774729618833633231941531333403744010619378997475183337224450843648913131458780615463900296389211449668911282991115171184653170167906062913921232964400561146792601325354025107183172114144784169596208877805222213699601989143210211038189598547685022247536976806315807057890676464430811813960217168432160091360752223667140817878444045222127700744845352705982947205350416033568820758533074931871448795787684898779195153103174867673372027411790194468629972797561036156241378564908390993235826771493427813472825015487027549142331247821510473393248474487
e = 68719476737
flag_md5 = 62f2189c09660f7c68ecbbf2ad7c1ec8
'''

由于p+q-n-1 = -phi，info - n - 1 = d-phi。已知e，d分解n是比较容易的，也就是已知k*phi分解n，那么这里对(d-phi)乘上e就能得到k.phi，直接打即可。

from hashlib import *
from gmpy2 import *
import gmpy2
import random

def getpq(n,e,d):
    while True:
        k = e * d - 1
        g = random.randint(0, n)
        while k%2==0:
            k=k//2
            temp=gmpy2.powmod(g,k,n)-1
            if gmpy2.gcd(temp,n)>1 and temp!=0:
                return gmpy2.gcd(temp,n)

check = '62f2189c09660f7c68ecbbf2ad7c1ec8'
info = 8624427976171269462118041236131860880353185724611115567769031391985212205334299206262416050893790496280487822633821896510164798860649610314643858720250778483148210218901983626065047187632632798657803619845039340275071550929875181405670087477995477977547400586054837874496784983655506143028794707073522709491957889389497112122398129617977201085938125308438851338856122300458905698778054527484342442183812543835926984418962888390266572594876953921925983459356710496966798344822306906157437194702449649080264101152002664874120624149638832121202508620869036457251193215517734116478672807574868697528296087842179376581201
n = 14646253358612854593317963725110988740491254060490903007910848037596846774729618833633231941531333403744010619378997475183337224450843648913131458780615463900296389211449668911282991115171184653170167906062913921232964400561146792601325354025107183172114144784169596208877805222213699601989143210211038189598547685022247536976806315807057890676464430811813960217168432160091360752223667140817878444045222127700744845352705982947205350416033568820758533074931871448795787684898779195153103174867673372027411790194468629972797561036156241378564908390993235826771493427813472825015487027549142331247821510473393248474487
e = 68719476737
l = info

d = info - n - 1
p = getpq(n,e,d)
print(p)
q = n//p
assert p*q ==n

flag = "flag{%s}"%(md5(str(p).encode()+str(q).encode()).hexdigest())
print(flag)

2023数字中国.数据安全产业人才能力挑战赛初赛

math_exam

challenge1

由于 $p > q$，故

$$leak = n+p \mod (q-1)\\ = p * (q-1+q) + p \mod (q-1)\\ =2p \mod (q-1) = 2 p - 2(q-1) = 2(p-q+1)$$

故 $\frac{leak}{2} + n= (p-1)(q-1)+2p \equiv 2 \mod (p-1)$

由费马小定理得 $2^{k(p-1)} \equiv 1 \mod p$

所以有 $2^{\frac{leak}{2} + n-2} -1 \equiv 0 \mod p$，由此得到$p$ 的一个倍数，与$n$ 求最大公因数得到$p$，从而分解 $n$，计算出flag1，此部分exp如下：

from Crypto.Util.number import *

# -------- challenge 1 --------
e = 65537
c = 112742443814287255411540092433156061065388404049949520959549377871297566383025041892192679147481155020865118811016470498351633875090973546567374001852295013083192495299811476604405637385307524194793969533646755764136014187430115618114840780368311166911900457224593131166970676797547489278410997707815915932756
n = 121127425328043404860413278637978444801342472819958112597540188142689720655042880213001676368390521140660355813910726809125567752172921410143437643574528335234973793653775043030021036875866776532570781661875022102733555943967261003246543180935987772711036868216508554536086688819118597075508026787867088355603
leak = 216638862637129382765636503118049146067015523924032194492700294200289728064297722088882791754351329407138196573832392846467607399504585045028165699421278
# leak = 2(p-q+1)
tmp = leak//2 + n - 2
kp = pow(2, tmp, n)
p = GCD(kp-1, n)
q = n//p
phi = (p-1) * (q-1)
d = inverse(e, phi)
flag1 = long_to_bytes(pow(c, d, n))[:14]
print(flag1)
# b'flag{9dc4b6dd-'

challenge2

$leak = d + p+q$，故有

$$(n+1-leak) e +1 \\ = ((p-1)(q-1)-d) e + 1\\ \equiv -ed + 1 \mod (p-1)(q-1) \equiv 0 \mod (p-1)(q-1)$$

故 $(n+1-leak) e +1$ 是 $\phi(n) = (p-1)(q-1)$ 的倍数，在这里与 $(p-1)(q-1)$ 等价，故可以直接计算出 $d$ 从而得到flag，此部分exp如下：

from Crypto.Util.number import *

# -------- challenge 2 --------
e = 65537
c = 7964477910021153997178145480752641882728907630831216554750778499596527781702830885213467912351097301767341858663701574005489585561370961723264247818377063081744522471774208105250855114831033452448184392499682147532404562876275189577321587660597603848038824026981539659156304028998137796242331160312370913038
n = 140571013522095816880929287025269553867630639381779595547026503691829940612178900269986625350464874598461222087427155791855120339533208468121389480964471710028253589422629569889402475311387750348466199387760629889238062977271925350490110043385800605640905324122017637306715108727700910035925728362455954862209
leak = 58442382248753295429370894053397615609981110383986887405127350139482893508400422595729520437678203735054593866306478994471465948872565590901376309380029015549809468112086393107585011072503638322671608471684607214064187044372418770555236721845694224676090744181562673509234801011420696349507624867568099759003
kphi = -((leak-n-1) * e - 1)
d = inverse(e, kphi)
flag2 = long_to_bytes(pow(c, d, n))[:14]
print(flag2)
# b'b162-479c-b087'

challenge3

由于 $p, q$ 互素

$$p^q = p p^{q-1}\\ p^{q-1} \equiv 1 \mod q\\ \Rightarrow p^ q = p + k_1pq\\ q^p = q q^{p-1}\\ q^{p-1} \equiv 1 \mod p\\ q^ p = q + k_2qp\\$$

故 $p^q + q^p \equiv p+q \mod n$，故 $\phi(n) = (p-1)(q-1) -leak+1$，从而可以求出$d$，继而得到flag3，此部分exp如下：

from Crypto.Util.number import *

# -------- challenge 3 --------
e = 65537
c = 54161995127842474543974770981473422085334044100057089719350274921419091368361244533281599379235907845996678762379778310924192757650322930707785543132446159092950451255660204858292974657119337026589911330412367633761103944916751660957776230135927005700707688661350641600954072696774954805514477330339449799540
n = 88207747624007183083381863279444163105330473097729276113333026679597864128605555600000789783468271680476780366740448641311570797876037993255307716167149079618302706650018518487351604778857406170722209469765782625409279109832638886179654096975665134276856272488090272822541461702907181545730309689190333058151
leak = 19596671928335648228117128090384865424885102632642665068992144783391306491716530155291726644158221224616817878768426330717188403310818678195631582453246848
phi = n-leak+1
d = inverse(e, phi)
flag3 = long_to_bytes(pow(c, d, n))[:14]
print(flag3)

print(flag1 + flag2 + flag3)
b'-01d351073d14}'

2023数字中国.数据安全产业人才能力挑战赛决赛

easybag

背包，但是模比较小，所以用常见的那几个格都打不了，可能的方法有二：一是用babai求解cvp，二是把原来的格子多加一维，放个模数进去规约，这里用的第二种：

p = 94154607166206368507849450076562888867777996786776585204541315115554265673239
t= 
c = 300528310281431128814608316680537971945579270793936168485054801251195415271
print(len(t))
A = Matrix(ZZ, 66, 66)
for i in range(64):
    A[i,i] = 1
    A[i,65] = -t[i]
    
A[64,64] = 1
A[64,65] = c
A[65,65] = p
print(A.LLL()[0])
    
from Crypto.Cipher import AES
k = (0, -1, 0, 0, 0, -1, 0, -1, -1, -1, 0, 0, 0, -1, -1, -1, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0, -1, -1, -1, 0, 0, 0, 0, 0, 0, -1, -1, 0, -1, 0, 0, -1, 0, 0, 0, -1, -1, -1, 0, 0, -1, -1, 0, 0, 0, -1, 0, -1, -1)
key = ''
for i in k:
    if i:
        key += '1'
    else:
        key += '0'
print(len(k))
print(hex(int(key,2))[2:])
key = bytes.fromhex(hex(int(key,2))[2:])
print(len(key))
enc = b'Z\x8b `I\xa6\xde\nF\x13J\xf4^1}\x98*R-[\x9c\x851\xf4\xeeF\xea\xbc$s\xd8\xb4F\xebg\x86\x8e\xb0\xc9%V\x12&Rw\xcc\n\xc0'
aes = AES.new(key=key * 2,mode=AES.MODE_ECB)
print(aes.decrypt(enc))

[NSSRound#11 Basic]

确实basic…

MyMessage

from pwn import *
from sympy.ntheory.modular import crt
from gmpy2 import iroot
from Crypto.Util.number import *

io = remote('node4.anna.nssctf.cn',28496)
#io.interactive()
ns = []
cs = []
for i in range(100):
    print(i)
    print(io.recv(16))
    io.sendline(b'1')
    n = int(io.recvline().strip()[3:])
    c = int(io.recvline().strip()[9:],16)
    ns.append(n)
    cs.append(c)

res = crt(ns,cs)[0]
flag = iroot(res,127)[0]
print(long_to_bytes(flag))

ez_fac

c= 3866279781013543205658463982680574789263686965906473424577486426942775694532574930616672988611113833539702690921446200225171584718802440563150487891096712274831420836933939779382822469222602044856724471573453348450920756403685981523107389025461368280902766853394997570763802420010913302243342822394651909187
n= 87665217778729524993118310155129480311708534438704150676980835344891979982717119161254489670350577173938239682286759779547789055360697960379769693294306641200724257991678505629369338313581657539655057636732714452287023658150014746541718058750871927050204352584824130972892779877896415568548748364583880371427
a0= 9362970563807702423162361787386216886594085863490420184497563324865248429693287404341206766515622648778272030443641712923250846610046357375553046092690266
a1= 9362970563807702423162361745963275441706212437133735476965289880825874017106479792816846422940594285630367772490647779230476318907092613021181772527068514
b0= 74836747076024432741470938222753940689278814091833170112470104078475118700897724833941621360216319460657128947837095907483
b1= 93520964011413593176393772179429258741894666938448164504029535235899813670669478849381259720656022408302270582527720184427

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

e = (n-a0**2)//(b0**2)
t = a1*b0 + a0*b1
p = gcd(t,n)
q = n//p
phi = (p-1)*(q-1)
d = invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

ez_signin

num1= 52094189070805820804424069707311784807157194903972872439434677248883216068691427397091287206739227220919493383737034374096848668365439528625160682561322951470871293036263842642491522909243273773919260520717204606422128387000039062461612208327799165806265429050467490481951704165618350489409782368149856166950
num2= 44228448973880794092811557437884460378759412017840065082804534133889768961575815311337323700431529464429743530485906039883376717153841258291258609059826848063127477487186404659693566117135799418568868159980514887386022167834037372135938523336342287230249271027079949968219310533046256883639803116927790020165
n= 98738932373188046024686505904611091324755905262596386173576767806810454582969932160298324350291905371874108126768204348061815027538651811193755634671810585929501964007542830297837035700490365176329686118281557209774930455457390777277376532139997885130229922205947097280963616902661679441980114384290036052957
c= 97751595771170183741059020607826350445818493283139901788335888783743233053935567691612719833760149160442642982219277553391300024636761543939370752084440994838400914263941671018563950741931060805020010336586743139356850718806959581718088821208788012369038995290781484069100872431520130453979814336360766383548
e = 65536
assert e == 2 ** 16

from Crypto.Util.number import *
import gmpy2

p = gmpy2.gcd(num1 + num2 ,n)
q = n//p
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)

def de_rabin(c):
    mp = pow(c, (p+1) // 4, p)
    mq = pow(c, (q+1) // 4, q)
    a = (inv_p * p * mq + inv_q * q * mp) % n
    b = n-int(a)
    c = (inv_p * p * mq - inv_q * q * mp) % n
    d = n-int(c)
    return [a,b,c,d]

res=de_rabin(c)
r=[]
for j in res:
    r.extend(de_rabin(j))
rr=[]
for i in range(14):
    for j in r:
        rr.extend(de_rabin(j))
    r=list(set(rr))
    rr=[]
for i in r:
    print(long_to_bytes(i))

MyGame

共模攻击。

NTR

数域上最简单的那个二维格。