首页 比赛

# babysign

# 题目

import hashlib
import ecdsa
from Crypto.Util.number import *
import random
import os
flag = b"xxx"
assert flag.startswith(b'DASCTF{') and flag.endswith(b'}')
assert len(flag) == 40
def init():
    """
    initiation
    """
    global pub_key, priv_key, order, base,secret
    gen = ecdsa.NIST256p.generator
    order = gen.order()
    secret = bytes_to_long(flag[7:-1])
    
    pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
    priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)
def sign(msg, nonce):
    """
    sign msg
    """
    msg = int(hashlib.sha256(msg).hexdigest(), 16)
    
    sign = priv_key.sign(msg, nonce)
    print("R:", hex(sign.r)[2:])
    print("S:", hex(sign.s)[2:])
init()
nonce = random.getrandbits(order.bit_length())
sign(b'welcome to ecdsa', nonce)
print(nonce)
'''
R: 7b35712a50d463ac5acf7af1675b4b63ba0da23b6452023afddd58d4891ef6e5
S: a452fc44cc36fa6964d1b4f47392ff0a91350cfd58f11a4645c084d56e387e5c
57872441580840888721108499129165088876046881204464784483281653404168342111855
'''
ECDSA 签名
签名步骤如下
  1. 选择随机整数数 k 作为临时密钥，0<k<q
  2. 计算r≡(gkmodp)modqr≡(g^kmodp)modq
  3. 计算s≡(H(m)+xr)k−1modqs≡(H(m)+xr)k^{−1}modq
我们已知了 r，s，H (m), k
并且
gen = ecdsa.NIST256p.generator
order = gen.order()
这是固定的所以 x 也已知
# exp
import hashlib
import ecdsa
from Crypto.Util.number import *
R=0x7b35712a50d463ac5acf7af1675b4b63ba0da23b6452023afddd58d4891ef6e5
S=0xa452fc44cc36fa6964d1b4f47392ff0a91350cfd58f11a4645c084d56e387e5c
k=57872441580840888721108499129165088876046881204464784483281653404168342111855
msg=b'welcome to ecdsa'
H = int(hashlib.sha256(msg).hexdigest(), 16)
gen = ecdsa.NIST256p.generator
order = gen.order()
x=(k*S-H)*inverse(R,order)%order
print(long_to_bytes(x))
DASCTF{11b7311d4f0137074a7256d3eb82f368}
# easyNTRU
# 题目
#from Crypto.Hash import SHA3_256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
#from secret import flag
# parameters
N = 10
p = 3
q = 512
d = 3
assert q>(6*d+1)*p
R.<x> = ZZ[]
#d1 1s and #d2 -1s
def T(d1, d2):
    assert N >= d1+d2
    s = [1]*d1 + [-1]*d2 + [0]*(N-d1-d2)
    shuffle(s)
    return R(s)
def invertModPrime(f, p):
    Rp = R.change_ring(Integers(p)).quotient(x^N-1)
    return R(lift(1 / Rp(f)))
def convolution(f, g):
    return (f*g) % (x^N-1)
def liftMod(f, q):
    g = list(((f[i] + q//2) % q) - q//2 for i in range(N))
    return R(g)
def polyMod(f, q):
    g = [f[i]%q for i in range(N)]
    return R(g)
def invertModPow2(f, q):
    assert q.is_power_of(2)
    g = invertModPrime(f,2)
    while True:
        r = liftMod(convolution(g,f),q)
        if r == 1: return g
        g = liftMod(convolution(g,2 - r),q)
def genMessage():
    result = list(randrange(p) - 1 for j in range(N))
    return R(result)
def genKey():
  while True:
    try:
      f = T(d+1, d)
      g = T(d, d)
      Fp = polyMod(invertModPrime(f, p), p)
      Fq = polyMod(invertModPow2(f, q), q)
      print(f)
      print(g)
      break
    except:
      continue
  h = polyMod(convolution(Fq, g), q)
  return h, (f, g)
def encrypt(m, h):
  e = liftMod(p*convolution(h, T(d, d)) + m, q)
  return e
# Step 1
h, secret = genKey()
m = genMessage()
e = encrypt(m, h)
print('h = %s' % h)
print('e = %s' % e)
# Step 2
sha3 = SHA3_256.new()
sha3.update(bytes(str(m).encode('utf-8')))
key = sha3.digest()
cypher = AES.new(key, AES.MODE_ECB)
c = cypher.encrypt(pad(flag, 32))
print('c = %s' % c)
NTRU 对 m 进行加密得到 h，e 多项式
将 m 的多项式当做 AES 的 key 对 flag 进行加密
我们只要知道 m 就可以求 flag
这道应该是非预期
本来 La 佬的脚本跑一下应该可以，但是他 Fp 没有逆元求不出来
然后看到 m
def genMessage():
    result = list(randrange(p) - 1 for j in range(N))
    return R(result)
p=3 n=10
也就是说 m 的系数只有 - 1,0,1 并且只有 10 位
就直接爆破 m 就行
# exp
#sage
from itertools import product
from Crypto.Cipher import AES
from Crypto.Hash import SHA3_256
li=[-1,0,1]
m=[]
R.<x> = ZZ[]
for i in product(li,repeat=10):
    m=list(i)
    m=R(m)
    sha3 = SHA3_256.new()
    sha3=sha3.update(bytes(str(m).encode('utf-8')))
    key = sha3.digest()
    c = b'\xb9W\x8c\x8b\x0cG\xde\x7fl\xf7\x03\xbb9m\x0c\xc4L\xfe\xe9Q\xad\xfd\xda!\x1a\xea@}U\x9ay4\x8a\xe3y\xdf\xd5BV\xa7\x06\xf9\x08\x96="f\xc1\x1b\xd7\xdb\xc1j\x82F\x0b\x16\x06\xbcJMB\xc8\x80'
    cypher = AES.new(key, AES.MODE_ECB)
    c = cypher.decrypt(c)
    if b'DAS' in c:
        print(c)
        break
DASCTF{b437acf4-aaf8-4f8f-ad84-5b1824f5af9c}
# NTRURSA
# 题目
from Crypto.Util.number import *
from gmpy2 import *
def gen():
    p1 = getPrime(256)
    while True:
        f = getRandomRange(1, iroot(p1 // 2, 2)[0])
        g = getRandomRange(iroot(p1 // 4, 2)[0], iroot(p1 // 2, 2)[0])
        if gcd(f, p1) == 1 and gcd(f, g) == 1 and isPrime(g) == 1:
            break
    rand = getRandomRange(0, 2 ^ 20)
    g1 = g ^^ rand
    h = (inverse(f, p1) * g1) % p1
    return h, p1, g, f, g1
def gen_irreducable_poly(deg):
    while True:
        out = R.random_element(degree=deg)
        if out.is_irreducible():
            return out
h, p1, g, f, g1 = gen()
q = getPrime(1024)
n = g * q 
e = 0x10001
#c1 = pow(bytes_to_long(flag), e, n)
hint = list(str(h))
length = len(hint)
bits = 16
p2 = random_prime(2 ^ bits - 1, False, 2 ^ (bits - 1))
R.<x> = PolynomialRing(GF(p2))
P = gen_irreducable_poly(ZZ.random_element(length, 2 * length))
Q = gen_irreducable_poly(ZZ.random_element(length, 2 * length))
N = P * Q
S.<x> = R.quotient(N)
m = S(hint)
c2 = m ^ e
print("p1 =", p1)
print("c1 =", c1)
print("p2 =", p2)
print("c2 =", c2)
print("n =", n)
print("N =", N)
'''
p1 = 106472061241112922861460644342336453303928202010237284715354717630502168520267
c1 = 20920247107738496784071050239422540936224577122721266141057957551603705972966457203177812404896852110975768315464852962210648535130235298413611598658659777108920014929632531307409885868941842921815735008981335582297975794108016151210394446009890312043259167806981442425505200141283138318269058818777636637375101005540308736021976559495266332357714
p2 = 64621
c2 = 19921*x^174 + 49192*x^173 + 18894*x^172 + 61121*x^171 + 50271*x^170 + 11860*x^169 + 53128*x^168 + 38658*x^167 + 14191*x^166 + 9671*x^165 + 40879*x^164 + 15187*x^163 + 33523*x^162 + 62270*x^161 + 64211*x^160 + 54518*x^159 + 50446*x^158 + 2597*x^157 + 32216*x^156 + 10500*x^155 + 63276*x^154 + 27916*x^153 + 55316*x^152 + 30898*x^151 + 43706*x^150 + 5734*x^149 + 35616*x^148 + 14288*x^147 + 18282*x^146 + 22788*x^145 + 48188*x^144 + 34176*x^143 + 55952*x^142 + 9578*x^141 + 9177*x^140 + 22083*x^139 + 14586*x^138 + 9748*x^137 + 21118*x^136 + 155*x^135 + 64224*x^134 + 18193*x^133 + 33732*x^132 + 38135*x^131 + 51992*x^130 + 8203*x^129 + 8538*x^128 + 55203*x^127 + 5003*x^126 + 2009*x^125 + 45023*x^124 + 12311*x^123 + 21428*x^122 + 24110*x^121 + 43537*x^120 + 21885*x^119 + 50212*x^118 + 40445*x^117 + 17768*x^116 + 46616*x^115 + 4771*x^114 + 20903*x^113 + 47764*x^112 + 13056*x^111 + 50837*x^110 + 22313*x^109 + 39698*x^108 + 60377*x^107 + 59357*x^106 + 24051*x^105 + 5888*x^104 + 29414*x^103 + 31726*x^102 + 4906*x^101 + 23968*x^100 + 52360*x^99 + 58063*x^98 + 706*x^97 + 31420*x^96 + 62468*x^95 + 18557*x^94 + 1498*x^93 + 17590*x^92 + 62990*x^91 + 27200*x^90 + 7052*x^89 + 39117*x^88 + 46944*x^87 + 45535*x^86 + 28092*x^85 + 1981*x^84 + 4377*x^83 + 34419*x^82 + 33754*x^81 + 2640*x^80 + 44427*x^79 + 32179*x^78 + 57721*x^77 + 9444*x^76 + 49374*x^75 + 21288*x^74 + 44098*x^73 + 57744*x^72 + 63457*x^71 + 43300*x^70 + 1508*x^69 + 13775*x^68 + 23197*x^67 + 43070*x^66 + 20751*x^65 + 47479*x^64 + 18496*x^63 + 53392*x^62 + 10387*x^61 + 2317*x^60 + 57492*x^59 + 25441*x^58 + 52532*x^57 + 27150*x^56 + 33788*x^55 + 43371*x^54 + 30972*x^53 + 39583*x^52 + 36407*x^51 + 35564*x^50 + 44564*x^49 + 1505*x^48 + 47519*x^47 + 38695*x^46 + 43107*x^45 + 1676*x^44 + 42057*x^43 + 49879*x^42 + 29083*x^41 + 42241*x^40 + 8853*x^39 + 33546*x^38 + 48954*x^37 + 30352*x^36 + 62020*x^35 + 39864*x^34 + 9519*x^33 + 24828*x^32 + 34696*x^31 + 2387*x^30 + 27413*x^29 + 55829*x^28 + 40217*x^27 + 30205*x^26 + 42328*x^25 + 6210*x^24 + 52442*x^23 + 58495*x^22 + 2014*x^21 + 26452*x^20 + 33547*x^19 + 19840*x^18 + 5995*x^17 + 16850*x^16 + 37855*x^15 + 7221*x^14 + 32200*x^13 + 8121*x^12 + 23767*x^11 + 46563*x^10 + 51673*x^9 + 19372*x^8 + 4157*x^7 + 48421*x^6 + 41096*x^5 + 45735*x^4 + 53022*x^3 + 35475*x^2 + 47521*x + 27544
n = 31398174203566229210665534094126601315683074641013205440476552584312112883638278390105806127975406224783128340041129316782549009811196493319665336016690985557862367551545487842904828051293613836275987595871004601968935866634955528775536847402581734910742403788941725304146192149165731194199024154454952157531068881114411265538547462017207361362857
N = 25081*x^175 + 8744*x^174 + 9823*x^173 + 9037*x^172 + 6343*x^171 + 42205*x^170 + 28573*x^169 + 55714*x^168 + 17287*x^167 + 11229*x^166 + 42630*x^165 + 64363*x^164 + 50759*x^163 + 3368*x^162 + 20900*x^161 + 55947*x^160 + 7082*x^159 + 23171*x^158 + 48510*x^157 + 20013*x^156 + 16798*x^155 + 60438*x^154 + 58779*x^153 + 9289*x^152 + 10623*x^151 + 1085*x^150 + 23473*x^149 + 13795*x^148 + 2071*x^147 + 31515*x^146 + 42832*x^145 + 38152*x^144 + 37559*x^143 + 47653*x^142 + 37371*x^141 + 39128*x^140 + 48750*x^139 + 16638*x^138 + 60320*x^137 + 56224*x^136 + 41870*x^135 + 63961*x^134 + 47574*x^133 + 63954*x^132 + 9668*x^131 + 62360*x^130 + 15244*x^129 + 20599*x^128 + 28704*x^127 + 26857*x^126 + 34885*x^125 + 33107*x^124 + 17693*x^123 + 52753*x^122 + 60744*x^121 + 21305*x^120 + 63785*x^119 + 54400*x^118 + 17812*x^117 + 64549*x^116 + 20035*x^115 + 37567*x^114 + 38607*x^113 + 32783*x^112 + 24385*x^111 + 5387*x^110 + 5134*x^109 + 45893*x^108 + 58307*x^107 + 33821*x^106 + 54902*x^105 + 14236*x^104 + 58044*x^103 + 41257*x^102 + 46881*x^101 + 42834*x^100 + 1693*x^99 + 46058*x^98 + 15636*x^97 + 27111*x^96 + 3158*x^95 + 41012*x^94 + 26028*x^93 + 3576*x^92 + 37958*x^91 + 33273*x^90 + 60228*x^89 + 41229*x^88 + 11232*x^87 + 12635*x^86 + 17942*x^85 + 4*x^84 + 25397*x^83 + 63526*x^82 + 54872*x^81 + 40318*x^80 + 37498*x^79 + 52182*x^78 + 48817*x^77 + 10763*x^76 + 46542*x^75 + 36060*x^74 + 49972*x^73 + 63603*x^72 + 46506*x^71 + 44788*x^70 + 44905*x^69 + 46112*x^68 + 5297*x^67 + 26440*x^66 + 28470*x^65 + 15525*x^64 + 11566*x^63 + 15781*x^62 + 36098*x^61 + 44402*x^60 + 55331*x^59 + 61583*x^58 + 16406*x^57 + 59089*x^56 + 53161*x^55 + 43695*x^54 + 49580*x^53 + 62685*x^52 + 31447*x^51 + 26755*x^50 + 14810*x^49 + 3281*x^48 + 27371*x^47 + 53392*x^46 + 2648*x^45 + 10095*x^44 + 25977*x^43 + 22912*x^42 + 41278*x^41 + 33236*x^40 + 57792*x^39 + 7169*x^38 + 29250*x^37 + 16906*x^36 + 4436*x^35 + 2729*x^34 + 29736*x^33 + 19383*x^32 + 11921*x^31 + 26075*x^30 + 54616*x^29 + 739*x^28 + 38509*x^27 + 19118*x^26 + 20062*x^25 + 21280*x^24 + 12594*x^23 + 14974*x^22 + 27795*x^21 + 54107*x^20 + 1890*x^19 + 13410*x^18 + 5381*x^17 + 19500*x^16 + 47481*x^15 + 58488*x^14 + 26433*x^13 + 37803*x^12 + 60232*x^11 + 34772*x^10 + 1505*x^9 + 63760*x^8 + 20890*x^7 + 41533*x^6 + 16130*x^5 + 29769*x^4 + 49142*x^3 + 64184*x^2 + 55443*x + 45925
'''
NTRU 与 RSA 的结合
先是生成 NTRU 的公私钥
将 g 做为 n 的一个乘数
flag 进行 RSA 加密
然后将 h 作为 hint RSA 多项式加密
我们可以求出 h 通过 h 求出 g1 详情戳
再爆破 g
p=64621
R.<x> = PolynomialRing(GF(64621))
N=R("25081*x^175 + 8744*x^174 + 9823*x^173 + 9037*x^172 + 6343*x^171 + 42205*x^170 + 28573*x^169 + 55714*x^168 + 17287*x^167 + 11229*x^166 + 42630*x^165 + 64363*x^164 + 50759*x^163 + 3368*x^162 + 20900*x^161 + 55947*x^160 + 7082*x^159 + 23171*x^158 + 48510*x^157 + 20013*x^156 + 16798*x^155 + 60438*x^154 + 58779*x^153 + 9289*x^152 + 10623*x^151 + 1085*x^150 + 23473*x^149 + 13795*x^148 + 2071*x^147 + 31515*x^146 + 42832*x^145 + 38152*x^144 + 37559*x^143 + 47653*x^142 + 37371*x^141 + 39128*x^140 + 48750*x^139 + 16638*x^138 + 60320*x^137 + 56224*x^136 + 41870*x^135 + 63961*x^134 + 47574*x^133 + 63954*x^132 + 9668*x^131 + 62360*x^130 + 15244*x^129 + 20599*x^128 + 28704*x^127 + 26857*x^126 + 34885*x^125 + 33107*x^124 + 17693*x^123 + 52753*x^122 + 60744*x^121 + 21305*x^120 + 63785*x^119 + 54400*x^118 + 17812*x^117 + 64549*x^116 + 20035*x^115 + 37567*x^114 + 38607*x^113 + 32783*x^112 + 24385*x^111 + 5387*x^110 + 5134*x^109 + 45893*x^108 + 58307*x^107 + 33821*x^106 + 54902*x^105 + 14236*x^104 + 58044*x^103 + 41257*x^102 + 46881*x^101 + 42834*x^100 + 1693*x^99 + 46058*x^98 + 15636*x^97 + 27111*x^96 + 3158*x^95 + 41012*x^94 + 26028*x^93 + 3576*x^92 + 37958*x^91 + 33273*x^90 + 60228*x^89 + 41229*x^88 + 11232*x^87 + 12635*x^86 + 17942*x^85 + 4*x^84 + 25397*x^83 + 63526*x^82 + 54872*x^81 + 40318*x^80 + 37498*x^79 + 52182*x^78 + 48817*x^77 + 10763*x^76 + 46542*x^75 + 36060*x^74 + 49972*x^73 + 63603*x^72 + 46506*x^71 + 44788*x^70 + 44905*x^69 + 46112*x^68 + 5297*x^67 + 26440*x^66 + 28470*x^65 + 15525*x^64 + 11566*x^63 + 15781*x^62 + 36098*x^61 + 44402*x^60 + 55331*x^59 + 61583*x^58 + 16406*x^57 + 59089*x^56 + 53161*x^55 + 43695*x^54 + 49580*x^53 + 62685*x^52 + 31447*x^51 + 26755*x^50 + 14810*x^49 + 3281*x^48 + 27371*x^47 + 53392*x^46 + 2648*x^45 + 10095*x^44 + 25977*x^43 + 22912*x^42 + 41278*x^41 + 33236*x^40 + 57792*x^39 + 7169*x^38 + 29250*x^37 + 16906*x^36 + 4436*x^35 + 2729*x^34 + 29736*x^33 + 19383*x^32 + 11921*x^31 + 26075*x^30 + 54616*x^29 + 739*x^28 + 38509*x^27 + 19118*x^26 + 20062*x^25 + 21280*x^24 + 12594*x^23 + 14974*x^22 + 27795*x^21 + 54107*x^20 + 1890*x^19 + 13410*x^18 + 5381*x^17 + 19500*x^16 + 47481*x^15 + 58488*x^14 + 26433*x^13 + 37803*x^12 + 60232*x^11 + 34772*x^10 + 1505*x^9 + 63760*x^8 + 20890*x^7 + 41533*x^6 + 16130*x^5 + 29769*x^4 + 49142*x^3 + 64184*x^2 + 55443*x + 45925")
C=R("19921*x^174 + 49192*x^173 + 18894*x^172 + 61121*x^171 + 50271*x^170 + 11860*x^169 + 53128*x^168 + 38658*x^167 + 14191*x^166 + 9671*x^165 + 40879*x^164 + 15187*x^163 + 33523*x^162 + 62270*x^161 + 64211*x^160 + 54518*x^159 + 50446*x^158 + 2597*x^157 + 32216*x^156 + 10500*x^155 + 63276*x^154 + 27916*x^153 + 55316*x^152 + 30898*x^151 + 43706*x^150 + 5734*x^149 + 35616*x^148 + 14288*x^147 + 18282*x^146 + 22788*x^145 + 48188*x^144 + 34176*x^143 + 55952*x^142 + 9578*x^141 + 9177*x^140 + 22083*x^139 + 14586*x^138 + 9748*x^137 + 21118*x^136 + 155*x^135 + 64224*x^134 + 18193*x^133 + 33732*x^132 + 38135*x^131 + 51992*x^130 + 8203*x^129 + 8538*x^128 + 55203*x^127 + 5003*x^126 + 2009*x^125 + 45023*x^124 + 12311*x^123 + 21428*x^122 + 24110*x^121 + 43537*x^120 + 21885*x^119 + 50212*x^118 + 40445*x^117 + 17768*x^116 + 46616*x^115 + 4771*x^114 + 20903*x^113 + 47764*x^112 + 13056*x^111 + 50837*x^110 + 22313*x^109 + 39698*x^108 + 60377*x^107 + 59357*x^106 + 24051*x^105 + 5888*x^104 + 29414*x^103 + 31726*x^102 + 4906*x^101 + 23968*x^100 + 52360*x^99 + 58063*x^98 + 706*x^97 + 31420*x^96 + 62468*x^95 + 18557*x^94 + 1498*x^93 + 17590*x^92 + 62990*x^91 + 27200*x^90 + 7052*x^89 + 39117*x^88 + 46944*x^87 + 45535*x^86 + 28092*x^85 + 1981*x^84 + 4377*x^83 + 34419*x^82 + 33754*x^81 + 2640*x^80 + 44427*x^79 + 32179*x^78 + 57721*x^77 + 9444*x^76 + 49374*x^75 + 21288*x^74 + 44098*x^73 + 57744*x^72 + 63457*x^71 + 43300*x^70 + 1508*x^69 + 13775*x^68 + 23197*x^67 + 43070*x^66 + 20751*x^65 + 47479*x^64 + 18496*x^63 + 53392*x^62 + 10387*x^61 + 2317*x^60 + 57492*x^59 + 25441*x^58 + 52532*x^57 + 27150*x^56 + 33788*x^55 + 43371*x^54 + 30972*x^53 + 39583*x^52 + 36407*x^51 + 35564*x^50 + 44564*x^49 + 1505*x^48 + 47519*x^47 + 38695*x^46 + 43107*x^45 + 1676*x^44 + 42057*x^43 + 49879*x^42 + 29083*x^41 + 42241*x^40 + 8853*x^39 + 33546*x^38 + 48954*x^37 + 30352*x^36 + 62020*x^35 + 39864*x^34 + 9519*x^33 + 24828*x^32 + 34696*x^31 + 2387*x^30 + 27413*x^29 + 55829*x^28 + 40217*x^27 + 30205*x^26 + 42328*x^25 + 6210*x^24 + 52442*x^23 + 58495*x^22 + 2014*x^21 + 26452*x^20 + 33547*x^19 + 19840*x^18 + 5995*x^17 + 16850*x^16 + 37855*x^15 + 7221*x^14 + 32200*x^13 + 8121*x^12 + 23767*x^11 + 46563*x^10 + 51673*x^9 + 19372*x^8 + 4157*x^7 + 48421*x^6 + 41096*x^5 + 45735*x^4 + 53022*x^3 + 35475*x^2 + 47521*x + 27544")
S=R("x^175 + 37040*x^174 + 24879*x^173 + 14573*x^172 + 33018*x^171 + 25241*x^170 + 33949*x^169 + 21333*x^168 + 31488*x^167 + 12566*x^166 + 13384*x^165 + 32134*x^164 + 9803*x^163 + 51396*x^162 + 21311*x^161 + 46915*x^160 + 56191*x^159 + 54048*x^158 + 21915*x^157 + 60654*x^156 + 12744*x^155 + 46606*x^154 + 27813*x^153 + 58327*x^152 + 51976*x^151 + 41193*x^150 + 46991*x^149 + 62161*x^148 + 42118*x^147 + 45229*x^146 + 43328*x^145 + 43132*x^144 + 47360*x^143 + 4923*x^142 + 34207*x^141 + 41295*x^140 + 23582*x^139 + 33173*x^138 + 52787*x^137 + 32953*x^136 + 61956*x^135 + 11571*x^134 + 34800*x^133 + 35486*x^132 + 46689*x^131 + 34646*x^130 + 22952*x^129 + 15720*x^128 + 57207*x^127 + 25261*x^126 + 6708*x^125 + 6744*x^124 + 1459*x^123 + 56502*x^122 + 53578*x^121 + 3930*x^120 + 40505*x^119 + 33208*x^118 + 47251*x^117 + 5962*x^116 + 40882*x^115 + 10797*x^114 + 39561*x^113 + 33573*x^112 + 14553*x^111 + 40379*x^110 + 9273*x^109 + 35779*x^108 + 52537*x^107 + 23012*x^106 + 16770*x^105 + 41799*x^104 + 18669*x^103 + 60660*x^102 + 11408*x^101 + 18032*x^100 + 41108*x^99 + 16731*x^98 + 40753*x^97 + 43719*x^96 + 58015*x^95 + 57612*x^94 + 41851*x^93 + 5452*x^92 + 41246*x^91 + 39669*x^90 + 53225*x^89 + 27078*x^88 + 39243*x^87 + 253*x^86 + 18536*x^85 + 14029*x^84 + 9735*x^83 + 20666*x^82 + 8484*x^81 + 46868*x^80 + 43436*x^79 + 40958*x^78 + 16239*x^77 + 26023*x^76 + 34094*x^75 + 8138*x^74 + 12145*x^73 + 16085*x^72 + 37075*x^71 + 53683*x^70 + 60150*x^69 + 44570*x^68 + 15521*x^67 + 555*x^66 + 44273*x^65 + 23019*x^64 + 15176*x^63 + 16181*x^62 + 44482*x^61 + 24615*x^60 + 18942*x^59 + 39750*x^58 + 59564*x^57 + 48814*x^56 + 1177*x^55 + 49053*x^54 + 58965*x^53 + 59790*x^52 + 599*x^51 + 22937*x^50 + 19399*x^49 + 53215*x^48 + 50910*x^47 + 52055*x^46 + 46395*x^45 + 9536*x^44 + 40689*x^43 + 34209*x^42 + 53536*x^41 + 55298*x^40 + 39536*x^39 + 54372*x^38 + 1225*x^37 + 3801*x^36 + 49121*x^35 + 55843*x^34 + 57913*x^33 + 15890*x^32 + 48606*x^31 + 28984*x^30 + 15322*x^29 + 23173*x^28 + 51266*x^27 + 7318*x^26 + 22491*x^25 + 61646*x^24 + 1853*x^23 + 12999*x^22 + 51701*x^21 + 55675*x^20 + 5050*x^19 + 20445*x^18 + 51646*x^17 + 22357*x^16 + 47886*x^15 + 24984*x^14 + 24470*x^13 + 63056*x^12 + 2633*x^11 + 14270*x^10 + 27955*x^9 + 33600*x^8 + 18549*x^7 + 59346*x^6 + 60878*x^5 + 28255*x^4 + 41383*x^3 + 34391*x^2 + 24028*x + 18769")
phi = (p**78-1)*(p**97-1)
e = 65537
d = inverse_mod(e, phi)
RES = R("1")
MUL = C
while(True):
	if(d % 2 == 1):
		RES = (RES * MUL) % S
		d = d - 1
	d = d / 2
	MUL = (MUL * MUL) % S
	if(d == 0):
		break
h=''.join([str(i) for i in RES.list()])
h=88520242910362871448352317137540300262448941340486475602003226117035863930302
p1 = 106472061241112922861460644342336453303928202010237284715354717630502168520267
c1 = 20920247107738496784071050239422540936224577122721266141057957551603705972966457203177812404896852110975768315464852962210648535130235298413611598658659777108920014929632531307409885868941842921815735008981335582297975794108016151210394446009890312043259167806981442425505200141283138318269058818777636637375101005540308736021976559495266332357714
v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p1])
m = matrix([v1,v2])
shortest_vector = m.LLL()[0]
g1=shortest_vector[1]
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import tqdm
g1=228679177303871981036829786447405151037
e = 65537
c = 20920247107738496784071050239422540936224577122721266141057957551603705972966457203177812404896852110975768315464852962210648535130235298413611598658659777108920014929632531307409885868941842921815735008981335582297975794108016151210394446009890312043259167806981442425505200141283138318269058818777636637375101005540308736021976559495266332357714
n=31398174203566229210665534094126601315683074641013205440476552584312112883638278390105806127975406224783128340041129316782549009811196493319665336016690985557862367551545487842904828051293613836275987595871004601968935866634955528775536847402581734910742403788941725304146192149165731194199024154454952157531068881114411265538547462017207361362857
for i in tqdm(range(2**20)):
    g=g1^i
    if(isPrime(g) and n%g==0):
        p=n//g
        phi=(p-1)*(g-1)
        print(long_to_bytes(pow(c,inverse(e,phi),n)))
DASCTF{P01yn0m141RS4_W17h_NTRU}
# LWE？(复现)
# 题目
from secret import secret
assert len(secret)==66*3
sec = [ord(x) for x in secret]
DEBUG = False
m = 66
n = 200
p = 3
q = 2^20
def errorV():
  return vector(ZZ, [1 - randrange(p) for _ in range(n)])
def matrixMn():
  return matrix(ZZ, [[q//2 - randrange(q) for _ in range(n)] for _ in range(m)])
A, B, C = matrixMn(), matrixMn(), matrixMn()
x = vector(ZZ, sec[0:m])
y = vector(ZZ, sec[m:2*m])
z = vector(ZZ, sec[2*m:3*m])
e = errorV()
b = x*A+y*B+z*C+e
if DEBUG:
  print('x = %s' % x)
  print('y = %s' % y)
  print('z = %s' % z)
  print('e = %s' % e)
print('A = \n%s' % A)
print('B = \n%s' % B)
print('C = \n%s' % C)
print('b = %s' % b)
把[ABC]\begin{bmatrix} A&B&C\\ \end{bmatrix} 看成普通 LWE 的 A，把[xyz]\begin{bmatrix} x\\ y\\ z\\ \end{bmatrix} 看成普通 LWE 的 x，就是个普通的 LWE
with open(r'C:\Users\gx\Downloads\tempdir\CRYPTO附件\LWE？\out',"r") as f:
    data=f.readline()
    A=[]
    for i in range(66):
        data=f.readline().strip().strip('[').strip(']').replace('   ',' ').replace('  ',' ').replace('  ',' ').split(' ')
        tmp_A=[]
        for i in data:
            if(i!=''):
                tmp_A.append(int(i))
        A.append(tmp_A)
    data = f.readline()
    B = []
    for i in range(66):
        data = f.readline().strip().strip('[').strip(']').replace('   ', ' ').replace('  ', ' ').replace('  ',
                                                                                                         ' ').split(' ')
        tmp_A = []
        for i in data:
            if (i != ''):
                tmp_A.append(int(i))
        B.append(tmp_A)
    data = f.readline()
    C = []
    for i in range(66):
        data = f.readline().strip().strip('[').strip(']').replace('   ', ' ').replace('  ', ' ').replace('  ',
                                                                                                         ' ').split(' ')
        tmp_A = []
        for i in data:
            if (i != ''):
                tmp_A.append(int(i))
        C.append(tmp_A)
b = [-19786291, -713104590, 79700973, 23261288, 203038164, 430352288, 147848301, 633183638, 188651439, 243206160, -654830271, 335642059, -100511588, 180023362, 130607831, 227597861, 188424473, 175518170, -246987997, 180879649, 421934976, -227575274, -628937118, 5466646, -254939474, -438417079, 150434624, 327054986, 163561829, 816959939, -265298657, 82651050, 176899880, 174020455, -419656325, -101606182, 300413909, 237169571, -589213744, 121803611, -38080334, -255712509, -133782964, 106220001, 195767251, -397096116, -583305587, -182462561, -271478737, -32014717, 114385188, 437506115, -1165732, 179349265, -77761751, -233976783, 410153356, 476453640, 91892631, -242168750, 506769243, -384438362, 131852532, 586202810, 376719791, 578215353, 874304742, 163584566, 434260863, 98013671, 213627784, 59622886, -84912852, 156744856, 169652328, 178143615, 400046730, 408163110, -357990863, -269552089, -199410809, 187503858, -853206157, 134901027, 313984185, -162544217, -69722073, 43817388, -47389463, 210346729, -46516961, 72002967, 327714191, 45052266, 1010509210, 110937225, 448179404, 341448936, 446550865, 221914340, -804918424, -12007071, 151215468, 440279795, -73408566, -112121988, 40294376, 283179449, -193812410, -30061804, 20326854, 65412625, -260020045, -570090340, 1546454, 548030557, 618148316, 290333796, 665474379, 301709165, -104726821, -503111899, 480689642, -331192606, -518345784, -314602459, 25354403, 410995568, 179675848, -207010027, 400838662, 125916880, 501112567, 578261227, 24802586, 493171331, 383306766, -390093502, -389822626, -303615722, 20813851, -399678371, -566907567, -432647113, -280465568, 1002042393, -510901339, 316603766, -139701243, 211217523, 108545545, -12948109, -569199543, 37065919, -150542603, 417851006, -470173530, -628557669, -128339015, -427978763, 381402990, 205835334, -30976552, -357466556, -104985580, -115366372, 296031071, -8036087, 79340491, 650365147, 295521125, 885900267, 133049758, 217970062, 237420894, 358760095, -2684469, 475711698, 316770575, -25024622, -193442003, 200260606, 89183826, 567491985, 726371428, 222116554, 87397506, -29529094, 125968479, -50793004, 218035181, -210376687, 1025673749, -262390458, 467412984, -71097225, 259125517, -337232810, 143359550, 27115363]
AA=[]
for i in A:
    AA.append(i)
for i in B:
    AA.append(i)
for i in C:
    AA.append(i)
e = b
W = AA
e = vector(e)
W = matrix(W)
def babai(A, w):
    A = A.LLL()
    G = A.gram_schmidt()[0]
    t = w
    for i in reversed(range(A.nrows())):
        c = ((t * G[i]) / (G[i] * G[i])).round()
        t -= A[i] * c
    return w - t
V=babai(W,e)
m=V/W
flag=[chr(i) for i in m]
print(flag)
跑好久
Oh, you get it?? Here is the flag: 'DASCTF{uuid}'. What? You don't know the uuid? The first part is 'dcf41556', second part-> 'c194', and then '4c66', '9092'. And finally, it's '059e0bf8b84e'!!! 0v0