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 の問題としてはシンプルで、 pqp \simeq q なので pnp \simeq \sqrt{n} が成り立ちます。 q=p+6q = 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)2n+1p = (2k + 1) 2^n + 1 ということだけ把握しました。 k1,k2k_1, k_2 の2変数で s=k1k2s = k_1 k_2n=pq=((2k1+1)2256+1)((2k2+1)2256+1)n = pq = ((2k_1 + 1)2^{256} + 1)((2k_2 + 1)2^{256} + 1) という2つの値がわかっているので、グレブナー基底を使えば k1,k2k_1, k_2 が求まりそうです。 これらが求まれば p,qp, q も求まるので OK です。

    Ideal(...).variety() が発動しなくてめちゃくちゃ焦ってしまいました…何か使い方を間違えたのだと思いますが、調べる時間がもったいなかったので Ideal(...).groebner_basis()k1+k2k_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=20211219k = 20211219 として、 (p2+q2)s=p3kqmodn(p^2 + q^2)s = p^3 - kq \mod n という式が与えられています。

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

    このあたりで RTA であることを忘れてじっくり解かないとまずそうと思い、式をがちゃがちゃし始めます。 ss の式をもうちょっと式変形をすると、 p2(ps)=q(sq+k)modnp^2(p-s) = q(sq + k) \mod n となります。 modp\mod p を考えると q(sq+k)=0modpq(sq + k) = 0 \mod p となるので sq+k=0modpsq + 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)}")

    n1=pqn_1 = pqn2=(p+k)rn_2 = (p + k)r (k>0k > 0p+kp+k が素数になる最も小さい値) が与えられています。

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

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

    フラグ提出後なんでこの格子でいけるのか考えたのですが、 qn2rn1=q(p+k)rrpq=kqrqn_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:}
      ;