RTACTF (SECCON Speedrun Challenge) 感想

完走失敗したので完走した感想はありません！！！！！！！

2021年12月19日（日） 15:40〜 SECCON電脳会議のコンテンツとしてRTACTF、あるいはSECCON Speedrun Challengeと名打ったライブ配信が行われていました。これはSECCONの作問者やSECCONで上位だったプレイヤーが如何に短い時間で問題を解けるかを競うものです。私はSECCON CTFで作問をしていたこともあり、この企画でcryptoの問題のspeedrunに挑戦する走者として参加しましたので、本記事では感想・振り返り・競技中に解いた問題のwriteupなどを書いていこうと思います。

そもそも
スコアサーバ
本番
総括

そもそも

そもそもこの企画はSpeedrunとあるようにできるだけ高速に、限られた時間で何かを達成しようとする、いわゆるRTAというやつなのですが、RTAがよく行われているジャンルであるゲームとは異なり、プレイヤーは問題について全く未知の状態で早時に挑戦することになります*1。これは企画として非常に挑戦的で、どれくらいの時間で解けるのか――そもそも走者がちゃんと問題を解くことができるのかさえ不透明な状態でのライブ配信となりました。

どのような結果になったかは、こちらのアーカイブから実際の様子をたどることができるのでぜひご覧ください。

ご覧くださいとは書いたものの、一言でまとめてしまえば概ね成功、という形に収まったのではないでしょうか。十分な準備を重ねてきたとは言えない状態での開催でしたから多少のわちゃわちゃはあるものの、大きなトラブルなく、当初描いていたような放送を実現することができたのではないかと思います。企画の立案から実現までの波乱万丈はいいだしっぺかつ最大級の功労者であるrexさんが書いてくださることと思いますので期待してお待ち下さい。

スコアサーバ

書きました。ptr-yudaiがいじれるようにめちゃくちゃ素朴なやつを書いたけど結局特にいじられることはなかった（完）。めちゃくちゃ雑につくったのでRTACTFが大人気になるとサーバが落ちる危険性もありました。結果として人気にならなくて良かった（？）あとLMTの面々には無理言ってサーバ緊急で用意してもらいました。ありがとう……

本番

一口 writeup + 一口感想です

Sexy RSA (163.75 sec)

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}")

ひと目ですね、セクシー素数という言葉には聞き覚えがあったので、問題の +6 という部分だけみてすぐ実装した……と思います

with open("output.txt") as f:
    n = int(f.readline().strip().split(" = ")[1], 16)
    e = int(f.readline().strip().split(" = ")[1], 16)
    c = int(f.readline().strip().split(" = ")[1], 16)

PR.<x> = ZZ[]
f = x*(x + 6) - n
p = int(f.roots()[0][0])
q =  n // p

d = int(pow(e, -1, (p-1)*(q-1)))
m = pow(c, d, n)
print(bytes.fromhex(hex(int(m))[2:]))

Proth RSA (465.36 sec)

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}")

$p = (2k+1)*(2^{n}) + 1$ という形になっていて、 $s = k_1 * k_2 \mod n$ が与えられています。 $k_1 * k_2 \lt n$ なので剰余をとっている意味はなく、 $k_1, k_2$ という2変数に関して、 $n, s$ の2式あるので適当に式変形を解けるはずです。というわけでグレブナー基底を使ってドン

with open("output.txt") as f:
    n = int(f.readline().strip().split(" = ")[1], 16)
    e = int(f.readline().strip().split(" = ")[1], 16)
    s = int(f.readline().strip().split(" = ")[1], 16)
    c = int(f.readline().strip().split(" = ")[1], 16)

PR.<u,v> = QQ[]
p = (2*u + 1) * (1<<512) + 1
q = (2*v + 1) * (1<<512) + 1

polys = [
    p*q - n,
    u*v - s,
]
I = Ideal(polys)
ans = I.variety(ring=ZZ)[0]
u, v = ans[u], ans[v]

p = (2*u + 1) * (1<<512) + 1
q = (2*v + 1) * (1<<512) + 1

d = int(pow(e, -1, (p-1)*(q-1)))
m = pow(c, d, n)

print(bytes.fromhex(hex(m)[2:]))

本番ではsとcを読む順番を取り違えて解けなくて焦っていました

Leaky RSA

解けませんでした。今にして思えばこれが解けないのは精進が不足していますね。うーん配信で緊張していたから……という言い訳も通用しなさそうですね。反省です。それにしたって良い問題ですね

Neighbor RSA (791.75 sec)

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 + \alpha)r = pr + \alpha r$ です。 $\alpha$ はごく小さい値なので $\alpha r$ は512〜bit程度です。こうしてみるとひと目Approximate GCD Problemですね。本番でもひとめそう見えたので高速に解きました。高速に解いた……はずですが負けてしまいました。なぜ……🤔

ちなみにApproximate GCD Problemについては以前記事にしました。これを書いたおかげでみんな解けたものと思いたいですね

furutsuki.hatenablog.com

with open("output.txt") as f:
  e = int(f.readline().strip().split(" = ")[1], 16)
  n1 = int(f.readline().strip().split(" = ")[1], 16)
  n2 = int(f.readline().strip().split(" = ")[1], 16)
  c1 = int(f.readline().strip().split(" = ")[1], 16)
  c2 = int(f.readline().strip().split(" = ")[1], 16)



# e = 65537
# p = random_prime(1<<2048)
# q = random_prime(1<<512)
# r = random_prime(1<<512)
# p2 = next_prime(p)
# 
# n1 = p * q
# n2 = p2 * r

K = 2**512
M = matrix(ZZ, [
  [K, 0, n1],
  [0, K, -n2],
])

L = M.LLL()
for row in L:
  zs = [int(abs(x//K)) for x in row]
  for r in zs:
    if r == 0 or r == 1:
      continue
    if n2 % r != 0:
      continue

    p2 = n2 // r
    print(r, p2)
    p = previous_prime(p2)
    q = n1 // p

    print(p, q, r)

    d1 = int(pow(e, -1, (p-1)*(q-1)))
    d2 = int(pow(e, -1, (p2-1)*(r-1)))

    m1 = pow(c1, d1, n1)
    m2 = pow(c2, d2, n2)

    print(hex(m1)[2:] + hex(m2)[2:])

タイムロス要素は2048bitの素数を生成するのに時間がかかったこと、previous_primeのことを忘れていたことですね

総括

負けて悔しい花いちもんめ。またやりたいですね。みんなつよい

*1:ゲームでいうと初見RTAみたいなものですか？

ふるつき

v('=')v かに