Happy was a 242 point crypto challenge on the 2019 Tokyo Westerns Qualifiers.

Problem Description

No, we’Re not SAd. We are Happy!

Solution

The problem description makes it pretty clear that this challenge is RSA. Indeed, we are given 3 files of importance: happy (.rb), pub.key, and flag.enc. We open happy.rb and find the definition of a custom defined Key class, which we figure out to be an implementation of multi-prime RSA (N = pq^k) (as shown below):

return Key.new({
    n: p * q ** k,
    e: e,
    p: p,
    q: q ** k,
    d1: d1,
    d2: d2,
    cf: cf,
})

Additionally, we note that the following lines are important:

def self.import(str)
    Key.new(Marshal.load(str))

So we can safely deduce here that the pub.key file is a serialized public key that is deserialized and parsed by the key class. Deserializing the pub.key file yields the following parameters:

irb(main):001:0> Marshal.load(File.binread("pub.key"))                                                  
=> {:n=>5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911, :e=>65537, :cf=>25895436290109491245101531425889639027975222438101136560069483392652360882638128551753089068088836092997653443539010850513513345731351755050869585867372758989503310550889044437562615852831901962404615732967948739458458871809980240507942550191679140865230350818204637158480970417486015745968144497190368319745738055768539323638032585508830680271618024843807412695197298088154193030964621282487334463994562290990124211491040392961841681386221639304429670174693151}

Interesting–normally, an RSA public key would contain only \((N, e)\). The cf parameter certainly doesn’t seem to match any known implementation of RSA, so we assume for now that it’s an arbitrary parameter.

Going back to the code, we find that cf = p.pow(q ** (k - 1) * (q - 1) - 1, q ** k)–in other words, \(cf \equiv p^{q^{(k - 1)}(q - 1) - 1} \pmod{q^k}\)

We aren’t explicitly given \(k\), but we can deduce that \(k = 2\), since we know \(p\) and \(q\) are both \(b\)-bit long primes, \(N = pq^k\) has a bit length of 2295, and \(q^k\) has a bit length of 1530, so we can simply divide by 3 to get the bit length of each prime factor (765) and obtain 1530/765 = 2. With \(k = 2\), we can simplify our above equation to obtain \(cf \equiv p^{\phi(q^2) - 1} \pmod{q^2}\), and through Euler’s theorem, \(cf \equiv p^{-1} \pmod{q^2}\). In its current form, \(cf\) isn’t super useful since the only information we have on \(p\) is in the form of its inverse, but we can multiply both sides of the equation by \(p^2\) to obtain \((cf \cdot p - 1)p \equiv 0 \pmod{N}\). We multiply by \(p^2\) because we want to form a polynomial in \(p\) over \(\mathbb{Z}/(N)\), where we know \(N\):

\[cf \cdot p \equiv 1 \pmod{q^2}\] \[\implies cf \cdot p - 1 \equiv 0 \pmod{q^2}\] \[\implies cf \cdot p - 1 = kq^2\]

for some integer \(k\). So multiplying by an additional factor of \(p\) allows us to obtain

\((cf \cdot p - 1)p = kpq^2 = kN\).

This is equivalent to saying that

\((cf \cdot p - 1)p \equiv 0 \pmod{N}\).

From here, we can use Coppersmith’s algorithm to solve for \(p\).

The code to do this is as follows:

n = 5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911
cf = 25895436290109491245101531425889639027975222438101136560069483392652360882638128551753089068088836092997653443539010850513513345731351755050869585867372758989503310550889044437562615852831901962404615732967948739458458871809980240507942550191679140865230350818204637158480970417486015745968144497190368319745738055768539323638032585508830680271618024843807412695197298088154193030964621282487334463994562290990124211491040392961841681386221639304429670174693151

P.<p> = PolynomialRing(Zmod(n))

f = (cf * p - 1) * p

roots = f.monic().small_roots()
print(roots)

# [0, 166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479]

We see 2 results: 0 is a trivial root, so we can discard it, but we find out that the second value 166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479 divides N!

Thus, we have found \(p\), and finding \(q\) is simply a matter of computing \(\sqrt{N / p}\). From here, computing \(\phi(N)\) and \(d\) is easy. However, the flag is padded with PKCS1_OAEP, so we have to PKCS1_OAEP unpad it to recover the original plaintext. We ran into incorrect decryption errors when trying to use pycrypto’s PKCS1_OAEP, and since we were sure all our recovered parameters were correct, we switched to the cryptography module for the last part of the challenge.

key = RSA.construct((long(n), long(e), long(d)))

final_key = load_pem_private_key(
		key.exportKey(),
		password=None, 
		backend=default_backend()
		)

flag = final_key.decrypt(
		c,
		padding.OAEP(
			mgf=padding.MGF1(algorithm=hashes.SHA1()),
			algorithm=hashes.SHA1(),
			label=None
			)
		)
print(flag)

Running this produces the flag TWCTF{I_m_not_sad__I_m_happy_always}.

The full code from start to finish can be found in solution.sage (install required libraries through sage -pip install cryptography pycrypto beforehand).

Flag

TWCTF{I_m_not_sad__I_m_happy_always}