gyckel.md

Writeup Open-gyckel-krypto from Midnightsun CTF 2019 (Quals)

Primes are fun, don't google translate me bro

gyckel.txt:

while True:
    p = next_prime(random.randint(0, 10**500))
    if len(str(p)) != 500:
        continue
    q = Integer(int(str(p)[250:] + str(p)[:250]))
    if q.is_prime():
        break

>> p * q
6146024643941503757217715363256725297474582575057128830681803952150464985329239705861504172069973746764596350359462277397739134788481500502387716062571912861345331755396960400668616401300689786263797654804338789112750913548642482662809784602704174564885963722422299918304645125966515910080631257020529794610856299507980828520629245187681653190311198219403188372517508164871722474627810848320169613689716990022730088459821267951447201867517626158744944551445617408339432658443496118067189012595726036261168251749186085493288311314941584653172141498507582033165337666796171940245572657593635107816849481870784366174740265906662098222589242955869775789843661127411493630943226776741646463845546396213149027737171200372484413863565567390083316799725434855960709541328144058411807356607316377373917707720258565704707770352508576366053160404360862976120784192082599228536166245480722359263166146184992593735550019325337524138545418186493193366973466749752806880403086988489013389009843734224502284325825989
>> pow(m, 65537, p * q)
3572030904528013180691184031825875018560018830056027446538585108046374607199842488138228426133620939067295245642162497675548656988031367698701161407333098336631469820625758165691216722102954230039803062571915807926805842311530808555825502457067483266045370081698397234434007948071948000301674260889742505705689105049976374758307610890478956315615270346544731420764623411884522772647227485422185741972880247913540403503772495257290866993158120540920089734332219140638231258380844037266185237491107152677366121632644100162619601924591268704611229987050199163281293994502948372872259033482851597923104208041748275169138684724529347356731689014177146308752441720676090362823472528200449780703866597108548404590800249980122989260948630061847682889941399385098680402067366390334436739269305750501804725143228482932118740926602413362231953728010397307348540059759689560081517028515279382023371274623802620886821099991568528927696544505357451279263250695311793770159474896431625763008081110926072287874375257

So we have for some $a, b \le 10^{250}$:

$$ \begin{aligned} p &= a \times 10^{250} + b\\ q &= b \times 10^{250} + a\\ n &= pq = ab \times 10^{500} + (a^2+b^2) \times 10^{250} + ab \end{aligned} $$

Let $x = ab$ and $y=a^2+b^2$. Then $n$ is in decimal notation:

  xxxxxxxx
+     yyyyyyyy
+         xxxxxxxx

So $x$ is just (int(str(n)[:250]) - carry) * 10**250 + int(str(n)[-250:]), where carry <= 10. Then

$$ \begin{aligned} y &= (n - x \times 10^{500} - x) / 10^{250}\\ a+b &= \sqrt{(a+b)^2} = \sqrt{2x + y} \end{aligned} $$

To decrypt, we compute

$$ \begin{aligned} \phi(n) &= (p-1)(q-1) = p\cdot q-p-q+1 = n+1 - p+q\\ p+q &= (a+b) \times 10^{250} + (a+b) \end{aligned} $$

Code:

for i in range(100):
    ab = (int(str(pq)[:250]) - i) * 10 ** 250 + int(str(pq)[-250:])

    a2_p_b2 = (pq - ab * 10**500 - ab) / 10**250

    a_p_b, ok = gmpy2.iroot(a2_p_b2 + 2 * ab, 2)
    if ok:
        p_p_q = 10**250 * a_p_b + a_p_b
        phi = n+1 - p_p_q
        d = gmpy2.invert(e, phi)
        m = pow(c, d, n)
        print unhex(hex(m)[2:])
#Flag: midnight{w3ll_wh47_d0_y0u_kn0w_7h15_15_4c7u4lly_7h3_w0rld5_l0n6357_fl46_4nd_y0u_f0und_17_50_y0u_5h0uld_b3_pr0ud_0f_y0ur53lf_50_uhmm_60_pr1n7_7h15_0n_4_75h1r7_0r_50m37h1n6_4nd_4m4z3_7h3_p30pl3_4r0und_y0u}

Coppersmith variant

There is also a fun way to obtain $a$ or $b$ directly using Coppersmith's algorithm. Basically, Coppersmith allows us to find a small root modulo a factor of $n$ of some polynomial.

For $f = (10^{250} - 1)\cdot x + (a+b)$, we have $f(a) = a \times 10^{250} + b \equiv 0 \mod p$.

Sage code:

F.<x> = PolynomialRing(Zmod(n), implementation='NTL')

apb = 15871665624873106757366073367006393842426740622843832520348006298484905394116528310818622424957645305919818028562611709016786155701425048746304994384930166284051799405392923428638445235361622797592069085322151835651113619585729206760658312388130829530

f = x * 10**250 - x + apb

f *= inverse_mod(10**250 - 1, n)  # make f monic, i.e., the leading coefficient must be 1

print f.small_roots(X=10**250-10**249, beta=0.4) # play around a little bit with the coefficients until finding a solution (see also http://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots)