CONFidence CTF 2019 Teaser|Really Suspicious Acronym

You can't break my public key if you don't know it, amirite?

The flag format is: p4{letters_digits_and_special_characters}.

def bytes_to_long(data):
    return int(data.encode("hex"), 16)


def rsa(msg, e, n):
    return pow(bytes_to_long(msg), e, n)


flag = open("flag.txt", "r").read()
tmp = randint(2 ** 1023, 2 ** 1024)
e = 65537
p = next_prime(0xDEAD * tmp + randint(2, 2 ** 500))
q = next_prime(0xBEEF * tmp + randint(2, 2 ** 500))
N = p * q
print("msg1 = " + str(rsa("You can't factor the modulus", e, N)))
print("msg2 = " + str(rsa("If you don't know the modulus!", e, N)))
print("flag = " + str(rsa(flag, e, N)))

msg1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
msg2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657

問題名からもわかるようにRSA。かなり特殊なp, q の作り方をしていて(Suspicious Prime)、Nさえ与えられていない。ただ、平文がわかっている2つの暗号文があり、同じN, eを用いて暗号化されているので、これを使うとNが求まったりするのだろう。

$C_1 \equiv m_1^e \mod N$ は適当な整数 $t_1$ を用いて $m_1^e - C_1 = N \times t_1$ を意味する。同様に $m_2^e - C_2 = N \times t_2$ なので、ここから $GCD(m_1^e - C_1, m_2^e - C_2) = GCD(N \times t_1, N \times t_2) = N * GCD(t_1, t_2)$ とNを求められそう。 $GCD(t_1, t_2)$ はなにかわからないけど、そう大きな数値ではないだろうし、多分素因数分解でもすればいい感じになるんじゃないだろうか。

というわけで次のようなsageスクリプトを書く。ちなみにpythonで実行したところGCDが遅くて1分以上やっても終わらなかったのに対してsageだと10秒程度で終わったのでやっぱり重たい計算をやるときにはsageは優秀

from Crypto.Util.number import bytes_to_long

exec(open("out.txt").read())
e = 65537
m1 = bytes_to_long(b"You can't factor the modulus")
m2 = bytes_to_long(b"If you don't know the modulus!")

c1 = pow(m1, e)
c2 = pow(m2, e)

n_times_k = gcd(c1 - msg1, c2 - msg2)
print(n_times_k)

で、次のような値が出てくるのでfactordb.comに投げる

34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

普通に2つの素数に分解されてしまった……。だれかが登録とかをしたということだろうか。とにかく $GCD(t_1, t_2) = 1$ だったことがわかり、 $p, q$ が求まったので後はやるだけ

from Crypto.Util.number import inverse
exec(open("out.txt").read())
e = 65537
p = 5464515205735326925761119032487290302632934062073740159550085833329195620883128193119114464715970222295879529811043479266336461838857130765922924760147062834608592475434477636982853991551857397250770678523016613460717030474350146320345990974222629526200926995286502665852233588787090358827238368163888045247465157
q = 6372975905868416117412643271076290098029632484472136455229293621574312002464099565227503018906562788149851932258813264092504143029195579682715201332927910081770552791548738518755413161806001832406651207088257424369670382480988120894685280764472916242514475060539101279784773630617990388487509349287688057345180529
phi = (p-1)*(q-1)
d = inverse(e, phi)

m = pow(flag, d, p*q)
print(bytes.fromhex(hex(m)[2:]))

p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}

---

ただし、Nが素因数分解できるのは明らかにおかしいので、こちらもやっておく。

今 $p = 0xDEAD \times tmp + 2^x, q = 0xBEEF \times tmp + 2^y$ で、tmpはおよそ1024bitで（1/2の確率で1024bitだし1/2 + 1/4 の確率で1023bit以上）、 $2^x, 2^y$ は512bit程度しかない上に足し算なので、 $\frac{p}{q}$ とかやると $\frac{p}{q} \simeq \frac{0xDEAD}{0xBEEF}$ になる

つまり、 $n \times \frac{0xDEAD}{0xBEEF} = pq \times \frac{0xDEAD}{0xBEEF} \simeq pq \times \frac{p}{q} = p^2$ が成り立つ。

pとかqのおおよその値がわかるときは univariate coppersmith methodが使えるらしい。

N = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

realN = RealField(1000)(N)  # 1000 bits of precision
p_ = int(sqrt(realN * 0xDEAD/0xBEEF))
F.<x> = PolynomialRing(Zmod(N))
f = x - p_

roots = f.small_roots(2^500, beta=0.4)
for r in roots:
    p = int(p_ - r)
    if N % p == 0:
        q = N // p
        print("p = {}".format(p))
        print("q = {}".format(q))
        exit()
print("Not found")