HackTM CTF Quals 2023 | kaitenzushi - crypto-writeup-public

#HackTM_CTF_Quals_2023

#good_challenges_2023

from math import gcd
from Crypto.Util.number import bytes_to_long, isPrime

from secret import p, q, x1, y1, x2, y2, e, flag

# properties of secret variables
assert isPrime(p) and p.bit_length() == 768
assert isPrime(q) and q.bit_length() == 768
assert isPrime(e) and e.bit_length() == 256
assert gcd((p - 1) * (q - 1), e) == 1
assert x1.bit_length() <= 768 and x2.bit_length() <= 768
assert y1.bit_length() <= 640 and y2.bit_length() <= 640
assert x1 ** 2 + e * y1 ** 2 == p * q
assert x2 ** 2 + e * y2 ** 2 == p * q

# encrypt flag by RSA, with xor
n = p * q
c = pow(bytes_to_long(flag) ^^ x1 ^^ y1 ^^ x2 ^^ y2, e, n)
print(f"{n = }")
print(f"{c = }")

# hints 🍣
F = RealField(1337)
x = vector(F, [x1, x2])
y = vector(F, [y1, y2])
# rotate
theta = F.random_element(min=-pi, max=pi)
R = matrix(F, [[cos(theta), -sin(theta)], [sin(theta), cos(theta)]])
x = R * x
y = R * y
print(f"{x = }")
print(f"{y = }")

RSA だが、どちらかというと数学っぽい？

以下のようなOng-Schnorr-Shamir Digital Signature Schemeを彷彿とさせる（しかし関係ない）制約があるが、更にこれを回転させた $X_1, X_2, Y_1, Y_2$ が与えられている

$\begin{cases}x_1^2 + ey_1^2 = n \ x_2^2 + ey_2^2 = n \end{cases}$

回転

$\begin{pmatrix} X_1 & Y_1 \ X_2 & Y_2 \end{pmatrix} = \begin{pmatrix} cos(\theta) & sin(-\theta) \ sin(\theta) & cos(\theta) \end{pmatrix} \begin{pmatrix} x_1 & y_1 \ x_2 & y_2 \end{pmatrix}$

考えることがいっぱいある。これらの問題をどの順番で解いたら良いかも難しい

$X_1, X_2, Y_1, Y_2$ から $x_1, y_1, x_2, y_2$ を求められるのか？
$X_1, X_2, Y_1, Y_2, n$ から $e$ をもとめられるのか？
$x_1, y_1, x_2, y_2, n, e$ で $n$ を素因数分解できるのか？

また、一見して $\theta$ を求めるのは無理そうに見える

[** $X_1, X_2, Y_1, Y_2, n$ から $e$ をもとめる]

性質の2式を足して $(x_1^2 + x_2^2) + e(y_1^2 + y_2^2) = 2n$ とすると、 $x_1^2 + x_2^2 = X_1^2 + X_2^2$ が成り立つので、 $e = \frac{2n - (X_1^2 + X_2^2)}{Y_1^2 + Y_2^2}$
あるいは以下の探索で先に $x_1, y_1, x_2, y_2$ を求められるのでそれでも良い

[** $x_1, y_1, x_2, y_2$ を求める]

$X_1, X_2, Y_1, Y_2$ は実数なので実数を見たら単調性を疑って探索するでやってみると意外と $\theta$ が求まるとか求まらないとか。
- 詳しくは https://genni21.github.io/cryptography/2023/02/19/wtlctf.html とかを見て
普通にやるなら $\sin\theta, \cos\theta$ を変数として置いて resultant を使うと良いという感じらしい
``` F = RealField(1337) PR.<cos_theta, sin_theta, x1, x2, y1, y2> = PolynomialRing(QQ) f1 = (x1cos_theta + x2sin_theta)² + e(cos_thetay1 + sin_thetay2)² - n f2 = (x2cos_theta - x1sin_theta)² + e(cos_thetay2 - sin_thetay1)² - n

f_sin = f1.resultant(f2, sin_theta) sin_roots = f_sin.subs({x1: X1, x2: X2, y1: Y1, y2: Y2}).univariate_polynomial().roots(ring=F, multiplicities=False)

f_cos = f1.resultant(f2, sin_theta) cos_roots = f_cos.subs({x1: X1, x2: X2, y1: Y1, y2: Y2}).univariate_polynomial().roots(ring=F, multiplicities=False)

```

素因数分解する

$x^2 - y^2 = n$ あるいは $x^2 \equiv y^2 \mod n$ という式にできたら $(x + y)(x - y) = n$ に因数分解するとこれが素因数分解になるので、この形にしたい。 $e$ わかっているので雑に resultant して $e$ を削除しても良いし、丁寧に式変形しても良いけど、 $X_1^2Y_2^2 - X_2^2Y_1^2 \equiv 0 \mod n$ という式がでる
- というわけで $\gcd(X_1Y_2 + X_2Y_2, n)$ とかすると素因数が出る
- 楕円上の点であることを利用してやる天才手法 https://kanzya.github.io/posts/HackTM-writeup/
あるいは $(X_1 + \sqrt{-e}Y_1)(X_1 - \sqrt{-e}Y_1) = n$ と分解できることに着目して $\mathbb{Z}({\sqrt{-e}})$ 上で解く方法もあるらしい
https://genni21.github.io/cryptography/2023/02/19/wtlctf.html

n = 990853953648382437503731888872568785013804329239290721076418541795771569507440261620612308640652961121590348037236708702361580700250705591203587939980126323233833431892076634892318387020242015741789265095380967467201291693288654956012435416445991341222221539511583706970342630678909437274145759598920314784293470918464283814408418704426938549136143925649863711450268227592032494660523680280136089617838412326902639568680941504799777445608524961048789627301462833
c = 312168688094168684887530746663711142224819184527420449851136749248641895825646649162310024737395663075921549510262779965673286770730468773215063305158197748549937395602308558217528064655976647148323981103647078862713773074121667862786737690376212246588956833193632937835958166526006128435536115531865213269197137648990987207140262543956087199861542889002996727146832659889656384027201202873352819689303456895088190857667281342371263570535523695457095802010885279
x = (9.93659400123277470926327676478883140697376509010297766512845139881487348637477791719517951397052010880811619509960535668814993293095146708957649613776125686226138447162258666762024346093786649228730054881453449071976210130217897905782845690384638460560301964009359233596889465133986468021963885911072779457835979983964294586954038412718305000570678333513135467257498071686562749882446495426493483289204e230, -1.20540611958254673086539287012513674064476659427085664430224592760592531301348857885707154893714440960111029743010026152632150988429192286517249118913535366887447596463819555191858702861383725310592687577510708180057642425944345656558038998574368521689142109798891989865473206201635908814994474491537093810680632691594902962470061189337645818851446622588020765058461348047229165216450857822980873846637e230)
y = (9.02899744041999015549480362358897037217795303901085937071039171882835297563545959015336648016772002396355451308252077767567617065937943765701645833054147976124287566465577491039263554806622908070370269238064956822205986576949383035741108310668397305286076364909407660314991847716094610949669608550117248147017329449889127749721988228613503029640191269319151291514601769696635252288607881829734506023770e191, 2.82245306887391321716872765000993510002376761684498801971981175059452895101888694909625866715259620501905532121092041448909218372087306882364769769589919830746245167403566884491547911250261820661981772195356239940907493773024918284094309809964348965190219508641693641202225028173892050377939993484981988687903270349415531065381420872722271855270893103191849754016799925873189392548972340802542077635974e192)

X1, X2 = x
Y1, Y2 = y

# solve for e
e = floor((2*n - (X1**2 + X2**2)) / (Y1**2 + Y2**2))
assert is_prime(e)


# find x1, x2, y1, y2
F = RealField(1337)
PR.<cos_theta, sin_theta, x1, x2, y1, y2> = PolynomialRing(QQ)
f1 = (x1*cos_theta + x2*sin_theta)^2 + e*(cos_theta*y1 + sin_theta*y2)^2 - n
f2 = (x2*cos_theta - x1*sin_theta)^2 + e*(cos_theta*y2 - sin_theta*y1)^2 - n

f_sin = f1.resultant(f2, sin_theta)
sin_roots = f_sin.subs({x1: X1, x2: X2, y1: Y1, y2: Y2}).univariate_polynomial().roots(ring=F, multiplicities=False)

f_cos = f1.resultant(f2, sin_theta)
cos_roots = f_cos.subs({x1: X1, x2: X2, y1: Y1, y2: Y2}).univariate_polynomial().roots(ring=F, multiplicities=False)

found = False
for sin_theta in sin_roots:
    if sin_theta == 0:
        continue

    for cos_theta in cos_roots:
        if cos_theta == 0:
            continue

        R = matrix(F, [[cos_theta, -sin_theta], [sin_theta, cos_theta]])
        M = matrix(F, [[X1, Y1], [X2, Y2]])
        x1, y1, x2, y2 = (R**(-1) * M).list()
        if x1 < 0 or x2 < 0 or y1 < 0 or y2 < 0:
            continue

        # if abs(round(x1) - x1) > 0.001 or abs(round(x2) - x2) > 0.001 or abs(round(y1) - y1) > 0.001 or abs(round(y2) - y2) > 0.001:
        #  continue

        x1 = round(x1)
        x2 = round(x2)
        y1 = round(y1)
        y2 = round(y2)

        found = True
        break
    if found:
        break

assert x1**2 + e*y1**2 == n
assert x2**2 + e*y2**2 == n


# factoring n
p = gcd(x1*y2 - y1*x2, n)
q = n // p

# decrypt
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, n)

print(bytes.fromhex(hex(m ^^ x1 ^^ y1 ^^ x2 ^^ y2)[2:]))