Signin

from Crypto.Util.number import *
from hashlib import md5

class RSA():
    def __init__(self, nbits):
        self.nbits = nbits
        self.p, self.q = self.getPrimes()
        self.n = self.p*self.q
        self.Gift = self.Gift()
        self.priv, self.pub = self.keyGen()

    def getPrimes(self):
        nbits = self.nbits
        p = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        while p == q:
            q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        return p,q

    def Gift(self):
        p,q = self.p, self.q
        return (p^2 + p + 1)*(q^2 + q + 1)

    def keyGen(self):
        nbits = self.nbits
        while True:
            d = randint(2^(nbits//4),2^(nbits//2))
            if gcd(d,self.Gift) != 1:
                d = randint(2^(nbits//4),2^(nbits//2))
            e = pow(d,-1,self.phi)
            return (self.p,self.q,self.n,e,d),(self.n,e)


RRR = RSA(512)

bp = long_to_bytes(int(RRR.p))
FLAG = 'SCTF{'+md5(bp).hexdigest()+'}'


print(f'N = {RRR.n}')
print(f'e = {RRR.pub[1]}')

'''
N = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840
'''

题目分析

WP

不完全阻塞

# The ship crashed into the sun, causing a massive magnetic storm
#part of script
msg = bytes_to_long(FLAG)
n = p^5*q^2
phi = p^4*(p-1)*q*(q-1)
e = 65537
d = inverse(d,phi)
c = pow(m,e,n)
# c = 145554802564989933772666853449758467748433820771006616874558211691441588216921262672588167631397770260815821197485462873358280668164496459053150659240485200305314288108259163251006446515109018138298662011636423264380170119025895000021651886702521266669653335874489612060473962259596489445807308673497717101487224092493721535129391781431853820808463529747944795809850314965769365750993208968116864575686200409653590102945619744853690854644813177444995458528447525184291487005845375945194236352007426925987404637468097524735905540030962884807790630389799495153548300450435815577962308635103143187386444035094151992129110267595908492217520416633466787688326809639286703608138336958958449724993250735997663382433125872982238289419769011271925043792124263306262445811864346081207309546599603914842331643196984128658943528999381048833301951569809038023921101787071345517702911344900151843968213911899353962451480195808768038035044446206153179737023140055693141790385662942050774439391111437140968754546526191031278186881116757268998843581015398070043778631790328583529667194481319953424389090869226474999123124532354330671462280959215310810005231660418399403337476289138527331553267291013945347058144254374287422377547369897793812634181778309679601143245890494670013019155942690562552431527149178906855998534415120428884098317318129659099377634006938812654262148522236268027388683027513663867042278407716812565374141362015467076472409873946275500942547114202939578755575249750674734066843408758067001891408572444119999801055605577737379889503505649865554353749621313679734666376467890526136184241450593948838055612677564667946098308716892133196862716086041690426537245252116765796203427832657608512488619438752378624483485364908432609100523022628791451171084583484294929190998796485805496852608557456380717623462846198636093701726099310737244471075079541022111303662778829695340275795782631315412134758717966727565043332335558077486037869874106819581519353856396937832498623662166446395755447101393825864584024239951058366713573567250863658531585064635727070458886746791722270803893438211751165831616861912569513431821959562450032831904268205845224077709362068478

题目分析

题目给出了加密的代码以及密文，同时又给了一个受到干扰的私钥文件，我们先提取出已知的私钥信息

n=0x0067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
e=65537
ph=0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e570194
qh=0x00e4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a39
ph=ph<<(125*4)
qh=qh<<(101*4)

我们可以得到p,q的高位，总的p,q都是1024bit的，我们已知p的高424bit和q的高620位，可以尝试用二元copper来解决。

WP

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

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

n=0x0067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
e=65537
ph=0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e570194
qh=0x00e4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a39
ph=ph<<(125*4)
qh=qh<<(101*4)
c=145554802564989933772666853449758467748433820771006616874558211691441588216921262672588167631397770260815821197485462873358280668164496459053150659240485200305314288108259163251006446515109018138298662011636423264380170119025895000021651886702521266669653335874489612060473962259596489445807308673497717101487224092493721535129391781431853820808463529747944795809850314965769365750993208968116864575686200409653590102945619744853690854644813177444995458528447525184291487005845375945194236352007426925987404637468097524735905540030962884807790630389799495153548300450435815577962308635103143187386444035094151992129110267595908492217520416633466787688326809639286703608138336958958449724993250735997663382433125872982238289419769011271925043792124263306262445811864346081207309546599603914842331643196984128658943528999381048833301951569809038023921101787071345517702911344900151843968213911899353962451480195808768038035044446206153179737023140055693141790385662942050774439391111437140968754546526191031278186881116757268998843581015398070043778631790328583529667194481319953424389090869226474999123124532354330671462280959215310810005231660418399403337476289138527331553267291013945347058144254374287422377547369897793812634181778309679601143245890494670013019155942690562552431527149178906855998534415120428884098317318129659099377634006938812654262148522236268027388683027513663867042278407716812565374141362015467076472409873946275500942547114202939578755575249750674734066843408758067001891408572444119999801055605577737379889503505649865554353749621313679734666376467890526136184241450593948838055612677564667946098308716892133196862716086041690426537245252116765796203427832657608512488619438752378624483485364908432609100523022628791451171084583484294929190998796485805496852608557456380717623462846198636093701726099310737244471075079541022111303662778829695340275795782631315412134758717966727565043332335558077486037869874106819581519353856396937832498623662166446395755447101393825864584024239951058366713573567250863658531585064635727070458886746791722270803893438211751165831616861912569513431821959562450032831904268205845224077709362068478
print(ph)

PR.<pl,ql>=PolynomialRing(Zmod(n))
f = (ph+pl)^5*(qh+ql)^2
res =f.small_roots(f, (2^600,2^404), m=2, d=3)
print(res)
# pplusq = int(res[0][1])
# pminusq = iroot(pplusq^2-4*n,2)[0]
# p = (pplusq + pminusq) // 2
# q = n // p

# d = inverse(e,(p^2+p+1)*(q^2+q+1))
# print(long_to_bytes(d^2 ^^ c))

Whisper

n1=0x1B5D4FE0AA6782E275D4CE12A6D57562EFBBE7DB6F5277255B891729BFA2A18D3EDB49843D7989A37B9516BE2DF8CA939058E65F64B5FB2071BEA4F5F8D1392895B32BF0377D99F4F79979125E5DB01CDB5080A1C2D665C9AC31B5823025499C9513277BAE5E7A846CD271C4396E2BA219020E58A9055CB18A28D36A00BF717B
e=0x079F5CCC665767B4A257E5C1FF56E9803DF2E5650302DAAD420105FE672447743BD3F0BEA1C46A4987932E9A886CA87A7AFD7796ABF1E5629C4986FE4F22E89CDCE7ABB06624465146A2E2B6CA9AB3196CEAB7467974C1DC45608A200411B291FDAF99F7D80DCE4DB3566F4A9E2E574C6224CD07D80638D28F7820BCF4B49143

n2=0x071C324E8769493187C15F72D5CC695729B48488EE3FBD01DB00D5C478F08C7CF32093BA61745051D3E9D169523AA91438181F47679AFF5EDD22950F74A1EB1443320AAA5D97F5C1E81B5EF9A3E69BA669ABC4C6C4B405F5088A603A74F9BCEF88823B4523574114C810600838728196F8E5E0D4AEEEEAB79DD8683A72F3C017
e=0x079F5CCC665767B4A257E5C1FF56E9803DF2E5650302DAAD420105FE672447743BD3F0BEA1C46A4987932E9A886CA87A7AFD7796ABF1E5629C4986FE4F22E89CDCE7ABB06624465146A2E2B6CA9AB3196CEAB7467974C1DC45608A200411B291FDAF99F7D80DCE4DB3566F4A9E2E574C6224CD07D80638D28F7820BCF4B49143

题目分析

题目给出了两组公钥，根据题目描述可以猜测出这是dual rsa，且d的长度应该是345bit。

Two public key certificates were monitored. And Mr. Dual intercepted a ciphertext. Just when he was in the rough, a Careless Whisper told that the length of a key parameter is carelessly set to 345 bits.

WP

这里使用的是2016年的Cryptanalysis of Dual RSA一文的方法

import math
import itertools


# display matrix picture with 0 and X
# references: https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
def matrix_overview(BB):
  for ii in range(BB.dimensions()[0]):
    a = ('%02d ' % ii)
    for jj in range(BB.dimensions()[1]):
      a += ' ' if BB[ii,jj] == 0 else 'X'
      if BB.dimensions()[0] < 60:
        a += ' '
    print(a)


def dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt):
  '''
  Attack to Dual RSA: Liqiang et al.'s attack implementation

  References:
    [1] Liqiang Peng, Lei Hu, Yao Lu, Jun Xu and Zhangjie Huang. 2016. "Cryptanalysis of Dual RSA"
  '''
  N = (n1+n2)/2
  A = ZZ(floor(N^0.5))

  _XX = ZZ(floor(N^delta))
  _YY = ZZ(floor(N^0.5))
  _ZZ = ZZ(floor(N^(delta - 1./4)))
  _UU = _XX * _YY + 1

  # Find a "good" basis satisfying d = a1 * l'11 + a2 * l'21
  M = Matrix(ZZ, [[A, e], [0, n1]])
  B = M.LLL()
  l11, l12 = B[0]
  l21, l22 = B[1]
  l_11 = ZZ(l11 / A)
  l_21 = ZZ(l21 / A)

  modulo = e * l_21
  F = Zmod(modulo)

  PR = PolynomialRing(F, 'u, x, y, z')
  u, x, y, z = PR.gens()

  PK = PolynomialRing(ZZ, 'uk, xk, yk, zk')
  uk, xk, yk, zk = PK.gens()

  # For transform xy to u-1 (unravelled linearlization)
  PQ = PK.quo(xk*yk+1-uk)

  f = PK(x*(n2 + y) - e*l_11*z + 1)

  fbar = PQ(f).lift()

  # Polynomial construction
  gijk = {}
  for k in range(0, mm + 1):
    for i in range(0, mm-k + 1):
      for j in range(0, mm-k-i + 1):
        gijk[i, j, k] = PQ(xk^i * zk^j * PK(fbar) ^ k * modulo^(mm-k)).lift()

  hjkl = {}
  for j in range(1, tt + 1):
    for k in range(floor(mm / tt) * j, mm + 1):
      for l in range(0, k + 1):
        hjkl[j, k, l] = PQ(yk^j * zk^(k-l) * PK(fbar) ^ l * modulo^(mm-l)).lift()

  monomials = []
  for k in gijk.keys():
    monomials += gijk[k].monomials()
  for k in hjkl.keys():
    monomials += hjkl[k].monomials()

  monomials = sorted(set(monomials))[::-1]
  assert len(monomials) == len(gijk) + len(hjkl) # square matrix?
  dim = len(monomials)

  # Create lattice from polynmial g_{ijk} and h_{jkl}
  M = Matrix(ZZ, dim)
  row = 0
  for k in gijk.keys():
    for i, monomial in enumerate(monomials):
      M[row, i] = gijk[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
    row += 1
  for k in hjkl.keys():
    for i, monomial in enumerate(monomials):
      M[row, i] = hjkl[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
    row += 1

  matrix_overview(M)
  print('=' * 128)

  # LLL
  B = M.LLL()


  matrix_overview(B)

  # Construct polynomials from reduced lattices
  H = [(i, 0) for i in range(dim)]
  H = dict(H)
  for j in range(dim):
    for i in range(dim):
      H[i] += PK((monomials[j] * B[i, j]) / monomials[j].subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ))
  # H = H.values()

  PQ = PolynomialRing(QQ, 'uq, xq, yq, zq')
  uq, xq, yq, zq = PQ.gens()

  # Inversion of unravelled linearlization
  for i in range(dim):
    H[i] = PQ(H[i].subs(uk=xk*yk+1))

  # Calculate Groebner basis for solve system of equations
  '''
  Actually, These polynomials selection (H[1:20]) is heuristic selection.
  Because they are "short" vectors. We need a short vector less than
  Howgrave-Graham bound. So we trying test parameter(at [1]) and decided it.
  '''
  # I = Ideal(*H[1:20])
  I = Ideal(list(H.values())[1:20])
  g = I.groebner_basis('giac')[::-1]
  # mon = map(lambda t: t.monomials(), g)
  mon = [t.monomials() for t in g]

  PX = PolynomialRing(ZZ, 'xs')
  xs = PX.gen()

  x_pol = y_pol = z_pol = None

  for i in range(len(g)):
    if mon[i] == [xq, 1]:
      print(g[i] / g[i].lc())
      x_pol = g[i] / g[i].lc()
    elif mon[i] == [yq, 1]:
      print(g[i] / g[i].lc())
      y_pol = g[i] / g[i].lc()
    elif mon[i] == [zq, 1]:
      print(g[i] / g[i].lc())
      z_pol = g[i] / g[i].lc()

  if x_pol is None or y_pol is None or z_pol is None:
    print('[-] Failed: we cannot get a solution...')
    return

  x0 = x_pol.subs(xq=xs).roots()[0][0]
  y0 = y_pol.subs(yq=xs).roots()[0][0]
  z0 = z_pol.subs(zq=xs).roots()[0][0]

  # solution check
  assert f(x0*y0+1, x0, y0, z0) % modulo == 0

  a0 = z0
  a1 = (x0 * (n2 + y0) + 1 - e*l_11*z0) / (e*l_21)

  d = a0 * l_11 + a1 * l_21
  return d


delta = 0.337
mm = 4
tt = 2

n1 = 19216005446310864558409934096148904703198882317083224129431545386380435777354723744624028053518278514595663319253560114239018542660582960464010994454707936550902872627309424890333127288994449006783158078916602020794628546065674981593736606481809198149080696037584037699638293870122512237711498004090515845499
n2 = 4992911943798277344804876549224813326447469267517432903838084455752417287982320183584988170455130118418117937196562948710115292838538880218156469801938645463822391931977946975012481667095710882823897026534267366981015926659114785262116088548568215969555191689632109516970297562458267207338397574333407150103
e = 5352708372343813403035593638037107517373724079700735571091908193413083617555211472255125798199165859811237950085789893649651552088125747433480591652396404710788778815075048587264350078253899425987466937040099316084273123603046629945048298154353920118466252136326911019666012632927688983695457057246503276867

d1 = dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt)
print('[+] d for alice = %d' % d1)
#40938683537002969349994490030778320037535387924227183600857028517800996704376695290532584573854353589803

d=40938683537002969349994490030778320037535387924227183600857028517800996704376695290532584573854353589803
print(d.bit_length())
print(long_to_bytes(pow(c,d,n)))

LinearARTs

from random import choices
import json
from sage.all import *
from Crypto.Util.number import *
from sage.groups.perm_gps.permgroup_named import SymmetricGroup



def Young(FLAG):
    f = int.from_bytes(FLAG, "big")
    q = 65537

    s = []
    while f:
        s.append(f % q)
        f //= q
    s = vector(GF(q), s)

    n, m = len(s), len(s) ** 2

    A = Matrix(GF(q), m, n, lambda i, j: randint(0, q - 1))
    e = vector(choices(range(2^8), k=m), GF(q))*Matrix(ZZ,PermutationGroupElement(SymmetricGroup(m).random_element()).matrix())
    b = (A*s) + e


    return A,b


def Old(m, nbits):
    Sn = SymmetricGroup(m)
    p = [getPrime(360) for i in range(m)]
    N = sorted([getRandomNBitInteger(nbits) for _ in range(m)])
    S = []
    for i in range(m):
        r = [N[_] % p[i] for _ in range(m)]
        r = vector(ZZ,r)

        Per = Sn.random_element()
        P = PermutationGroupElement(Per)
        Pm = Matrix(ZZ,P.matrix())
        r *= Pm
        S.append(r)
    S = matrix(ZZ,S)

    with open('Old.matrix','w') as f:
        json.dump({"S": str(list(S)),"p": str(p)}, f)

    return N

def chall(nn):
    # The challenge lasted nn rounds
    # Young_level * virtue >= Old_level , where virtue = nn + 1

    h = []
    HP = []
    MP = []
    Old_level = 625*2*2
    Young_level = 25*5*5*2

    M = getPrime(Old_level)
    XP = getRandomRange(1,M)
    for _ in range(nn):
        a = getRandomRange(1,M)
        b = a*XP % M
        HP.append(a)
        MP.append(b)
        delta_level = Old_level - Young_level
        h.append(b >> delta_level << delta_level)




    return XP,M,HP,MP,h


mm = 16
nn = 9
nbits = 3840


A,b = Young(FLAG)
N = Old(mm, nbits)  

XP,M,HP,MP,h = chall(nn)

# MP is useful ,I can use him to cast five lightning spells
D = diagonal_matrix(GF(0x10001),N+MP) 
Sn = SymmetricGroup(5*5)
Per = Sn.random_element()

P = PermutationGroupElement(Per)
PM = Matrix(GF(0x10001),P.matrix())




AA = A*D*PM

with open('D.matrix','w') as f:
    json.dump({"D": str(list(D))}, f)



# OK! Find your martial arts, and then you can get the flag.


with open("output.txt", "w") as f:
    json.dump({"AA": str(list(AA)), "b": str(b)}, f)


print(f'My SymmetricGroup is {Sn}, and my element is {Per}')
print(f'M = {M}')
print(f'h = {h}')
print(f'HP = {HP}')

题目分析

题目给出了多个数据我们只提取主要的几个数据

#AA,D,Per已知
P = PermutationGroupElement(Per)
PM = Matrix(GF(0x10001),P.matrix())
AA = A*D*PM

我们通过已知量就可以求出AA,D,PM然后就可以顺势求出A的值了

t=PM.solve_left(AA)
A=D.solve_left(t)

接下来观察与flag相关的Young函数

A = Matrix(GF(q), m, n, lambda i, j: randint(0, q - 1))
e = vector(choices(range(2^8), k=m), GF(q))*Matrix(ZZ,PermutationGroupElement(SymmetricGroup(m).random_element()).matrix())
b = (A*s) + e

这里的b和A我们都知道了，e是一个2^8下的随机误差，那么就可以转化成一个lwe的问题了。这里e还是较大的，但是A是一个625*25的矩阵，数据量多，可以尝试求解，这里直接求cvp即可。由于用上全部数据求LLL较慢，所以我爆破尝试了几组数据，发现在325情况下能够求出结果。

注意到这里求出结果后要做一个65537进制的转化，而不是常规的直接转byte

sum=0
q = 65537
sum=0
for i in range(len(t)):
    sum+=t[i]*(q**(i))
print(long_to_bytes(sum))

WP

m = 325
n = 25
q = 65537
A_values = A[:m,:n]
b_values = b[:m]
A = matrix(ZZ, m + n, m)
for i in range(m):
    A[i, i] = q
for x in range(m):
    for y in range(n):
        A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

print("Ingredients: {}".format(ingredients))


from Crypto.Util.number import *
t=(58903, 2963, 39256, 25173, 62086, 5284, 45419, 10132, 50811, 41636, 42833, 8227, 63647, 10096, 28276, 29628, 54509, 9776, 44228, 39961, 48996, 60060, 43678, 34392, 21307)
print(len(t))
sum=0
q = 65537
sum=0
for i in range(len(t)):
    sum+=t[i]*(q**(i))
print(long_to_bytes(sum))