格密码入门

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 2.3k 阅读时长 ≈ 8 分钟

初识格密码

做题关键，构造出下列矩阵乘法
$$
v·M=\overrightarrow{w}
$$

$$
v:未知量矩阵
$$

$$
M:已知量矩阵
$$

$$
\overrightarrow{w}:目标向量，即要求的值
$$

需要注意的是，因为LLL算法是一步一步约减的，所以目标向量一定要比原来已知矩阵小

根据$Hermite$定理，我们所求的目标向量一定要满足SVP的范围

NTRU有关

入门题

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
from secret import flag
from Crypto.Util.number import *

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f+20192020202120222023, p) * g % p

print('h =', h)
print('p =', p)
"""
h = 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p = 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281
"""

$$
要拿到flag,就得求出f的值
$$

$$
先令f’ = f+20192020202120222023
$$

$$
已知h \equiv f’^{-1}g (\mod p)
$$

$$
\therefore hf’ \equiv g (\mod p)
$$

$$
\therefore g = hf’ -kp
$$

构造出

LLL算法可以把$(h,1),(p,0)$这组基，变成正交化程度最大的一组基

其实际过程是把向量$(h,1),(p,0)$做线性组合，最后的结果就是$x_1(h,1)+x_2(p,0)=(x_1h+x_2p,x_1+0)$

当$x_1=f’,x_2=-k$的时候，就是我们要的结果

为什么LLL算法的结果就是我们要的值？

LLL算法是求解SVP问题的，我们要求的向量$\vec{v} = (f’,g)$满足$||\vec{v}||\le \sqrt{2}det(\mathcal{L})$

其中，$\mathcal{L}$是$(h,1),(p,0)$构成的矩阵，其行列式为$p$

求解出$f’$后，我们便能求出$f$

构造的矩阵依赖下式

exp:

1
2
3
4
5
6
7
8
9
10
11
import libnum

h = 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p = 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281

Ge = Matrix(ZZ,[[1,h],[0,p]])
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)

print(libnum.n2s(int(f-20192020202120222023)))

NSSCTF [HNCTF 2022 WEEK2] ——littleLattice

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from hashlib import *

p = getPrime(2048)
f = getPrime(1024)
g = getPrime(768)
h = pow(f,-1,p)*g%p
verify = sha256(bytes.fromhex(hex(f+g)[2:])).hexdigest()
print(f'verify = {verify}')
print(f'p = {p}')
print(f'h = {h}')
print('NSSCTF{' + md5(bytes.fromhex(hex(f+g)[2:])).hexdigest() + '}')



'''
verify = 24425b693dbcace08a32572d499a5cbeb36e30db9278704195c67c3d32a81bdf
p = 29908110980126088961686288727545150169450107297750996656924523214377817308111189721234667959695817050736874247951762130190209278324144437406652857446810518839546701950883392761869656586963587376306050382973323860395932741791372333809871487575268245618618143456971257992301722141464238875859134379745122404533776003095129169004284619647906206323263396219776072091827094295366090100037898314156271404760715453914459484087562963158208356228410105170495322276351631637885450926240143055767142216931354736779666836018983658010126520397012025067407223630891975504746697630878807952266767406899527721170062789607980517722293
h = 26523576589113781532769165293024254940419790396713708680496148398686334583553504180195363282085884580924842673123375450894537445679687851322807762432476357713740302064160599132450619363411158141423252170448770929403179895813409897048848337375715079396639330537231353596884530617911351334318435031007342479134081403319324838464987064025256038807217697133175585927493402963025439540077915248356077623612217525231722274634984400273765262532561558296870531741633238736650375250957780701118781183335729715295271752736307479795186963108377228330313771245434127095507278278768792281414702334956407755841000748255424212840137
'''

$$
我们已知h \equiv f^{-1}×g (\mod p)
$$

$$
\therefore hf \equiv g (\mod p)
$$

$$
g = hf-kp
$$

$$
要求flag,我们要求出f,g
$$

$$
我们的目标量就是f,g了
$$

因为$g,f$的值小于已知的$h,p$，而且$||(f,g)||\approx 1024bit$的大小小于$\sqrt{2p} \approx \sqrt{2}×1024bit$

所以可以用LLL算法求解$g,f$
$$
构造的矩阵依赖于下式:
$$

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from hashlib import sha256,md5

verify = "24425b693dbcace08a32572d499a5cbeb36e30db9278704195c67c3d32a81bdf"
p = 29908110980126088961686288727545150169450107297750996656924523214377817308111189721234667959695817050736874247951762130190209278324144437406652857446810518839546701950883392761869656586963587376306050382973323860395932741791372333809871487575268245618618143456971257992301722141464238875859134379745122404533776003095129169004284619647906206323263396219776072091827094295366090100037898314156271404760715453914459484087562963158208356228410105170495322276351631637885450926240143055767142216931354736779666836018983658010126520397012025067407223630891975504746697630878807952266767406899527721170062789607980517722293
h = 26523576589113781532769165293024254940419790396713708680496148398686334583553504180195363282085884580924842673123375450894537445679687851322807762432476357713740302064160599132450619363411158141423252170448770929403179895813409897048848337375715079396639330537231353596884530617911351334318435031007342479134081403319324838464987064025256038807217697133175585927493402963025439540077915248356077623612217525231722274634984400273765262532561558296870531741633238736650375250957780701118781183335729715295271752736307479795186963108377228330313771245434127095507278278768792281414702334956407755841000748255424212840137

Ge = Matrix(ZZ,[[1,h],[0,p]])
#print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)

if sha256(bytes.fromhex(hex(f+g)[2:])).hexdigest() == verify:
    flag = 'NSSCTF{' + md5(bytes.fromhex(hex(f+g)[2:])).hexdigest() + '}'
    print(flag)

NSSCTF{884beaede45bb83d3706bcc14827dece}

CSDN某博主分享

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
 
p = getPrime(1024)
 
f = getPrime(400)
g = getPrime(512)
r = getPrime(400)
 
h = inverse(f, p) * g % p
 
m = b'******'
m = bytes_to_long(m)
 
c = (r*h + m) % p
 
print(f'p = {p}')
print(f'h = {h}')
print(f'c = {c}')
 
'''
p = 170990541130074930801165526479429022133700799973347532191727614846803741888876816210632483231997413973919037199883422312436314365293577997262903161076615619596783971730864586404602951191341733308807254112018161897113881363794353050758324742415299277578203838160939521046655099610387485947145087271531951477031
h = 19027613518333504891337723135627869008620752060390603647368919831595397216728378486716291001290575802095059192000315493444659485043387076261350378464749849058547797538347059869865169867814094180939070464336693973680444770599657132264558273692580535803622882040948521678860110391309880528478220088107038861065
c = 75639016590286995205676932417759002029770539425113355588948888258962338419567264292295302442895077764630601149285564849867773180066274580635377957966186472159256462169691456995594496690536094824570820527164224000505303071962872595619159691416247971024761571538057932032549611221598273371855762399417419551483
'''

$$
\because c \equiv (r×f^{-1}×g +m) \mod p,这里f^{-1}是模p的逆元
$$

$$
\therefore fc \equiv (rg + mf) \mod p
$$

$$
mf \equiv (fc - rg) \mod p
$$

两边同模g，把r消去
$$
mf \equiv (fc\mod p) \mod g
$$

$$
m \equiv(fc\mod p) ×f^{-1}\mod g,这里f^{-1}是模g的逆元
$$

这里需要注意的是$rg+mf应当小于p$,$m应当小于g$才能正确解密

如果不满足上式的参数条件，$m$在加密过程中便有可能丢失数据

已知$c,p$，求出$f,g$即可求解$m$

构造

$\because \vec{v}=(f,g) \approx 512bit < \sqrt{2p} \approx \sqrt{2}×512bit$

依然是依赖于下式

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import libnum
import gmpy2

p = 170990541130074930801165526479429022133700799973347532191727614846803741888876816210632483231997413973919037199883422312436314365293577997262903161076615619596783971730864586404602951191341733308807254112018161897113881363794353050758324742415299277578203838160939521046655099610387485947145087271531951477031
h = 19027613518333504891337723135627869008620752060390603647368919831595397216728378486716291001290575802095059192000315493444659485043387076261350378464749849058547797538347059869865169867814094180939070464336693973680444770599657132264558273692580535803622882040948521678860110391309880528478220088107038861065
c = 75639016590286995205676932417759002029770539425113355588948888258962338419567264292295302442895077764630601149285564849867773180066274580635377957966186472159256462169691456995594496690536094824570820527164224000505303071962872595619159691416247971024761571538057932032549611221598273371855762399417419551483

Ge = Matrix(ZZ,[[h,1],[p,0]])
print(Ge.LLL())
g,f = Ge.LLL()[0]
g,f = abs(g),abs(f)

m = ((f*c%p)*gmpy2.invert(f,g)) % g
print(libnum.n2s(int(m)))

NSSCTF{94068324-38bb-410b-b464-e1b8baf6b358}

2020巅峰极客修改

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import gmpy2
from secret import flag
from Crypto.Util.number import *


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)
print('h =', h)
print('p =', p)
print('c =', c)
"""
h = 15920807412952692847985174177588211960281948838307253586797239960508125481987882224605864406372742338485793530131031795389776531751200676051949170672004649326503467447518123006808297262753280286176914568491022298784897984879823370933511805201516939304165656461649805404345353075803763209810253831770288511818668398003443730898078080711296567200650962390927974385735100849320021423318726773493255693093044142610555698370275203822724528162516863483780170076614868308468049805668954554578089167666866242081591436319781031943877834260419842837279937368942586813623585114579680192182136454951076576180846308031147577895183
p = 29616445112694260274774681537287299269831042656521626513009034520717072986110554689452007791622053679125813101887358792411152206641110832730768759894034995329749945245036475665938165090997263055454214551943883405059392525425764609291470545536168035201657530029849113821500078015786845062143152799634844986753056256220285729693791666273618731684193516606613125066125143895019716948226556471128531174411802630235945882713680099627033330758906060609807833477234842026397619463093836747345939002210487194276855948870859245196439206070300222410002340377429280616491741559912351526804469748340235688215655559714767093336011
c = 24894154600738747801028572977171957374256712941786243361235711912410748252475712552938200529578615522555383736598357845901370674754857388874985225645650913059820754690696257510209172235875364336887131653254443697948965333434213242584604843844646774324930722413839123594241879178636469903372909302377061318833174246232722769872293078758804927418352848560803152544304608965368181815249876729133751310904899772060616419975025741262545479052454752165874425435226386604586446369944613258629120527951194286510228752204113015018002437399369034486123978271982779314575972603420464431960235222295086660836240988842127196837233
"""

和上题一样

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import libnum
import gmpy2

h = 15920807412952692847985174177588211960281948838307253586797239960508125481987882224605864406372742338485793530131031795389776531751200676051949170672004649326503467447518123006808297262753280286176914568491022298784897984879823370933511805201516939304165656461649805404345353075803763209810253831770288511818668398003443730898078080711296567200650962390927974385735100849320021423318726773493255693093044142610555698370275203822724528162516863483780170076614868308468049805668954554578089167666866242081591436319781031943877834260419842837279937368942586813623585114579680192182136454951076576180846308031147577895183
p = 29616445112694260274774681537287299269831042656521626513009034520717072986110554689452007791622053679125813101887358792411152206641110832730768759894034995329749945245036475665938165090997263055454214551943883405059392525425764609291470545536168035201657530029849113821500078015786845062143152799634844986753056256220285729693791666273618731684193516606613125066125143895019716948226556471128531174411802630235945882713680099627033330758906060609807833477234842026397619463093836747345939002210487194276855948870859245196439206070300222410002340377429280616491741559912351526804469748340235688215655559714767093336011
c = 24894154600738747801028572977171957374256712941786243361235711912410748252475712552938200529578615522555383736598357845901370674754857388874985225645650913059820754690696257510209172235875364336887131653254443697948965333434213242584604843844646774324930722413839123594241879178636469903372909302377061318833174246232722769872293078758804927418352848560803152544304608965368181815249876729133751310904899772060616419975025741262545479052454752165874425435226386604586446369944613258629120527951194286510228752204113015018002437399369034486123978271982779314575972603420464431960235222295086660836240988842127196837233

Ge = Matrix(ZZ,[[1,h],[0,p]])
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)

m = ((f*c%p)*gmpy2.invert(f,g)) % g
print(libnum.n2s(int(m)))

NSSCTF [深育杯2021]——GeGe

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
import gmpy2
from flag import flag

def encrypt(plaintext):
    p = getStrongPrime(3072) 
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        c = (r * h + m * f) % p
        return (h, p, c)

h, p, c = encrypt(flag)
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")
    
    
    
#output
h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672

$$
已知h \equiv f^{-1}g (\mod p)
$$

有

$\because \vec{v}=(f,g) \approx 512bit < \sqrt{2p} \approx \sqrt{2}×512bit$


$$
又\because c \equiv rh+mf (\mod p)
$$

$$
c \equiv rf^{-1}g + mf (\mod p )
$$

$$
fc \equiv rg+mf^2 (\mod p)
$$

$$
mf^2 = (fc(\mod p))(\mod g)
$$

$$
m =(fc(\mod p))×f’^{2}(\mod g),这里f’是模g的逆元
$$

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import libnum
import gmpy2

h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672

Ge = Matrix(ZZ,[[1,h],[0,p]])
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)

f1 = gmpy2.invert(f,g)
m = ((f * c % p)*f1**2)%g
print(libnum.n2s(int(m)))

上面五道题都是NTRU加密

结合RSA

羊城杯2020 LRSA

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import gmpy2
from pwn import *
from hashlib import sha256
import string
from Crypto.Util.number import *
from random import *


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

m=bytes_to_long(flag)

def getPQ(p,q):
    P=getPrime(2048)
    Q=getPrime(2048)
    t=(p*P-58*P+q)%Q
    assert (isPrime(Q))
    return P,Q,t

B=getRandomNBitInteger(11)
p=getPrime(B)
q=getPrime(B)
n=p*q
e=65537
c=pow(m,e,n)
P,Q,t=getPQ(p,q)

print("B=",B)
print("P*P*Q=",P*P*Q)
print("P*Q*Q=",P*Q*Q)
print("t=",t)
print("c=",c)

"""
# B=1023
# P*P*Q=17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
# P*Q*Q=17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
# t=44
# c=4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746

先求$PPQ,PQQ$的公因数$PQ$

$P = PPQ // PQ$,$Q = PQQ // PQ$
$$
\because t \equiv (p-58)P+q (\mod Q)
$$

$$
\therefore t-q \equiv (p-58)P (\mod Q)
$$

$$
\therefore t-q = (p-58)P+kQ
$$

构造格:

$t$已知，随后便可求出$p,q$

这里事先不知道$p,q$的大小，但是最后结果出来以后，$(p-58,t-q)$的长度是非常接近$\sqrt{2Q}$的

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import gmpy2
import libnum

B = 1023
PPQ = 17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
PQQ = 17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
t = 44
c = 4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746

PQ = gmpy2.gcd(PPQ,PQQ)

P = PPQ // PQ
Q = PQQ // PQ

Ge = Matrix(ZZ,[[1,P],[0,Q]])

p1 ,q1 = Ge.LLL()[0]

#print(p1,q1)
p1 = abs(p1)

#print(p1,q1)
p = p1 + 58
q = t + q1
n = p*q

d = gmpy2.invert(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(libnum.n2s(int(m)))

[NUSTCTF 2022 新生赛]——lattice

一道简单论文题

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from Crypto.Util.number import *
from random import randint
from secret import flag

flag = bytes_to_long(flag)
d = getPrime(randint(370, 390))


def enc(i):
    print()
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = inverse(d, phi)
    c = pow(flag, e, n)
    print(f'e_{i} =', e)
    print(f'n_{i} =', n)
    print(f'c_{i} =', c)


if __name__ == '__main__':
    for i in range(3):
        enc(i)

# e_0 = 37389635736858807810703086504264263440188928763651776502954117173983775626039037008534821321761858567723984257427640816113325770208734640385635663643682102780255726244659849205653007212192504491177021176624605722718152646889627480051142935241036578957272339153039961711802753021931124235464986935316295647379
# n_0 = 87704526707772151782606625126900349506318713860335977395824997219721333991491994027303721441548488339412359519408127174109547119019245873976917916080340858937125736650376514406944094998893225164676363063781400756374403299951466867573215964360920244878373810391250391475087527409213204756990192602517961590163
# c_0 = 78656123855003406993963573497876652287109947684890741747390020445306861422604130132525802389554149844489256622057009394678814584233565675702142297935509191018145970589418173328145004732595569847696022333024124469320873194195223535859964387627938665526123562969554622541694399263934496631337485091067073489148

# e_1 = 28535169211141109871379321582501492434722235009040085167442370469971731780018594508141105234950857774463438226249819106596920677559656398153362076685288045484306156454558741088396794170762527953573082734587618137075161676392362016474076363311708889307420903699720319611668580377903356783222664068961626803615
# n_1 = 134298877057487865189085342936485527664167450453080897084604607959501054859295769447683135156167266222961308751016451904929475702646252122360203167489936020076488657815646993920082535307414536854323149177250531362615850689341066360635074886835720438532107976530111551202845697404444502476862934946146194420313
# c_1 = 3208711484494445700905074340207543865325589037128163311082565190422756093807236786011349707275838139469873445326457948489588753029946395247710197747538418278782966047404435385208682596795152082296050804126524129644617710791433973098499266439604632728957505961744280687343384601998774018570047292904007768763

# e_2 = 27653153186459366670449283776658896188717513017934031993526241644501850206894800647711159987946276669184047769965182746812351757618147642060630769822810070480507035319320426666128599562714143342910248758055424582501972900763786232170145957578683616604737178839977216709381529813768748145393798635858691196687
# n_2 = 82113192811251631639012300385672674439485256963081847790431181633372052788107703751257606763043873164706839243919206719171536710944060815484051324239120708906418093409305166299531826404505861042666985630956832163750255358332156122245372899824101210233079028706971698312018388678352739819636695333269309456613
# c_2 = 79145689398302968140315554300835109898158799236562716569497147385375487041207363302776833573990584370222316102267792795080448018216133931915984139305260191001847394275311719986838969706049641052337337102739487620502723651258075501409442088938776353037366614208693030741599888985069155346722608948495955447606

令$M = \sqrt{N_{max}}$，$M$是一组$N$中最大的$N$并且开根号。这组$N$满足：$N_1<N_2<\dots<N_r <2N_1$

又$\because e_id \equiv 1 (\mod \phi(N_i))$

这里把它写成$e_id = 1+k_i\phi{N_i}$

假设$\phi(N_i)$可以写成$k_i(N_i-s_i)$的形式。其中$|s_i<3N_i^{\frac{1}{2}}|$

则$e_id = 1 + k_i(N_i-s_i)$

化简得$e_id-k_iN_i = 1-k_is_i$

所以我们有$r+1$个等式:

写成矩阵相乘的形式

因为最后的目标向量满足LLL算法，所以我们可以得到$dM$

求得$dM$之后，我们可以求得$d$

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import libnum
import gmpy2

e0 = 37389635736858807810703086504264263440188928763651776502954117173983775626039037008534821321761858567723984257427640816113325770208734640385635663643682102780255726244659849205653007212192504491177021176624605722718152646889627480051142935241036578957272339153039961711802753021931124235464986935316295647379
n0 = 87704526707772151782606625126900349506318713860335977395824997219721333991491994027303721441548488339412359519408127174109547119019245873976917916080340858937125736650376514406944094998893225164676363063781400756374403299951466867573215964360920244878373810391250391475087527409213204756990192602517961590163
c0 = 78656123855003406993963573497876652287109947684890741747390020445306861422604130132525802389554149844489256622057009394678814584233565675702142297935509191018145970589418173328145004732595569847696022333024124469320873194195223535859964387627938665526123562969554622541694399263934496631337485091067073489148

e1 = 28535169211141109871379321582501492434722235009040085167442370469971731780018594508141105234950857774463438226249819106596920677559656398153362076685288045484306156454558741088396794170762527953573082734587618137075161676392362016474076363311708889307420903699720319611668580377903356783222664068961626803615
n1 = 134298877057487865189085342936485527664167450453080897084604607959501054859295769447683135156167266222961308751016451904929475702646252122360203167489936020076488657815646993920082535307414536854323149177250531362615850689341066360635074886835720438532107976530111551202845697404444502476862934946146194420313
c1 = 3208711484494445700905074340207543865325589037128163311082565190422756093807236786011349707275838139469873445326457948489588753029946395247710197747538418278782966047404435385208682596795152082296050804126524129644617710791433973098499266439604632728957505961744280687343384601998774018570047292904007768763

e2 = 27653153186459366670449283776658896188717513017934031993526241644501850206894800647711159987946276669184047769965182746812351757618147642060630769822810070480507035319320426666128599562714143342910248758055424582501972900763786232170145957578683616604737178839977216709381529813768748145393798635858691196687
n2 = 82113192811251631639012300385672674439485256963081847790431181633372052788107703751257606763043873164706839243919206719171536710944060815484051324239120708906418093409305166299531826404505861042666985630956832163750255358332156122245372899824101210233079028706971698312018388678352739819636695333269309456613
c2 = 79145689398302968140315554300835109898158799236562716569497147385375487041207363302776833573990584370222316102267792795080448018216133931915984139305260191001847394275311719986838969706049641052337337102739487620502723651258075501409442088938776353037366614208693030741599888985069155346722608948495955447606


n = [n0,n1,n2]
M = isqrt(max(n))

ge = [[M,e0,e1,e2],
    [0,-n0,0,0],
    [0,0,-n1,0],
    [0,0,0,-n2]]
Ge = Matrix(ZZ,ge)

dM = Ge.LLL()[0][0]
d = abs(dM) // M
m = pow(c0,d,n0)
print(libnum.n2s(int(m)))

参考论文

IJCSI-9-2-1-311-314.pdf

CSDN某博主分享

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
import random
 
flag = b'******'
m = bytes_to_long(flag)
 
a = getPrime(1024)
b = getPrime(1536)
 
p = getPrime(512)
q = getPrime(512)
r = random.randint(2**14, 2**15)
assert ((p-r) * a + q) % b < 50
 
c = pow( m, 65537, p*q )
 
print(f'c = {c}')
print(f'a = {a}')
print(f'b = {b}')
 
'''
c = 78168998533427639204842155877581577797354503479929547596593341570371249960925614073689003464816147666662937166442652068942931518685068382940712171137636333670133426565340852055387100597883633466292241406019919037053324433086548680586265243208526469135810446004349904985765547633536396188822210185259239807712
a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587
b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609
'''

已知等式((p-r) * a + q) % b < 50

令$x \equiv ((p-r)×a+q) \mod b$

$\therefore x - q \equiv (p-r)×a \mod b$

$\therefore x-q = (p-r)×a+kb$

构造格求$p-r和x-q$，再爆破得到$p,q$

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# sage
import gmpy2
import libnum
from tqdm import *

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

Ge = Matrix(ZZ,[[a,1],[b,0]])

x_q,p_r = Ge.LLL()[0]
xq,pr = -abs(x_q),abs(p_r)				#因为x是远小于q的，所以x-q肯定是负的

for x in trange(50):
    for r in range(2**14,2**15):
        p = pr + r
        q = x - xq
        n = p*q
        try:
            d = gmpy2.invert(e,(p-1)*(q-1))
            m = pow(c,d,n)
            flag = libnum.n2s(int(m))
            if b'NSSCTF' in flag:
                print(flag)
                break
        except:
            pass

CSDN分享

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from gmpy2 import *
 
flag = b'******'
flag = bytes_to_long(flag)
 
p = getPrime(1024)
r = getPrime(175)
a = inverse(r, p)
a = (a*flag) % p
 
print(f'a = {a}')
print(f'p = {p}')
 
'''
a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591
'''

已知等式： $a \equiv r^{-1}flag (\mod p)$

$\therefore flag \equiv ar (\mod p)$

即$flag = ar + kp$

$a=1023bit$

构造格$\mathcal{L}$

$\vec{v} = (flag,k)且||\vec{v}||<\sqrt{2}Det(\mathcal{L})$

exp:

1
2
3
4
5
6
7
8
9
10
import libnum

a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

Ge = Matrix(ZZ,[[a,0],[p,1]])

m,k = Ge.LLL()[0]
m = abs(m)
print(libnum.n2s(int(m)))

CSDN分享

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from gmpy2 import *
 
flag = b'******'
m = bytes_to_long(flag)
 
assert m.bit_length() == 351
p = getPrime(1024)
b = getPrime(1024)
c = getPrime(400)
 
a = (b*m + c) % p
 
print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')
 
'''
a = 92716521851427599147343828266552451834533034815416003395170301819889384044273026852184291232938197215198124164263722270347104189412921224361134013717269051168246275213624264313794650441268405062046423740836145678559969020294978939553573428334198212792931759368218132978344815862506799287082760307048309578592
b = 155530728639099361922541063573602659584927544589739208888076194504495146661257751801481540924821292656785953391450218803112838556107960071792826902126414012831375547340056667753587086997958522683688746248661290255381342148052513971774612583235459904652002495564523557637169529882928308821019659377248151898663
p = 100910862834849216140965884888425432690937357792742349763319405418823395997406883138893618605587754336982681610768197845792843123785451070312818388494074168909379627989079148880913190854232917854414913847526564520719350308494462584771237445179797367179905414074344416047541423116739621805238556845903951985783
'''

已知等式$\quad $$a \equiv bm + c(\mod p)$
$$
\therefore c = a -bm + kp
$$
构造格

由于不知道中间矩阵最后一列应该是什么，我们先从右边的矩阵入手。

因为$c$是$400bit$，$m$是$351bit$，所以向量$\vec{V}=(c,m,?)$的长度大概就是在$400bit$左右

由$Hermite$定理我们知道最短向量有上界

$||\vec{v} ||< \sqrt{3}×\sqrt[3]{||det(\mathcal{L}||})$$\therefore det(\mathcal{L})$应大于$400bit$

我认为$?$的取值应该在$176bit$以上

所以构造下列格：

这个$2^{176}$需要不断测试，我测试结果为$2^{180}$即可获得正确答案

-------------已经到底啦！-------------