NSSCTF Crypto系列--格密码

Crypto系列--格密码

Crypto系列--格密码(一)

[格密码1]P1

• 加密：

\(h \equiv f^{-1}*g \pmod{p}\)

\(c \equiv r*h + m \pmod{p}\)

\(c \equiv r*g*f^{-1} + m \pmod{p}\)

• 解密：

\(f*c \equiv r*g + m*f \pmod{p}\)

\(m*f \equiv (f*c \pmod{p}) \pmod{g}\)

\(m \equiv (f*c \pmod{p})*f^{-1} \pmod{g}\)

造格子

\[ \left[ \begin{matrix} k & f \end{matrix} \right] * \left[ \begin{matrix} p & \\ h & 1 \end{matrix} \right] = \left[ \begin{matrix} g & f \end{matrix} \right] \]

from libnum import *
from Crypto.Util.number import *

p = 170990541130074930801165526479429022133700799973347532191727614846803741888876816210632483231997413973919037199883422312436314365293577997262903161076615619596783971730864586404602951191341733308807254112018161897113881363794353050758324742415299277578203838160939521046655099610387485947145087271531951477031
h = 19027613518333504891337723135627869008620752060390603647368919831595397216728378486716291001290575802095059192000315493444659485043387076261350378464749849058547797538347059869865169867814094180939070464336693973680444770599657132264558273692580535803622882040948521678860110391309880528478220088107038861065
c = 75639016590286995205676932417759002029770539425113355588948888258962338419567264292295302442895077764630601149285564849867773180066274580635377957966186472159256462169691456995594496690536094824570820527164224000505303071962872595619159691416247971024761571538057932032549611221598273371855762399417419551483

A = p
B = h
mat = [[A,0],[B,1]]
M = Matrix(ZZ,mat)
hh = M.LLL()
# print(hh)

f = hh[0][1]
g = hh[0][0]

m = f * c %p %g * inverse(f,g) %g
flag = n2s(int(m))
print(flag) 

[格密码1]P2

背包加密：

脚本1

下载一个包 lattice

https://github.com/jvdsn/crypto-attacks

import os
import sys
from math import ceil
from math import log2
from math import sqrt

from sage.all import QQ
from sage.all import matrix

# path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
# if sys.path[1] != path:
#     sys.path.insert(1, path)

# sys.path.append(os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from lattice import *


def attack(a, s):
    """
    Tries to find e_i values such that sum(e_i * a_i) = s.
    This attack only works if the density of the a_i values is < 0.9048.
    More information: Coster M. J. et al., "Improved low-density subset sum algorithms"
    :param a: the a_i values
    :param s: the s value
    :return: the e_i values, or None if the e_i values were not found
    """
    n = len(a)
    d = n / log2(max(a))
    N = ceil(1 / 2 * sqrt(n))
    assert d < 0.9408, f"Density should be less than 0.9408 but was {d}."

    L = matrix(QQ, n + 1, n + 1)
    for i in range(n):
        L[i, i] = 1
        L[i, n] = N * a[i]

    L[n] = [1 / 2] * n + [N * s]
    for v in shortest_vectors(L):
        s_ = 0
        e = []
        for i in range(n):
            ei = 1 - (v[i] + 1 / 2)
            if ei != 0 and ei != 1:
                break

            ei = int(ei)
            s_ += ei * a[i]
            e.append(ei)

        if s_ == s:
            return e
        
b = [...]
c = ...

print(attack(b,c))
# [1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]

from Crypto.Util.number import *

m = ...

v = ''
for i in m:
    v += str(i)

flag = long_to_bytes(int(v,2))
print(flag)

脚本2

from Crypto.Util.number import *

b = [...]
c = ...

n = len(b)
print(n)
L = Matrix(ZZ, n+1, n+1)

for i in range(n):
    L[i,i] = 1
    L[i,-1] = b[i]
L[-1,-1] = -c

res = L.LLL()

for i in range(n + 1):
    M = res.row(i).list()
    flag = True
    for m in M:
        if m != 0 and m != 1:
            flag = False
            break
    if flag:
        print(i, M)

# flag =  [1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]

# flag = int(''.join(list(map(str, flag))), 2)

# print(long_to_bytes(flag))

[格密码1]P3

• 已知

$r  14bits $

\(x \ < 50\)

\(x \equiv (p-r) * a + q \pmod{b}\)

\(\Rightarrow (p-r)*a + k*b = x - q\)

造格子

\[ \left[ \begin{matrix} k & p-r \end{matrix} \right] * \left[ \begin{matrix} b & \\ a & 1 \end{matrix} \right] = \left[ \begin{matrix} x-q & p-r \end{matrix} \right] \]

from libnum import *
from Crypto.Util.number import *
from tqdm import *

c = 78168998533427639204842155877581577797354503479929547596593341570371249960925614073689003464816147666662937166442652068942931518685068382940712171137636333670133426565340852055387100597883633466292241406019919037053324433086548680586265243208526469135810446004349904985765547633536396188822210185259239807712
a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587
b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609
e = 65537

# ((p-r) * a + q) % b < 50

mat = [[b,0],[a,1]]
M = Matrix(ZZ,mat)
hh = M.LLL()
# print(hh)

p = abs(hh[0][1])  # p-r
q = abs(hh[0][0])  # q-x

for i in tqdm(range(2**14, 2**15)):
    for j in range(50):
        pp = p + i
        qq = q + j
        phi = (pp-1)*(qq-1)
        if gcd(phi, 65537) != 1:
            continue
        d = inverse(e,phi)
        n = pp*qq
        m = pow(c,d,n)
        flag = n2s(int(m))
        if b'NSSCTF' in flag :
            print(flag)
            break

[格密码1]P4

\[ a * r = flag \pmod{p} \]

\[ k * p + a * r = flag \]

\[ \left[ \begin{matrix} k & r \end{matrix} \right] * \left[ \begin{matrix} p & 0 \\ a & 1 \end{matrix} \right] = \left[ \begin{matrix} flag & r \end{matrix} \right] \]

from Crypto.Util.number import *

a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

# a * r = flag mod p
# r 175 bits 

# k*p  + a* r  = flag 
mat = [[p,0],[a,1]] 
M = Matrix(ZZ,mat)
hh = M.LLL()
m = hh[0][0]
flag = long_to_bytes(m)
print(flag)

[格密码1]P5

\[ a = b*m + c \pmod{p} \]

\[ b,p \ 1024bits \\ c \ 400bits \\ a 已知 \]

\[ a = b*m + c \pmod{p} \]

\[ - b*m + a = c \pmod{p} \]

\[ \left[ \begin{matrix} k & m & 1 \end{matrix} \right] * \left[ \begin{matrix} p & & \\ -b & 1 & \\ a & & 2^{400} \end{matrix} \right] = \left[ \begin{matrix} c & m & k \end{matrix} \right] \]

from Crypto.Util.number import *
from libnum import *

a = 92716521851427599147343828266552451834533034815416003395170301819889384044273026852184291232938197215198124164263722270347104189412921224361134013717269051168246275213624264313794650441268405062046423740836145678559969020294978939553573428334198212792931759368218132978344815862506799287082760307048309578592
b = 155530728639099361922541063573602659584927544589739208888076194504495146661257751801481540924821292656785953391450218803112838556107960071792826902126414012831375547340056667753587086997958522683688746248661290255381342148052513971774612583235459904652002495564523557637169529882928308821019659377248151898663
p = 100910862834849216140965884888425432690937357792742349763319405418823395997406883138893618605587754336982681610768197845792843123785451070312818388494074168909379627989079148880913190854232917854414913847526564520719350308494462584771237445179797367179905414074344416047541423116739621805238556845903951985783

mat = [[p,0,0],[-b,1,0],[a,0,2^400]]
M = Matrix(ZZ,mat)
hh = M.LLL()
# print(hh)

m = hh[0][1]
flag = n2s(int(m))
print(flag)

[格密码1]P6

https://www.ijcsi.org/papers/IJCSI-9-2-1-311-314.pdf

论文

\[ c_{0} = m^{e_{0}} \pmod{n_{0}} \\ c_{1} = m^{e_{1}} \pmod{n_{1}} \\ c_{2} = m^{e_{2}} \pmod{n_{2}} \\ c_{3} = m^{e_{3}} \pmod{n_{3}} \]

分割

\(M = \sqrt{n_{0}}\) \[ \left[ \begin{matrix} M & e_{0} & e_{1} & e_{2} & e_{3} \\ 0 & -n_{0}& 0 & 0 & 0 \\ 0 & 0 & -n_{1} & 0 & 0 \\ 0 & 0 & 0 & -n_{2} & 0 \\ 0 & 0 & 0 & 0 & -n_{3} \end{matrix} \right] \] \(hh = L.LLL()\)

\(d = hh / M\)

完整代码

from Crypto.Util.number import *
from tqdm import tqdm
from libnum import *

# https://www.ijcsi.org/papers/IJCSI-9-2-1-311-314.pdf

e0 = 14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0 = 104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0 = 66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1 = 62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1 = 89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1 = 75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2 = 5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2 = 53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2 = 22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3 = 57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3 = 97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3 = 56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465

M = isqrt(n1)
mat = [[M, e0, e1, e2, e3],
       [0,-n0,  0,  0,  0],
       [0,  0,-n1,  0,  0],
       [0,  0,  0,-n2,  0],
       [0,  0,  0,  0,-n3]]

L = Matrix(ZZ,mat)
hh = L.LLL()
d = hh[0][0] // M
m = power_mod(c0,d,n0)
flag = long_to_bytes(m)
print(flag)

[格密码1]P7

扩展维纳攻击

用\(W_1,G_{1,2},W_1*W_2\)来构造格子

脚本1

from Crypto.Util.number import *
n = ...
c = ...
e0 = ...
e1 = ...
a = 5/14
D = diagonal_matrix(ZZ, [n, int(n^(1/2)), int(n^(1+a)), 1])
M = Matrix(ZZ, [[1, -n, 0, n^2],
                [0, e0, -e0, -e0*n],
                [0,  0, e1,  -e1*n],
                [0,  0,  0,  e0*e1]])*D
L = M.LLL()
t = vector(ZZ, L[0])
x = t * M^(-1)

x * M = t
phi = int(x[1]/x[0]*e0)

d = inverse_mod(65537, phi)
m = power_mod(c, d, n)
print(long_to_bytes(m))

脚本2

from Crypto.Util.number import *
from tqdm import tqdm
from libnum import *

n = 110697784133988071803253124431092603234028687101567047811203431433689306543322837414808117411806181193598553341878079973980865551938790090419082150555675782822484149943421418447579383449269148197087985041351210982545320569973241390962326458234562044133505940521052500278777242988196544039226173227204865907343
c = 3281096209929505523196793672137624804022934270452947405454462490250571524417033484978613243658208567511735641542935158434165363547355697159503378251318054879687577130170122911449101189974762808655638497967674004219512386442280269940950792767174561412932638740423542930763914255112354969122157915514816022159
e0 = 28562806554366667733480283991307446762365777397933141571728113235368201162305126722188842319240464207580134816039095093401651171977877327756351539588974913736802534970867173212883308325913939353140276201705478124488858328502643345172188729914731042179091733244225184522680724392375975935305371163502863968963
e1 = 28572469216883232254074869113744730984165641173439644880182528671699871929340616919028955398474678696802739685594548793470261306125219888911330937557582939811068530294470712859439149735950996866732508004061234613146407591546995439312326450834903885979660916965052092661398640105827442036234500556755520316031

a = 5/14
# D = diagonal_matrix(ZZ, [n, int(n^(1/2)), int(n^(1+a)), 1])
D = diagonal_matrix(ZZ, [1, int(n^(1+a)), int(n^(1/2)), n])     # 对角线矩阵 用来平衡
mat = [
    [e0*e1,   0,  0,  0],
    [-e1*n,  e1,  0,  0],
    [-e0*n, -e0, e0,  0],
    [  n^2,   0, -n,  1]
]
M = Matrix(ZZ,mat)
M = M*D
hh = M.LLL()

L = vector(ZZ,hh[0])
x = L * M^(-1)
# print(x)

# x * M = L
phi = int((x[2]//x[3])*e0)
d = inverse_mod(65537, phi)
m = power_mod(c, d, n)
print(long_to_bytes(m))

[格密码1]P8

\(c \equiv a_0*s_0^{2}*s_1^{2} + a_1*s_0*s_2^{2} + a_2*s_1*s_2 \pmod{p}\)

\(s_1*s_2 = k*p + a_0*a_2^{-1}*s_0^{2}*s_1^{2}+a_1*a_2^{-1}*s_0*s_2^{2} - c*a_2^{-1}\)

造格子

\[ \left[ \begin{matrix} k & s_0^{2}*s_1^{2} & s_0*s_2^{2} & 1 \end{matrix} \right] * \left[ \begin{matrix} p & & & \\ a_0*a_2^{-1} & 1 & & \\ a_1*a_2^{-1} & & 1 & \\ - c*a_2 & & & 1 \end{matrix} \right] = \left[ \begin{matrix} s_1*s_2 & s_0^{2}*s_1^{2} & s_0*s_2^{2} & 1 \end{matrix} \right] \]

from gmpy2 import *
from libnum import *
c = 740925064346371394698186587854547113606276228956443989781507592148712696471120454242180757282913190509143771235457885619359315384722931529795071829165028
flag = 68803130911709451943985629442913968356735244797651554293510331427148284907075221530061581131130283569506280604032687824733336171953927
a = [8205051800134728054685810600921116779466017139080528864745521629232854690213051609775306424843961090482436503418278207286549634492623172279113808752825877, 7656695314164580223033364292542508972053206838456547579023164583502640699225283686572923544677077467571265812610524520719197913305928971777756847148151453, 12016313094941119621096276870216129960285946825332008187797823075795491053640261786033376211694851951499688886358239835607622191418940486434225440651886891]
p = 9725369974716521164256395525866212215114818770667579116304398350357785690930260317036889742178436308598088096925530431498664796728861093872628194022265573

a2 = invert(a[2],p)

mat = [[p      ,       0,      0,      0],
       [a[0]*a2,       1,      0,      0],
       [a[1]*a2,       0,      1,      0],
       [-c*a2  ,       0,      0,      1]
]

M = Matrix(ZZ,mat)
hh = M.LLL()
# print(hh)

s0s1 = iroot(hh[0][1],2)[0]
print(s0s1)   #  factordb
s0 =  3635120927
s1 =  2562131939
s2 = iroot(hh[0][2]//s0,2)[0]

m = flag //s0//s1//s2
print(n2s(int(m)))