pbctf 2021 | yet another RSA

pbctf_2021 rbtree 有限群 rsa murru_and_saettone_scheme small_d pbctf2020_|_special_gift 因数分解 式変形 数学 multivariate_coppersmith

#pbctf_2021

#rbtree

#!/usr/bin/env python3

from Crypto.Util.number import *
import random


def genPrime():
    while True:
        a = random.getrandbits(256)
        b = random.getrandbits(256)

        if b % 3 == 0:
            continue

        p = a ** 2 + 3 * b ** 2
        if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
            return p


def add(P, Q, mod):
    m, n = P
    p, q = Q

    if p is None:
        return P
    if m is None:
        return Q

    if n is None and q is None:
        x = m * p % mod
        y = (m + p) % mod
        return (x, y)

    if n is None and q is not None:
        m, n, p, q = p, q, m, n

    if q is None:
        if (n + p) % mod != 0:
            x = (m * p + 2) * inverse(n + p, mod) % mod
            y = (m + n * p) * inverse(n + p, mod) % mod
            return (x, y)
        elif (m - n ** 2) % mod != 0:
            x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
            return (x, None)
        else:
            return (None, None)
    else:
        if (m + p + n * q) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
            y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
            return (x, y)
        elif (n * p + m * q + 2) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
            return (x, None)
        else:
            return (None, None)


def power(P, a, mod):
    res = (None, None)
    t = P
    while a > 0:
        if a % 2:
            res = add(res, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return res


def random_pad(msg, ln):
    pad = bytes([random.getrandbits(8) for _ in range(ln - len(msg))])
    return msg + pad


p, q = genPrime(), genPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)

print(f"N: {N}")

d = getPrime(400)
e = inverse(d, phi)
k = (e * d - 1) // phi

print(f"e: {e}")

to_enc = input("> ").encode()
ln = len(to_enc)

print(f"Length: {ln}")

pt1, pt2 = random_pad(to_enc[: ln // 2], 127), random_pad(to_enc[ln // 2 :], 127)

M = (bytes_to_long(pt1), bytes_to_long(pt2))
E = power(M, e, N)

print(f"E: {E}")

\phi = (p^2 + p + 1)(q^2 + q + 1)となるような有限群の上のRSA variant

群構造自体は \mathbb{F\lbrack x\rbrack /(x^3 - r)}上のものらしい。さらにこれにはMurru and Saettone schemeという名前がついているらしい。知らないねぇ

当然知らなくても解けて、要するに p, q \approx 2^{512} \phi = N^2 + N(p + q) + N + p^2 + q^2 + p + q + 1より \phi \approx 2^{2048}であるのにたいして、

ed = 1 + k \phiにおいて d, k \approx 2^{400}なのでsmall d

pbctf2020 | Special Giftでもやったように \mod eを取れば未知数をだいぶ小さく抑えることができる。問題は p^2, q^2が1024bitと大きいことだけど、 (p + q)^2 = p^2 + 2pq + q^2であることを思い出せば、 p + q = sとおいて

ed = 1 + k(N^2 + Ns + N + s^2 - 2N + N + s + 1) と変形できる（因数分解 / 式変形 / 数学）。このとき未知数は e, d, sでそれぞれ 2^{400}, 2^{400}, 2^{512}程度。更に先程言及したように \mod eとると

0 \equiv 1 + k(N^2 + Ns - N + s^2 + s + 1) \mod e で、これは十分multivariate coppersmithで解ける。本番これを解けなかったことは反省しましょう

load("./defund.sage")


N =  144256630216944187431924086433849812983170198570608223980477643981288411926131676443308287340096924135462056948517281752227869929565308903867074862500573343002983355175153511114217974621808611898769986483079574834711126000758573854535492719555861644441486111787481991437034260519794550956436261351981910433997
e = 3707368479220744733571726540750753259445405727899482801808488969163282955043784626015661045208791445735104324971078077159704483273669299425140997283764223932182226369662807288034870448194924788578324330400316512624353654098480234449948104235411615925382583281250119023549314211844514770152528313431629816760072652712779256593182979385499602121142246388146708842518881888087812525877628088241817693653010042696818501996803568328076434256134092327939489753162277188254738521227525878768762350427661065365503303990620895441197813594863830379759714354078526269966835756517333300191015795169546996325254857519128137848289

PR.<k, s> = PolynomialRing(Zmod(e))
f = 1 + k*(N^2 + N*s + N + s^2 - 2*N + s + 1)
print( small_roots(f, [2^400, 2*2^512], m=3, d=4) )

RSA解くパートは省略

元ネタ