Find short vectors in two-dimensional lattices

Notes for $An\ Introduction\ to\ Mathematical\ Cryptography$

“A toy model of a real public key cryptosystem”

这里以 An Introduction to Mathematical Cryptography 书中的一个简单的加密模型为例，简单介绍一下通过高斯格基规约算法（Gaussian Lattice Reduction）解决二维的格上的寻找最短向量问题。

最近在书中看到这个，刚好 西电新生赛@Mini L-CTF 有两个题目刚好是用这个模型实现的，当做例题整个 writeup，感谢出题人。

task.py

from Crypto.Util.number import bytes_to_long, getPrime, inverse
from gmpy2 import iroot

q = getPrime(1024)
f = getPrime(511)
g = getPrime(511)

while g < iroot(q//4, 2)[0] or g > iroot(q//2, 2)[0]:
    g = getPrime(511)

f_inv_q = inverse(f, q)
h = f_inv_q*g % q
m = bytes_to_long(b'flag')  # flag is base**(flag)
r = getPrime(510)
e = (r*h+m) % q
print(f)
print(g)
print(q)
print(e)
'''
f = 4685394431238242086047454699939574117865082734421802876855769683954689809016908045500281898911462887906190042764753834184270447603004244910544167081517863
g = 5326402554595682620065287001809742915798424911036766723537742672943459577709829465021452623299712724999868094408519004699993233519540500859134358256211397
q = 172620634756442326936446284386446310176482010539257694929884002472846127607264743380697653537447369089693337723649017402105400257863085638725058903969478143249108126132543502414741890867122949021941524916405444824353100158506448429871964258931750339247018885114052623963451658829116065142400435131369957050799
e = 130055004464808383851466991915980644718382040848563991873041960765504627910537316320531719771695727709826775790697704799143461018934672453482988811575574961674813001940313918329737944758875566038617074550624823884742484696611063406222986507537981571075140436761436815079809518206635499600341038593553079293254
'''

其中私钥为 ( f , g ) ，公钥为 ( q , h ) ，这个已经给了私钥，所以解密过程非常简单。

$e \equiv rh+m \equiv \frac{rg}{f}+m \ (mod \ q)$

两边同时乘 $f$:

$\tag{1}ef \equiv rg+mf \ (mod \ q)$

这时注意到 $g$ 的范围是$\sqrt{\frac{q}{4}} < g < \sqrt{\frac{q}{2}}$，所以：

$rg+fm< \sqrt{\frac{q}{2}}\sqrt{\frac{q}{2}}+\sqrt{\frac{q}{2}}\sqrt{\frac{q}{4}}< q$

那么同余式 $(1)$，可以直接看做等式：

$\tag{2}ef = rg+mf$

接下来只需计算：

$(ef)f^{-1}\equiv (rg+mf)f^{-1} \equiv rgf^{-1}+mff^{-1} \equiv mff^{-1}\equiv m \ (mod\ g)$

就得到明文了。

from Crypto.Util.number import long_to_bytes,inverse
f = 4685394431238242086047454699939574117865082734421802876855769683954689809016908045500281898911462887906190042764753834184270447603004244910544167081517863
g = 5326402554595682620065287001809742915798424911036766723537742672943459577709829465021452623299712724999868094408519004699993233519540500859134358256211397
q = 172620634756442326936446284386446310176482010539257694929884002472846127607264743380697653537447369089693337723649017402105400257863085638725058903969478143249108126132543502414741890867122949021941524916405444824353100158506448429871964258931750339247018885114052623963451658829116065142400435131369957050799
e = 130055004464808383851466991915980644718382040848563991873041960765504627910537316320531719771695727709826775790697704799143461018934672453482988811575574961674813001940313918329737944758875566038617074550624823884742484696611063406222986507537981571075140436761436815079809518206635499600341038593553079293254
m = (e*f % q) % g
m *= inverse(f, g)
print(long_to_bytes(m % g))
# y0u_ar3_s0_f@st

从公钥得到私钥

上面只是介绍了这个简单的加密模型，如果要破解它，就要从公钥 $(q,h)$ 计算出私钥 $(f,g)$ ，其中 $h=g/f$，并且 $g$ 和 $f$ 都是在 $\sqrt{q}$ 的数量级。

所以可以找到符合条件的 $(F,G)$ 就可以解密了，所以构建向量：

$F(1,h)-R(0,q)=(F,G)$

其中$v_1=(1,h),\ v_2=(0,q)$，所以短向量 $(F,G)$ 在格$L=\{a_1v_1,a_2v_2\}$ 中。

现在问题就被转化成二维的格的最短向量问题，由于是二维的格，可以用高斯格基规约算法。

from gmpy2 import iroot, sqrt
from Crypto.Util.number import *
q = 126982824744410328945797087760338772632266265605499464155168564006938381164343998332297867219509875837758518332737386292044402913405044815273140449332476472286262639891581209911570020757347401235079120185293696746139599783586620242086604902725583996821566303642800016358224555557587702599076109172899781757727
h = 31497596336552470100084187834926304075869321337353584228754801815485197854209104578876574798202880445492465226847681886628987815101276129299179423009194336979092146458547058477361338454307308727787100367492619524471399054846173175096003547542362283035506046981301967777510149938655352986115892410982908002343
e = 81425203325802096867547935279460713507554656326547202848965764201702208123530941439525435560101593619326780304160780819803407105746324025686271927329740552019112604285594877520543558401049557343346169993751022158349472011774064975266164948244263318723437203684336095564838792724505516573209588002889586264735

def gaussian(v1, v2):
    while True:
        if sqrt(v2[0]**2+v2[1]**2) < sqrt(v1[0]**2+v1[1]**2):
            v1, v2 = v2, v1
        m = int((v1[0]*v2[0]+v1[1]*v2[1])/(v1[0]**2+v1[1]**2))
        if m == 0:
            return (v1, v2)
        v2 = [v2[0]-m*v1[0], v2[1]-m*v1[1]]

s1, s2 = gaussian([1, h], [0, q])
f, g = s1[0], s1[1]

m = (e*f % q) % g
m *= inverse(f, g)
print(long_to_bytes(m % g))
# l1Ii5n0tea5y