### lalala

``Source.py``

from random import randint
from re import search

flag = "bi0sctf{ %s }" % f"{randint(2**39, 2**40):x}"

p = random_prime(2**1024)
unknowns = [randint(0, 2**32) for _ in range(10)]
unknowns = [f + i - (i%1000)  for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]

output = []
for _ in range(100):
    aa = [randint(0, 2**1024) for _ in range(1000)]
    bb = [randint(0, 9) for _ in range(1000)]
    cc = [randint(0, 9) for _ in range(1000)]
    output.append(aa)
    output.append(bb)
    output.append(cc)
    output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p)

print(f"{p = }")
print(f"{output = }")

Bài này flag được ẩn trong **unknowns** bao gồm 10 giá trị với 100 vòng for :

Ta hãy để ý

output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p)

Ở vòng for đầu tiên ta sẽ có coefficient $coeff_i$ là:

$$coeff_0 * unknown_{b0}^2 * unknown_{c0}^3 + coeff_0 * unknown_{b1}^2 * unknown_{c1}^3 + coeff_0 * unknown_{b2}^2 * unknown_{c2}^3 + ... + coeff_0 * unknown_{b9}^2 * unknown_{c9}^3 + sum(aa_0) = output_0 $$

Với $b, c \in [0,9]$

Ta sẽ dựng ma trận như sau:

$$
\begin{equation*}
\begin{bmatrix}
coeff_0.b_0.c_0 & coeff_0.b_0.c_1 & ... & coeff_0.b_9.c_9 \\
coeff_1.b_0.c_0 & coeff_1.b_0.c_1 & ... & coeff_1.b_9.c_9 \\
\vdots & \vdots & & \vdots \\
coeff_{99}.b_0.c_0 & coeff_{99}.b_0.c_1 & ... & coeff_{99}.b_9.c_9 \\
\end{bmatrix}
=
\begin{bmatrix}
output_0 - sum(aa_0) \\
output_1 - sum(aa_1) \\
\vdots \\
output_{99} - sum(aa_{99})
\end{bmatrix}
\end{equation*}
$$

Giải ma trận bằng sage ta thu được 100 nghiệm của $unknown_0^2 * unknown_0^3$ đến $unknown_9^2 * unknown_9^3$

Thu được 10 giá trị của $unknown_0^5$ đến $unknown_9^5$ ta chỉ cần căn bậc 5 của $unknown$ và chia dư cho 1000 để khôi phục lại flag.

``solved.py``

from sage.all import *

p = ...
output = ...

m = []
y = []
vars = [[i, j] for i in range(10) for j in range(10)]

for i in range(0, len(output), 4):
    aa = output[i]
    bb = output[i+1]
    cc = output[i+2]
    rs = output[i+3]
    
    coeffs = [0]*100

    # sum([aa[i] + unknowns[bb[i]]^2 + unknowns[cc[i]]^3 for i in range(1000)])
    sum = 0

    for j in range(1000):
        sum = (sum + aa[j]) % p
        temp = [bb[j], cc[j]]
        coeffs[vars.index(temp)] += 1

    y.append((rs-sum) % p)
    row = coeffs
    m.append(row)

l = len(m)
m = Matrix(GF(p), m)
y = vector(GF(p), y)

ans = list(m.solve_right(y))
print(ans)

flag = []
for i in range(100):
        u = gmpy2.iroot(int(ans[i]), 5)
        print(u)
        if u[1] == True:
            u = u[0] % 1000
            flag.append(u)
            print(u)
            print(flag)
print("".join([bytes([c]).decode() for c in flag]))

### challengename

``chall.py``

from ecdsa.ecdsa import Public_key, Private_key
from ecdsa import ellipticcurve
from hashlib import md5
import random
import os
import json

flag = open("flag", "rb").read()[:-1]

magic = os.urandom(16)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = ###REDACTED###
b = ###REDACTED###
G = ###REDACTED###

q = G.order()

def bigsur(a,b):
    a,b = [[a,b],[b,a]][len(a) < len(b)]
    return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

def bytes_to_long(s):
    return int.from_bytes(s, 'big')

def genkeys():
    d = random.randint(1,q-1)
    pubkey = Public_key(G, d*G)
    return pubkey, Private_key(pubkey, d)

def sign(msg,nonce,privkey):
    hsh = md5(msg).digest()
    nunce = md5(bigsur(nonce,magic)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
    return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})

def enc(privkey):
    x = int(flag.hex(),16)
    y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
    F = ellipticcurve.Point('--REDACTED--', x, y)
    Q = F * privkey.secret_multiplier
    return (int(Q.x()), int(Q.y()))

pubkey, privkey = genkeys()
print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
print("Encrypted flag:",enc(privkey))

# Public key: (99122053878685444817852582103585646482441799670468212049632161370423019963573, 49681263796445807694244738028189208770171168855624587289690892802435841601423)
# Encrypted flag: (22455982735997721923198309515515820680837002550923840212531066823876108860098, 49955453626898315794129063911602706078234097783588068635922441060010795905908)

nonces = set()

for _ in '01':
    try:
        msg = bytes.fromhex(input("Message: "))
        nonce = bytes.fromhex(input("Nonce: "))
        if nonce in nonces:
            print("Nonce already used")
            continue
        nonces.add(nonce)
        print(sign(msg,nonce,privkey))
    except ValueError:
        print("No hex?")
        exit()

Chall này tôi nhận được 2 điểm từ đường cong: Public key là **dG** và Encrypt flag là **dF**

Từ 2 điểm trên ta có

$$y_1^2 = x_1^3 + ax_1 + b$$

$$y_2^2 = x_2^3 + ax_2 + b$$

$$(y_1^2 - y_2^2) - (x_1^3 - x_2^3) = a(x_1-x_2)$$

Ta có a, b được tính bằng

sage: p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
....: x1 = 5683931425003308547431366441507256115275884385439908235960128031931809224426
....: y1 = 103504881232349341101391567415775837049449360982146318680463741565720272773736
....: x2=  87512180974071789579460785103236717308728056532898014966250203004749159040100
....: y2 = 5463487042701233117805115066761912607366330124308643383693672326808102345649
....: a=Mod(((y1^2 - y2^2)-(x1^3 - x2^3))*inverse_mod((x1-x2),p),p)
....: b=Mod(y2^2 - x2^3 - a*x2, p)
....: a, b
(115792089210356248762697446949407573530086143415290314195533631308867097853948,
 41058363725152142129326129780047268409114441015993725554835256314039467401291)
sage:

Ta có curve của bài

sage: p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
....: a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
....: b =  41058363725152142129326129780047268409114441015993725554835256314039467401291
....: E = EllipticCurve(GF(p), [a, b])
....: E.order()
115792089210356248762697446949407573529996955224135760342422259061068512044369
sage:

Ở đây hàm **bigsur** trông rất dài nhưng thực chất nó là phép xor. Nếu chúng ta chọ **nonce1 = b"\x00"** và **nonce2 = b"\x00\x00"** thì sẽ có thể lấy cùng một **nunce** trong hàm **sign()** mà server ký message

Để tìm lại private key **d** tôi sử dụng [️ECDSA Nonce Reuse Attack](https://crypto.stackexchange.com/questions/71764/is-it-safe-to-reuse-a-ecdsa-nonce-for-two-signatures-if-the-public-keys-are-diff)

Chúng ta có **r1 = r2 = R**, **(r1, s1)** là chữ ký của $m_1$, **(r2, s2)** là chữ ký của $m_2$ khi đó chúng ta có

$$s_1 * k - H(m_1) = s_2 * H(m_2) = R * privatekey$$

$$k = \frac{s_1 - s_2}{H(m_1) - H(m_2)}$$

$$privatekey = \frac{s_1 * k - H(m_1)}{R}$$

Khi có **privatekey** ta dễ dàng tìm lại **F** bằng phép tính $F = private^
{-1} * Q$

``solved.sage``

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

def inverse_mod(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def recover_private_key(H_m1, H_m2, r, s1, s2, q):
    H_m1_int = bytes_to_long(md5(H_m1).digest())
    H_m2_int = bytes_to_long(md5(H_m2).digest())
    r_inv = inverse_mod(r, q)
    d = ((inverse_mod(s1 - s2, q) * (H_m1_int * s2 - H_m2_int * s1) % q) * r_inv) % q
    return d

        
# vanluongkma@Nitro:~$ nc 13.201.224.182 30773
x1, y2 = (5683931425003308547431366441507256115275884385439908235960128031931809224426, 103504881232349341101391567415775837049449360982146318680463741565720272773736)
x2, y2 =  (87512180974071789579460785103236717308728056532898014966250203004749159040100, 5463487042701233117805115066761912607366330124308643383693672326808102345649)
# Message: 4b435343
# Nonce: 00
# {"msg": "4b435343", "r": "0x634c264ed704268912a6770587a38659be6b14c02276b7b8a357663aa4b807e", "s": "0xee0223546119ce0300f129d9b3df224805b58eb2d6974ff43f6ba9cad1b774cb"}
# Message: 4b435343435446
# Nonce: 0000
# {"msg": "4b435343435446", "r": "0x634c264ed704268912a6770587a38659be6b14c02276b7b8a357663aa4b807e", "s": "0xab628f493d21b15f1ae5626f3c08e6533942ffd558d62d9f3470765119ab4b04"}
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(GF(p), [a, b])
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
E.set_order(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1)
n = int(E.order())

H_m1 = b"KCSC"
H_m2 = b"KCSCCTF"

r = 0x634c264ed704268912a6770587a38659be6b14c02276b7b8a357663aa4b807e  
s1 = 0xee0223546119ce0300f129d9b3df224805b58eb2d6974ff43f6ba9cad1b774cb 
s2 = 0xab628f493d21b15f1ae5626f3c08e6533942ffd558d62d9f3470765119ab4b04 
q = int(E.order())


d = recover_private_key(H_m1, H_m2, r, s1, s2, q)
print(d)

d_inverse=inverse_mod(d,n)
Q = E(x2, y2)
F = d_inverse*Q
print(long_to_bytes(int(F[0])))

### rr

``chall.py``

from Crypto.Util.number import *
from FLAG import flag
from random import randint

flag = bytes_to_long(flag)
n = ..
rr = ..
ks = [randint(0, rr**(i+1)) for i in range(20)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), (1<<7)-1, n)
c2 = pow(flag, (1<<16)+1, n)
ks = [pow(69, k, rr**(i+2)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")

Challenge cho chúng ta 2 bản mã $c_1, c_2$ của **flag**

$$
\begin{cases}
c_1 = (\sum_{i=1}^{20} k_i flag^i)^{127} \mod n \\
c_2 = flag^{65537} \mod n \\
\end{cases}
$$

Những hệ số $k_1, k_2, k_3, ... , k_{20}$ đã biết, chúng ta cần xây dựng đa thức $$f(x) = (\sum_{i=1}^{20} k_i x^i)^{127} - c_1$$ $$g(x) = x^{65537} - c_2$$

Chúng ta có thể tìm GCD của 2 đa thức **f(x), g(x)** để recover lại flag

Nhưng mà hệ số $k_i$ cũng đã được mã hóa theo phương trình sau:

$$K_i = 69 ^ {k_i} \mod p^{i+1}, k_i < p^{i}, i \in [1...20]$$

Với i = 0

$$K_1 = 69^{k_1} \mod p^2, k_1 < p$$

Nâng cả 2 vế lũy thừa **q**

$$K_1^q = (69^q)^{k_1} \mod p^2$$

Với định lý fermat nhỏ( $a^{\phi(p)} = p * k + 1$) ta có :

$$\underbrace{(c_1 * p + 1)}_{K_1^q \mod p^2} = {\underbrace{(d_1 * p + 1)}_{69^q \mod p^2}}^{k_1} \mod p^2$$

Khai triển [Binomial theorem](https://en.wikipedia.org/wiki/Binomial_theorem) cho vế phải ta có

$$c_1 * p + 1 = \binom{k_1}{0} 1^n (d_1 * p)^0 + \binom{k_1}{1}1^{n-1}(d_1p)^1 \underbrace{ + \cdots }_{0 \mod p^2} \mod p^2$$

Thu được

$$c_1p + 1 = 1 + d_1k_1p \mod p^2$$

$$\implies c_1 = d_1 * k_1 \mod p$$

$$\implies k_1 = c_1 * d_1 ^ {-1} \mod p$$

Ta đã giải quyết được discrete logarithm trên $Z_{p^2}$ tiếp theo là $Z_{p^r}$

$$y = g^x \mod p^{r+2}, \ x < p^{(r+1)}$$

Đặt $x = x_r * p^r + ... + x_1 * p^1 + x_0 = p - 1$ ta khai triển như sau

$$y^q = (g^q)^x \mod p^{r+2}$$

Tương tự như trên thu được

$$=> c_{1} = d_1 * x{1} \mod \ p$$

$$=> x_{1} = c_{1} * d_{1}^{-1} \mod \ p$$

Như vậy ta đã recover được $x_0$, biến đổi phương trình như sau

$$y^q = (g^q)^x \mod p^{r+2}$$

$$y^q = (g^q)^{({x_{r} \ p^{r} + … + x_{1} \ p + x_{0}})} \mod p^{r+2}$$

$$(y \ g^{-x_{0}})^q = (g^q)^{p \ ({x_{r} \ p^{r} + … + x_{2} \ p + x_{1}})} \mod p^{r+2}$$

đặt: $y’ = (y \ g^{-x_{0}})$ và $g’ = g^p$

Tương tự như trên ta sẽ thu được $x_1$. Lặp lại đến khi $g^{p^{r+1} \ q} = 1 \mod p^{r+2}$, ta sẽ thu được x hoàn chỉnh.

``solved_1.py``

from data import ks, c1, c2, rr, n
from Crypto.Util.number import *

def binomial_dlog_sub(y,g,p,q,r=2):
    C = ZZ(pow(y, q, p^r))
    B = ZZ(pow(g, q, p^r))
    kx = (C - 1)//p^(r-1)
    k =  (B - 1)//p^(r-1)
    x = ZZ(kx * pow(k, -1, p) % p)
    return x

def binomial_dlog(y,g,p,q,r):
    assert r >= 2
    y = ZZ(y)
    g = ZZ(g)
    xs = []
    for i in range(r-1):
        xi = binomial_dlog_sub(y, g, p, q, i + 2)
        xs.append(xi)
        y = ZZ(y * pow(g,-xi,p^r) % p^r)
        g = ZZ(pow(g,p,p^r))
    return ZZ(xs, p)
    
def pgcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

p = rr
q = rr - 1

coeffs = []
g  = 69
for rd in range(20):
    y = ks[rd]
    r = rd + 2
    x = binomial_dlog(y,g,p,q,r)
    print(f"[+] rounds {rd} check ", ZZ(pow(g, x, p^r)) == y)
    coeffs.append(x)

PR.<x> = PolynomialRing(Zmod(n))
f1 = (sum(k*x**i for i, k in enumerate(coeffs)))^((1<<7)-1) - c1
f2 = x^(65537) - c2
f0 = pgcd(f1,f2)
print(long_to_bytes(int(- f0.constant_coefficient() % n)))

Cách khác ta sẽ recover lại $k_i$ bằng bài toán trên trường số p-adic

``solved_2.py``

import sys
sys.path.append("/mnt/c/Users/dinhv/Documents/Tool/crypto-attacks/")
from sage.all import *
from data import c1,c2,ks,n,rr
from Crypto.Util.number import *
from shared.polynomial import fast_polynomial_gcd

def dlog_on_Zp(p, exponent_of_p, g, y):
    Z = Zp(p, prec=exponent_of_p)
    x_Z = Z(y).log() / Z(g).log()
    x = x_Z.lift()
    return x

sol = []
for i,k in enumerate(ks):
    tmp = dlog_on_Zp(rr, i+2, 69, k)
    sol.append(tmp)
    print("Found", tmp)

P = PolynomialRing(Zmod(n), names='x')
(x,) = P.gens()

g1 = sum(k*x**i for i, k in enumerate(sol))**((1<<7)-1) - c1
g2 = x**65537 - c2
f = fast_polynomial_gcd(g1,g2)
print(long_to_bytes(int(f.small_roots()[0])))

#### Reference

[1] [crypto-attack](https://github.com/jvdsn/crypto-attacks/blob/master/shared/polynomial.py)

[2] Thanks [nomorecaffeine](https://github.com/nguyen-xuan-quoc)

[3] Thanks [tl2cents](https://tanglee.top/2024/02/27/bi0sCTF-2024-Crypto-Writeups/)

### daisy_bel

``chall.py``

from Crypto.Util.number import *
from FLAG import flag

p = getPrime(1024)
q = getPrime(1024)
n = p*q
c = pow(bytes_to_long(flag), 65537, n)

print(f"{n = }")
print(f"{c = }")
print(f"{p>>545 = }")
print(f"{pow(q, -1, p) % 2**955 = }")

"""
n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349
p>>545 = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
pow(q, -1, p) % 2**955 = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858
"""

Với bài này ta có

$$u=q^{-1} mod p$$

$$uq = 1 + kp$$

$$uq^2 = q + kpq$$

$$uq^2 - q = 0 mod n$$

Chúng ta có 545 high bits của p ($p_h$) và 955 low bits của ($q_l^{-1}$) = $q^{-1} mod (p)$

Từ thông tin trên chúng ta có $f(x,y) = (u_h * 2^{955} + u_l) * (q_h * 2^{545} + q_l)^2 - (q_h * 2^{545} + q_l) = 0 \ mod \ (n)$

Chúng ta sẽ sử dụng thuật toán coppersmith để tìm ($q_l, u_h$)

Ở đây ta sẽ dùng [**coppersmith multivariate heuristic**](https://github.com/kionactf/coppersmith/blob/main/coppersmith_multivariate_heuristic.py) để giải quyết bài toán này.

``solved.sage``

from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic
from lll import *
from sage.all import *
from Crypto.Util.number import *
import sys
sys.path.append("/coppersmith")


n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349

msb_p = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
lsb_u = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858
msb_q = (n // (msb_p << 545))

x, y = PolynomialRing(Zmod(n), "x, y").gens()

f = (y * 2**955 + lsb_u) * (msb_q + x)**2 + (msb_q + x)

ans = coppersmith_multivariate_heuristic(f, [2**545, 2**69], beta = 1)
lsb_q, msb_u = ans[0]

qq = msb_q + x
q = int(qq(lsb_q))
p = n // q
d = pow(65537, -1, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))