记一个NTRU板子题

巅峰极客（~~不知道哪一年~~）——NTRUE

先上task！

from Crypto.Util.number import *
import gmpy2
from flag import flag


def generate():
    p = getStrongPrime(2048)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        return (p, f, g, h)


def encrypt(plaintext, p, h):
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    c = (r * h + m) % p
    return c


p, f, g, h = generate()
c = encrypt(flag, p, h)
with open("cipher.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")

我们可以得到这几个关系其中f为1024位的素数，g为768位的素数，p为2048位的素数，h至多768位

从2式来看，我们已知h、p、c，唯独不知道r，因此只需要求出r就可以得到明文。但r是一个1024位的大数，爆破r几乎是不可能的，因此只能想办法绕过r

狠狠的解题（被拷打）

题目既然叫NTRU，那肯定是NTRU的方式去解决。为了加深印象，就再推一次

在之前的分析中，有两个被忽略掉的变量，f和g

step 1

我们假设已知f和g

将（1）式代入（2）式，并同时乘上f 注意看右边的式子，由于p是2048位，易得小于p，因此的值就是在已知f和g的前提下我们就得到了求m的公式

step 2

另一个问题摆在了面前：如何求f和g

求得f和g需要用到格（lattice）

我们用已知量h和p构建一个向量用这个向量作为一组基，构建一个格

将f和g写成行向量的形式稳妥起见，验证一下这个向量是否在S所张成的格上故有根据格的性质，可看作是格的另一组基，故在S张成的格上

不只一组值，任意一组值都可以求出m，因此我们选择最短的一条，本质就是SVP问题

在二维格上求最短向量用高斯消元可以有效解决：

令L是由两个基向量v1, v2所张成的2维lattice，假设|v1| < |v2|，通过减去v1的某个倍数来使得v2变短。 这样我们就能够得到一个与v1正交（垂直）的新向量v2，且使得v2变短。

减完，如果v1 > v2，交换v1, v2，继续；否则，就结束

def GaussLatticeReduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1*v2 / v1.norm()^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

h = ...
p = ...
v1 = vector(ZZ, [1,h])
v2 = vector(ZZ, [0,p])
f,g = GaussLatticeReduction(v1, v2)[0]
print(f)
print(g)

也可用sage自带的LLL算法求解

h = ...
p = ...
s = matrix([[1,h],[0,p]])
f,g = s.LLL()[0]
print(f)
print(g)

验证一下f和g的位数，与task一样，这样就得到了f和g

接下来求解明文就很好做了

exp

from Crypto.Util.number import *

h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757
s = matrix([[1,h],[0,p]])
f,g = s.LLL()[0]
#print(f)
#print(g)
inv_f = inverse(f,g)
a = c*f%p
m = a*inv_f%g
print(long_to_bytes(m))
#b'flag{c3bb1f88-2c0b-48fc-9902-beada6d50df6}'

Sth.

说一下个人对这种题粗浅的理解

核心点是构造一个基，让(f,g)在这个基张成的lattice上，才能变成SVP问题去解决

Canzik's Blog