格密码合集 - SeanDictionary

LCG未知a,b求seed

题目

from Crypto.Util.number import getPrime, inverse
from secret import seed, flag
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()
assert flag == '0xGame{' + MD5(seed) + '}'
assert seed.bit_length() == 510

class LuanGao:
    def __init__(self, bits:int, seed:int):
        self.bits = bits
        self.m = getPrime(self.bits)
        self.a = getPrime(self.bits // 2)
        self.cur = (self.a * seed) % self.m

    def extract(self):
        ret = self.cur
        b = getPrime(self.bits // 4)
        self.cur = ( self.a * self.cur + b ) % self.m
        return ret

C = LuanGao(512, seed)
Cs = [C.extract() for _ in range(5)]

print(f'Cs = {Cs}')
print(f'C.m = {C.m}')

'''
Cs = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
C.m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
'''

exp

# 0xGame 2024
# LLL-II
from Crypto.Util.number import *
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()
m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
c = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
ge = [
[m,0,0,0,0,0],
[0,m,0,0,0,0],
[0,0,m,0,0,0],
[0,0,0,m,0,0],
[c[0],c[1],c[2],c[3],1,0],
[c[1],c[2],c[3],c[4],0,1]]

Ge = Matrix(ZZ,ge)
L = Ge.LLL()
a = abs(L[0][-2])
seed = c[0]*inverse(a,m)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')
# '0xGame{2db84757dd4197f9b9441be25f35bfd5}'
# 2512273436977220996062855314655393786244910444920037228737234078954182704102442213664768806368325362960908940985195233026259876194811260795362098878115082

LCG已知state高位求seed

[0xGame]LLL-III

题目

from Crypto.Util.number import *
from secret import seed,flag
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()
assert flag == '0xGame{' + MD5(seed) + '}'
assert seed.bit_length() == 256

class LCG:
    def __init__(self,bits:int,seed:int):
        self.m = getPrime(bits+1)
        self.a = getPrime(bits)
        self.b = getPrime(bits)
        self.cur = ( self.a * seed + self.b ) % self.m

    def extract(self):
        ret=self.cur >> 115
        self.cur = ( self.a * self.cur + self.b ) % self.m
        return ret

lcg=LCG(bits=256,seed=seed)

out = []
for _ in range(20):
    out.append(lcg.extract())

print(f'm = {lcg.m}')
print(f'a = {lcg.a}')
print(f'b = {lcg.b}')
print(f'out = {out}')
'''
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
out = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]
'''

exp

# 0xGame 2024
# LLL-III
from Crypto.Util.number import *
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
c = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]

ge = [[0]*21 for i in range(21)]

for i in range(19):
    ge[i][i] = m
ge[-2][-2],ge[-1][-1] = 1,1
ge[-2][0], ge[-1][0]  = a,a*(c[0]<<115)+b-(c[1]<<115)
for i in range(1,19):
    ge[-2][i]=a^(i+1)
    ge[-1][i]=ge[-1][i-1]*a+a*(c[i]<<115)+b-(c[i+1]<<115)

Ge = Matrix(ZZ,ge)
Ge = Ge.LLL()
assert Ge[0][-1] == 1
state = abs(Ge[0][-2])+(c[0]<<115)
seed = pow(a,-1,m)*(state-b)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')

# 101639613050544872292192629515273562035022699788445344858455157668840828973361
# '0xGame{459049e068d93f6d70f1ea0da705264a}'

LWE问题

咕咕ing

AGCD问题

咕咕ing

HSSP问题

[HGAME 2025] SPiCa

参考链接

问题描述

有一个大整数$M$，行向量$\alpha \in \mathbb{Z} _M^n$和一个由$n$个行向量$x_i \in \mathbb{Z} _2^m$构成的矩阵$A_{n \times m}$

计算$h=\alpha A$

已知$M,h,n,m$，求$\alpha , A$

其中满足$M.bits = 2 \iota n^2 + n \cdot log\ n,\iota = 0.035$

求解

主要思路：寻找A的正交格（因为A未知，于是要从h去构造），然后计算正交格的右核空间，并规约即可得到A

寻找向量$u$使得$u,h$垂直

$$h \cdot u = \alpha Au = \sum_{i=1}^n\alpha_i(x_i \cdot u) = 0\ mod\ M$$

令向量$p_u$

$$p_u=Au=(x_1u,x_2u,\cdots,x_nu)$$

所以满足

$$\alpha p_u=0\ mod\ M$$

这表明$p_u$和$\alpha$在模M下相互垂直

当$p_u=0$时，即可认为$u$垂直于$A$的行向量$x_i$为基构成的格，即$u\in L_x^{\perp}$

由于$L_x$的维度是n，因此$L_x^{\perp}$的维度是$m-n$，也就是说找到$m-n$个线性无关的$u$就能复原$L_x^{\perp}$，再计算出与其正交的格即可找到$L_x$，由于$x_i \in \mathbb{Z} _2^m$是短向量，对$L_x$规约即可得到构成矩阵$A$的基

$$h\cdot u=\sum_{i=1}^mh_iu_i\ mod\ M$$

可以尝试构造格，由于$p_u=0$可知$p_u$是短向量，而$x_i$的元素是$0,1$，所以$u$也是短向量

$$(u_1,u_2,\cdots,u_m,-k) \begin{pmatrix} h_1& 0&\cdots& 0&1\\ h_2& 0&\cdots& 1&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ h_m& 1&\cdots& 0&0\\ M& 0&\cdots& 0&0\\ \end{pmatrix} =(0,u_m,\cdots,u_2,u_1)$$

还有一种构造格的方法

$$h\cdot u=h_1u_1+\sum_{i=2}^mh_iu_i\ mod\ M$$

$$kM-\sum_{i=2}^mu_ih_ih_1^{-1}=u_1$$

$$(k,u_2,\cdots,u_m) \begin{pmatrix} M& 0&\cdots& 0&0\\ -h_2h_1^{-1}& 1&\cdots& 0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ -h_3h_1^{-1}& 0&\cdots& 1&0\\ -h_mh_1^{-1}& 0&\cdots& 0&1\\ \end{pmatrix} =(u_1,u_2,\cdots,u_m)$$

对$L_x$规约无法恢复矩阵$A$，因为矩阵$A$是在基上的进一步线性组合，不一定是最短基，所以可以通过类似背包密码的方式将基转化为$2x_i-e,e=(1,\cdots,1)$，以此筛选出目标基(元素落在${0,1}$)，因为非目标基(元素落在${-1,0,1}$)在新格中会使得模变长，而在规约中被筛去。此算法对数据大小有要求$m\ge \frac{n^2}{2}$

于是进行如下的构造

$$B=\begin{pmatrix}-e\\2L_x\end{pmatrix}_{(n+1)\times m}$$

令$L_x,A$存在如下线性关系

$$UL_x=A$$

于是有

$$(e^T,U)_{n\times (n+1)}B=(2UL_x-e^Te)_{n\times m}=\begin{pmatrix} 2x_1-e\\\vdots\\2x_n-e \end{pmatrix}$$

所以最终对$B$规约后去除加入的$e$的影响，即可恢复出矩阵$A$

# HSSP

def checkMatrix(M, wl=[-1, 1]):
    M = [list(i) for i in list(M)]
    ml = list(set(flatten(M)))
    return sorted(ml) == sorted(wl)

def hssp_solve(n,m,M,h):
    ge1 = [[0]*m for _ in range(m)]
    tmp = pow(h[0], -1, M)
    for i in range(1,m):
        ge1[i][0] = -h[i]*tmp
        ge1[i][i] = 1
    ge1[0][0] = M

    Ge1 = Matrix(ZZ,ge1)

    L1 = Ge1.BKZ()

    Lx_orthogonal = Matrix(ZZ, L1[:m-n])
    Lx = Lx_orthogonal.right_kernel(algorithm='pari').matrix()

    e = Matrix(ZZ, [1] * m)
    B = block_matrix([[-e], [2*Lx]])

    L2 = B.BKZ()
    assert checkMatrix(L2)

    E = matrix(ZZ, [[1]*L2.ncols() for _ in range(L2.nrows())])
    L2 = (L2 + E) / 2

    assert set(L2[0]) == {0}

    L2 = L2[1:]

    space = Lx.row_space()

    Lx2 = []
    e = vector(ZZ, [1] * m)
    for lx in L2:
        if lx in space:
            Lx2 += [lx]
            continue
        lx = e - lx
        if lx in space:
            Lx2 += [lx]
            continue
        return None

    Lx = matrix(Zmod(M), Lx2)

    vh = vector(Zmod(M), h)
    va = Lx.solve_left(vh)
    return Lx, va

n = ?
m = ?
M = ?
h = ?

A,a = hssp_solve(n,m,M,h)

for row in A:
    ans = "".join(str(i) for i in row)
    try:
        print(long_to_bytes(int(ans,2)).decode())
    except:
        None

AHSSP问题

问题描述

有模数$p$，行向量$\alpha_{1 \times n} \in \mathbb{Z} _p^n$，一个由$n$个行向量$x_i \in \mathbb{Z} _2^m$构成的矩阵$A_{n \times m}$和行向量$e_{1 \times m}\in \mathbb{Z} _p^m$，$s$

计算$h = \alpha A-se\ mod\ p$，已知$h,e,p$，求$s$

求解

主要思路还是利用正交格来求解，然后之后的步骤和HSSP是大致相同的

构造正交矩阵$M$，使得满足$hM=\alpha AM-seM\ mod\ p$

构造如下的格对其规约，即可得到正交格M

$$(M_1,M_2,\cdots,M_m,k_1,k_2) \left(\begin{array}{cc|cc} h_1& e_1& 1& 0&\cdots& 0&0\\ h_2& e_2& 0& 1&\cdots& 0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ h_m& e_m& 0& 0&\cdots& 0&1\\ \hline p& 0& 0& 0&\cdots& 0&0\\ 0& p& 0& 0&\cdots& 0&0\\ \end{array}\right) =(0,0,M_1,M_2,\cdots,M_m)$$

*论文题

关键字：RSA、相同私钥、格基规约、格、同一明文多次加密

Kumar R S, Narasimham C, Setty S P. Lattice Based Attack on Common Private Exponent RSA[J]. International Journal of Computer Science Issues (IJCSI), 2012, 9(2): 311.

题目

from Crypto.Util.number import *
 
flag = b'******'
flag = bytes_to_long(flag)
d = getPrime(400)
 
 
for i in range(4):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    e = inverse(d, (p-1)*(q-1))
    c = pow(flag, e, n)
    print(f'e{i} =', e)
    print(f'n{i} =', n)
    print(f'c{i} =', c)
 
'''
e0 = 14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0 = 104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0 = 66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1 = 62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1 = 89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1 = 75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2 = 5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2 = 53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2 = 22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3 = 57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3 = 97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3 = 56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465
'''

依据论文内容同理构造格子

from Crypto.Util.number import *
import gmpy2
 
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 = gmpy2.iroot(n0,2)[0]
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()[0]
d = hh[0] // M
m = gmpy2.powmod(c0,d,n0)
flag = long_to_bytes(m)
print(flag)
 
# NSSCTF{12514adb-2c14-4777-96ff-90e95bc2b5cb}