Giải thuần bú win các anh

# EBG
> SBG loves LCG, he also loves ECC. Thus he combined both of them and had EBG.
>
> Flag format: deadsec{}
>
> Updates:
>
> G = (211046629312383495603203047061896203904, 184028273928357402268058957910316279756)
> q.bit_length() = 168, a < p and b < p
> Yet another update: The handout given in the previous version was wrong apparently. It has been updated in the link now.

ebg_final_updated.sage

#!/usr/bin/env sage

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from random import randint
from secret import a, b, p, q, flag

Fp = GF(p)
Fq = GF(q)
E = EllipticCurve(Fp, [a, b])

class LCG:
    def __init__(self, seed, a, b):
        self.a, self.b = Fq(a), Fq(b)
        self.state = Fq(seed)

    def next_state(self):
        nxt = self.state * self.a + self.b
        self.state = nxt
        return int(nxt)

seed = randint(1, q)
lcg = LCG(seed, a, b)

collect, points = [], []

itr = 0
while len(collect) != 50:
    itr += 1
    y = lcg.next_state()
    P.<x> = PolynomialRing(Fp)
    try:
        x_ = (x^3+a*x+b-y^2).roots()[0][0]
        assert (x_, y) in E
        collect.append((itr, x_, Fp(y^2)))
        points.append((x_, Fp(y)))
    except:
        pass

qsz = q.bit_length()
#qsz = 168
qhi = q >> (qsz//2)
qlo = q & ((1 << (qsz//2)) - 1)

assert qhi.bit_length() == qsz//2 == 84
assert qlo.bit_length() == qsz//2

G = E.gens()[0]
#G = (211046629312383495603203047061896203904, 184028273928357402268058957910316279756)
hints = [
    sum([i[1]*G for i in points]).xy(),
    ((qhi^2 + (qlo^3)*69) * G).xy(),
    (((qhi^3)*420 + qlo^2) * G).xy()
]

for _ in range(10^18):
    lcg.next_state()

key = sha256(str(lcg.next_state()).encode()).digest()
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag.encode(), 16)).hex()

with open('output_69.txt', 'w') as f:
    f.write(f'{collect=}\n')
    f.write(f'{hints=}\n')
    f.write(f'{ct=}')

* **collect = [index, x_, $y^2 \mod p$]**
* **points = [x_, $y \mod p$]**
* **q** bị tách thành qhi và qlo
* **hint = [$\sum_{i=1}^{50} y_i \cdot G, (qhi^2 + 69 \cdot qlo^3) \cdot G, (420 \cdot qhi^3 + qlo^2) \cdot G$]**
* Seed sẽ biến đổi như sau
itr = 75
* Mục tiêu của chúng ta là khôi phục lại seed, để từ đó thu được key và giải mã ciphertext, qua hai phương trình sau

và lấy sqrt của cái này


1. Khôi phục a, b, q, p đã

1.1 Tìm p
* Từ phương trình ECC, ta sẽ thiết lập các phương trình sao cho có dạng k $\cdot$ p, và tìm gcd của chúng
nhân chéo lên ta được
khi đó num sẽ có dạng k $\cdot$ p, với i $\ne$ j $\ne$ k

1.2 Tìm a, b
a = $\frac{c_i - c_j}{x_i-x_j}$
b = $c_i$ - $ax_i$

1.3 Tìm q
* **q** bị tách thành **qhi** và **qlo** nên ta sẽ phải đi tìm 2 thành phần con trước
từ đây ta sẽ dlog để lấy được hệ số

khi đó ta thu được phương trình bên dưới, và chỉ cần biến đổi một chút để đưa về phương trình 1 ẩn để giải

a = 210201763039972449186286141207774547530
b = 227313635393666788814653401272488978271
p = 281966007153199959768827186794698649037
q = 201670286310674408750557303575927151106950475452573

2. Khôi phục $y_i$
* Lấy căn bậc hai $y_i^2 \mod p$ (từ collect), ta sẽ thu được một list chứa 50 các giá trị {$\pm y_i$}, và ta sẽ phải chọn trong mỗi list con giá trị đúng sao cho $\sum_{i = 0}^{49}y_i = sumpoint$
* Ta có thể thử nghĩ đến việc brute force $2^{50}$, nhưng điều đó gần như bất khả thi. Vì thế ta sẽ dùng meet in the middle, giảm xuống chỉ còn $2 \cdot 2^{25}$ lần brute force

ord = E.order()
Z = Zmod(ord)
y_sqrts = [list(map(Z, Fp(coll[2]).nth_root(2, all=True))) for coll in collect]

(Đưa về trường mod(ord) vì hint[0] là phép cộng điểm trên ECC)

script anh Kiệt (dựa vào bitmask để lấy giá trị):
VD: 1011
y_sqrt = [[1, 2], [3, 4], [5, 6], [7, 8]]
-> ys = [2, 3, 6, 8]

target = sumpoint

dic = {}

res = 0
for i in tqdm.tqdm(range(2**25)):
    sum_val = 0
    temp_i = i  # Use a temporary variable
    for b in range(25):
        sum_val += y_sqrts[b][temp_i & 1]
        temp_i >>= 1
    dic[target - sum_val] = i  # Store the original i

for i in tqdm.tqdm(range(2**25)):
    sum_val = 0
    temp_i = i  # Use a temporary variable
    for b in range(25):
        sum_val += y_sqrts[b + 25][temp_i & 1]
        temp_i >>= 1
    if sum_val in dic:
        print('[+] Found match:', i, dic[sum_val])
        res = (i << 25) + dic[sum_val]  # Fix operator precedence with parentheses
        break

* Nhưng việc brute force hết cả 50 giá trị y cũng không để làm gì, ta có một cách nhanh hơn (đa tạ anh Minh) là chỉ cần biết được giá trị y1, và y2 (tương ứng ys[0], ys[1] ở trên) là đã đủ để giải bài, khi đó ta chỉ cần thử 4 trường hợp $\pm y_1$, $\pm y_2$

ys = [266489192832751574677681454092403388186, 145384831519404601550835412047646430859]

3. Khôi phục seed và lấy key
* Ở hai bước biến đổi cuối, nếu ta tính d2 (int(-ad1_d2) % int(a)) thì ta sẽ thấy d2 <<< a => $\frac{d2}{a} < 1$
Và ad1 - d2 < q, nên ta sẽ được bỏ mod q, khi đó ta đưa về phương trình số nguyên
* Có d1 (lắp vào s0) thì ta sẽ có được seed

seed = ((t1 + d1 * p - b)) * pow(a, -1, q) % q

Sau đó cho cái seed đi qua 75 + $10^{18}$ + 1 vòng **next_state()**, hash cái đó thì ta sẽ thu được key

Code:

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

collect = [(1, 129878933909759106346680577632702938145, 64803144266873896929676879739596453119), (2, 47220119480700323979436440438758568517, 3893349004730020878867885140196143162), (3, 135697371446505401996219663500480702535, 189464444217229459768207485455773596223), (5, 186182129928944137532744753332646781304, 47505021787622187627054996066834279986), (7, 137954541206367141157174681214137207747, 112455404714804866219968592681230422581), (9, 175529667588843919176395264612892894471, 218843045729950688472274397830483106785), (11, 128862675358503122400510283922445116890, 138035279566900850637481257540805975414), (12, 97805691366916592363261988507134163988, 177720227234190472988958454612517881331), (13, 37320607457069782511660220198288107093, 255228446758895847755153926039894325307), (14, 100970458868941221421819357068618407949, 91676140984835531582333563847664881098), (15, 82201463401316898075841094019745395963, 260266487802082630684592031519201292651), (17, 5043114699373728171906139671315211181, 248425135022969603482075220432126198400), (18, 119640544102070570692595557127168058306, 268111579624200820306713336942009180324), (20, 110463588191793193141778331277649841048, 4797532526832775982058880463729523264), (22, 278760755999967948519718565533805994706, 136114112271686814800164621343407719288), (25, 110672302544743724380319906762024264356, 68680445916196630263730189447972347932), (26, 240750825991734313849435188671112102063, 140607262286812515787062677112161357228), (27, 212077470771446192506159056893734649290, 139208919729552913218784867774523882872), (28, 137637831635933080402772142835363827980, 47952484402249020094794225674618712649), (29, 192994530647669979393287183382819077102, 167677548999714807450176064433600746494), (31, 14853647048237317965187228947005266698, 102841562937362181108723194061026812490), (34, 240107202043865516942839134775325798950, 2686453816150521537647060532916993425), (36, 73208029507938820821678102306884024515, 90830604924044189991821688941618008840), (40, 25688624474081509405065828826894970251, 263114103038651382917528468474421508970), (41, 78444213858637888025402155644962081478, 1227650586741174850554304777128981999), (43, 272942766489216606077566698464127091018, 137920053698013650330067140095258036186), (44, 65798204149688203259735816406425062061, 117621237377924339748816089574759379471), (45, 131164003547852147184888525175195630124, 14904081683490860466570512910215589498), (46, 198466350447032123061643384415553595098, 78673541778689512186828743280254957513), (47, 197456491312964552004328416921871060830, 230552334439900737955532832928073720340), (51, 241080610190893259502582771341275897638, 219241528921916095074065425829699162686), (52, 148459555599428230670439700969600524001, 37542155356992331599174012814840216579), (53, 88059495731975372270014306339160333953, 108930682089148605379197113672692244026), (54, 115218259744290243775271950656221479749, 24723167154472613578408645343075852359), (55, 207399571896461152245542849222195688602, 21366453255883339351183514872583156635), (56, 162307501083695252772393446813067625372, 191168518546056204278865539774903892632), (58, 100929302163253206689572191975387995056, 105655790195719548802588224439073087010), (60, 12467572025112492680780827851502701102, 54871130437582472120151895946144021439), (61, 205044598922926919923814282423301960892, 185500343153585563548380780384458785364), (62, 101024911549455856285493310072738139255, 76426169921217098398822065726722097433), (63, 231246082087521230014357912014877077244, 199878288912218183844553469641314538467), (65, 267247319359974237615551546666284905313, 167770265994317786428930391203034793125), (66, 271656252329029052888122578423472817324, 162845261167206139764057460246628847647), (67, 11194166780031032504314879126098171978, 100571427681629308118238960034711766909), (69, 99610796406662719216184922009261055141, 139125655131793785350771137873823884055), (70, 268494533197282920070461981868984975932, 158245833042764716130784905936126410852), (71, 172741136840482342263614648174626917928, 112917916923656776758887751909500383428), (72, 154815184807577433299929253616883247343, 101386650699861829992568531051280621901), (74, 210025894946768524275430773071874322579, 235998024821648094726633123862575190685), (75, 134368050189744696586177857951066985541, 178126351653628059845405725796083335991)]
hints = [(5792995813021327870769979628676579982, 143804545079278507495499534347219572515), (243532848166469089179921880480016489388, 63410286149522930076665255263173251947), (241284753827628767067447517837810323910, 208806014494840714718680309755272416222)]
ct = '0052c609180b701244836c4e269748ca72c3e89e7897a8a10a11c047ac09adb76f024fa410f8869fc8381439e59c0fabd97b99a536bba33bfce7542e47b53f1d55fa2f55a8333beda85f51e5c71e1667cd22a0bbd3219895f28cebef42c622d2'

class LCG:
    def __init__(self, seed, a, b):
        self.a, self.b = Fq(a), Fq(b)
        self.state = Fq(seed)

    def next_state(self):
        nxt = self.state * self.a + self.b
        self.state = nxt
        return int(nxt)

# Find P
vals = []
for stt, (i, xi, y21) in enumerate(collect):
    for (j, xj, y22) in collect[stt+1:]:
        ci, cj = y21 - xi**3, y22 - xj**3  # fix ^ to **
        for (k, xk, y23) in collect:
            if k in (i, j): continue
            ck = y23 - xk**3  # fix ^ to **
            vals.append(abs((ci - cj) * (xj - xk) - (cj - ck) * (xi - xj)))

p = gcd(vals)

# Find a, b
a = ((collect[0][2] - collect[0][1]**3) - (collect[1][2] - collect[1][1]**3)) / (collect[0][1] - collect[1][1]) % p
b = (collect[0][2] - collect[0][1]**3 - a * collect[0][1]) % p

Fp = GF(p)
E = EllipticCurve(Fp, [a, b])
G = E.gens()[0]

# Recover q
hint0 = E(hints[0])
hint1 = E(hints[1])
hint2 = E(hints[2])

ord = E.order()

sumpoint = hint0.log(G)
k1 = hint1.log(G)
k2 = hint2.log(G)

P = PolynomialRing(Zmod(ord), 'qhi')
qhi = P.gen()
f =  (k1 - qhi**2) ** 2 - 69 ** 2 * (k2 - 420 * qhi ** 3) ** 3
for root in f.roots(multiplicities=False):
    if int(root).bit_length() == 84:
        qhi = int(root)
        
        P = PolynomialRing(Zmod(ord), 'y')
        y = P.gen()
        g = 420 * qhi ** 3 + y ** 2 - k2
        for root1 in g.roots(multiplicities=False):
            if int(root1).bit_length() == 84:
                qlo = int(root1)
                q = (qhi << 84) + qlo
                assert is_prime(q) == True

Fq = GF(q)
Z = Zmod(ord)
y_sqrts = [list(map(Z, Fp(coll[2]).nth_root(2, all=True))) for coll in collect]

ans = [266489192832751574677681454092403388186, 145384831519404601550835412047646430859]

t1 = ans[0]
t2 = ans[1]

ad1_d2 = ((t2 - (a * t1 + b)) % q) * pow(p, -1, q) % q
d2 = (-ad1_d2) % a
d1 = ad1_d2 // a + 1
seed = ((t1 + d1 * p - b)) * pow(a, -1, q) % q

lcg = LCG(seed, a, b)
for i in range(75):
    x = lcg.next_state()
mat = matrix(Fq, [[a,b], [0,1]])
v = vector(Fq, [lcg.state, 1])
state = int((mat^ (10 ^ 18 + 1) * v)[0])
key = sha256(str(state).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
ct = bytes.fromhex(ct)
pt = unpad(cipher.decrypt(ct), 16)  
print(pt)

flag: deadsec{y0u_p40b4bly_7h1nk_7h15_w45_1n5p1r3d_f40m_cH1m3r4_w311...y0u_a43_n07_wr0n6_3n71431Y}

# imrul kAES

> Imrul Kayes may not always be in the playing XI, but somehow, he's found himself inside an AES encryption scheme. We don't know how. He doesn't know how. But he's in. And he’s trolling hard.
> Instead of swinging the bat, Imrul is now swinging bytes, and dropping more blocks than a DJ with Parkinson’s.

server:

#!/usr/local/bin/python
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES

print('Yo welcome to my sign as a service...')

p, q = getPrime(512), getPrime(512)
e = 12389231641983877009741841713701317189420787527171545487350619433744301520682298136425919859970313849150196317044388637723151690904279767516595936892361663
n = p * q
d = pow(e, -1, (p - 1) * (q - 1))

k = get_random_bytes(16)
cipher = AES.new(k, AES.MODE_ECB)

flag = open('flag.txt', 'rb').read()
assert len(flag) <= 50
ct = pow(bytes_to_long(flag), e, n)

print(ct)

while 1:
	try:
		i = int(input("Enter message to sign: "))
		assert(0 < i < n)
		print(cipher.encrypt(pad(long_to_bytes(pow(i, d, n) & ((1<<512) - 1)), 16)).hex())
	except:
		print("bad input, exiting")

* Đầu tiên, đề không cho n sẵn nên ta phải tìm. Ta sẽ sử dụng binary search, cận dưới là $2^{1023}$ còn cận trên là $2^{1024}$ (n ~ $2^{1024}$), ta sẽ dựa vào điều kiện 0 < i < n.
* RSA có tính chất $E(m1) \cdot E(m2) = E(m1 \cdot m2) \mod \ n$
* Việc chỉ lấy 512 bit cuối có vẻ khả nghi, ta có thể khai thác bằng cách dịch $bit_i$ lên đầu (bit thứ 512/index 511) để từ đó recover plaintext.
* Ta sẽ tận dụng bằng cách gửi cho server một plaintext (partial/existing), và so sánh khi gửi ciphertext (đã dịch bit) xem có trùng nhau không. Nếu trùng tức là $bit_i$ là 0 (do partial khi dịch ở đầu sẽ luôn là 0), còn không thì sẽ là 1.

Ta thu được công thức sau:
Chỉ thu 512 bit cuối tương đương phép toán mod $2^{512}$, ta cộng $2^{512}$ với partial để đảm bảo điều kiện 0 < i, vì partial ban đầu là 0, và $2^{512}$ khi mod $2^{512}$ cũng k ảnh hưởng gì đến partial của chúng ta.

Code:

#!/usr/local/bin/python
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from pwn import *
from tqdm import tqdm

e = 12389231641983877009741841713701317189420787527171545487350619433744301520682298136425919859970313849150196317044388637723151690904279767516595936892361663
r = remote('nc.deadsec.quest', 31050)
r.recvline()
ct = int(r.recvline())
print(ct)


def find_n():
    hi = 1 << 1024
    lo = 1 << 1023
    while hi > lo:
        print(lo - hi)
        mid = (hi + lo) // 2
        r.sendlineafter(b'Enter message to sign:', str(mid).encode())
        res = r.recv()
        if res != b'bad input, exiting':
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

n = find_n()

def encrypt(pt):
    return pow(pt, e, n)

def encrypt_mul(mul, c2):
    return (encrypt(mul) * c2) % n


def sending(msg):
    r.sendlineafter(b'Enter message to sign:', str(msg).encode())
    return r.recvline()

def guess_bit(i, existing):
    mul = pow(2, 511 - i, n)
    if sending(encrypt_mul(mul, ct)) == sending(encrypt_mul(mul, encrypt((1 << 512) + existing))):
        return existing
    else:
        return (1 << i) + existing

pt = 0 
for i in tqdm(range(400)):
    pt = guess_bit(i, pt)

print(long_to_bytes(pt))

flag: DEAD{p4ddin6_04aC13_477aCk!_ad6c2927cb2557ed}

# Infant RSA
> Mandatory RSA challenge

infant_rsa.py

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p, q = getPrime(512), getPrime(512)
n = p * q
e = 65537
phi = (p-1) * (q-1)
hint = phi & ((1 << 500)-1)

m = bytes_to_long(flag)
c = pow(m, e, n)

print(f'{n=}')
print(f'{c=}')
print(f'{hint=}')
#n=144984891276196734965453594256209014778963203195049670355310962211566848427398797530783430323749867255090629853380209396636638745366963860490911853783867871911069083374020499249275237733775351499948258100804272648855792462742236340233585752087494417128391287812954224836118997290379527266500377253541233541409
#c=120266872496180344790010286239079096230140095285248849852750641721628852518691698502144313546787272303406150072162647947041382841125823152331376276591975923978272581846998438986804573581487790011219372437422499974314459242841101560412534631063203123729213333507900106440128936135803619578547409588712629485231
#hint=867001369103284883200353678854849752814597815663813166812753132472401652940053476516493313874282097709359168310718974981469532463276979975446490353988

* Bài này là một bài thuần RSA, nhưng để lộ 500 LSB của phi (hint = phi mod $2^{500}$)
(p+q) mod $2^{500}$ tương đương
Vì vậy ta chỉ cần brute force 12 - 13 MSB của (p+q) rồi cộng với phần retain chính là (-hint + 1 + n) % (1 << 500) sẽ ra được S = p+q
* Sau đó giải phương trình bậc 2: $x^2 - 4Sx + P = 0$ (S = p + q, P = p * q = n).

do p, q là số nguyên nên delta chắc chắn phải là số chính phương, từ đó ta sẽ tìm lại được p, q.

Code:

from Crypto.Util.number import long_to_bytes
from tqdm import tqdm
from math import isqrt

n = 144984891276196734965453594256209014778963203195049670355310962211566848427398797530783430323749867255090629853380209396636638745366963860490911853783867871911069083374020499249275237733775351499948258100804272648855792462742236340233585752087494417128391287812954224836118997290379527266500377253541233541409
c = 120266872496180344790010286239079096230140095285248849852750641721628852518691698502144313546787272303406150072162647947041382841125823152331376276591975923978272581846998438986804573581487790011219372437422499974314459242841101560412534631063203123729213333507900106440128936135803619578547409588712629485231
hint = 867001369103284883200353678854849752814597815663813166812753132472401652940053476516493313874282097709359168310718974981469532463276979975446490353988
e = 65537

base = (-hint + 1 + n) % (1 << 500)
for i in range(1 << 12, 1 << 13):
    S = base + (i << 500)

    D = S * S - 4 * n # Delta ^ 2 - 4ac (a = 1, c = n)
    if D < 0:
        continue
    dealta = isqrt(D)   
    if dealta * dealta == D:
        x1 = (S + dealta) // 2
        x2 = (S - dealta) // 2
        if x1 * x2 == n:
            p = x1
            q = x2
            break

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

flag: deadsec{1_w0nd3r_1f_7h15_p40bl3m_c0u1d_b3_s0lv3d_1f_m0r3_b1t7_w343_unKn0wn}

Ta có: $n = p \cdot q$
\begin{align}
phi &= (p - 1) \cdot (q-1) \\
&= pq \ - (p+q) + 1 \\
&= n - (p+q) + 1
\end{align}

\begin{align}
phi &= hint \ mod \ 2^{500} \\
n - (p+q) + 1 &= hint \ mod \ 2^{500} \\
p+q &= (n -hint +1) \ mod \ 2^{500}
\end{align}

`p, q = getPrime(512), getPrime(512)`

$\Rightarrow p + q \in (2^{512}, 2^{513})$

 hint = phi & ((1 << 500)-1)
 hint = phi mod 2^500

bit thứ:
(512) 511 510 ... 500 / 499 498 ... 1 0
(cắt)