# LACTF Writeup
真的只會做密碼學的

## VeryHot

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from flag import FLAG

FLAG = bytes_to_long(FLAG.encode())

p = getPrime(384)
while(not isPrime(p + 6) or not isPrime(p + 12)):
    p = getPrime(384)
q = p + 6
r = p + 12

n = p * q * r
e = 2**16 + 1
ct = pow(FLAG, e, n)

print(f'n: {n}')
print(f'e: {e}')
print(f'ct: {ct}')

就RSA，他的n有3個質因數，可以很容易的分解

from Crypto.Util.number import *
p = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077
b = 481484964540720113472607671311958003544610499422246847987589354560178323791038264141087579324461879222750445224381527035495936943975826481974450340297411968236802328325641633227089888411307197205354087888800340238955852318668831387
q = p + 6
r = b // q
e = 2**16 + 1
ct = 9953835612864168958493881125012168733523409382351354854632430461608351532481509658102591265243759698363517384998445400450605072899351246319609602750009384658165461577933077010367041079697256427873608015844538854795998933587082438951814536702595878846142644494615211280580559681850168231137824062612646010487818329823551577905707110039178482377985

n = 10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799

phi = (p - 1) * (q - 1) * (r - 1)

d = pow(e, -1, phi)

flag = pow(ct, d, n)
print(long_to_bytes(flag))

## hOlyT

from Crypto.Util.number import getPrime, bytes_to_long
import random
def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

def tonelli(n, p):
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r
def xgcd(a, b): 
    if a == 0 : 
        return 0,1
             
    x1,y1 = xgcd(b%a, a) 
    x = y1 - (b//a) * x1 
    y = x1 
     
    return x,y 
def crt(a, b, m, n):
    m1, n1 = xgcd(m, n)
    return ((b *m * m1 + a *n*n1) % (m * n))

def advice(x, p, q):
    if legendre(x, p) != 1:
        exit()
    if legendre(x, q) != 1:
        exit()
    x1 = tonelli(x, p) * random.choice([1, -1])
    x2 = tonelli(x, q) * random.choice([1, -1])
    y = crt(x1, x2, p, q)
    return y
    
def main():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e = 65537
    m = bytes_to_long(b"lactf{redacted?}")
    ct = pow(m, e, N)
    print(f"ct = {ct}")
    print(f"N = {N}")
    print(f"e = {e}")
    while 1:
        x = int(input("What do you want to ask? > "))
        ad = advice(x, p, q)
        print(ad)

if __name__ == "__main__":
    main()

這題也是RSA，你可以給他一個數，他會回傳給你他模n下的平方根。因為模n下平方根和n的因式分解是等價問題，可以直接轉換。方法是取一對不是相反數的平方根，兩個相減再和n取gcd

from Crypto.Util.number import *
from pwn import *

r = remote("chall.lac.tf", 31171)

def get_sqrt(x):
    r.sendlineafter(b"> ", str(x).encode())
    return int(r.recvline().decode().strip())
ct = int(r.recvline().decode().split(' ')[-1].strip())
n = int(r.recvline().decode().split(' ')[-1].strip())
e = int(r.recvline().decode().split(' ')[-1].strip())

a = 2
b = get_sqrt(4)
while b == 2:
    b = get_sqrt(4)
q = GCD(a - b, n)
p = n // q

phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

flag = pow(ct, d, n)

print(long_to_bytes(flag))

## Prove It

#!/usr/local/bin/python
import random

flag = "lactf{??????????}"
p = 171687271187362402858253153317226779412519708415758861260173615154794651529095285554559087769129718750696204276854381696836947720354758929262422945910586370154930700427498878225153794722572909742395687687136063410003254320613429926120729809300639276228416026933793038009939497928563523775713932771366072739767


if __name__ == "__main__":
    
    s = random.getrandbits(128)
    alpha = random.getrandbits(40)
    g = redacted
    ss = [pow(g, s**i, p) for i in range(1,8)]
    alphas = [pow(g, alpha * s**i, p) for i in range(1,8)]
    print(f"Use these values to evaluate your polynomials on s")
    print(f"Powers of s: {ss}")
    print(f"Powers of alpha*s: {alphas}")
    tries = 0
    while True:
        if tries >= 2:
            print("Fool me once shame on you, fool me twice shame on me")
            break
        print("Can you prove to me you know the polynomial f that im thinking of?")
        target = []
        for i in range(8):
            target.append(random.randrange(p))
        print(f"Coefficients of target polynomial: {target}")
        ts = sum([(pow(s,7 - i, p) * target[i]) % p for i in range(len(target))]) % p
        f = int(input("give me your evaluation of f(s) > ")) % p
        h = int(input("give me your evaluation of h(s) > ")) % p
        fa = int(input("give me your evaluation of f(alpha * s) > ")) % p
        if f <= 1 or h <= 1 or fa <=1 or f == p-1 or h == p-1 or fa == p-1:
            print("nope")
            exit()
            
        if pow(f, alpha, p) != fa or f != pow(h, ts, p):
            print(f"failed! The target was {ts}")
            tries += 1
            continue

        print(f"you made it! here you got {flag}")
        break

這題先有未知的$g, s, \alpha$和已知的$p$然後給你$g^{s^i}和g^{\alpha s^i}$，$i從1到7$。然後給你一個$target$陣列，叫你求$f, h, fa$使得$fa = f^\alpha且f=h^{ts}$，其中$ts=\sum_{i=0}^7s^{7 - i}target_i$
這題其實沒那麼難，只是我把他搞得很複雜，後來才想到簡單的做法。
我的作法是求出$s和\alpha$，首先先用ss[0]和alphas[0]去把$\alpha$求出來，因為$\alpha<2^{40}$，所以bsgs很快就能跑出來。接下來因為他能多問一次，而且會給我$ts$，所以我可以構造出一個多項式，用coppersmith，然後再用ss的前兩項去檢查哪個根是正確的。

from pwn import *
# from tqdm import tqdm
from math import ceil, sqrt
from sage.all import *
import random
r = remote("chall.lac.tf", int(31179))
p = 171687271187362402858253153317226779412519708415758861260173615154794651529095285554559087769129718750696204276854381696836947720354758929262422945910586370154930700427498878225153794722572909742395687687136063410003254320613429926120729809300639276228416026933793038009939497928563523775713932771366072739767
r.recvuntil(b": ")
ss = list(map(int, r.recvline().decode().strip('\n[]').split(', ')))
r.recvuntil(b": ")
alphas = list(map(int, r.recvline().decode().strip('\n[]').split(', ')))
def bsgs(g, y, p):
    m = int(ceil(sqrt(1 << 40)))
    S = {pow(g, j, p): j for j in range(m)}
    gs = pow(g, p - 1 - m, p)
    for i in range(m):
        if y in S:
            return i * m + S[y]
        y = y * gs % p
    return None
x = ss[0]
y = alphas[0]
alpha = bsgs(x, y, p)

r.recvuntil(b": ")
target = list(map(int, r.recvline().decode().strip('[]\n').split(', ')))
r.sendlineafter(b"> ", b"2")
r.sendlineafter(b"> ", b"2")
r.sendlineafter(b"> ", b"2")
r.recvuntil(b"was ")
res = int(r.recvline().decode().strip())
# print(res)
F = GF(p)
P.<x> = PolynomialRing(F)
f = 0
for i in range(len(target)):
    f += x ** (7 - i) * target[i]
f -= res
f = f.monic()
root = f.roots()
s = root[0][0]
for a, b in root:
    if pow(ss[int(0)], int(a), p) == ss[int(1)] % p:
        s = a
        print("Hello")
        break
ts = int(0)
for i in range(len(target)):
    ts += s ** (7 - i) * target[i]
print(ts % p == res % p)
r.recvuntil(b": ")
target = list(map(int, r.recvline().decode().strip('[]\n').split(', ')))
ts = int(0)
for i in range(len(target)):
    ts += s ** (7 - i) * target[i]
h = 2
f = pow(h, ts, p)
fa = pow(f, alpha, p)
r.sendlineafter(b"> ", str(f).encode())
r.sendlineafter(b"> ", str(h).encode())
r.sendlineafter(b"> ", str(fa).encode())
res = r.recvline().decode()
print(res)

後來我有想到另一個，在我求出$s$之後，我可以試很多次直到$s$和$p - 1$互質之後，就能用類似RSA的方式把$g$求出來，然後他g很漂亮的是2。我們可以發現他的結果其實可以用ss和alphas指數的線性組合求出來，也就是說每個做$target_i$次方之後再相乘，而$h$就設$g$就好。我沒去寫他，不過看起來很完美。

## selamat pagi
我真的不太會古典密碼，這題就是一個參雜印尼文的substition cipher
，作法就是先頻率，讓英文顯現出來，稍微校正一下後去查一下那些印尼文，然後在調整一下去頻率分析，答案就出來了。

## budget-bag(賽後)
這提示橢圓曲線的背包問題，光是橢圓曲線的離散對數問題就很複雜了，還要做成背包?

#部分橢圓曲線的函數我直接省略掉，太佔空間了
import random
from hidden import DollarStore
p = 95773813056613526295315889615423014145567365190638271416026411091272805051097

flag = "lactf{REDACTED}" 

flag = flag.lstrip("lactf{").rstrip("}")

flagarray = [((random.randrange(2**10) >> 8) << 8) + ord(flag[i]) for i in range(len(flag))]

ec = DollarStore()

points = []
while len(points) < len(flagarray):
    x = random.randrange(p)
    point = ec.getPoint(x)
    if point != None:
        points.append(point)

s = scalar_mult(points[0], flagarray[0], ec)
for i in range(1,len(flagarray)):
    s += (scalar_mult(points[i], flagarray[i], ec))

print(f"s= {s}")

print(f"points = {points}")
# s= (4690331917760414380672348505790486524786128272326163170078478915876334878778,77902523131087061897126273610460347147805642819184490444996378236375931739511)

# points = [(48868244275342945713292068450286493306842109652612873048852850861527337784625,8598765896895208028227058726713353098258128734049351946507804225327296634514), (72658254142472216221352003377742816858998248904595208415554148006123670275598,71428807550814004521976397789820845661680868197262344890701351814974388342261), (67870089007566708724312416903523370462932434169535354040601985891516954713089,8943567664814248988234978385637474582139875658136599562153182844933110782161), (33253625948635661442757699647500419774784100109285386672321733886811106048412,12192737861983844212244996021850136772489630870822316368037176061423925074233), (66860062037424526223822695383825242848539148827022939438364758097578810377221,58417846450117166884245720025471073320694519590707170823524720597081409174976), (28494672393178906436249791305135018577103930778774058381902322150406763293156,62195276890799494520787073550388771924399268413246266294642567344115775718432), (6537035443546098222408014705048663302006517570643500213251743726265246911764,63349815264954414001975570394948853390727370840181019491330859064400691177034), (9320970269062399750695489734826172234568831562993926393303183822807296243087,34696165501221265426922128243581570921860165265147807824051427532585333222152), (18573558660261827041235280489756954152038727051914639466830055088004904233178,19919769712016625050600762893366674039791157427716018448797516577097120142300), (16615614708193334022500574592689709918593068922396962286039360740901902767297,60958319794367285409532630915520850753365486357306708351189641978639088395040), (83083247653266404965046108107297707899250352411953326131401506377288013650507,88351052151438822336155560751456315613347554340471433918143267841048354530206), (13931833861234698857264824825124064884725829615801172933808997361805649306770,1863009430945401243652911885817518397081699859060155426336485589307965515267), (82335726721747347474239651051504187390571418091882782437152555488102933140061,75024532808592482514720186660630997309420973593419858494992760319543418493327), (15679700475641029146383479082391061723840711201191220489551315259170835916116,4902015468380176276259510377701509023242706106231852614815501538737950056248), (69563107209744135957874607288632923528358557330713606279779688661831937343313,47637699504526623569498379978585572196126141235987754666684744952203096777656), (12240300385069346445384926360689199410381482418493148959106963671703717348546,23386458637256108310036365005044561845597767155973474723611711176033278672500), (2686945382892345707901179849163807293774497407910463972517367748359032899306,63993175447658077329987948939524654748779134053698498595737451593308819319039)]

橢圓曲線的$a, b$不難求，只要帶兩個點進去解方程就好了，會發現$a=b=0$，代表這是一個$singular\ curve$，我們構造一個函數$\phi(x, y) = x/y\ (mod\ p)$，那這個橢圓曲線的加法群會同態於經過映射後的加法群，$\phi(P+Q)=\phi(P)+\phi(Q)$，也就是橢圓曲線的離散對數直接簡化為了乘法的相乘。也就是原本的背包問題$x_1P_1+x_2P_2+...+x_nP_n=S$可以簡化為$x_1\phi(P_1)+x_2\phi(P_2)+...+x_n\phi(P_n)=\phi(S)$，也就是普通的背包問題。好啦，也不普通拉，因為他是模$p$下的背包問題，不過也只是在$lattice$中多加一列$p$進去，讓他可以進去線性組合。

from sage.all import *
from Crypto.Util.number import *
from solve_mod import *

points = [(48868244275342945713292068450286493306842109652612873048852850861527337784625,8598765896895208028227058726713353098258128734049351946507804225327296634514), (72658254142472216221352003377742816858998248904595208415554148006123670275598,71428807550814004521976397789820845661680868197262344890701351814974388342261), (67870089007566708724312416903523370462932434169535354040601985891516954713089,8943567664814248988234978385637474582139875658136599562153182844933110782161), (33253625948635661442757699647500419774784100109285386672321733886811106048412,12192737861983844212244996021850136772489630870822316368037176061423925074233), (66860062037424526223822695383825242848539148827022939438364758097578810377221,58417846450117166884245720025471073320694519590707170823524720597081409174976), (28494672393178906436249791305135018577103930778774058381902322150406763293156,62195276890799494520787073550388771924399268413246266294642567344115775718432), (6537035443546098222408014705048663302006517570643500213251743726265246911764,63349815264954414001975570394948853390727370840181019491330859064400691177034), (9320970269062399750695489734826172234568831562993926393303183822807296243087,34696165501221265426922128243581570921860165265147807824051427532585333222152), (18573558660261827041235280489756954152038727051914639466830055088004904233178,19919769712016625050600762893366674039791157427716018448797516577097120142300), (16615614708193334022500574592689709918593068922396962286039360740901902767297,60958319794367285409532630915520850753365486357306708351189641978639088395040), (83083247653266404965046108107297707899250352411953326131401506377288013650507,88351052151438822336155560751456315613347554340471433918143267841048354530206), (13931833861234698857264824825124064884725829615801172933808997361805649306770,1863009430945401243652911885817518397081699859060155426336485589307965515267), (82335726721747347474239651051504187390571418091882782437152555488102933140061,75024532808592482514720186660630997309420973593419858494992760319543418493327), (15679700475641029146383479082391061723840711201191220489551315259170835916116,4902015468380176276259510377701509023242706106231852614815501538737950056248), (69563107209744135957874607288632923528358557330713606279779688661831937343313,47637699504526623569498379978585572196126141235987754666684744952203096777656), (12240300385069346445384926360689199410381482418493148959106963671703717348546,23386458637256108310036365005044561845597767155973474723611711176033278672500), (2686945382892345707901179849163807293774497407910463972517367748359032899306,63993175447658077329987948939524654748779134053698498595737451593308819319039)]

p = 95773813056613526295315889615423014145567365190638271416026411091272805051097
F = GF(p)


x = [[points[0][0], 1], [points[1][0], 1]]
x = Matrix(F, x)
y = [points[0][1] ^ 2 - points[0][0] ^ 3, points[1][1] ^ 2 - points[1][0] ^ 3]
y = vector(F, y)

a, b = x.solve_right(y)

#a = b = 0

s= (4690331917760414380672348505790486524786128272326163170078478915876334878778,77902523131087061897126273610460347147805642819184490444996378236375931739511)

def phi(P: tuple):
    x, y = P
    return x * pow(y, -1, p) % p

phi_points = [phi(i) for i in points]
res = phi(s)


m = [[0 for i in range(len(phi_points) + 2)] for j in range(len(phi_points) + 2)]
for i in range(len(phi_points)):
    m[i][i] = 1
    m[i][-1] = int(phi_points[i])

m[-1][-1] = -int(res)
m[-2][-1] = p
m[-2][-2] = 1

m = matrix(ZZ, m)
m = m.LLL()

for i in m:
    if i[-1] == 0:
        k = ""
        for j in i:
            k += chr(j & ((1 << 8) - 1))
        print(k[:-2])