RTACTF Writeup (Crypto)

Sun Dec 19 2021

12/19 に開催していた RTACTF の Crypto part に参加しました。用事があり pwn は参加できず…後でやってみます。

RTA ということで普段と違う脳を使った感じがしました。めちゃくちゃ楽しかったです。続編があったらまたやりたいです。今回の Writeup では RTA 特有な話 (≒お気持ち) も書いていきたいと思います。

Crypto

Sexy RSA

116.43 sec で、現時点で1位です！

chall.py
from Crypto.Util.number import getPrime, isPrime
import os

def getSexyPrime(n=512):
    # Sexy prime: https://en.wikipedia.org/wiki/Sexy_prime
    while True:
        p = getPrime(n)
        if isPrime(p+6):
            return p, p+6

if __name__ == '__main__':
    # Plaintext (FLAG)
    m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big')

    # Generate key
    p, q = getSexyPrime()
    n = p * q
    e = 65537

    # Encryption
    c = pow(m, e, n)

    # Information disclosure
    print(f"n = 0x{n:x}")
    print(f"e = 0x{e:x}")
    print(f"c = 0x{c:x}")

まず、事前準備として sage のインタプリタを起動しておき、 long_to_bytes などを使えるように from Crypto.Util.number import * を叩いておきました (以下の問題でも同様なので省略)。 sage にするか ipython にするかは悩みました。 sage はいろんな builtin 関数があって便利な一方で、 RSA 問だと d = pow(e, -1, phi) みたいなことをするときに sage では d = int(pow(e, -1, phi)) としないと m = pow(c, d, n) で死ぬので… でも結果論的には sqrt 関数が使えたので sage を選んでよかったっぽいです。

sage については万全の準備をしていたのにダウンロードしたファイルを置くための directory を作り忘れており、時間のロスがありました…よくないですね。

Crypto の問題としてはシンプルで、 $p \simeq q$ なので $p \simeq \sqrt{n}$ が成り立ちます。 $q = p + 6$ なので p = round(sqrt(n)) をしたあと、 n % p, n % (p + 1), ... とやって 0 になる値を探しました。

全部インタプリタ上で解いたので、コードはありません…

Proth RSA

443.63 sec で、現時点で1位です！

chall.py
from Crypto.Util.number import getRandomInteger, getPrime, isPrime
import os

def getProthPrime(n=512):
    # Proth prime: https://en.wikipedia.org/wiki/Proth_prime
    while True:
        k = getRandomInteger(n)
        p = (2*k + 1) * (1<<n) + 1
        if isPrime(p):
            return p, k

if __name__ == '__main__':
    # Plaintext (FLAG)
    m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big')

    # Generate key
    p, k1 = getProthPrime()
    q, k2 = getProthPrime()
    n = p * q
    e = 65537
    s = (k1 * k2) % n

    # Encryption
    c = pow(m, e, n)

    # Information disclosure
    print(f"n = 0x{n:x}")
    print(f"e = 0x{e:x}")
    print(f"s = 0x{s:x}")
    print(f"c = 0x{c:x}")

Proth prime というのを知らなかったのですが、 RTA なので一旦無視し、 $p = (2k + 1) 2^n + 1$ ということだけ把握しました。 $k_1, k_2$ の2変数で $s = k_1 k_2$ と $n = pq = ((2k_1 + 1)2^{256} + 1)((2k_2 + 1)2^{256} + 1)$ という2つの値がわかっているので、グレブナー基底を使えば $k_1, k_2$ が求まりそうです。これらが求まれば $p, q$ も求まるので OK です。

Ideal(...).variety() が発動しなくてめちゃくちゃ焦ってしまいました…何か使い方を間違えたのだと思いますが、調べる時間がもったいなかったので Ideal(...).groebner_basis() で $k_1 + k_2$ の値を求めた後で2次方程式を自前で解きました。大きな時間ロス…

solve.py
n = 0xa19028b5c0e77e19fc167374358aa346776e6c20c27499505be59c83ea02014e97af631ba0ccbab881313818fd323c15c82dad8793220ba6679ec4b38787e04d0c1fff0880e04423ea288e443660c63a1607532e47dbaad421723d0546c208447f701cd7e9ee1bb43774d132abbb2e91bf50b67be40ed854dbe6c3071ca3ae3307ac03abd76f74e506594106a22795d4b7938611301248a9957e1a637538a9169cf38daf5d60ffc05ae32ea7e638e16d790ffeebfff655a645c99a513616d3ce00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
e = 0x10001
s = 0x28640a2d7039df867f059cdd0d62a8d19ddb9b08309d265416f96720fa808053a5ebd8c6e8332eae204c4e063f4c8f05720b6b61e4c882e999e7b12ce1e1f812c11cfed72a5c33cfb8f3d34f650e4c19579cf34745f2588aa2fd08a8746257cb789f23ca232346fcf72468a2b160934911902de3f90620aba5874a2d79a33699
c = 0x4595c3c923bd191ba07456611f80e656a197ff528a031e2952adedda532b1fa2caef719c929132a3cdf06d0e55e6a00f7eb1f189a614b26759916ec42f83579a75ab5948186769a1a936b019466f918f29e32852675c464b7f0797c6fdc55efcd54fbe2083761b1df3dde0b9a9a35b96e3b216c54770b444b1f02525f0268c44483c6e84a781fe9111e6912130d69f462c519873043d44e4a3f1f938491feeb591b5831d0abe7399bc87244576decaf2925f287d3c2bb4061d560c919d820e364744f2322c7efd37d42563842bcf9b1d6b46218694dcd49758d311c6896e38cf2b55c7114d78cfdfaeba74720ecf30d9133034799b9735e26ec913cc9f26bb0a

PR.<k1, k2> = PolynomialRing(Zmod(n))
p = (2 * k1 + 1) * 2**512 + 1
q = (2 * k2 + 1) * 2**512 + 1
polys = [p * q - n, k1 * k2 - s]
I = Ideal(polys)
basis = I.groebner_basis()
print(basis)
k1_k2 = n - 20395454563409867656617278217828189042208130201653144079515462893108235291959386336828853848840919483776716211380827788569533851096098894111797056850473973215977506955765638320965700609202656074252440878871479437642421736402628440279746509595855847453146967895481905399926423917985459031590852011496691628662604259167416232330264857609102516325571135277439495982072415418716300644648555729595994325721230901044096167777386912138442924390203810728808854693589734150101148074301478029960268708923366959989928005874227107020841823527632715276090921124020041240950439333518284946100275969081529147302101259207747197769243
PR.<x> = PolynomialRing(ZZ)
f = x**2 - k1_k2 * x + s
(k1, _), (k2, _) = f.roots()

p = (2 * k1 + 1) * 2**512 + 1
q = (2 * k2 + 1) * 2**512 + 1
phi = (p - 1) * (q - 1)
d = int(pow(e, -1, phi))
long_to_bytes(int(pow(c, d, n)))

Leaky RSA

1761.73 sec で、現時点で3位です…

このあたりの問題から急に難易度が上がり、自分の中で RTA という思考は終わってしまいました (RTA を放棄したという意味ではなく、じっくり腰を据えて考えないと解けなそうなのでむやみに手を動かすのをやめたという意味)。

chall.py
from Crypto.Util.number import getPrime, isPrime, inverse
import os

if __name__ == '__main__':
    # Plaintext (FLAG)
    m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big')

    # Generate key
    p = getPrime(600)
    q = getPrime(500)
    n = p*p*q*q
    e = 65537
    s = ((p**3 - 20211219*q) * inverse(p*p+q*q,n)) % n # tekitou (ha?)

    # Encryption
    c = pow(m, e, n)

    # Information disclosure
    print(f"n = 0x{n:x}")
    print(f"e = 0x{e:x}")
    print(f"c = 0x{c:x}")
    print(f"s = 0x{s:x}")

$k = 20211219$ として、 $(p^2 + q^2)s = p^3 - kq \mod n$ という式が与えられています。

初手は $\phi = (p^2 - p)(q^2 - q) = n + pq - pq(p+q)$ となるので $p + q$ がわかるとよさそうだなと思い、そっちの方向性で考えていました。今から覚えればそれは無理な話なのですが、本気でした。 RTA 怖い… $s$ の式が対称式じゃないのでこの方向性は厳しそうです。

このあたりで RTA であることを忘れてじっくり解かないとまずそうと思い、式をがちゃがちゃし始めます。 $s$ の式をもうちょっと式変形をすると、 $p^2(p-s) = q(sq + k) \mod n$ となります。 $\mod p$ を考えると $q(sq + k) = 0 \mod p$ となるので $sq + k = 0 \mod p$ が言えます。ここまで次元を落とすことができれば Coppersmith が刺さりそうだったので試したら行けました。

solve.py
n = 0x2ac1fcbbf63ffeade11cd2c57c37db18d96d52e433bd9034d4eac2c269ea49a81e5ac41fb631523bb5983adc6fc939c073c13d8a3a42a06accf5a9c304fc444508a8b5833b5431e9af7007bb216c510c62a97eb1fe380bf155b3e497c7d70c2bb921f97eec61e9e9ac7b5d71e47876d20cbfb1a0732e29ec6872041eb67e0ccd39d7b6429bda1581537dda95e79d3aad4df072beada1c72a4ffd86db91918ec9db44ab9c4bebf387ccc1ce7b2540b0d595a4c11823cdbcd8850bd3b666b4a08bd69de515afecc75b283ae47fbf3af6f034f3b0f7848dec935ba8b97e36d2d0a9208df63610cf8825fb729aacaa4c119d0b4c5e230e080d7633f145d22eb06b917fe632c01a373b1c4c8a741bea1d5dd98003e9
e = 0x10001
c = 0xe50a858f715238a9ab44dfd691f6e5ced84e74115e003e31a98b324cf9e8bc9cfe08065f2538cff519e035566b4080742139062e672a0ad3196275cb121ea837de2808f99958bcfe58d1c8996f291412220d01fe65fbf18611b348407b2e2db45b2adcc341926c6d76a9d08fc77db0fedef78cec9e4b881812e60c015c1005dfd0b9408cb3c6f9f98332f165acc3ae98ef97f2a1d98524fe240d3351676ed84ddb73283a6d3efc40bbd466fe3532e579eb9adf07ebbc49af71fb22934a75a69a538eca0fd4e2a5b617abb361a64c553985950dd5201ac7c631580c8bb27d795a196d584ae7c7478bdc1b5ff531ff88e984bceb1e26cf9793f99a11287555d5d2d2a13e1171f77bf8491d8dfa297e9cd6d4b7d
s = 0x14c0af71a961be72e2d4e5ee06337cde2034db1d920f4476e3a3371c8a35e7ba8efabf5c8e8ff86e7297156c4fde5bdc7aabe1516a46c554236104022eb4544f1d7fcb80279595dfe0527bcc373909ce7cc0965ece5ff76b7ee9a5cc31a1b567ed3ddd2364bb596e3c41e4fffb5974f71e788da5c21598e9c6dc32bca162026ba3c410bb1c5c9d5bed4c3b97e3cacbd7b6693f29c74b0756381b658efaa757d448f62a48fbdb06604525222aa51797a1a1e43af4b0c221deef47f84bb5bfa1480cd31242c3d7fba21bdf487709853879dcea284e44cb5ee1a02c558a29740a44e39c7ee3a97ab4805d21cb90b596bd86c51f4e0f783701da73c66f5a4c67d989bb2dba2b8a55a697eb187cc181fc8ce54de370


k = 20211219
pq = round(sqrt(n))
PR.<x> = PolynomialRing(Zmod(n))
f = s * x + k
f = f.monic()
q = int(f.small_roots(X=2**500, beta=0.20)[0])
p = pq // q

phi = (p**2 - p) * (q**2 - q)
d = int(pow(e, -1, phi))
long_to_bytes(int(pow(c, d, n)))

Neighbor RSA

1572.52 sec で、現時点で7位です………

chall.sage
import os

# Plaintext (FLAG)
plaintext = os.getenv("FLAG", "FAKE{sample_flag}").encode()
plai  = plaintext[:len(plaintext)//2]
ntext = plaintext[len(plaintext)//2:]
m1 = int.from_bytes(plai  + os.urandom(128), 'big')
m2 = int.from_bytes(ntext + os.urandom(128), 'big')

# Generate key
e = 65537
p = random_prime(1<<2048)
q = random_prime(1<<512)
r = random_prime(1<<512)
n1 = p * q
n2 = next_prime(p) * r
assert m1 < n1 and m2 < n2

# Encryption
c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)

# Information disclosure
print(f"e = {hex(e)}")
print(f"n1 = {hex(n1)}")
print(f"n2 = {hex(n2)}")
print(f"c1 = {hex(c1)}")
print(f"c2 = {hex(c2)}")

$n_1 = pq$ と $n_2 = (p + k)r$ ( $k > 0$ は $p+k$ が素数になる最も小さい値) が与えられています。

見たことない形式で、これ解けるのか？と絶望的な気持ちになりました… RTA なので知ってる人には常識な典型問題なのかなと考え、検索することを決めました。 $p \gg q$ なことと $k$ が小さいということから LLL を使うような手法があるのかなと推測し、「RSA LLL CTF writeup」みたいな単語列で検索しました (これはうろ覚え)。そうすると https://ctftime.org/writeup/20491 を見つけました。割と似たような問題設定です。

$(K, 0, n_2)$ , $(0, K, -n_1)$ ( $K$ は weight を調整するパラメータで、今回の場合 $2^{512+10}$ ) という格子基底で LLL をかけると $q, r$ が求まるっぽいことをソースコードから確認し、実装しました。ほんまか？という気持ちが強かったのですが $q, r$ がたしかに求まりました。後は RSA 特有の処理をするだけです。

フラグ提出後なんでこの格子でいけるのか考えたのですが、 $qn_2 - rn_1 = q(p+k)r - rpq = kqr$ が十分小さい数になるからですね。これは普通に考察して求めるべきだなと非常に反省しています。 RTA 恐ろしい…

solve.py
e = 0x10001
n1 = 0xa8ed020c3dd125d503bf124052d643ba1405f2c349244122140e79e7d2244304a1590762c61ac83900c2aced76007b2e3f320464fd51fcfad167ebdc87e69329230869e0a3e153b44ed3b04bfe94174bc8b5ee1a3fa8036b6b9e834666aa07229a431b477e589d94f9a4cfed25b195215b0c694b86e874413b8a00cb064809c8e3677632cde9b43b87a0b812c2024b0c821b5c10764fd4de2d18af55d897d94aeded80b71e36fd73014f75641a8c5b38b36faa020e7cf1327a707bb7d42503bcc28768ef184d66b9ba16efd019b68268885a2da302cd326e78b1d473bcf7cd62442ccd25dc85d23aeb5408922b6b00f13584bea394f1bca4cc431f3c29c5d98ec1683453cc0c526abe4aec08781c7a53f50f2047b4995b9bea6a7a9f6b5425b29be6e867764efaa050799f716af78273041372cfe4f3c88a62329f6f1feff99
n2 = 0x16ea1bde86ea11cdec196a9173258efca235da66f8e3d5437e39e1b2e2574dd3f93d65104ca0225d6119519ae9ea9c035e0f85f02212c0992d0705723fa8b97ed6cff860c4d8fb65f0214a0047feca64e662dcbf025fff47590305e90e5d070d39871880828f5e960ab2ef330129ed5752c3b4debe827376a632b06487740fff4b622a88de23649e3e6993cd332b0284b84eb8765d58527209cc202c89d479421131a2f64ae517ee1e62e6c0f329c306569e427113ec6a8b9d96d73e95580d3a33f6add681f9a9156f0681eb1804183dfa8cebbe921d2fb1d43b256f727d46c5859cc5229f7e555ad25397e5cd14620ebbaefa0a0a520bada3ef8b115481734242af6befbd9b069d4a03281094c0f4aca4e6fdcbe2558b104fc2b383e1c70f0e5a07d1a623f9fc2309ca1d09b69aa1869e280fbc50de2adbada7ea545743b12b
c1 = 0x690e49037fee7649033ffaaa71e4730d2d7143fab97beb22e2afdf6eca449cad3f95b60295f592e7e84833e08b3468d61a34c1d1123f4c683c79d68bbe27dd0af203fc50ef7ebe98b1bc1221918470f058a8fb7645eacb569931835bd7f80494dbb67fbaa592ec19d9b4930c787a2ce1267f8088229b5031e710d6cd5720756923ccb64444939a0f09a51c87488650d4d02551fd4ed7a2fd248825ec34c5df8b6077a6d0d75c5832f9140420c92d3d00cf51e3b0665f5a6d031cb369ddebbb5ce77f2176cd12bb0add5aeda6ae88c4ceade0c1fd0ff3960d3ee36a0c6455ae3027f33e660663d0e2298654e19e8c8a06b4de991fac3b4c1673825b3d9f8f5c675f920a7d137f85ba723bf741321904e0c3c601f5c18d02e1e5b7b118e62e91a7926a9b1eda3cc53e2a6cbc95553e1990ec3f6cceddf283410d6e6849a26f89b
c2 = 0x5c4c7dce82753a68dcdbcdce9af52c9b7af2f561c08b8e23b27c6145d4c3df29d498303bee1bd29829a2e0ae9faaf243b387c39d69daccba07dace7bb420115ffaa69f89a3ea4e1ef0e08eb19043e012a090b79e51d6ae8446ca76e88abe5adbdbe25a731d7ee9aa333a84447edafbc360b505ff293c751571c6bf29dee99fdc443b756f182eb588b4a03de3d35dc4f23736d7239cfbd0ca13fa7b234bc4064a2053ab0045f4833250c8c9de91798502b09d4312ee52f3dc5229dfcb73b42f7c3440932839e6e790bb0db1788fbd7c60365121bbe3858ecedd3d48261d081c380e7ddf6ca570c13cc89c0af2011b4978b22d5456d1122dabd7b2068ab30e301a674809732daede77a27ae13e1bc4779e15d51210f6c10be159907ec1a59bfaf8db6cf290a348f734fd88e3c2b7df6bda84665b810cfe55bc3645d8d118c9172

# https://ctftime.org/writeup/20491
K = 2**(512+10)
mat = matrix(ZZ, 2, 3)
mat[0, 0] = K
mat[1, 1] = K
mat[0, 2] = n2
mat[1, 2] = -n1
res = mat.LLL()
_q = res[0, 0] // K
_p = n1 // _q
_r = n2 // next_prime(_p)

phi1 = (_p - 1) * (_q - 1)
phi2 = (n2 // _r - 1) * (_r - 1)

d1 = int(pow(e, -1, phi1))
d2 = int(pow(e, -1, phi2))

long_to_bytes(int(pow(c1, d1, n1)))
long_to_bytes(int(pow(c2, d2, n2)))
# RTACON{1nt3nd3d_s0lut10n_1s_Approximate_GCD_:pray:}