Write up CorCTFand DeadSecCTF

CorCTF:

steps:

Challenge description and source code:

Alice and Bob have taken steps to communicate securely.

from Crypto.Util.number import getPrime
from random import randint
from hashlib import sha512
from secret import FLAG

p = getPrime(1024)

Pair = tuple[int, int]

def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p

def calculate(n: int) -> Pair:
    out = 0, 1
    base = 1, 1

    while n > 0:
        if n & 1 == 1: out = apply(out, base)
        n >>= 1
        base = apply(base, base)

    return out

def step(x: Pair, n: int):
    '''Performs n steps to x.'''
    return apply(x, calculate(n))

def xor(a: bytes, b: bytes) -> bytes:
    return bytes(i ^ j for i, j in zip(a, b))

def main() -> None:
    g = tuple(randint(0, p - 1) for _ in range(2))
    a = randint(0, p)
    b = randint(0, p)

    A = step(g, a)
    B = step(g, b)

    print(p)
    print(g)
    print(A)
    print(B)

    shared = step(A, b)
    assert shared == step(B, a)

    pad = sha512(str(shared).encode()).digest()
    print(xor(FLAG, pad))

if __name__ == "__main__":
    main()
'''
Output:
140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
(96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
(70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
(112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'
'''

Solving:

Looking into the code we see that

def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p

With $g(x,y)$ and a point $t(a,b)$ will return $(xb+ya-xa),(xa+yb)$. and we already know $g(x,y)$. So using some basic opration we can find the value of $t(a,b)$ from that easily find the flag. Note: My code using Sage with support finite field arithmetic, so it is easiler. But in Zmod(p) division operation should be replace with multiply with modulo inverse of x.

from hashlib import sha512
from pwn import xor
p=140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
g=(96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
A=(70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
B=(112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
ct = b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'
Pair = tuple[int, int]

def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p
K = GF(p)
x = K(g[0])
y = K(g[1])
matrix = Matrix(K,[[x,y-x+p],
                   [y,x]])
rhs = vector(K,[A[0]+p,A[1]+p])
t = matrix.solve_right(rhs)
z = int(t[1]),int(t[0])
rhs2 = vector(K,[B[0],B[1]])
t2 = matrix.solve_right(rhs2)
z2 = int(t2[1]),int(t2[0])
shared = apply(B, z)
shared2 = apply(A, z2)
assert shared == shared2

pad = sha512(str(shared).encode()).digest()
print(xor(ct, pad))
#corctf{w4it_i7's_4ll_f1b0n4cci?}

DeadSec CTF:

Flag killer:

Challenge description and source code:

Is it enough obfuscation?

#!/usr/bin/python3

from binascii import hexlify

flag = hexlify(b'DEAD{test}').decode()

index = 0
output = ''

def FLAG_KILLER(value):
    index = 0
    temp = []
    output = 0
    while value > 0:
        temp.append(2 - (value % 4) if value % 2 != 0 else 0)
        value = (value - temp[index])/2
        index += 1
    temp = temp[::-1]
    for index in range(len(temp)):
        output += temp[index] * 3 ** (len(temp) - index - 1)
    return output


while index < len(flag):
    output += '%05x' % int(FLAG_KILLER(int(flag[index:index+3],16)))
    index += 3

print(output)
'''
output = 0e98b103240e99c71e320dd330dd430de2629ce326a4a2b6b90cd201030926a090cfc5269f904f740cd1001c290cd10002900cd100ee59269a8269a026a4a2d05a269a82aa850d03a2b6b900883
'''

Solving:

Because I have solved the other easy challange - SSP, so I just copy the knapsack 01 code from that, modified a bit and get the temp array. The rest is reversed of that the source doing.

from Crypto.Util.number import long_to_bytes
from tqdm import *
from itertools import product
ct = '0e98b103240e99c71e320dd330dd430de2629ce326a4a2b6b90cd201030926a090cfc5269f904f740cd1001c290cd10002900cd100ee59269a8269a026a4a2d05a269a82aa850d03a2b6b900883'
output = []

for i in range(0,len(ct),5):
    oo = int(ct[i:i+5],16)
    output.append(oo)

hmm = [1]
t = 3
for i in range(13):
    hmm.append(t)
    t *= 3
def solve(target, weight):
    n = len(weight)
    for x in product([-1, 0, 1], repeat=n):
        temp = sum(w * x_i for w, x_i in zip(weight, x))
        if temp == target:
            return list(x)
    return None

tmp_arr = []
for i in tqdm(output):
    tt = solve(i,hmm)
    tmp_arr.append(tt)


m = ''
for i in tmp_arr:
    #print(i)
    tt = i[::-1]
    for oo in range(len(tt)):
        if tt[oo]!=0:
            tt = tt[oo:]
            break
    
    value = 0
    for t in tt:
        value = (value)*2 +t
    
    #print(value)
    tt = str(hex(value)[2:])
    #print(tt)
    m += tt.ljust(3,'0')
    #print(m)
    
print(long_to_bytes(int(m+'0',16)))
#b'DEAD{263f871e880e9dc7d2401003004fc60e98c7c588}\x00'

SSP:

Challenge description and source code:

Sometimes it requires GPU to compute huge amount of operation… like $O(2^{100})$..? Nah, you’ll use better algorithm, $O(2^{50})$ seems fair huh?

MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method

from random import randrange

for n in range(1, MAX_N + 1):

    print(f"Stage {n}")

    arr = [ randrange(0, RAND_MAX) for _ in range(n) ]
    counts = randrange(0, n + 1)
    
    used = set()
    
    while True:

        idx = randrange(0, n)
        used.add(idx)

        if len(used) >= counts:
            break
    
    s = 0
    for idx in used:
        s += arr[idx]
    
    for a in arr:
        print(a, end=' ')
    print(s)

    answer = list(map(int, input().split()))

    user_sum = 0
    for i in answer:
        user_sum += arr[i]
    
    if user_sum != s:
        print("You are wrong!")
        exit(0)

    print(f"Stage {n} Clear")

print("Long time waiting... Here's your flag.")

with open('./flag', 'r') as f:
    print(f.read())

Solving:

We can easily understand that this is a 0-1 knapsack problem, normally required bruteforcing all the combination to have the correct result. But in this case, $n=100$ and normal algorithm have $O(2^n)$ time complexity so it is not feasible. But using LLL and lattices we can solve the problem will reasonable time - paper.

from pwn import *
from tqdm import *
def knap_sack_normal(target, weight):
    from itertools import product

    n = len(weight)
    for x in product([0, 1], repeat=n):
        temp = sum(w * x_i for w, x_i in zip(weight, x))
        if temp == target:
            return list(x)
    return None

def knap_sackLLL(a,s):
    n = len(a)
    N = int(sqrt(n)/2)
    b = []
    for i in range(n):
        vec = [0 for _ in range(n + 1)]
        vec[i] = 1
        vec[-1] = N * a[i]
        b.append(vec)

    b.append([1/2 for _ in range(n)] + [N * s])

    BB = matrix(QQ, b)
    l_sol = BB.LLL()
        #print(l_sol)
    for e in l_sol:
        if e[-1] == 0:
            msg = ""
            valid = True
            for i in range(len(e) - 1):
                ei =  1-(e[i]+1/2)
                if ei != 1 and ei != 0:
                    valid = False
                    break
                msg +=str(ei)
            if valid:
                return msg
                
                      
io=process(["python3","chall.py"])
#io = remote('34.121.62.108', 32651)
for i in trange(1,101):

    io.recvuntil(f"Stage")
    n  = io.recvline().decode().strip()
    n = int(n)
    data = io.recvline().decode().strip().split(' ')
    data = [int(x) for x in data]
    target = data[-1]
    data = data[:-1]
    if n < 15:
        ans = knap_sack_normal(target,data)
        msg = b''
        for i in range(len(ans)):
            if ans[i] == 1:
                msg += str(i).encode() + b' '
        #print(msg)
        io.sendline(msg)
    else:
        ans = knap_sackLLL(data,target)
        msg = b' '
        for i in range(len(ans)):
            if ans[i] == '1':
                msg += str(i).encode() + b' '
        #print(msg)
        io.sendline(msg)
    io.recvline()
print(io.interactive())
#DEAD{T00_B1g_Number_Causes_Pr0blem...}

Raul Rosas:

Challenge description and source code:

“I say weird stuff all the time.”

from Crypto.Util.number import * 
from sympy import nextprime

p1 = bin(getPrime(1024))[2:]
p2 = p1[:605]
p2 = p2 + ('0'*(len(p1)-len(p2)))

p1 = int(p1,2)
p2 = nextprime(int(p2,2))

q1 = getPrime(300)
q2 = getPrime(300)

n1 = p1*p1*q1 
n2 = p2*p2*q2 

e = 65537 
flag = bytes_to_long(b'REDACTED')
c1 = pow(flag,e,n1)
c2 = pow(flag,e,n2)

print(f'{n1=}')
print(f'{n2=}')
print(f'{c1=}')
print(f'{c2=}')


"""
n1=33914684861748025775039281034732118800210172226202865626649257734640860626122496857824722482435571212266837521062975265470108636677204118801674455876175256919094583111702086440374440069720564836535455468886946320281180036997133848753476194808776154286740338853149382219104098930424628379244203425638143586895732678175237573473771798480275214400819978317207532566320561087373402673942574292313462136068626729114505686759701305592972367260477978324301469299251420212283758756993372112866755859599750559165005003201133841030574381795101573167606659158769490361449603797836102692182242091338045317594471059984757228202609971840405638858696334676026230362235521239830379389872765912383844262135900613776738814453
n2=45676791074605066998943099103364315794006332282441283064976666268034083630735700946472676852534025506807314001461603559827433723291528233236210007601454376876234611894686433890588598497194981540553814858726066215204034517808726230108550384400665772370055344973309767254730566845236167460471232855535131280959838577294392570538301153645042892860893604629926657287846345355440026453883519493151299226289819375073507978835796436834205595029397133882344120359631326071197504087811348353107585352525436957117561997040934067881585416375733220284897170841715716721313708208669285280362958902914780961119036511592607473063247721427765849962400322051875888323638189434117452309193654141881914639294164650898861297303
c1=5901547799381070840359392038174495588170513247847714273595411167296183629412915012222227027356430642556122066895371444948863326101566394976530551223412292667644441453331065752759544619792554573114517925105448879969399346787436142706971884168511458472259984991259195488997495087540800463362289424481986635322685691583804462882482621269852340750338483349943910768394808039522826196641550659069967791745064008046300108627004744686494254057929843770761235779923141642086541365488201157760211440185514437408144860842733403640608261720306139244013974182714767738134497204545868435961883422098094282377180143072849852529146164709312766146939608395412424617384059645917698095750364523710239164016515753752257367489
c2=3390569979784056878736266202871557824004856366694719533085092616630555208111973443587439052592998102055488632207160968490605754861061546019836966349190018267098889823086718042220586285728994179393183870155266933282043334755304139243271973119125463775794806745935480171168951943663617953860813929121178431737477240925668994665543833309966378218572247768170043609879504955562993281112055931542971553613629203301798161781786253559679002805820092716314906043601765180455118897800232982799905604384587625502913096329061269176369601390578862509347479694697409545495592160695530037113884443071693090949908858172105089597051790694863761129626857737468493438459158669342430468741236573321658187309329276080990875017
"""

Solving:

When I were solving the problem in the contest time, I googling a found a blog that RSA that depicts a same prime structure $N=p_1 \cdot p_1\cdot q_1$.

Implement of this appoarch:

from gmpy2 import *
from Crypto.Util.number import *
N1=33914684861748025775039281034732118800210172226202865626649257734640860626122496857824722482435571212266837521062975265470108636677204118801674455876175256919094583111702086440374440069720564836535455468886946320281180036997133848753476194808776154286740338853149382219104098930424628379244203425638143586895732678175237573473771798480275214400819978317207532566320561087373402673942574292313462136068626729114505686759701305592972367260477978324301469299251420212283758756993372112866755859599750559165005003201133841030574381795101573167606659158769490361449603797836102692182242091338045317594471059984757228202609971840405638858696334676026230362235521239830379389872765912383844262135900613776738814453
N2=45676791074605066998943099103364315794006332282441283064976666268034083630735700946472676852534025506807314001461603559827433723291528233236210007601454376876234611894686433890588598497194981540553814858726066215204034517808726230108550384400665772370055344973309767254730566845236167460471232855535131280959838577294392570538301153645042892860893604629926657287846345355440026453883519493151299226289819375073507978835796436834205595029397133882344120359631326071197504087811348353107585352525436957117561997040934067881585416375733220284897170841715716721313708208669285280362958902914780961119036511592607473063247721427765849962400322051875888323638189434117452309193654141881914639294164650898861297303
C1=5901547799381070840359392038174495588170513247847714273595411167296183629412915012222227027356430642556122066895371444948863326101566394976530551223412292667644441453331065752759544619792554573114517925105448879969399346787436142706971884168511458472259984991259195488997495087540800463362289424481986635322685691583804462882482621269852340750338483349943910768394808039522826196641550659069967791745064008046300108627004744686494254057929843770761235779923141642086541365488201157760211440185514437408144860842733403640608261720306139244013974182714767738134497204545868435961883422098094282377180143072849852529146164709312766146939608395412424617384059645917698095750364523710239164016515753752257367489
C2=3390569979784056878736266202871557824004856366694719533085092616630555208111973443587439052592998102055488632207160968490605754861061546019836966349190018267098889823086718042220586285728994179393183870155266933282043334755304139243271973119125463775794806745935480171168951943663617953860813929121178431737477240925668994665543833309966378218572247768170043609879504955562993281112055931542971553613629203301798161781786253559679002805820092716314906043601765180455118897800232982799905604384587625502913096329061269176369601390578862509347479694697409545495592160695530037113884443071693090949908858172105089597051790694863761129626857737468493438459158669342430468741236573321658187309329276080990875017
E1 = 65537
E2 = 65537
def continuedFra(x, y): #不断生成连分数的项
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF
def Simplify(ctnf): #化简
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]: #倒叙遍历
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator) #把连分数分成分子和算出来的分母
def getit(c):
    cf=[]
    for i in range(1,len(c)):
        cf.append(Simplify(c[:i])) #各个阶段的连分数的分子和分母
    return cf #得到一串连分数
def wienerAttack(e, n):
    cf=continuedFra(e,n)
    for (Q2,Q1) in getit(cf):#遍历得到的连分数，令分子分母分别是Q2，Q1
        if Q1 == 0:
            continue
        if N1%Q1==0 and Q1!=1:#满足这个条件就找到了
            return Q1
    print('not find!')
Q1=wienerAttack(N1,N2)

print(Q1)
n1 = N1//Q1

t1 = (iroot(n1,2)[0])

phiN1 = t1*(t1-1)*Q1
d = pow(E1,-1,phiN1)
flag = pow(C1,d,n1)
print(long_to_bytes(flag))

Another Ways:

After that, I found another way - with hints from my senior. That $nextprime(p_2)$ have the different from the original $p_2$ is small (<1000). So N2 last ~320 bits is just $(dif)^2 \cdot q2$ from that we can find q2 and solve the challenge.