TokyoWesterns CTF 2019 - happy! Solver & simple writeup

solve.rb

require_relative './happy' # rename happy -> happy.rb

q = 180754955592872777770305021165949447837520820408608437544593001477325680227199967219036800612237524673886247520794601572290402702594122131782305474875236404413820478308317235725623037177247985490515533618988964977186476558003216903
p = 166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479
k = 2
e = 65537
d1 = e.pow((p - 1) / 2 - 2, (p - 1))
d2 = e.pow(((q - 1) / 2 - 1) * (q - 1) * (k > 1 ? q ** (k - 2) : 1) - 1, q ** (k - 1) * (q - 1))
cf = p.pow(q ** (k - 1) * (q - 1) - 1, q ** k)
key = Key.new({
                n: p * q ** k,
                e: e,
                p: p,
                q: q ** k,
                d1: d1,
                d2: d2,
                cf: cf,
})
File.binwrite("flag.txt", key.private_decrypt(File.binread("flag.enc")))

=begin
Sun Sep  1 18:59:16 JST 2019 ~/Downloads/twctf/happy 100%
> ruby solve.rb && cat flag.txt
TWCTF{I_m_not_sad__I_m_happy_always}
=end

solve.sage

from sage.all import *


n = 5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911
e = 65537
cf = 25895436290109491245101531425889639027975222438101136560069483392652360882638128551753089068088836092997653443539010850513513345731351755050869585867372758989503310550889044437562615852831901962404615732967948739458458871809980240507942550191679140865230350818204637158480970417486015745968144497190368319745738055768539323638032585508830680271618024843807412695197298088154193030964621282487334463994562290990124211491040392961841681386221639304429670174693151

F = Zmod(n)
PR.<x> = PolynomialRing(F)

pol = x * cf - 1
pol = pol.monic()
# I guessed X and beta from some experiments...
x0 = pol.small_roots(X=2^800, beta=0.2)[0]

qk = ZZ(gcd(x0 * cf - 1, n))
q, k = is_prime_power(qk, get_data=True)
p = ZZ(n / qk)

assert is_prime(p)
assert is_prime(q)
print "[+] q, k = %d, %d" % (q, k)
print "[+] p = %d" % p


"""
Sun Sep  1 18:58:48 JST 2019 ~/Downloads/twctf/happy 100%
> time sage solve.sage
[+] q, k = 180754955592872777770305021165949447837520820408608437544593001477325680227199967219036800612237524673886247520794601572290402702594122131782305474875236404413820478308317235725623037177247985490515533618988964977186476558003216903, 2
[+] p = 166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479

real    0m8.301s
user    0m7.995s
sys     0m0.265s
"""

Summary: Break a variant of RSA cryptosystem with CRT coefficient.

Writeup:
This RSA variant is a Multi-power RSA. i.e. This RSA cryptosystem uses n = p*q^k where p, q are primes and k is some non-zero positive integer. we don't have p, q and k. We have public key (e, n), encrypted flag, and cf. cf is not a part of public key but It included to public key file because It has a simple mistake at this problem code (:ce).

It holds cf * p ≡ 1 (mod q^k) thus we know cf * x - 1 ≡ 0 (mod q^k) has a solution x = p. If we got that solution(named x0), cf * x0 - 1 is a multiple of q^k, so we can get q^k by compute gcd(n, cf * x0 - 1). furthermore, we can compute the solution of cf * x - 1 ≡ 0 (mod q^k) using a multiple of q^k (i.e. n = p*q^k) by Coppersmith's Method.

I wrote solve.sage and execute it. then I got p, q, and k. finally, I copy/paste/edit solve.rb and got flag.

Nice! I overkilled it, by finding small roots of a 3-variate linear polynomial, but over integers.