2022 巅峰极客 Crypto

题目质量一般，知识问答还全是搬运今年 ciscn 的。 然后三个队友都没啥空，就我一个做了两道密码，排 88 名，对我这个菜鸡来说也还行吧。

point-power

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

assert len(flag)==42
p=getPrime(600)
a=bytes_to_long(flag)
b=randrange(2,p-1)
E=EllipticCurve(GF(p),[a,b])
G=E.random_element()

x1,y1,_=G
G=2*G
x2,y2,_=G

print(f"p = {p}")
print(f"b = {b}")
print(f"x1 = {x1}")
print(f"x2 = {x2}")
'''
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
'''

这题完全是现学现卖，之前只听说过椭圆曲线，然后就跑去学抽代忘记回来了。。。 首先查到椭圆曲线的加法（两点相同的情形）：

又在 Sagemath 文档查到曲线定义 ，就能联立出一个一元二次方程，exp 如下：

p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727

K = GF(p)
n=(K(x2+2*x1)).sqrt()
P.<x>= PolynomialRing(K)
A=1
B=6*x1**2-4*n**2*x1
C=-(4*n**2*x1**3+4*n**2*b-9*x1**4)
f=A*x**2+B*x+C
roots=f.roots()
print(roots)
flag=roots[1][0]
from Crypto.Util.number import *
print(long_to_bytes(int(flag)))

strange curve

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

def add(P,Q):
    (x1,y1)=P
    (x2,y2)=Q


    x3=(x1+x2)*(1+y1*y2)*invert((1+x1*x2)*(1-y1*y2),p)%p
    y3=(y1+y2)*(1+x1*x2)*invert((1-x1*x2)*(1+y1*y2),p)%p

    return (x3,y3)

def mul(e,P):
    Q=(0,0)
    e=e%p
    while e:
        if e&1:
            Q=add(Q,P)
        P=add(P,P)
        e>>=1
    return Q

def Legendre(a,p):
    return (pow((a%p+p)%p,(p-1)//2,p))%p

def get_ts(p):
    p=p-1
    count=0
    while p%2==0:
        count+=1
        p=p//2
    return count,p

def get_nonre(p):
    a=random.randint(1,p)
    while Legendre(a,p)==1:
        a=random.randint(1,p)
    return a

def amm2(a,p):
    t,s=get_ts(p)
    ta=pow(get_nonre(p),s,p)
    tb=pow(a,s,p)
    h=1
    for i in range(1,t):
        d=pow(tb,2**t-1-i,p)
        if d==1:
            k=0
        else:
            k=1
        tb=(tb*pow(ta,2*k,p))%p
        h=(h*pow(ta,k,p))%p
        ta=pow(ta,2,p)
    return h*pow(a,(s+1)//2,p)%p  

def solve(a,b,c,p):
    tmpa=1
    tmpb=b*inverse(a,p)%p
    tmpc=c*inverse(a,p)%p
    assert Legendre(tmpb**2*inverse(4,p)-tmpc,p)==1
    res1=(amm2(tmpb**2*inverse(4,p)-tmpc,p)-tmpb*inverse(2,p))%p
    res2=(-amm2(tmpb**2*inverse(4,p)-tmpc,p)-tmpb*inverse(2,p))%p
    return (res1,res2)

def lift(x,a,b,p):
    tmp=b*(x**2-1)*inverse(a*x,p)%p
    return solve(1,-tmp,-1,p)[0]

p=9410547699903726871336507117271550134683191140146415131394654141737636910570480327296351841515571767317596027931492843621727002889086193529096531342265353
a=54733430689690725746438325219044741824500093621550218736194675295708808435509
b=75237024593957256761258687646797952793573177095902495908321724558796076392871
x=bytes_to_long(flag)

while True:
    try:
        y=lift(x,a,b,p)
        break
    except:
        x+=1
        continue

assert a*x*(y**2-1)%p==b*y*(x**2-1)%p

P=(x,y)
e=65537

eP=mul(e,P)
print(f"P = {P}")
print(f"eP = {eP}")
'''
P = (56006392793427940134514899557008545913996191831278248640996846111183757392968770895731003245209281149, 5533217632352976155681815016236825302418119286774481415122941272968513081846849158651480192550482691343283818244963282636939305751909505213138032238524899)
eP = (mpz(8694229840573103722999959579565187489450818138005222030156495740841851804943200684116883831426548909867463656993852596745698999492932194245562062558787005), mpz(9279986963919197374405152604360936066932975197577643570458423456304679111057526702737279809805694360981565554506626018364382736924914907001214909905449002))
'''

这题真的是蚌不住，刚放出来解出数就蹭蹭往上涨，还有点怀疑人生，然后仔细观察题目，一看上面，什么玩意，再看下面，什么玩意。。。 直接拿第一个数 long_to_bytes ，得到 flag。

Learning with fault

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

class RSA():
    def __init__(self,p,q,e):
        self.p=p
        self.q=q
        self.e=e
        self.phi=(p-1)*(q-1)
        self.d=invert(self.e,self.phi)
        self.dp=self.d%(p-1)
        self.dq=self.d%(q-1)
        self.n=p*q
        self.N=getPrime(512)*getPrime(512)

    def sign(self,message):
        m=bytes_to_long(message)
        sig_p=pow(m,self.dp,self.p)
        sig_q=pow(m,self.dq,self.q)
        alpha=q*invert(q,p)
        beta=p*invert(p,q)
        return long_to_bytes((alpha*sig_p+beta*sig_q)%self.n)

    def corrupt_sign(self,message):
        m=bytes_to_long(message)
        sig_p=pow(m,self.dp,self.p)
        sig_q=pow(m,self.dq,self.q)
        alpha=q*invert(q,p)
        beta=p*invert(p,q)
        return long_to_bytes((alpha*sig_p+beta*sig_q)%self.N)

    def verify(self,message,sign):
        return long_to_bytes(pow(bytes_to_long(sign),self.e,self.n))==message

p=getPrime(512)
q=getPrime(512)
e=65537
rsa=RSA(p,q,e)

with open("sign.txt","w") as f1:
    with open("corrupted_sign.txt","w") as f2:
        for _ in range(6):
            message=os.urandom(64)
            sign=rsa.sign(message)
            corrupted_sign=rsa.corrupt_sign(message)
            assert rsa.verify(message,sign)
            f1.write(str(sign)+'\n')
            f2.write(str(corrupted_sign)+'\n')

enc=pow(bytes_to_long(flag),rsa.e,rsa.n)
print(f"n = {rsa.n}")
print(f"N = {rsa.N}")
print(f"e = {rsa.e}")
print(f"enc = {enc}")
'''
n = 99670316685463632788041383175090257045961799409733877510733415402955763322569510896091638507050126669571444467488936880059210773298729542608112756526719533574432327269721804307073353651955251188547245641771980139488000798458617636759823027148955008149512692983471670488580994385743789385091027299901520585729
N = 81332992898551792936282861980393365170738006789835182134055801566584228471896473385776004610279937176800796971820133195300006470892468060034368863410462219133248069442508287516929262751427926825122839525496671527936622212986733708071962237633082743396115729744192159064241674410003857168101669882043743570731
e = 65537
enc = 2476965183785968993595493003363618829317072815989584886372189393899395623714779397354978469504773556228655475355703015337932838278988328384587983506790841663233499939173166353582189202860394411808445422387063648198432242875738065748287034529713834303346017134249834382745931627301273142828893469374138264396
'''

出题论文：https://eprint.iacr.org/2011/388.pdf 这题一开始是搜到了论文，瞟了两眼，以为不是，就没看下去了。。。 后来学长发给我这篇，我焯了两个钟复现出来了，说不定真有机会现场解出，唉还是太菜。 照着论文的 Attack Summary 敲就行了，一开始没理解到 向量的意思，直接从格子拿，跑不出来，学长问我 和 的选取是不是有问题，我才知道要枚举出所有 和 。然后 和 在 0 到 10 间选取也不行，改成了 −10 到 10 。 exp 如下：

from tqdm import tqdm
from itertools import combinations
from sage.all import *
from Crypto.Util.number import *
co_sig = [b"\x17\x8bb3\x11\x1b\xb9\xb9\xc6M\xb0\xaa\x07-\x1ar\xff\xfb\xb4&H7!\xb8\xa1\xce\x07\x8b\x84M\x0bw=m\x193Oc\x97w\x8f\xffy4\xa1\x99\xfcW\xf9|\xeb\xa4\x00\x1eD*\xe8-'\xa9\xef\x9d\x13*\xf4\xbe\x9d\x9b&w\xcb\xfd\xb3\xb6\xa3n\xb8\xb4\x97vT\xec@\x86\xd1R\xb0\n\xe1uC\xbc\x14\xeb\xceSu&'{\xb9\x12\x90\x82\xc7,\xdbr\xebP\xe1j\x11E\xd5\x17\xe1\xd0D\xe7z\x94vt\xbf\x1a\xc4+",
          b'\x1dJ\xc5\xb2\xbe\x05\xe6\xc8T\n\xbe"\xbeU\xed\xba\xec\x85\x05\x8b\x8ayE\xa3}0\x1dk\xa7\x10\xe2E\x19\xfe\x10\x90\xef\r\xdbV\x8b\x87|(\xd1\xb5\xfd\xb9\x14\x84\x05\x03\x81\xc8\xf6\xe5\x8a\x92\xa0\x01I\x8aG:\xc19\x9e\xf0\x8eZ\\Yx\x80|\xb7\x80\x0e\xcd\xa3\xba6\xf8\x98\xb1pB\x05\x8aT#\xbf\x1e\x1b~\xcb\xf5\t\xa2H9\xc9n\x81e\xa2\x15\x97\x11\xe4\x93\xf2\xe6\x80\x97\x99G\xb5\xfe\x07/\xd2\xbd\xad\xcf\x04\x9e\xd0',
          b'Gs\xda\xb8\x8a\x85\xccK\xf7\xa8y\x16\xa5\xf0\x06\xbe\xeb\x83&}a\x85q\x8d:\x1fSb\xb8\xc5\x84\xba*[\xe7\xbb{\x86\xd3\xb3r\xb6\xaaCN\x93\x1d<(\xe2\x1c;\x8crU\x8fD=W\xa7\x0b\xc7\xeag\x96\x06\xd6\xbb\xe4\x04b\xd8\x02\x12\xd6\xfa2\x1e#\xf0\xde\x8b\x88M\xd2\xf47\\\x98\xe0\x04Fu\x1bsy\xf2\xc4\xad\xd6Y\x81u~B:\xd2\x1f\xb3\xab\x01:\xfa\xdf\x19J8\xd0\x18RN\xfe,CA\x15\xb3\xe0',
          b"0I\xda5\x9f\x05v\x17\xdc\xd4q\xd6\x83,\x9d\r\xccc\x8a\xa1\xd4U\xd3\x18\xc9\xc6g\xcd\nX\x99Ah\xed}\xf3\xb1(\xd5I\xc6\x0f@yw9\x9d\xfdv\x15x\xeaRA\xd6\xb0\x1e\xb5B\xe5\x05cc\x06m\xf4NN'\x02q\x1a\x11\xe4\x87P:\xc8\x11a\x9f\xbd\x9c\x98x\xda\xea\xc4\xa8f\x89s\xcaJ\x7f\xeb\xd8\xc1G#\xf4\xdc\xe2\x01\xf2\xa5\x95\x19`)2!\xf5\xb9\xf0\xf2\xbb\xf8\x0bF&&`\xfd*\xe1\xf2\x9c",
          b':\x99/Hxt\xd1\xd4\xaaB\xd6H\x16\xe1\xc9\xe2\xb3\xc3\xa9b\xd3\x96\x9c\x05x6\xf1\xc3d\xa2\xd1U+.\x1b\xac^\xf6Mh7\xb7\x03\x8e\xdc\xca\x0bn\xac\xed\x92\xb8x\x04)\x0f|\x11\xcc\xfa\xf2\\\xba\xee\xc4X\xa8(\x05\xf2\xb5\x8f&\xf3\xff\x1eB\xe7\x94\xf4\xa6\x00!\xe5v\xd9x\xf0s\x94\xf4D(\xa9g\x118\xa7z\x83\xad\xdb\xe6\xe3\xe7\xf8\xf2\xef\xe5@\xe9\x13\x00OB\xcc\x05\xd1,_=\xd2/Og\x81\xa6+',
          b'\x1c|\xb6\xcc\xdfj\xc5\xa0s\xac w\xa6\xf2\x87D\xe3\xf9Y\xf5=\xf0\x0b\xd9\xea\x89,+e\x1e\xb7m#\x99\xd1\x87\x17Z\xed\x1d\xc8\x97;\xa0K\x05.\xaa<\xc6s\xcf\xa2\xa2\\PO\x12&\xb4\x11\xec\xad\x10\xf8\xf7\xd1\xd3_\x80\x17\xe0\x1eP\x93\xe3\xc2\x1e\x03\xea]^\xc6a\x9c\xcb\x90\xbb\x9f\x8by\xa5dhM\xce\xc7\xbc\xf7\xafe\xcf\xc1\xf1\x18@\x1e\xe2\xdb\xfb\xe4^\xc8\xe7\x19\xccnY\xc6o\x7fL\x9fV\xd4\xc4\x15\xe8',
          ]
sig = [b'\t\x8b\xde\x98\x84\x1d\x9e\xd4\xa0\xb7f\xe0\x05\xb1\xbd8\xb9G\xe3\x0c\x83\x8a\xe5\xf0G7\x12\x1eT\x85o-B\xe4_\xd2\x04\xd9:\xab\xdf\xa1 \x8f\xedt+\x0f\xce\xb5\x90\xaaK\xf0U~v=\x84\xe7$G\xf5\xfb\xd3ok~V\x1a\xec&\x15\x18Y\x0c\x80u\xafF\xf1\x10\x9f\xf2\xe6\xa6\x9a\xbb\xbd+\xa4l\xa9\x11\xd5\t\x13\x16\xa3\xde\xe1\xdfZ\xa9$r\xb5`\xc9"\x11\xab\xc5\x87\xc4\x1d@\x9e\xa4t\xdb#\xbdj\xcb\x95\xefK',
       b'z/\xd6\xfb\xd8\xfa\xc4\xed\xbd\x99\xd0\xa0\x90\xcb\xca\x83\xd8B\xa7\xf4\xbd\xe0\xc2&\x1aQl(\xd6p\x8f\x89=tT\xf1(\xeb\xab\x84[oR\x1fl=\xda\xf5\x18q\x8f\xa7k\x00\x1b\x1a\x0ei\x1fa.ho\x15\x04\x12\xe4\xc2\xd7\x19\x92\xc3\x9b\xfe\xd5\xb6R\xf8\x95\x9fr\x93\xddD\x1c[\x873\xd5\x06\x1b\xa5\x82/6\x9a\x13\xcf\xa4\xcd\x0e]\t\xad?\xd6\x84\r\x90\xef\x86\xf15)\xe34\xf7\xb77\xef\x0c&\xdb8\xa6\xe0\xa5a',
       b'U\x0b\xf6\x9cm])1\xe2\xad\xf9G\x8f\xa2\xbc}\xd7\x18\x89\xa4\xfdFQ\x80m"\xf9\to^\xd9A\x98\xd2\xca\x1e(b\xa8\xbe\xc2m\xf7\n[O\x00\xbc\x87\x17\xed\x0cG\xf2=H\x0e\xc0\x14+\xcb\xd0\x1feT2\xf2Th\xec\xc2\xcf>6,<\x88X\x8f\xe9g\xa8\x00\xafr\x05\x95\rj\x9c\xc6\n\xbb\x8a\x019\xc1\x1ef#\x02[Rh\xd8\xdc|{6\xeb\xe8U\x91\xa4\xeb}\xf4s;E\xe72$i\xdft\xff\'',
       b'[\x94\x95T\xf4\xc4\xca\x8drO\x80\x14\xc9<H\xa2a\xdc\xf4`\xac>\xab\x03\xfa\x80Sx\x99\x14\x83$U\x0b\xfa\x8fv\xfd\xda\x1a\xa0\xebY\xaa\x01\xe2XsG\t\xcf\xae\xa0\xbf\x82iG\tQ \xb1\xfe\xa5k\x12\xd9\x12\xf7\x95\xa3\xa5\x8d`z\x19\x1a\x90-\x9aj\x15\xf6f>\x18\x08\xb8\x1f\x88\x1a\x80Th\xd0\x15\x9bw#\'`K\xa5\xf1\xbf"\xe79\xaf\xc7z%p\xa5\x9f\x14\xef\'1\x11\x05Gg\xe9\xda\xc9\x18~[',
       b':\xefRE\xd7\xa1?\xf3\xb5\xf7\xdd\xe2\xb6~\x85014\xc0\x8a\x80\xe1\xb5#\x94\x10\xb2\xa0\xfe\x87\xd1t\xc3$&\xde8\x195\xcd\xf4@3\x15\xcaK\xcc\xcd\r:\x83*\xd7l\xb6\xf2} \tJ\xb5xKfjh.\xfb\xb5\x91\xc6\xf2x\x8e\x83\xdc\xc3\xef\x8b\x8dW\xa6\xa6\xb0w\xd8\xf2G\xa5-\xc3\x87\x17;\xedH`:\xcd\x08ts\x9eqPE\xd7\xfc\xc4\x98\xb5\xe0\xad\xb7A\x7f\xcb\x01\xbd\x98\xd3Ea\xb9\x07\x80\xf8\x19',
       b"8\xca\x7f!;\\\xde\x1b\x80i\x9b!\x1c??u\x13\x955\xd0xG\xff\xd7\xba\xfe+\x95\x0eu^\x15\x1a\x0e*\xfe\x8a\xafM\xc0\xd1Ty\xd7\xf1\xa7@\xd6\xa6\xee\x0c:It\x1a\xeag\xfc\x0c\xaf\x02<\x03T)\xeb\xb0\x15\x1cz\x85\x992\xa9\xbe\x9bm\xc4D\x83\xf7\xb5T\xdd9?\x94\xd4\x13\xb4\xb3\x8d\xa9\x92\x9dt\x86\xdb\x0b$\x19l\xb1\xb9\x05'o\xf3!\t\x01\x93'z\x15P\x88\xd7iN\n\x8bA\xb5\xd2}\xe8\x10"
       ]
n = 99670316685463632788041383175090257045961799409733877510733415402955763322569510896091638507050126669571444467488936880059210773298729542608112756526719533574432327269721804307073353651955251188547245641771980139488000798458617636759823027148955008149512692983471670488580994385743789385091027299901520585729
N = 81332992898551792936282861980393365170738006789835182134055801566584228471896473385776004610279937176800796971820133195300006470892468060034368863410462219133248069442508287516929262751427926825122839525496671527936622212986733708071962237633082743396115729744192159064241674410003857168101669882043743570731
e = 65537
enc = 2476965183785968993595493003363618829317072815989584886372189393899395623714779397354978469504773556228655475355703015337932838278988328384587983506790841663233499939173166353582189202860394411808445422387063648198432242875738065748287034529713834303346017134249834382745931627301273142828893469374138264396


def orthogonal_lattice(B):
    _d, _n = B.nrows(), B.ncols()
    _c = 2 ** min(((_n-1)/2+(_n-_d)*(_n-_d-1)/4), 20)
    for b in B:
        _c *= b.norm()
    B_bot = (ceil(_c)*B).stack(identity_matrix(ZZ, _n))
    B_r = B_bot.transpose().LLL()
    LB = B_r.matrix_from_rows_and_columns(range(_n-_d), range(_d, _n+_d))
    assert (B*LB.transpose()).is_zero()
    return LB


v = [crt([bytes_to_long(co_sig[i]), bytes_to_long(sig[i])], [N, n])
     for i in range(6)]

Lv = orthogonal_lattice(matrix(ZZ, v))

result = orthogonal_lattice(Lv.matrix_from_rows(range(0, 6-2)))

for x, y in combinations(result, 2):
    for a in tqdm(range(-10, 10)):
        for b in range(-10, 10):
            z = a*x+b*y
            if z.norm() > sqrt(6*n):
                continue
            else:
                vv = vector(v)-z
                for i in vv:
                    if gcd(i, n) != 1:
                        p = gcd(i, n)
                        assert n % gcd(i, n) == 0
                        q = n//p
                        phi = (p-1)*(q-1)
                        d = inverse_mod(e, phi)
                        m = long_to_bytes(int(pow(enc, d, n)))
                        print(m)
                        exit()

原理

RSA-CRT 签名中计算了：

然后签名 ，其中 ， 。 题目中给出 6 对签名，每对签名用 CRT 不难算出

其中 和 和 一个数量级， 和 又和 一个数量级，故右式远小于 ，那么上式在整数域上是成立的。 一对算不出，但是多对可以，组成向量，有：

其中 和 是分量 位的未知向量， 和 是有关 和 的 CRT 系数。 不难计算出一组与 中正交于 的向量的格 的约化基 。（可能此时你会疑惑为什么是 个向量，下面的拓展里有解释） 特别地，我们有：

（也不是很特别的感觉） 现在观察方程 ，最小的非零解 是 ，其中 盲猜是非常小的（经测试基本在10以内），意味着 中 常量是非常小的。（啥玩意？）对 ，有以下两种可能：

情形1： 。此时 属于 中与 和 正交的向量的格

情形2： 和 有绝对值 ，其中 是一个小常数。因为 和 的范数都不超过 ，由柯西-施瓦茨不等式，这意味着

因为格 的秩是 ，当全部 个向量 线性无关时情形1不成立，所以最长的 应该在情形2中，因此 。另一方面，其他向量形成一个秩为 的格，且体积

盲猜是一个随机的格。特别地，我们有：

一旦 ，这个长度就远小于 。假设是这种情况，那么对于 ， 应该是情形1中。这意味着这些向量生成 中一个满秩的子格 。 取正交格，我们得到 。因此， 和 属于 的正交格 。令 为一组该格的约化基，我们可以枚举 中的长度不超过 且为 和 线性组合的所有格向量。高斯启发式表明这大约为：

这样的向量，所以这肯定是可行的。对这些向量 ，我们计算 。我们将因此很快在其中找到 ，因为 是一个 中长度 的向量。但根据 的定义，我们有：

故 ，从而分解 。

拓展阅读-正交格

令 为 （这玩意念Lambda）中的向量。如果这 个向量在 上线性无关且 中的任意元素可以由 整系数线性表出，则这 个向量形成 中的一组基。 中至少存在一组基。 的基都有相同的基数，称为 的维度。

如果 包含 ，且两者有相同的维度，则称 为 在 上的一个子格。（子格的定义？） 的所有基张成相同的 的 向量子空间（啥玩意？），记为 。 上 的维度与 的维度相同。令格 。 是 的一个子格。如果 ，那么我们称 是一个完备格，特别的， 是一个完备格。

笔者注记：

这里首先将 张成一个有理数空间，不局限于整系数向量组合了，记为 的E我猜是欧几里得的意思？然后与 相交得到的是整数点集合 ，如此 是 子格的事应该挺自然的。然后如果两者相等，想象一下，都那样张成了都找不到新的点，那这个格确实也挺完备。 PS:发现自己念了十年的欧几里得，难怪输入法打不出来（）

令 为一般意义上的欧里几德内积， 是它对应的范数 （奇怪的表示方法）。令 是关于该内积的正交向量子空间。我们定义正交格 。因此， 是一个 上的完备格，其维度为 。这意味着 等于 。令 为 的一组基。

笔者注记：

看到这就有点迷糊了，捋一捋： 是 张成出的有理空间，然后 是其正交向量子空间，即任意从 和 分别抓两个向量出来，其内积都为 。 再然后 是 的一个子格，注意到 把 所有整数点都框进去了，这就很有意思了，由上面的定义就不难得出正交格 是一个 上的完备格。 至于其维度为何是 ，有个概念叫正交补，就是正交空间的维数是刚刚好的，对于列空间维数为 的矩阵 ，其左零空间的维数是 ，相加恰好为 。举例来说，三维中与线正交的是二维空间，与面正交的是一维空间。 这篇 paper 习惯用 表示正交向量子空间，但似乎 的写法较为广泛。

在 的正则基上解析每个 如下：

（这里吐槽一下，由于下划线和 Markdown 语法有冲突，如果不加反斜杠， 写成 Latex 就会炸，下文一开始也炸了几回，弄了几次才发现是这问题）

定义整数 的整数矩阵 ，格 由 的列向量张成，我们称 由 张成。令 为 的对称 Gram 矩阵。 的行列式是与 无关的正整数。 的行列式被定义为 。

笔者注记：

这是的 应该是 的意思，又是奇怪的写法（） 至于 Gram 矩阵，中文音译为格拉姆矩阵，对 维欧氏空间上的 个向量，其 Gram 矩阵为

不难看出这个可以等价表示为 ，得出的矩阵也显然是对称的。 这里 不是一个方阵，故不能直接求出其行列式，那么就应该通过其 Gram 矩阵来求行列式，这里我觉得应该是 ，但我不确定。

定理1 令 为 上的完备格，那么 。 证明：我们有 和 。从另一篇论文（我也没读过）我们知道：

其中 表示 上的极格。但 （？为什么要说但呢？）且 ，故 。

推论2 令 为 上的格，那么 。

定理3 令 为格 在 上的一组 LLL 约化基，那么：

  2. 对任意线性无关的向量 ，当 时，有：

我们现在描述计算正交格的一组 LLL 约化基的基本方法。令 为 的一组基， 为其对应的 的矩阵。令 为一个正整数常量。定义 为 上由以下 矩阵张成的格。

矩阵 被分成两块：上面 部分是 ，下面 部分是单位阵。 设 和 是两个投影，将 的任何向量分别映射到由其前 个坐标构成的 向量和由其最后 个坐标构成的 向量，所有投影都与正则基有关。（这段翻译累死我了） 令 为 的一个向量并记 ，那么

因此，当且仅当 时有 。此外，如果 ，那么 。

定理4 令 为格 的一组 LLL 约化基。若

则 为 的一组 LLL 约化基。

使用阿达马不等式，我们得到以下算法：

算法5 给定一组 上格 的基 ，该算法计算一组 的LLL约化基。

  1. 选取

  2. 计算 的整数矩阵 和 对应的 矩阵

  3. 计算由 张成的格的一组 LLL 约化基

  4. 输出

可以证明，这是一个关于空间维数 、格维数 和 比特长度的任何上界的确定性多项式时间算法。在实践中，不需要选择这样大的常数 ，因为 LLL 算法的理论界非常悲观。（翻译了这么久都看不懂，我也很悲观.jpg）

笔者注记：

和 表示向上取整，例如 。

实现

之前看过 Herry 师傅从 dbt 那抄的一个求法是用左零空间求解，代码如下

def orthogonal_lattice(B):
    LB = B.transpose().left_kernel(basis="LLL").basis_matrix()
    return LB

但笔者发现这样似乎只能在低维下求解，高维情况下时间会爆炸（至少试过一夜都没跑出来） 于是照着 paper 搓了一个 implemention ，快了很多，三分钟左右就能求解 矩阵的正交格，代码如下

def orthogonal_lattice(B):
    _d, _n = B.nrows(), B.ncols()
    _c = 2 ** min(((_n-1)/2+(_n-_d)*(_n-_d-1)/4),20)    # this bound can be adjusted as needed
    for b in B:
        _c *= b.norm()
    B_bot = (ceil(_c)*B).stack(identity_matrix(ZZ, _n))
    B_r = B_bot.transpose().LLL()
    LB = B_r.matrix_from_rows_and_columns(range(_n-_d), range(_d,_n+_d))
    assert (B*LB.transpose()).is_zero()
    return LB

参考

标签CTFCrypto
日期2022 年 8 月 18 日
分类CTF
文章作者weyung
文章链接https://weyung.cc/posts/bc807997/
许可协议CC BY-NC-SA 4.0
上一篇

密码学论文记

下一篇

Reed-Solomon 纠错码