Writeup in 2022CryptoCTF

It’s my first time to participate CCTF. Finally I got 1218 points and rank 30. During CCTF, I learned some tricks and gained many new view.

I will choose to record some meaningful challenges which I have solved or are still puzzling

BTW , it’s my first time to write solution in English , it can be lame. But it did a opportunity to know terminology.

SOTS

A classical math problem. Maybe called Sum of Gauss squares. I always use it during the math competition to prove some proposition. But I haven’t thought how to find it. I just search some algorithm named Fermat reduced order method and achieve it.

import random
n=2076404368738342225663114052301802417814286369156942765753400865872024253
p=1872032952276373491266413
q=1077425514328313332690477
r=1029464059232560561627253
def facp(p):
    b=1
    r=random.randrange(0,p-3)+2
    x=(p-1)//4
    pm=pow(r,x,p)
    while pm**2%p!=p-1:
        r=random.randrange(0,p-2)+1
        pm=pow(r,x,p)
    a=pm
    s=a**2+b**2
    while s!=p:
        M=s//p
        k=M//2
        u=a%M
        v=b%M
        if u>k:
            u=M-u
        if v>k:
            v=M-v
        if (u*a+v*b)%M:
            tmp=a
            a=b
            b=tmp
        y=(u*a+v*b)//M
        z=(v*a-u*b)//M
        s=y**2+z**2
        a=y
        b=z
    return a,b

a1,b1=facp(p)
a2,b2=facp(q)
a3,b3=facp(r)
uu=(a1*a2+b1*b2)
vv=(a1*b2-b1*a2)
u=uu*a3+vv*b3
v=uu*b3-vv*a3
print(u)
print(v)

sagemath have relevant function to solve it

p=1872032952276373491266413
print(two_squares(p))

A higher point is factor n in , I try it in sage but fail

Diploma

A problem about GL(n)’s order. I’ve seen this problem before. In a paper I get answer . But sage still have relative func M.multiplicative_order()

The interaction is painful

from pwn import *
from sage.all import *
context(log_level='debug')
io=remote('08.cr.yp.toc.tf',37313)
p=127

while True:
 io.recvuntil('M = \n')
 M=[]
 while True:
  tmp=''
  re=io.recvuntil('\n')[:-1]
  if b'matrix M:' in re:
   break
  tmp+=chr(re[0])
  for i in range(1,len(re)):
   if i>2 and re[i]==32:
    if tmp[len(tmp)-1]!=',' and tmp[len(tmp)-1]!=']':
     tmp+=','
   else:
    tmp+=chr(re[i]) 
  print(tmp)
  M.append(eval(tmp))
 M=Matrix(GF(p),M)
 order=M.multiplicative_order()
 io.sendline(str(order))

Starter ECC

this challenge is to solve with

I solve it using the same idea in SEECTF(DLP) just like a lifting theorem

import gmpy2
def recover2(t,w):
    cofs=[]
    PR.<x>=PolynomialRing(Zmod(2))
    f=x^2-t
    root=f.roots()[0][0]
    cofs.append(int(root))
    tmp=int(root)
    cofs.append(1)
    tmp+=2
    for i in range(4,w+1):
        cof=((t-tmp^2)*gmpy2.invert(tmp,2^i)%2^i)//2^(i-1)
        cofs.append(cof)
        tmp+=cof*2^(i-2)
    cofs.append(1)
    re=0
    for i in range(w):
        re+=cofs[i]*2^i
    return re

def recover(t,p,w,i):
    cofs=[]
    PR.<x>=PolynomialRing(Zmod(p))
    f=x^2-t
    root=f.roots()[i][0]
    cofs.append(int(root))
    tmp=int(root)
    for i in range(2,w+1):
        cof=((t-tmp^2)*gmpy2.invert(2*tmp,p^i)%p^i)//p^(i-1)
        cofs.append(cof)
        tmp+=cof*p^(i-1)
    re=0
    for i in range(w):
        re+=cofs[i]*p^i
    return re
        

xx = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
p1=2
p2=690712633549859897233
p3= 651132262883189171676209466993073
n=117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
t=(xx^3+a*xx+b)%n
y1=recover2(t,63)
y2=recover(t,p2,6,1)
y3=recover(t,p3,5,1)
m=crt([y1,y2,y3],[p1^63,p2^6,p3^5])
print(bytes.fromhex(hex(m)[2:]))

another way is to use p-adic. It’s easy beacause sage have some module. But I don’t know much about it.

can use it like this

t=93537210270650150510202879113948342209471088325309071397356033881709266017880457869963986668043867063176965473274592196316442
p=690712633549859897233
s=ZZ(Qp(p)(t).sqrt())%p^6
assert pow(s,2,p^6)==t
print(s)

Oak Land

A interesting challenge. I do it but fail to observe the special data.

It looks like multiple element dlp, but you can simply it by build connection between variable. Finally it’s just need solve a low degree equation.

p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576
c=871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356
Fp=GF(p)
e=Fp(e)
f=Fp(f)
g=Fp(g)
t1=int(f.log(e))
t2=int(g.log(e))
#print(p)
#print(t1)
#print(t2)
PR.<x>=PolynomialRing(Zmod(p))
f=110*x^3-c*x^2+313*x+114
cc=f.roots()[0][0]
cc=Fp(cc)
m=cc.log(e)
print(bytes.fromhex(hex(int(m))[2:]))

Infinity Castle

diamond(n) is , triage(n) is , TaylorSeries is the Taylor expansion of the square root of x

You can emtimate summarize’s result by integral. Because we don’t need exact value of key. So do it by estimating is feasible

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

def xor(cip, key):
    repeation = 1 + (len(cip) // len(key))
    key = key * repeation
    key = key[:len(cip)]

    msg = bytes([c ^ k for c, k in zip(cip, key)])
    return msg

c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045
s1=gmpy2.iroot(c1,3)[0]
s2=gmpy2.iroot(c0**3//c1,3)[0]
p=(s1+s2)//2
q=(s1-s2)//2
phi=(p-1)*(q-1)
n=p*q
e=0x10001
d=inverse(e,phi)
key=long_to_bytes(int(2*isqrt(pow(n,3))//3))
c=long_to_bytes(pow(enc,d,n))
print(xor(c,key))

Resign

I didn’t finish it on time because lack the proper Smooth number. However I find this problem can be solved by reduce the smooth level.(Cyclic groups have higher orders)

from Crypto.Util.number import *
def gen_primes(nbit, imbalance):
	p = 2
	FACTORS = [p]
	while p.bit_length() < nbit - 2 * imbalance:
		factor = getPrime(imbalance)
		FACTORS.append(factor)
		p *= factor
	rbit = (nbit - p.bit_length()) // 2

	while True:
		r, s = [getPrime(rbit) for _ in '01']
		_p = p * r * s
		if _p.bit_length() < nbit: rbit += 1
		if _p.bit_length() > nbit: rbit -= 1
		if isPrime(_p + 1):
			FACTORS.extend((r, s))
			p = _p + 1
			break

	FACTORS.sort()
	return (p, FACTORS)

p,_=gen_primes(1024,20)
q,_=gen_primes(1024,20)
print('p=',p)
print('q=',q)

import gmpy2
s=7984117781193502575412750505430979186228119017807317960994355227205949819092428731236337909197167584395143960813661416647917034357707829764233170814875745583208603309833382309448961632449932606644599794982667065067211545658432155270344026432978482493058391281970539985258874195736716168226015296465896222711449764960924598244484042742120206434449431821943587424974496744540622137023049971061842575042202489321438759754822828568020390315315068482818064779065128579172903182839413115643905215071190495277703316420230587526327805179182224313125252287971253632106014646086776569402554056131078566070017884013630764049336
h=859134015240994359820678247621894875833976723365
p= 122415509565518531443147639848448248409469589947486005320386529550844357405484773578332786457733733732418287234961042780614741190123679692506761189624673309052253155681404430445151991408962587788043621396541174258856184502345401381866169756836931056269731266097189703314853514497934474702757788612726278471587
q= 76506675455644608060963110138362743927973612279961964190480978401417336483425872394063064854906790750016782282678362690623938928815788994891134844315959485830145364283392280519872728172078240496191944338394829808009536643696258457554553352482738348872308968685891720161748887997488378363675678238379325906643
phi=(p-1)*(q-1)
fp=GF(p)
fq=GF(q)
d1=discrete_log(s,fp(h))
d2=discrete_log(s,fq(h))
e=crt([d1,d2],[p-1,q-1])
d=gmpy2.invert(e,phi)
print(e)

Faonsa&Fiercest

Both of two question have same thought. We need make the modulu smooth using fault attack(just a name but interesting)

from Crypto.Util.number import *
n=98946348531671552366599636519893607646703047155335246624251536405323524152537202603241932094835105000412311403806982008184571354393081819367329019220712532243268590378962545968974721430598690895928222554884889004911627379371908932211309804472944234919739986668246269664956128234005360667329571534551093537337
MSG = "4lL crypt0sy5t3ms suck5 fr0m faul7 atTaCk5 :P"
m = bytes_to_long(MSG.encode('utf-8'))
e=65537
for i in range(1,len(bin(n)[2:])):
    tmp=n^(2**(len(bin(n)[2:])-i))
    if isPrime(tmp):
        print(i-1)
        p=tmp
        phi=p-1
        d=inverse(e,phi)
        sign=pow(m,d,tmp)
        print(sign)
        se=pow(sign,e,p)-m
        print(se)

But these two question all have a same bug, called shallow copy. It’s really interesting. By it,we can make modulu be whatever we want.

a=[1,2,3]
b=a
print(a)
b[0]=7
print(a)
#[1, 2, 3]
#[7, 2, 3]

Mino

I did’t finish it. I see someone do it by recursion. It’s perfect but a little hard. Rencently, I see some new solution- and it’s fast.

from z3 import *
n=40
V=[z3.BitVec("V{}".format(i),42) for i in range(n)]
con1=[z3.And(1<=V[i],V[i]<=n) for i in range(n)]
con2=[z3.Distinct(V)]
con3=[sum(V[i]*(-2)**i for i in range(n))==0]
sol=Solver()
sol.add(con1+con2+con3)
print(sol.check())
print(sol.model())

Side step

All it takes is a simple idea, use to check s bit by bit

function pow_d’s process will calculate pow(g,bin(s)[:i],p) for any i. So we can use g=pow(2,-bin(s)[:i],p) to check whether the bit of s is equal to 1.

The script may needs to be run multiple times to make sure s is 1023 bits

from pwn import *
from Crypto.Util.number import *
from tqdm import tqdm
import gmpy2
context(log_level='debug')
io=remote('01.cr.yp.toc.tf',17331)
#io=process('./side.py')
p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
s='1'

def ts(m, p):
 m = m % p
 return pow(m, (p - 1) // 2, p) == 1

def search():
 global s
 io.sendlineafter('[Q]uit\n','t')
 e=int(s,2)
 d=gmpy2.invert(e,(p-1)//2)
 g=pow(2,d,p)
 io.sendline(str(g))
 io.recvuntil('t, r = (')
 sign=int(io.recvuntil(',')[:-1])
 if sign==0:
  s+='1'
 else:
  s+='0'
  
for i in tqdm(range(1022)):
 search()
print(s)
s=int(s,2)
dd=inverse(s,(p-1)//2)
m=pow(4,dd,p)
io.sendlineafter('[Q]uit\n','t')
sleep(0.01)
io.sendline(str(m))
io.interactive()