SECCON BEGINNERS CTF2023 Choice[Crypto,midium]作問者writeup

0.はじめに

初めまして。高校二年のもちもちと言います
まずはSECCON BEGINNERS CTF2023に参加していただきありがとうございました！
solve数はこんな感じになりました。思いのほか崖ができちゃったみたく、Cryoto準備陣一同ひいひい言ってました

他の作問者のwriteupまとめ(順不同)

• taskさん(CoughingFox2)
• satokiさん(aiwaf, polyglot4b, polyglot4b2)
• yuasaさん(double check, oooauth)
• Tsubasaさん(Forbidden)
• xryuseixさん(shaXXX,drmsaw,phisher2)
  ......(追記予定)

1.考察ステップ

まずコード全体に目を通してあげると、
$$n,e,c,pq+qr+rp$$
が既知で$n$以上の任意の整数$k$に対して
$$p^k+q^k+r^k \mod n$$
が何度でも取得できるといった特徴の3変数のRSA暗号(Multi-Prime-RSA)だとわかります。
$$c^d \equiv m \mod n$$
であることからdを求めてあげたく、
$$ed \equiv 1 \mod φ(n)$$
を思い出してあげると、
$$n=pqr$$
より
$$φ(n)=(p-1)(q-1)(r-1)=pqr-(pq+qr+rp)+(p+q+r)-1=n-(pq+qr+rp)+(p+q+r)-1$$
となります。ここで$pq+rq+rp$と$n$が既知であることから、あとは$p+q+r$を求めてやればよく、この形までいけば三次の基本対象式を思い浮かんでくるのではないでしょうか

2.解法

$p^k+q^k+r^k$についての値を何度でも引っ張ってこれるので、連続する4整数でこの値をとってあげ、これらを$A_1,A_2,A_3,A_4$とすると
$$A_1=(p+q+r)A_2-(pq+qr+rp)A_3+pqrA_4$$が成り立ちます(実際に展開してみてください)。式変形をしてあげると
$$p+q+r= \frac{A_1+(pq+qr+rp)A_3-pqrA_4}{A_2}$$
となり、これを$\mod n$の世界で考えてやればよくなります
ただし、$\mod n$の世界において、加算減算乗算は適当で大丈夫ですが、除算は注意してください。
実装

from typing import Tuple, Iterator, Iterable, Optional
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long, getPrime
import sys

sys.setrecursionlimit(10000)
from number import n, A1, A2, A3, A4, c, s, e


def extGCD(a: int, b: int) -> Tuple[int, int, int]:
    if b != 0:
        d, y, x = extGCD(b, a % b)
        y -= (a // b) * x
        return d, x, y
    return a, 1, 0


def gcd(a: int, b: int) -> int:
    while b != 0:
        t = a % b
        a, b = b, t
    return a


def modinv(a: int, m: int) -> int:
    if gcd(a, m) != 1:
        return 0
    if a < 0:
        a %= m
    return extGCD(a, m)[1] % m


def main():
    while True:
        k = n
        # A1 = (pow(p, k+3, n) + pow(q, k+3, n) + pow(r, k+3, n)) % n
        # A2 = (pow(p, k+2, n) + pow(q, k +2, n) + pow(r, k +2, n)) % n
        # A3 = (pow(p, k+1, n) + pow(q, k +1, n) + pow(r, k+1, n)) % n
        # A4 = (pow(p, k, n) + pow(q, k, n) + pow(r, k, n)) % n
        X = (A1 + s * A3 - n * A4) % n
        Y = (modinv(A2, n) * X) % n
        phi = (n + Y - s - 1) % n
        d = modinv(e, phi)
        m = pow(c, d, n)
        print(long_to_bytes(m))
        break


if __name__ == "__main__":
    main()

ctf4b{E4sy_s7mmetr1c_polyn0mial}