HITCON CTF 2022 | easy NTRU - crypto-writeup-public

#HITCON_CTF_2022

from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Util.number import long_to_bytes as l2b
import random

Zx.<x> = ZZ[]


def convolution(f, g):
    return (f * g) % (x ^ n-1)


def balancedmod(f, q):
    g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
    return Zx(g) % (x ^ n-1)


def randomdpoly(d1, d2):
    result = d1*[1]+d2*[-1]+(n-d1-d2)*[0]
    random.shuffle(result)
    return Zx(result)


def invertmodprime(f, p):
    T = Zx.change_ring(Integers(p)).quotient(x ^ n-1)
    return Zx(lift(1 / T(f)))


def invertmodpowerof2(f, q):
    assert q.is_power_of(2)
    g = invertmodprime(f, 2)
    while True:
        r = balancedmod(convolution(g, f), q)
        if r == 1:
            return g
        g = balancedmod(convolution(g, 2 - r), q)


def keypair():
    while True:
        try:
            f = randomdpoly(61, 60)
            f3 = invertmodprime(f, 3)
            fq = invertmodpowerof2(f, q)
            break
        except Exception as e:
            pass
    g = randomdpoly(20, 20)
    publickey = balancedmod(3 * convolution(fq, g), q)
    secretkey = f
    return publickey, secretkey, g


def encode(val):
    poly = 0
    for i in range(n):
        poly += ((val % 3)-1) * (x ^ i)
        val //= 3
    return poly


def encrypt(message, publickey):
    r = randomdpoly(18, 18)
    return balancedmod(convolution(publickey, r) + encode(message), q)


n, q = 263, 128
publickey, _, _ = keypair()

flag = open('flag', 'rb').read()
print(publickey)

for i in range(24):
    print(encrypt(b2l(flag), publickey))

明らかにNTRUの問題で、フラグを暗号化した24個の異なる暗号文が手に入る。

NTRUで、同じ公開鍵で同じ平文を暗号化したときはMultiple Transmission Attackという攻撃が可能らしい https://ntru.org/f/tr/tr006v1.pdf

0番目の暗号文 $e_0 = r_0 * h + m \mod q$ と $i$ 番目の暗号文 $e_i = r_i * h + m \mod q$ の差を考えると

$e_0 - e_i = h(r_0 - r_i) \mod q$ となり、更に変形して $r_0 - r_i = (e_0 - e_i) * h^{-1} \mod q$ となる。このとき、 $r_i$ の係数の範囲は $\lbrack -1, +1 \rbrack$ と小さいので、十分な数の $r_0 - r_i$ の組を手に入れたら、 $r_0$ の候補が定まる

ただし、現実には $h$ のinverseである $h^{-1}$ を求めるのは不可能である（なぜなら逆数がないから……）

そこで直接の逆数の代わりにpseudo inverseを考える。

もともと $h \in \mathbb{Z_{128}} \lbrack X \rbrack / (X^{263} - 1)$ では逆数が存在しなかったが、 $\mathbb{Z_{2}} \lbrack X \rbrack / (X^{263} - 1)$ で考えることでうまく行く。

$\mathbb{Z_{2}} \lbrack X \rbrack$ では $X^{263} - 1$ は既約ではないので、この多項式環は別の複数の多項式環の直積として表すことができる。それぞれの多項式でinverseをもとめてCRTで $\mathbb{Z_{2}} \lbrack X \rbrack / (X^{263} - 1)$ でのinverseを求め、さらにそれをHensel's Liftで $\mathbb{Z_{128}} \lbrack X \rbrack / (X^{263} - 1)$ 上のpseudo inverseに持ち上げる

もっとくわしいことは https://hackmd.io/@vishiswoz/ryDA_PGPo に書いてある