2023羊城杯密码题WP

2023羊城杯，Crypto六题Writeup。

基本都是模板题，甚至原题，还有给错数据的emmm

不过有一两题还是出的可以的

反正都AK了而且WP都写了，就来水个博客（

Danger_RSA·

题目：Danger_RSA的附件.zip

这个是2023 Crypto CTF原题，可以直接套春乎或V的公众号的WP解，但其实这里并不需要爆破$e$的因子恢复$s$和$t$，下面细说。

首先根据题目有$p = X_p^a + s$、$q = X_q^a + t$和$e = st$，乘一下有

$$N = pq = (X_p X_q)^a + t X_q^a + s X_p^a + st \approx (X_p X_q)^a$$

$t X_q^a + s X_p^a$相对于$(X_p X_q)^a$可忽略，对$N$开$a$次方或者对$N-e$开$a$次方然后取整可得$X_p X_q$（这个可以本地自己生成数据测试验证）。

接下来把已知的放一边，可得

$$t X_q^a + s X_p^a = N - e - (X_p X_q)^a$$

到这里就跟RSA知道$p + q$分解$N$的情况一样，只是现在是知道$t X_q^a + s X_p^a$分解$(X_p X_q)^a$，

$$t X_q^a - s X_p^a = \sqrt{(t X_q^a + s X_p^a)^2 - 4 e (X_p X_q)^a} \\ t X_q^a = \frac{(t X_q^a + s X_p^a) + (t X_q^a - s X_p^a)}{2} \\ s X_p^a = (t X_q^a + s X_p^a) - t X_q^a \\$$

然后$t X_q^a$里面含因子$t$，$s X_p^a$里面含因子$s$，$e$同时含因子$s$和$t$，所以做两次GCD可得$k_tt$和$k_ss$

$$k_t t = \text{GCD}(e, t X_q^a) \\ k_s s = \text{GCD}(e, s X_p^a) \\$$

在这个题目上可以验证$k_t = k_s = 1$，即GCD解出来的就是$s$和$t$，然后代回可计算$p$和$q$

$$p = X_p^a + s \\ q = X_q^a + t \\$$

解出$p$和$q$，最后RSA解密即可。

参考代码：

# Sage10

N = 20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223
e = 11079917583
c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766
a = 4

from gmpy2 import iroot
XpXq = Integer(iroot(N, 4)[0])

tXpa_plus_sXqa = N - e - XpXq^a
tXpa_minu_sXqa = Integer(pow(tXpa_plus_sXqa^2 - 4 * e * XpXq^a, 1/2))
tXpa = (tXpa_plus_sXqa + tXpa_minu_sXqa) // 2
sXqa = tXpa_plus_sXqa - tXpa

t = gcd(e, tXpa)
s = gcd(e, sXqa)
assert s * t == e

Xpa = tXpa // t
Xqa = sXqa // s
p = Xpa + s
q = Xqa + t
assert p * q == N

def nth(y, n, p, k=1):
  F = Zmod(p^k)
  x0 = F(y).nth_root(n)
  u0 = F(1).nth_root(n)
  x = []
  u = []
  for i in range(n):
    u += [u0^(i+1)]
    x += [x0 * u[i]]
  return list(set(x))

ep = gcd(e, p-1)
eq = gcd(e, q-1)
mpe = pow(c, (e//ep).inverse_mod(p-1), p)
#mqe = pow(c, (e//eq).inverse_mod(q-1), q)
mp = nth(mpe, ep, p)
#mq = nth(mqe, eq, q)

import libnum
print(mp)
for m in mp:
  if pow(m, e, N) == c:
    flag = libnum.n2s(int(m))
    print(flag)
    break
  

exit(0)
import itertools
import libnum
for mpmq in itertools.product(*[mp, mq]):
  m = crt(list(mpmq), [p, q])
  flag = libnum.n2s(int(m))
  print(flag)
  
'''
[193791037461644233995376284256372330707402849716940510299664007594824393064330407551687966974688298171142448610230412894226758054727293, 4621918813609781938184868550308988637756887568019678607295799714628811400020200938948497213213266863345216963431445323903028310990768116969361205699319340511813959490981159388955349135031712993955623301024170851428211368608095579239028266700933791397393913281642170606710629062650325921270741696558455903, 5208729084606622037477057818114301217586973260495250596256426296665212781531551895530187842325287550850010085926299699465469816420388206942360370092161366930224726149614873162410172870586923295035593372597252017796986589030221182923984470817141858596481035087931223300902769414406785642085542700850347562021]
b'DASCTF{C0nsTruct!n9_Techn1qUe2_f0r_RSA_Pr1me_EnC2ypt10N}'
'''

PS：这里后面解出来会发现$\varphi$和$e$不互素，还要开个方，后来发现我自己的模板不在Sage10上跑会卡住，有空再偷一下春哥的板子（逃

PPS：这里对$q$的开方会有点麻烦，后来发现只用$p$也可以解密就没有管了

Easy_3L·

题目：Easy_3L的附件.zip

题目套了几层，首先是一个种子为$m$的线性同余LCG，给出S1、S2和S4、S5，由于不知道模数，只根据这几个无法求出LCG的系数$a$和$b$，还需要S3。S3被一个一维的NTRU加密，LLL老套路规约一下可以求密钥然后解密（只是变量名被换了）。所以这就是个LCG+LLL的模板题。

首先解NTRU的密钥，根据密钥生成有$h \equiv f^{-1}q \pmod p$，即$fh - kp = q$，令

$$v = (f, -k) \\ B = \begin{bmatrix} 1 & D h \\ 0 & Dp \end{bmatrix} \\ w = (f, D q)$$

可以构造出线性方程$vB = w$，对$B$进行LLL规约得$f$和$q$。

PS：其中$D$是配平数，这个$D$可以控制上面向量$w$的大小，从而可以控制规约出来的$q$的大小。这里说明一下，只要对$B$规约成功就可以解出一组合法的$(f, q)$，即符合$h \equiv f^{-1}q \pmod p$，但是如果需要解密成功的话需要足够大的$q$，否则会因为模$q$操作造成$S_3$值得损失。为了让$q$足够大，这里的$D$需要足够小，但是不是每个$D$都可以规约成功，所以后面exp中对$D$从小到大进行枚举。

有了密钥后就是NTRU解密出$S_3$，

$$S_3 = (c f \pmod p) * f^{-1} \mod q$$

再然后根据题目的LCG有

$$S_{i} \equiv a S_{i-1} + b \pmod n$$

先凑够两个相减消去碍事的$b$

$$S_{i+1} - S_i \equiv a (S_i - S_{i-1}) \pmod n$$

然后提取出$a$

$$(S_{i+1} - S_i) (S_i - S_{i-1})^{-1} \equiv a \pmod n$$

但是现在并不知道模数$n$，再凑个$j$就有

$$(S_{j+1} - S_j) (S_j - S_{j-1})^{-1} \equiv a \pmod n$$

所以

$$(S_{i+1} - S_i) (S_i - S_{i-1})^{-1} \equiv (S_{j+1} - S_j) (S_j - S_{j-1})^{-1} \pmod n \\ (S_{i+1} - S_i)(S_j - S_{j-1}) - (S_{j+1} - S_j)(S_i - S_{i-1}) \equiv 0 \pmod n$$

去掉模操作后

$$(S_{i+1} - S_i)(S_j - S_{j-1}) - (S_{j+1} - S_j)(S_i - S_{i-1}) = k_{ij} n$$

代入$i=2$、$j=3$和$i=3$、$j=4$，就可得$k_{23}n$和$k_{34}n$，盲猜$k_{23}$和$k_{34}$互素，做个GCD可以恢复$n$。

最后计算

$$a \equiv (S_{i+1} - S_i) (S_i - S_{i-1})^{-1} \pmod n \\ b \equiv S_{i+1} - a S_i \pmod n \\ m = a^{-1} (S_1 - b) \pmod n$$

得flag。

参考代码：

S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287


for i in range(200, 700):
  print(i)
  D = 2^i
  B = matrix(ZZ, [[1, D*h], [0, D*p]])
  L = B.LLL()
  f = Integer(abs(L[0][0]))
  q = Integer(abs(L[0][1]) // D)
  if not h == (f.inverse_mod(p) * q) % p:
    continue

  a = c * f % p
  S3 = a * f.inverse_mod(q) % q

  n = gcd((S3-S2)^2 - (S2-S1)*(S4-S3), (S4-S3)^2 - (S3-S2)*(S5-S4))
  if n != 1:
    print('f = %d' % f)
    print('q = %d' % q)
    print('n = %d' % n)
    break
a = (S3 - S2) * (S2 - S1).inverse_mod(n) % n
b = (S2 - a * S1) % n
print('a = %d' % a)
print('b = %d' % b)
m = (S1 - b) * a.inverse_mod(n) % n
import libnum
print(libnum.n2s(int(m)))

'''
213
f = 413301180038546973316137674870589882147305293496057497772073927555046884257486263836713004292833493132001243260591164367442485193468991124058625234552087046120678322178758072868296612348525542661280286775661127225791195231643203301751435284753
q = 18772753754134873622668068261315956077681347161806060082164835888595835700109818730322267553874027247668932797883276028015173786305189273696314195165370843863808886406071416313879
n = 12433235385460084327215142269091752668477278692416805859007828624838647815241707248797912107322868748847211061641608674422095027981318008221949510129177787
a = 1017579321905754831612145134014116183026524698685218523407174987842084260441
b = 1244547131344198183940330607549789182491018543684349414313485985685030480
b'DASCTF{NTRU_L0G_a6e_S1mpLe}'
'''

SigninCrypto·

题目：SigninCrypto的附件.zip

flag被DES3加密，首先分析IV，可得digest1和digest2相等，所以IV1和IV2相等。

分析hint2，解码一下就可以看到前4 byts是可见字符GWHT，算一下长度，发现hint2只是抹去了IV得低4 bytes，所以可知IV1和IV2为4 bytes长，且都为GWHT，于是恢复了IV。

然后KEY = K1 + K2 + K3，首先分析长度，DES3的密钥长度是16或24（否则会报VallueError），K2和K3都是8，所以KEY应该是24，即K1长度是8，再分析xor，hint实际有效得只有2 bytes，即os.urandom(2)，而hint1长度为16 bytes，即hint1的前8 bytes由4个os.urandom(2)重复，估可恢复hint1，异或回去得K1。

Rand()的循环长度明显提示了随机数预测，由于每次循环前都重置一样的seed，根据MT19937可由List1恢复List2，即List1中刚好含有List2输出时被抹去的信息，然后就有624个32比特，上RandCrack预测随机数。

flag头是DASCTF，爆破1 bytes得K3。

最后解密得flag。

from Crypto.Util.number import *
from Crypto.Cipher import DES3
from randcrack import RandCrack
from string import printable
import itertools
import hashlib

mode = DES3.MODE_CBC
xor = 334648638865560142973669981316964458403
digest = '62343937373634656339396239663236643437363738396663393438316230353665353733303939613830616662663633326463626431643139323130616333363363326631363235313661656632636265396134336361623833636165373964343533666537663934646239396462323666316236396232303539336438336234393737363465633939623966323664343736373839666339343831623035366535373330393961383061666266363332646362643164313932313061633336336332663136323531366165663263626539613433636162383363616537396434353366653766393464623939646232366631623639623230353933643833'
hint2 = 22078953819177294945130027344
hint2 = '47574854d913bccd757e9950'
ciphertext = 'a6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1'
ciphertext = bytes.fromhex(ciphertext)

digest1 = digest[: len(digest)//2]
digest2 = digest[len(digest)//2: ]
assert digest1 == digest2

IV1 = bytes.fromhex(hint2[: -16])
IV = IV1 * 2
print(IV)

with open('./task.txt', 'r') as f:
    data = f.read()
data = data.split('\n')[:-1]
data = [int(x, 16) for x in data]
List1 = data[: 624]
List2 = data[624:]
assert len(List2) == 312

'''
Leak1 = []
for i in range(0, 624, 2):
    Leak1 += [List1[i]*2^16 + List1[i+1]]
'''

Leak2 = []
for i in range(312):
    Leak2 += [List1[2*i]   * 2**16 + List2[i] % 2**16]
    Leak2 += [List1[2*i+1] * 2**16 + (List2[i] >> 16)]
assert len(Leak2) == 624
rc = RandCrack()
for l in Leak2:
    rc.submit(l)
K2 = long_to_bytes(rc.predict_getrandbits(64))

xx = long_to_bytes(xor)[:2]
hint1 = bytes_to_long(xx * 8)
K1 = long_to_bytes(hint1 ^ xor)
print(K1)
for f7 in printable:
    K3 = ('DASCTF{' + f7).encode()
    KEY = K1 + K2 + K3

    des3 = DES3.new(KEY, mode, IV)
    m = des3.decrypt(ciphertext)
    if b'DASCTF' in m:
        print(m)
        break

'''
b'GWHTGWHT'
b'dasctfda'
b'DASCTF{8e5ee461-f4e1-4af2-8632-c9d62f4dc073}\x04\x04\x04\x04'
'''

esyRSA·

题目：esyRSA的附件.zip

和Wiener攻击一样，大$d$小$e$套一下连分数可解$e$，然后由$e$和$d$可以恢复$p$和$q$。

奈何这**出题人把$n$贴了两次。。。服了

直接套Wiener模板可解

#n = 8064259277274639864655809758868795854117113170423331934498023294296505063511386001711751916634810056911517464467899780578338013011453082479880809823762824723657495915284790349150975180933698827382368698861967973964030509129133021116919437755292590841218316278732797712538885232908975173746394816520256585937380642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
# cao
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913

from tqdm import tqdm
fra = (d/n).continued_fraction()
for i in tqdm(range(len(fra))):
    k = fra.numerator(i)
    e = fra.denominator(i)

    if k != 0 and (e*d-1) % k == 0:
      try:
        phi = (e*d-1) // k
        p_plus_q = n + 1 - phi
        p_min_q = (p_plus_q^2 - 4*n)^(1/2)
        p = (p_plus_q + p_min_q) // 2
        q = n // p
        if p*q == n:
          break
      except:
        continue
      
print('p = %s' % p)
print('q = %s' % q)
print('e = %s' % d)

from hashlib import md5
print("Flag: DASCTF{%s}" % md5(str(p + q).encode()).hexdigest())

'''
p = 10181341212828413853336916619161138854377885230386496425058202154486415709366161346816273366144505351043947477469664133317598479763451392984403646602585037
q = 7920625690369490250766357750388349704260128405941822835255851274284409978206593795103040446837018619894098452542488850045009467407103749792461438242280929
e = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
Flag: DASCTF{4ae33bea90f030bfddb7ac4d9222ef8f}
'''

另外提一下，Wiener和格规约其实是互通的，用格做复杂度反而会更低，参考代码：

#n = 8064259277274639864655809758868795854117113170423331934498023294296505063511386001711751916634810056911517464467899780578338013011453082479880809823762824723657495915284790349150975180933698827382368698861967973964030509129133021116919437755292590841218316278732797712538885232908975173746394816520256585937380642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913

D = 2^512
m = matrix(ZZ, [
  [D, n+1],
  [0, -d]
])
L = m.LLL()
w = L[0]
v = m.solve_left(w)
k = abs(v[0])
e = abs(v[1])
print(k, e)

if k != 0:
  phi = (e*d-1) // k
else:
  phi = e*d - 1
p_plus_q = n + 1 - phi
p_min_q = (p_plus_q^2 - 4*n)^(1/2)
p = (p_plus_q + p_min_q) // 2
q = n // p
assert p*q == n

print('p = %s' % p)
print('q = %s' % q)
print('e = %s' % d)

from hashlib import md5
print(md5(str(p+q).encode()).hexdigest())

'''
2384 13521
p = 10181341212828413853336916619161138854377885230386496425058202154486415709366161346816273366144505351043947477469664133317598479763451392984403646602585037
q = 7920625690369490250766357750388349704260128405941822835255851274284409978206593795103040446837018619894098452542488850045009467407103749792461438242280929
e = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
4ae33bea90f030bfddb7ac4d9222ef8f
'''

PS：这个也是原题

MCeorpkpleer·

题目：MCeorpkpleer的附件.zip

给了$p$的高位，Coppersmith分解$n$得$p$和$q$，套了之前强网杯的代码。

$w < m$，所以w = pubkey[0]，知道$w$。

由公钥生成可知

$$k_i \equiv w l_i \equiv w 3^i \pmod m$$

所以

$$3 k_i - k_{i-1} \equiv 0 \pmod m \\ 3 k_i - k_{i-1} = \alpha_i m$$

凑两个$i$然后GCD可恢复$m$，但这里要选后面的$i$，不然前面的没有模$m$，就会$3 k_i - k_{i-1}$，不含因子$m$。

$$m = \text{GCD}(3 k_i - k_{i-1}, 3 k_{j} - k_{j})$$

再看en_e，

$$e_{ne} \equiv \sum k_i e_i \equiv \sum w l_i e_i \equiv w \cdot \sum 3^i e_i \pmod m$$

所以

$$\sum 3^i e_i \equiv e_{ne} w^{-1} \mod m$$

由$m$的生成可知$\sum 3^i < m$，所以

$$\sum 3^i e_i = (e_{ne} w^{-1} \mod m)$$

$\sum 3^i e_i$其实就是$e$的三进制表示，包含$e$的所有比特，所以做个进制转换即可恢复$e$，然后RSA解密。

参考代码：

ph = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
pubkey = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
en_e = 31087054322877663244023458448558

def solve(n, ph, pl=1, pbits=1024):
  hbits = ph.nbits()
  lbits = pl.nbits()
  PR.<x> = PolynomialRing(Zmod(n))
  f = ph * 2^(pbits-hbits) + x * 2^lbits + pl
  f = f.monic()
  roots = f.small_roots(X=2^(pbits-hbits-lbits+1), beta=0.4)
  if roots:        
    pm = Integer(roots[0])
    p = ph * 2^(pbits-hbits) + pm * 2^lbits + pl
    if n % p == 0:
      q = n // p
      return p, q
  return None
p, q = solve(n, ph>>435)
print('p = %d' % p)
print('q = %d' % q)
assert p * q == n

leb = len(pubkey)
l = [pow(3, i) for i in range(leb)]
print(len(bin(sum(l))) - 1)

assert pubkey[0] * 3 == pubkey[1]
w = pubkey[0]
m = gcd(3*pubkey[-2] - pubkey[-1], 3*pubkey[-3] - pubkey[-2])
print('w = %d' % w)
print('m = %d' % m)
assert sum(l) < m

en_e = en_e * w.inverse_mod(m) % m
bine = []
for i in range(leb):
  bine += [str(en_e % 3)]
  en_e //= 3
e = Integer(''.join(bine), 2)
print('e = %d' % e)

import libnum
m = pow(c, e.inverse_mod((p-1)*(q-1)), n)
print(libnum.n2s(int(m)))

'''
p = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179677630589032444985150800881889090713797496239571291907818169058929859395965304623825442220206712660451198754072531986630133689525911
q = 162585259972480477964240855936099163585362299488578311068842002571891718764319834825730036484383081273549236661473286892739224906812137330941622699836239606393084030874487072527724286268715004074797344316619876830720445250395986443767703356842297999006344406006724963545062388183647988548800359369190326996261
102
w = 18143710780782459577
m = 4522492601441914729446821257037
e = 15960663600754919507
b'DASCTF{T81I_tPPS_6r7g_xlPi_OO3M_6vyV_Rkba}'
'''

XOR贯穿始终·

题目：XOR贯穿始终的附件.zip

核心价值观编码解码得压缩包密码

C0ngr4tulati0n5_y0u_fou^d_m3

PEM文件被corrupt，参考之前的手撕PEM密钥手撕一下，得

30820277
020100  # junk
300d06092a864886f70d0101010500048202613082025d
0201    # version
00
028181  # n
00b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913
0203    # e
010001
028181  # d
00974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361
0241    # p
00ea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb95fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9
0241    # q
00cad4c29d017e30ddabd606805044d9ca3e6a3184fb4e1f332845555498c36b02e7b97e2eb09d85c919e30a493ce94ef9412261c3998c7344271b6e6e1b3dfefb

然后做RSA解密发现明文后面不可读

b'DASCTF{0e287wQ\x08R\x17\x00FGXYFZ\x07V\x03kIUCn\x02VDg\x01f\x0cN'

结合题目名字盲猜异或了啥东西，分析不可读的长度发现和压缩包密码长度一致，异或之得flag。

PS：打开压缩包其实也可以看到有说密钥后面还有用。

#from Crypto.PublicKey import RSA
from base64 import b64decode
with open('./pri.pem', 'r') as f:
  data = f.read()

n = 0x00b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913
e = 0x010001
d = 0x00974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361
p = 0x00ea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb95fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9
q = 0x00cad4c29d017e30ddabd606805044d9ca3e6a3184fb4e1f332845555498c36b02e7b97e2eb09d85c919e30a493ce94ef9412261c3998c7344271b6e6e1b3dfefb
c = 91817924748361493215143897386603397612753451291462468066632608541316135642691873237492166541761504834463859351830616117238028454453831120079998631107520871612398404926417683282285787231775479511469825932022611941912754602165499500350038397852503264709127650106856760043956604644700201911063515109074933378818

print(p * q == n)
m = pow(c, d, n)
import libnum
flag = libnum.n2s(int(m))
print(flag)
key = b'C0ngr4tulati0n5_y0u_fou^d_m3'
flag1 = flag[:12].decode()
flag = flag[12:]
flag2 = ''
for i in range(len(key)):
  flag2 += chr(key[i] ^^ flag[i])
flag = flag1 + flag2
print(flag)

'''
True
b'DASCTF{0e287wQ\x08R\x17\x00FGXYFZ\x07V\x03kIUCn\x02VDg\x01f\x0cN'
DASCTF{0e2874af5e422482378640e61d919e9a}
'''

另外也可以对PEM密钥进行修复然后用工具读取，稍微分析一下，发现是头部的长度被改了，还塞了个垃圾数据

30820277	# Wrong length 0x0277
020100		# Repeated version
300d06092a864886f70d0101010500048202613082025d	# Junk

删除垃圾数据后计算长度是0x0196，所以再修改头部为30820196即可正常读取。

参考代码：

from Crypto.PublicKey import RSA
from base64 import b64decode
from Crypto.Util import asn1
import libnum
with open('./pri.pem', 'r') as f:
  data = f.read()
try:
    key = RSA.importKey(data)
except Exception as e:
    print(e)
key_64 = ''.join(data.split('\n')[1:-1])
key_num = libnum.s2n(b64decode(key_64))
key_hex = hex(key_num)[2:]
#print(key_hex)

key_hex = '30820196' + key_hex[60:]
seq = asn1.DerSequence()
seq.decode(bytes.fromhex(key_hex))
#print(list(seq))

_, n, e, d, p, q = seq
print('n = %d' % n)
print('e = %d' % e)
print('d = %d' % d)
print('p = %d' % p)
print('q = %d' % q)

再另外，观察一下垃圾数据，发现是一个新的SEQUENCE，继续分解一下

300d  # SEQUENCE
0609  # OBJECT IDENTIFIER
2a864886f70d010101	# algo_oid: (1.2.840.113549.1.1.1  - PKCSv1.2)
0500  # NULL

04820261  # OCTET STRING
3082025d  # SEQUENCE? emmm

发现垃圾数据其实只是048202613082025d和重复的版本号020100，300d06092a864886f70d0101010500其实是一个OBJECT IDENTIFIER（algo_oid），说了使用PKCSv1.2，可以说也不算垃圾数据吧（如果下次使用了其他算法的话还需要这个来获得所使用的算法）

所以还可以继续进行精修，重新计算长度。

参考代码：

from Crypto.PublicKey import RSA
from base64 import b64decode
from Crypto.Util import asn1
import libnum
with open('./pri.pem', 'r') as f:
  data = f.read()
try:
    key = RSA.importKey(data)
except Exception as e:
    print(e)
key_64 = ''.join(data.split('\n')[1:-1])
key_num = libnum.s2n(b64decode(key_64))
key_hex = hex(key_num)[2:]
#print(key_hex)

key_hex = key_hex[8+6: 8+6+30] + key_hex[8+6+30+16: ]
key_hex = '3082%s' % hex(len(key_hex)//2)[2:].zfill(4) + key_hex
seq = asn1.DerSequence()
seq.decode(bytes.fromhex(key_hex))
#print(list(seq))

a, v, n, e, d, p, q = seq
print('a = %s' % a)
print('v = %d' % v)
print('n = %d' % n)
print('e = %d' % e)
print('d = %d' % d)
print('p = %d' % p)
print('q = %d' % q)