NSS密码工坊非官方dlc

记录鸡块师傅给群友出的几道题目

easy_mod系列

easy_mod

task.py

from Crypto.Util.number import *
from random import *

table = "01234567"
p = getPrime(328)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(70)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)

'''
p = 501785758961383005891491265699612686883993041794260611346802080899615437298977076093878384543577171
c = 327005346153237517234971706274055111857447948791422192829214537757745905845319188257204611848165263
'''

已知
$$
m \equiv c \mod p
$$
一开始以$m$为目标构造格：

经过配平发现，当目标向量第一个元素为0的时候，其他元素只能达到328bit，意味着无法规约出$m$

于是转换目标，以$k$为目标构造格，这样把目标向量从$623bit$降低到$300bit$:

这个格甚至规约不出k

于是转变思路，把每一个$m_i$作为未知量，构造格

这样可以把目标向量从$300bit$降低到$6bit$

尝试配系数(配系数的作用是为了让这一列最后的结果是0，当这一列的结果为0的时候，无论怎么扩大行列式，对于规约结果已经没有作用)

配上大系数之后的规约结果在30以下，而$m_i$的值在48~56，说明目标向量还是太大了

经鸡块师傅指导

因为flag = b"NSSCTF{" + "".join([choice(table) for i in range(70)]).encode() + b"}"

我们可以把他写成这样的形式：

未知的字节只有70个，而且这70个字节，是从01234567中生成的

因此，可以把$m_i$写为$m_i = 48 + x_i$

这样的话，我们可以把目标向量降低到$0-7$的值

这时候我们构造格：

其中

因为目标向量中每个元素为$0-7$，所以在倒数第二行第二列设为4或3，是为了规约目标向量大小，提高规约成功率

用LLL算法规约的结果还是有比较大的值，选择用BKZ算法

exp

from Crypto.Util.number import *

p = 501785758961383005891491265699612686883993041794260611346802080899615437298977076093878384543577171
c = 327005346153237517234971706274055111857447948791422192829214537757745905845319188257204611848165263


Ge = Matrix(ZZ,72,72)

temp = bytes_to_long(b"NSSCTF{") * 256^71 + bytes_to_long(b"}") 
for i in range(70):
    temp += 48*256^(70-i)


for i in range(70):
    Ge[i,i] = 1
    Ge[i,-1] = 256^(70-i)
    
Ge[-2,-2] = 3
Ge[-2,-1] = (temp - c)
Ge[-1,-1] = p

for line in Ge.BKZ():
    m = ""
    if line[-1] == 0 and abs(line[-2]) == 3:
        print(line)
        for i in line[:-2]:
            m += str(abs(i))
        flag = "NSSCTF{" + m + "}"
        print(flag)

# NSSCTF{5036541772751046406531362142757356307107252723754051320011253505562041}

easy_mod2

task.py

from Crypto.Util.number import *
from random import *

table = "01234567"
p = getPrime(328)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(80)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)
print(flag)

'''
p = 324556397741108806830285502585098109678766437252172614832253074632331911859471735318636292671562523
c = 141624663734155235543198856069652171779130720945875442624943917912062658275440028763836569215230250
'''

和上题的区别是flag长度变长了，但p的数量级没变。

沿用上题的格发现规约的结果存在很多0-7范围之外的值

于是想到，减去52，这样0,1,2,3,4,5,6,7就可以用$-4,-3,-2,-1,0,1,2,3$表示

又一次把目标向量的值缩小

构造格

其中temp = bytes_to_long(b'NSSCTF{') * 256^{81} + bytes_to_long(b'}') +$\sum_{i=0}^{80}52\times 256^{80-i}$

exp

from Crypto.Util.number import *

p = 324556397741108806830285502585098109678766437252172614832253074632331911859471735318636292671562523
c = 141624663734155235543198856069652171779130720945875442624943917912062658275440028763836569215230250


Ge = Matrix(ZZ,82,82)

temp = bytes_to_long(b"NSSCTF{") * 256^81 + bytes_to_long(b"}")

for i in range(80):
    temp += 52*256^(80-i)

T = 2^100
for i in range(80):
    Ge[i,i] = 1
    Ge[i,-1] = 256^(80-i) * T

Ge[-2,-2] = 1
Ge[-2,-1] = (temp - c) * T
Ge[-1,-1] = p * T


for line in Ge.BKZ(block_size=16):
    m = ""
    if line[-1] == 0 and abs(line[-2]) == 1:
        print(line)
        for i in line[:-2]:
            m += chr((52 + i))
        flag = "NSSCTF{" + m + "}"
        print(flag)
# NSSCTF{25350625451533421162474265547571536103420331260232652121722452361537257541460235}

配大系数为了规约出0，用BKZ(size_block=16)是为了更精确

easy_mod3

task.py

from Crypto.Util.number import *
from random import *

table = "Nss"
p = getPrime(328)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(100)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)

'''
p = 421384892562377694077340767015240048728671794320496268132504965422627021346504549648945043590200571
c = 273111533929258227142700975315635731051782710899867431150541189647916512765137757827512121549727178
'''

首先把flag写成逐字节的形式
$$
flag = prefix + x_0\times256^{100} + x_1\times 256^{99} + … + x_i\times 2^{100-i} + x_{99}\times 256
$$

于是有
$$
c \equiv prefix + x_0\times256^{100} + x_1\times 256^{99} + … + x_i\times 2^{100-i} + x_{99}\times 256 \mod p
$$
$x_i = 78$或$x_i = 115$

根据前两题的思路，我们还是要把目标向量弄得更小

解这个同余式组
$$
ord(‘N’)\times a + b \equiv 1 \mod p
$$

$$
ord(‘s’)\times a+b \equiv 0 \mod p
$$

计算出a,b后，我们即可用$1$表示$N$,用$0$表示$s$，引入$m_i$，$m_i = 0$或$m_i = 1$

用$m_i$表示$x_i$为
$$
m_i \equiv ax_i + b \mod p
$$
此时，先对c作减法
$$
c - prefix \equiv x_0\times256^{100} + x_1\times 256^{99} + … + x_i\times 2^{100-i} + x_{99}\times 256 \mod p
$$

然后乘上a
$$
(c-prefix)a\equiv ax_0\times256^{100} + ax_1\times 256^{99} + … + ax_i\times 2^{100-i} + ax_{99}\times 256 \mod p
$$

再依次加上$b\times 256^{i}$,$i=(1,100)$

同样配上大系数

exp

from Crypto.Util.number import *
import gmpy2

a = 45555123520257048008361164001647572835532085872486083041351888153797515821243735097183247955697359
b = 239164398481349502043896111008649757386543450830551935967097412807436958061529609260212051767411138
p = 421384892562377694077340767015240048728671794320496268132504965422627021346504549648945043590200571
c = 273111533929258227142700975315635731051782710899867431150541189647916512765137757827512121549727178

prefix = bytes_to_long(b"NSSCTF{") * 256^101 + bytes_to_long(b"}")

c = (c - prefix) % p
c = c*a % p

Ge = Matrix(ZZ,102,102)

T = 2^100
for i in range(100):
    Ge[i,i] = 1
    Ge[i,-1] = 256^(100-i)
    c += b*256^(100-i)
    c %= p
    
Ge[-2,-2] = 1
Ge[-2,-1] = -c
Ge[-1,-1] = p
Ge[:,-1:] *= T

for line in Ge.BKZ():
    m = ""
    if line[-1] == 0 and abs(line[-2]) == 1:
        print(line)
        for i in line[:-2]:
            if i == 0:
                m += "s"
            else:
                m += "N"
        flag = "NSSCTF{" + m + "}"
        print(flag)
        # NSSCTF{NNNssNsNNNNsNNNsNNNNNssNNNssNNNsNsNNsNsNNssNNNNNNsNNNssNsNNNNNssNssssNsNNsNsssNNNNssNNNssNsNNssNsNss}

easy_mod_final

旧附件

task.py

from Crypto.Util.number import *
from random import *

p = 382341578876755047910270786090569535013570954958220282576527310027607029356817834229805565170363061
table1 = "NsS"
table2 = [363240026866636825072669542082311717933742315917012606686823760007829170314055842025699242629919061, 353526073204447024446020739384656942280539226749705781536551943704760671350652481846175115676519925, 343812119542257223819371936687002166627336137582398956386280127401692172387249121666650988723120789]
choose = [choice(table1) for i in range(100)]

flag = b"NSSCTF{" + "".join(choose).encode() + b"}"
c = 0
for i in range(len(choose)):
    c += 256**i*table2[table1.index(choose[i])]
    c %= p

print("c =",c)

'''
c = 207022199908418203957326448601855685285890830964132201922954241454827344173832839490247666897642796
'''

题目分别用$m_0,m_1,m_2$来表示N,s,S

我的思路是找到用什么值来作为$m_0,m_1,m_2$的代换，我这里用的是$1,0,-1$，是瞎蒙的

正解似乎是通过table2中的值是模p的等差数列，所以构造1,0,-1代换，不过我看不出来这是等差数列
$$
am_0 + b \equiv 1 \mod p
$$

$$
am_1+ b \equiv 0 \mod p
$$

$$
am_2 + b \equiv -1 \mod p
$$

以$1,0,-1$表示N,s,S，解出a,b分别为

a = 209130262916047757416181023902826867689263063069308312825701745088099619813047283985737596011902631
b = 184152803971204556520143517132487605286111694029965260002835796960581806700950306119300303760936459

因为
$$
c \equiv m_0\times 256^{0} + m_1 \times 256 + … + m_i \times 256^i + m_{99}\times256^{99} \mod p
$$
左边乘上a有
$$
ac \equiv am_0\times 256^{0} + am_1 \times 256 + … + am_i \times 256^i + am_{99}\times256^{99} \mod p
$$
再依次加上$b\times 256^i$

这里的c是处理后的c

exp

p = 382341578876755047910270786090569535013570954958220282576527310027607029356817834229805565170363061
a = 209130262916047757416181023902826867689263063069308312825701745088099619813047283985737596011902631
b = 184152803971204556520143517132487605286111694029965260002835796960581806700950306119300303760936459
c = 207022199908418203957326448601855685285890830964132201922954241454827344173832839490247666897642796

Ge = Matrix(ZZ,102,102)

c = c * a % p
T = 2^100
for i in range(100):
    Ge[i,i] = 1
    Ge[i,-1] = 256^i
    c += b * 256^i
    c %= p

Ge[-2,-2] = 1
Ge[-2,-1] = - c
Ge[-1,-1] = p
Ge[:,-1:] *= T

for line in Ge.BKZ():
    m = ""
    if line[-1] == 0 and abs(line[-2]) == 1:
        print(line)
        for i in line[:-2]:
            if i == -1:
                m += "N"
            if i == 0:
                m += "s"
            if i == 1:
                m += "S"
    flag = "NSSCTF{" + m + "}"
    print(flag)
    # NSSCTF{NssSNSsNSNSNsSssSssSssSSsNsNNNNNSsNNssNsSSSSSssSNSsSssSSSNSsNsSsSsSsSNSSsSSsNNsNSsSNSNsSSSNNSNSSSSSs}

因为此时规约的向量是

(-1, 0, 0, 1, -1, 1, 0, -1, 1, -1, 1, -1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, -1, 0, -1, -1, -1, -1, -1, 1, 0, -1, -1, 0, 0, -1, 0, 1, 1, 1, 1, 1, 0, 0, 1, -1, 1, 0, 1, 0, 0, 1, 1, 1, -1, 1, 0, -1, 0, 1, 0, 1, 0, 1, 0, 1, -1, 1, 1, 0, 1, 1, 0, -1, -1, 0, -1, 1, 0, 1, -1, 1, -1, 0, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, 0, -1, 0)

倒数第二个值本该是1，但是是-1，因此需要把-1对应S改为-1对应N

新附件

task.py

from Crypto.Util.number import *
from random import *

table = "GAME"
p = getPrime(440)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(100)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)
print(flag)

'''
p = 2271129678202363707972156644097566224560370806295266873816026779022614695317611229903770390498322537051358521932851893609555063610221
c = 244176818026839545554951436126300508547217557099550914232243928051857553603712968234687200629719468115535825237511413058786560692170
'''

根据前几题的经验，思路还是把G,A,M,E对应到很小的值，但是这题的难处在，对于直线$y \equiv ax + b \mod p$，只需要2点就能确定一条直线，如果随意选取$y$的话，很难能够找出系数$a,b$让(ord('G'),y1)，(ord('A'),y2)，(ord('M'),y3)，(ord('E'),y4)四点共线

参考鸡块师傅的做法：文章列表 | NSSCTF

把GAME按大小顺序排序：A,E,G,M，两两之间的差值为4,2,6，因此一定可以找到一个变换，使得依次排列的四个点，纵坐标差值的比例为2：1：3(这句话的解释如下)

先把4个点的方程写出来
$$
y_1 = ax_1 + b \mod p
$$

$$
y_2 = ax_2 + b \mod p
$$

$$
y_3 = ax_3 + b \mod p
$$

$$
y_4 = ax_4 + b\mod p
$$

两两作差可以消去b，得到
$$
y_1 - y_2 = a(x_1-x_2) \mod p
$$

$$
y_2 - y_3 = a(x_2-x_3) \mod p
$$

$$
y_3 - y_4 = a(x_3-x_4) \mod p
$$

因为$(x_1-x_2):(x_2-x_3):(x_3-x_4) = 2:1:3$

我们可以用$(G,0),(E,1)$来确定另外两个点的纵坐标，即$(A,3),(M,-3)$

之后再确定$a,b$，计算a,b我都是通过gb基计算的

p = 2271129678202363707972156644097566224560370806295266873816026779022614695317611229903770390498322537051358521932851893609555063610221
c = 244176818026839545554951436126300508547217557099550914232243928051857553603712968234687200629719468115535825237511413058786560692170

R.<a,b> = PolynomialRing(Zmod(p))

f1 = a*ord('G') + b - 0
f2 = a*ord('A') + b - 3
f3 = a*ord('M') + b + 3
f4 = a*ord('E') + b - 1


F = [f1,f2,f3,f4]
I = Ideal(F)

a = ZZ(-I.groebner_basis()[0].univariate_polynomial()(0))
b = ZZ(-I.groebner_basis()[1].univariate_polynomial()(0))

print(f"a = {a}")
print(f"b = {b}")

计算出a,b后还是一样的思路
$$
\because c \equiv prefix + x_0\times 256^{100} + x_1\times 256^{99} +…+x_{i}\times 256^{100-i} + … +x_{99}\times 256 \mod p
$$

$$
\therefore c-prefix \equiv x_0\times 256^{100} + x_1\times 256^{99} +…+x_{i}\times 256^{100-i} + … +x_{99}\times 256 \mod p
$$

两边同乘a
$$
a(c-prefix) \equiv ax_0\times 256^{100} + ax_1\times 256^{99} +…+ax_{i}\times 256^{100-i} + … +ax_{99}\times 256 \mod p
$$
再依次加上$b\times 256^{100-i}$，$i \in [0,99]$

构造格

记得在最后一列配上大系数

exp

from Crypto.Util.number import *
import gmpy2

p = 2271129678202363707972156644097566224560370806295266873816026779022614695317611229903770390498322537051358521932851893609555063610221
a = 1135564839101181853986078322048783112280185403147633436908013389511307347658805614951885195249161268525679260966425946804777531805110
b = 1135564839101181853986078322048783112280185403147633436908013389511307347658805614951885195249161268525679260966425946804777531805146
c = 244176818026839545554951436126300508547217557099550914232243928051857553603712968234687200629719468115535825237511413058786560692170

prefix = bytes_to_long(b"NSSCTF{") * 256^101 + bytes_to_long(b"}")

c = (c - prefix) % p
c = c*a % p

Ge = Matrix(ZZ,102,102)

T = 2^100
for i in range(100):
    Ge[i,i] = 1
    Ge[i,-1] = 256^(100-i)
    c += b*256^(100-i)
    c %= p
    
Ge[-2,-2] = 1
Ge[-2,-1] = -c
Ge[-1,-1] = p
Ge[:,-1:] *= T

for line in Ge.BKZ(block_size = 16):
    m = ""
    if line[-1] == 0 and abs(line[-2]) == 1:
        print(line)
        for i in line[:-2]:
            if i == 0:
                m += "G"
            if i == -3:
                m += "M"
            if i == 3:
                m += "A"
            if i == 1:
                m += "E"
        flag = "NSSCTF{" + m + "}"
        print(flag)
        # NSSCTF{GEEGEEEMEEMMAAMGGGGEEGMMAMEGGEEEGAGGMEMEMMAMGGGEAAGMGEAAGEMMEEEMGMAAMMGEAAEEEEEGGEMMMMAEGAAAMEMEAEGE}

easy_factor系列

easy_factor1

task.py

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *
from secret import flag

p,q,r = getPrime(256),getPrime(256),getPrime(256)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)

key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
c = enc.encrypt(pad(flag,16))

print("n =",n)
print("hint =",getrandbits(256)*phi**3)
print("c =",c)

'''
n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'
'''

参考官方wp：文章列表 | NSSCTF

题目给出$hint = k\times \phi(n)^3$，$\phi(n) = (p-1)(q-1)(r-1)$

分解$hint$得

2^11 · 3^6 · 7^3 · 13^6 · 41^3 · 79^3 · 83^3 · 277^3 · 248701^3 · 2421845446…11<714>

注意到只含3次方的因子，例如$7^3,41^3$，说明7只可能是$p-1$或$q-1$或$r-1$三个数中一个数的因子，假设他是$p-1$的因子

我们用hint把他除掉有
$$
temp = \frac{hint}{7^3}
$$
此时
$$
temp = k_1\times (q-1)(r-1)
$$
所以
$$
temp = k_1\phi(q\times r)
$$
而
$$
temp \ne k_2\phi(n)
$$
因此$a ^{temp} \equiv 1 \mod q\times r$，其中a是随机一个素数

则$gcd(a^{temp} - 1,n) = q\times r$，有了$q\times r$，相当于有了$p$

再选取不同的小因子求解$q,r$

选择277,248701的时候可以得到另外两个值

exp

from hashlib import sha256
from Crypto.Cipher import AES
import gmpy2

n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'

temp1 = hint // 7**3
qr = gmpy2.gcd(pow(2,temp1,n)-1,n)
p = n // qr
print(p)

temp2 = hint // 277**3
pr = gmpy2.gcd(pow(2,temp2,n)-1,n)
q = n // pr
print(q)

temp3 = hint // 248701**3
pq = gmpy2.gcd(pow(2,temp3,n)-1,n)
r = n // pq
print(r)

key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
flag = enc.decrypt(c)
print(flag)
# b'NSSCTF{Just_simply_try_t0_divid3_s0m3_f4ct0rs_0f_phi}\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'

easy_factor2

task.py

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

m = bytes_to_long(flag)

def gen_prime(bits,common_bits):
    shift = bits - common_bits
    while(True):
        high = ((1<<(common_bits-1)) + getrandbits(common_bits-1)) << shift
        p = high + 2*getrandbits(shift-1) + 1
        q = high + 2*getrandbits(shift-1) + 1
        if(isPrime(p) and isPrime(q)):
            return p,q

p,q = gen_prime(1024,350)
n = p*q
leak = (pow(p,q,n) + pow(q,p,n)) & ((1 << 300) - 1)
e = 65537
c = pow(m,e,n)

print("n =",n)
print("e =",e)
print("c =",c)
print("leak =",leak)

#n = 20304817598463991883487911425007927214135740826150882692657608404060781116387976327509281041677948119173928648751205240686682904704601086882134602075008186227364732648337539221512524800875230120183740426722086488143679856177002068856911689386346260227545638754513723197073169314634515297819111746527980650406024533140966706487847121511407833611739619493873042466218612052791074001203074880497201822723381092411392045694262494838335876154820241827541930328508349759776586915947972105562652406402019214248895741297737940426853122270339018032192731304168659857343755119716209856895953244774989436447915329774815874911183
#e = 65537
#c = 7556587235137470264699910626838724733676624636871243497222431220151475350453511634500082904961419456561498962154902587302652809217390286599510524553544201322937261018961984214725167130840149912862814078259778952625651511254849935498769610746555495241583284505893054142602024818465021302307166854509140774804110453227813731851908572434719069923423995744812007854861031927076844340649660295411912697822452943265295532645300241560020169927024244415625968273457674736848596595931178772842744480816567695738191767924194206059251669256578685972003083109038051149451286043920980235629781296629849866837148736553469654985208
#leak = 1511538174156308717222440773296069138085147882345360632192251847987135518872444058511319064

已知$leak \equiv p^q \mod n + q^p \mod n \equiv p+q$

所以leak是$p+q$的低300位，这个信息可以尝试费马分解法，其原理如下(参考来源:文章列表 | NSSCTF)：
$$
n = p\times q = (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2
$$

$$
令a = \frac{p+q}{2},b = \frac{p-q}{2}
$$

其思想是从$a = \sqrt{n}$开始，逐步增加到$a = \frac{p+q}{2}$，直到发现$a^2-n$是个平方数，也就是$(\frac{p-q}{2})^2$

根据其思想，我们可以发现，费马分解的时间取决于$\frac{p+q}{2}$和$\sqrt{n}$的差值。

本题$p,q$高位相等，会使得$\frac{p+q}{2}$接近$\sqrt{n}$(原因是：$p,q$高位相等使得$p-q$比较小，所以$n = (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$使得$n \approx (\frac{p+q}{2})^2$)

实际测试发现，$\sqrt{n}$和$\frac{p+q}{2}$的大概高700位相等，加上leak的300位，我们只差24位就可以恢复p+q

然后用费马分解法进行分解

exp

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

n = 20304817598463991883487911425007927214135740826150882692657608404060781116387976327509281041677948119173928648751205240686682904704601086882134602075008186227364732648337539221512524800875230120183740426722086488143679856177002068856911689386346260227545638754513723197073169314634515297819111746527980650406024533140966706487847121511407833611739619493873042466218612052791074001203074880497201822723381092411392045694262494838335876154820241827541930328508349759776586915947972105562652406402019214248895741297737940426853122270339018032192731304168659857343755119716209856895953244774989436447915329774815874911183
e = 65537
c = 7556587235137470264699910626838724733676624636871243497222431220151475350453511634500082904961419456561498962154902587302652809217390286599510524553544201322937261018961984214725167130840149912862814078259778952625651511254849935498769610746555495241583284505893054142602024818465021302307166854509140774804110453227813731851908572434719069923423995744812007854861031927076844340649660295411912697822452943265295532645300241560020169927024244415625968273457674736848596595931178772842744480816567695738191767924194206059251669256578685972003083109038051149451286043920980235629781296629849866837148736553469654985208
leak = 1511538174156308717222440773296069138085147882345360632192251847987135518872444058511319064

temp = gmpy2.iroot(n,2)[0]

high = 2 * (int(bin(temp)[2:][:700],2) << 324)

for i in trange(2**25,0,-1):
    p_add_q = high + i*2**300 + leak
    if (p_add_q**2 - 4*n < 0):
        t = gmpy2.iroot(4*n - p_add_q**2,2)
        if t[1]:
            p_sub_q = t[0]
            p = (p_add_q + p_sub_q) // 2
            q = n // p
            d = gmpy2.invert(e,(p-1)*(q-1))
            m = pow(c,d,n)
            print(long_to_bytes(m))
            break
    else:
        t = gmpy2.iroot(p_add_q**2 - 4*n,2)
        if t[1]:
            p_sub_q = t[0]
            p = (p_add_q + p_sub_q) // 2
            q = n // p
            d = gmpy2.invert(e,(p-1)*(q-1))
            m = pow(c,d,n)
            print(long_to_bytes(m))
            break
            # NSSCTF{JUST_@pply_Fermat's_factorization_method_W1tH_Brut3F0rce!}

easy_factor3

task.py

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

def gen_noisy_sum_of_base(m,p):
    sum = 0
    while(m):
        sum += m % p
        m //= p
    return sum//1000

flag = bytes_to_long(flag)
e = 65537
p = getPrime(256)
q = getPrime(256)
n = p*q

m1 = getRandomNBitInteger(2048)
m2 = getRandomNBitInteger(2048)
print("m1 =",m1)
print("m2 =",m2)
print("sum1 =",gen_noisy_sum_of_base(m1,p))
print("sum2 =",gen_noisy_sum_of_base(m2,p))
print("n =",n)
print("c =",pow(flag,e,n))

'''
m1 = 23145761572719481962762273155673006162798724771853359777738044204075205506442533110957905454673168677138390288946164925146182350082798412822843805544411533748092944111577005586562560198883223125408349637392132331590745338744632420471550117436081738053152425051777196723492578868061454261995047266710226954140246577840642938899700421187651113304598644654895965391847939886431779910020514811403672972939220544348355199254228516702386597854501038639792622830084538278039854948584633614251281566284373340450838609257716124253976669362880920166668588411500606044047589369585384869618488029661584962261850614005626269748136
m2 = 21293043264185301689671141081477381397341096454508291834869907694578437286574195450398858995081655892976217341587431170279280993193619462282509529429783481444479483042173879669051228851679105028954444823160427758701176787431760859579559910604299900563680491964215291720468360933456681005593307187729279478018539532102837247060040450789168837047742882484655150731188613373706854145363872001885815654186972492841075619196485090216542847074922791386068648687399184582403554320117303153178588095463812872354300214532980928150374681897550358290689615020883772588218387143725124660254095748926982159934321361143271090861833
sum1 = 309575642078438773208947649750793560438038690144069550000470706236111082406
sum2 = 303394719183577651416751448350927044928060280972644968966068528268042222965
n = 4597063839057338886607228486569583368669829061896475991448013970518668754752831268343529061846220181652766402988715484221563478749446497476462877699249731
c = 3253873276452081483545152055347615580632252871708666807881332670645532929747667442194685757039215506084199053032613562932819745309368748317106660561209205
'''

m可以写成p进制的形式：
$$
m = x_0 + x_1\times p + x_2\times p^2 +…+x_n\times p^n
$$
而$sum = x_0 + x_1 + x_2 +…+x_n$，最后把sum低3位抹去

做减法有
$$
m - sum = x_1(p-1) + x_2(p^2-1) + …+x_n(p^n-1)
$$
易知$p^i-1,(i\ge2)$可以整除$p-1$，所以$m-sum = K(p-1)$

题目给了两组$m$和$sum$，刚好可以求公因数

exp

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


m1 = 23145761572719481962762273155673006162798724771853359777738044204075205506442533110957905454673168677138390288946164925146182350082798412822843805544411533748092944111577005586562560198883223125408349637392132331590745338744632420471550117436081738053152425051777196723492578868061454261995047266710226954140246577840642938899700421187651113304598644654895965391847939886431779910020514811403672972939220544348355199254228516702386597854501038639792622830084538278039854948584633614251281566284373340450838609257716124253976669362880920166668588411500606044047589369585384869618488029661584962261850614005626269748136
m2 = 21293043264185301689671141081477381397341096454508291834869907694578437286574195450398858995081655892976217341587431170279280993193619462282509529429783481444479483042173879669051228851679105028954444823160427758701176787431760859579559910604299900563680491964215291720468360933456681005593307187729279478018539532102837247060040450789168837047742882484655150731188613373706854145363872001885815654186972492841075619196485090216542847074922791386068648687399184582403554320117303153178588095463812872354300214532980928150374681897550358290689615020883772588218387143725124660254095748926982159934321361143271090861833
sum1 = 309575642078438773208947649750793560438038690144069550000470706236111082406
sum2 = 303394719183577651416751448350927044928060280972644968966068528268042222965
n = 4597063839057338886607228486569583368669829061896475991448013970518668754752831268343529061846220181652766402988715484221563478749446497476462877699249731
c = 3253873276452081483545152055347615580632252871708666807881332670645532929747667442194685757039215506084199053032613562932819745309368748317106660561209205

for i,j in tqdm(itertools.product(range(1000),repeat=2)):
    tmp1 = m1 - (sum1 * 1000 + i)
    tmp2 = m2 - (sum2 * 1000 + j)
    p = gmpy2.gcd(tmp1,tmp2) + 1
    if isPrime(p) and int(p).bit_length() == 256:
        q = n // p
        d = gmpy2.invert(65537,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))
        break
        # NSSCTF{M@k3_U53_0F_GCD_beHinD_th3_p-Base!}

easy_NTRU

task.py

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

assert flag.startswith(b"NSSCTF{") and flag.endswith(b"}")
assert b"!!NSSCTF!!" in flag
assert len(flag)==65

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = inverse(f,p) * g % p

print('h =', h)
print('p =', p)

#h = 1756927950546402823211991210884487117388985427696056353000574684529449680817044069252055937789026298359737442776894512901268732373696001068086438971265520
#p = 9154925474221530551204374718472364426110749279786123087256403092166680682021327157348820042798042742469289027059354748716972834115194900518063143041804941

$$
\because h \equiv f^{-1}g \mod p
$$

$$
\therefore g = fh + kp
$$

常规NTRU的格为

规约的目标向量值只能达到256bit，但本题flag有520bit

注意到flag中含有字符NSSCTF{}和!!NSSCTF!!，但!!NSSCTF!!位置不确定

首先处理NSSCTF{}，记prefix = bytes_to_long(b'NSSCTF{') * 256^(58) + bytes_to_long(b'}')

然后处理!!NSSCTF!!，假设!!NSSCTF!!右边有i个不确定字符

那么记suffix = bytes_to_long(b'!!NSSCTF!!') * 256^(i+1)，这里+1是因为末尾的}，i的范围为$(0,47)$

所以flag可以写为
$$
flag = prefix + m_1\times 256^{i+11} + suffix + m_2\times 256
$$
$m_1$的数量级为$256^{47-i}$,$m_2$的数量级为$256^{i}$

记$C = suffix + prefix$

进行配平即可

exp

from Crypto.Util.number import *

h = 1756927950546402823211991210884487117388985427696056353000574684529449680817044069252055937789026298359737442776894512901268732373696001068086438971265520
p = 9154925474221530551204374718472364426110749279786123087256403092166680682021327157348820042798042742469289027059354748716972834115194900518063143041804941

prefix = bytes_to_long(b"NSSCTF{")*256^(58) + bytes_to_long(b"}")

for i in range(48):
    suffix = bytes_to_long(b"!!NSSCTF!!")*256^(i+1)
    C = (prefix + suffix) * h
    T = 2^(377 - 128)
    T1 = 256^i
    T2 = 256^(47-i)
    Ge = Matrix(ZZ,[
        [T1,0,0,256^(i+11)*h*T],
        [0,T2,0,256*h*T],
        [0,0,256^47,C*T],
        [0,0,0,p*T]
    ])
    
    line = Ge.LLL()[0]
    m1 = abs(line[0]) // T1
    m2 = abs(line[1]) // T2
    flag = prefix + m1 * 256^(i+11) + suffix + m2 * 256
    print(long_to_bytes(int(flag)))
    # NSSCTF{Task_1s_to_FinD_where_th3_!!NSSCTF!!_IS_in_thi5_FLAGHhah!}

思路并不难，重点在于对字节转整形的细节把控以及flag其实是对几段字符的拼接，把握好flag那个等式就清晰了，然后就是配平目标向量。

easy_copper1

旧附件

task.py

from Crypto.Util.number import *
from random import *
from secret import flag

assert flag.startswith(b"NSSCTF{") and flag.endswith(b"}")
assert len(flag) == 37

def gen_data(p,length):
    coeff = [randint(-2**32,2**32) for i in range(length-1)] + [randint(1,2**32)]
    return sum([coeff[i]*p**i for i in range(length)])

b = getPrime(1400)
a = gen_data(b,6)
p = getPrime(256*5)
q = getPrime(256)
n = p
m = bytes_to_long(flag[7:-1])

print("a =",a)
print("b =",b)
print("n =",n)
print("c =",a % (b-m) % p)


'''
a = 29089145861698849533587576973295257566874181013683093409280511461881508560043226639624028591697075777027609041083214241167067154846780379410457325384136774173540880680703437648293957784878985818376432013647415210955529162712672841319668120257447461567038004250028029752246949587461150846214998661348798142220559280403267581983191669260262076357617420472179861844334505141503479938585740507007167412328247901645653025038188426412803561167311075415186139406418297360055617953651023218144335111178729068397052382593835592142212067930715544738880011596139654527770961911784544010189290315677772431190278256579916333137165255075163459126978209678330136547554839703581615386678643718339211024128344190549574517564644382447611744798875041346881354781693931986615205673317996958906543168487424513288646586386898335386252942417294351991435595389041536593887748040184886941013614961741810729168951559211294246606230105751075721451317188926451002620849423314518170658209171671914315184519999959495351937563075042077266900864146159426562183965523296477064353921084645981585062809887031916148806349242025315612913825933164149679421566262446757892475611986630543538188150542432463200651189833933982458007114429715435568714619661080138790893459960671301328455259702189597680258358027148120577359065875450633562059381985788036798654456426180261922908112060328808638698523351620789566317389045953829508142189900185007810978556531031234520426854056485675147172190502028351264431318960694075186507102430581156550179324060430995652420952731818727684039692796018771140481392835706804763480391403219506727895338895364591606497253163676677638669786786858737497920439433198267927890300667623673919500396414839378381934354516285899285278671196050670328000271445003863863854641343057226519772851093922041622949244909881042639419520750870739146022239848882362576253955639971615811326995401478442990402656532205515168792715334542129193521733882886780427236290633270965571593377055933030570964314193668632743086843644521712276882644432083012275643889490106050284317873072564495246844741833922331897169054478543498374111011001360629887265387016903
b = 23842135454777432891743223391138265563241799870175456642327123278749657522050965688647025271946838603033997215457359121062031090678062337376719430593135764515364544052891212988546634081941717578522276652565205405071925932782899189391582928430745625545751168223235578140422316604775465116636679365817463642606682382103650151553859378443311951637645862682606805670610169631771916714125895199501221576523042203542953632992797
n = 11325979084644128572298911896847368512066889699114922766957825496829789701040409280284912163337390977205935027654824418075908113980923567819511384456223871894254826496727684822147076089401320253972280078822901143659851738555573580052473815798989309369428595758953805619194262607259107358103749807085316873971927412767250429330952340169403993890298557816024130952523480708504075717017477
c = 91637278981727419311704062766528605893241365739887714388981571071807672497690225964001055671982318124750997320763003521883860470498708606433206468782382765369836856610266602374015551078759628514665188339252922366320922478645026704734702460355236791287112842409076450962765866362852307351865564192898522584768904066046337899302561685937649000409332117647123
'''

$$
a = coeff_0\times b^0 + coeff_1\times b^1 + coeff_2\times b^2 + coeff_3\times b^3 + coeff_4\times b^4 + coeff_5 \times b^5
$$

参考鸡块师傅的思路：文章列表 | NSSCTF

首先把a模掉b
$$
coeff_0 = a \mod b
$$
然后
$$
a_1 = \frac{a-coeff_0}{b} = coeff_1 + coeff_2\times b + coeff_3\times b^2 + coeff_4\times b^3 + coeff_5 \times b^4
$$

$$
coeff_1 = a_1 \mod b
$$

同理即可求出所有$coeff_i$
$$
c \equiv (a \mod (b-m)) \mod p
$$
我们先不考虑mod p，有
$$
c \equiv a \mod b-m
$$

$$
c \equiv coeff_0\times b^0 + coeff_1\times b^1 + coeff_2\times b^2 + coeff_3\times b^3 + coeff_4\times b^4 + coeff_5 \times b^5 \mod b - m
$$

根据上面计算的$a_i$，可以把c写为
$$
c \equiv a_1b + coeff_0 \equiv a_1(b-m) + a_1m + coeff_0 \equiv a_1m + coeff_0 \mod b-m
$$
再把$a_1$写为如下形式
$$
a_1 \equiv a_2b + coeff_1 \equiv a_2(b-m) + a_2m + coeff_1 \equiv a_2m+coeff_1 \mod b - m
$$
这个时候$c \equiv (a_2m+coeff_1)m + coeff_0$

由此迭代下去有
$$
c \equiv (((((a_6m+coeff_5)m+coeff_4)m+coeff_3)m+coeff_2)m+coeff_1)m + coeff_0
$$
$a_6$其实是0

所以$c \equiv ((((coeff_5m+coeff_4)m+coeff_3)m+coeff_2)m + coeff_1)m+coeff_0 \mod b-m$

最后在模p下解这个方程，这里应该是鸡块师傅失误了直接n = p，按理说应该是n = p * q，所以直接用$f.roots()$函数就能出

Exp

from Crypto.Util.number import *

a = 29089145861698849533587576973295257566874181013683093409280511461881508560043226639624028591697075777027609041083214241167067154846780379410457325384136774173540880680703437648293957784878985818376432013647415210955529162712672841319668120257447461567038004250028029752246949587461150846214998661348798142220559280403267581983191669260262076357617420472179861844334505141503479938585740507007167412328247901645653025038188426412803561167311075415186139406418297360055617953651023218144335111178729068397052382593835592142212067930715544738880011596139654527770961911784544010189290315677772431190278256579916333137165255075163459126978209678330136547554839703581615386678643718339211024128344190549574517564644382447611744798875041346881354781693931986615205673317996958906543168487424513288646586386898335386252942417294351991435595389041536593887748040184886941013614961741810729168951559211294246606230105751075721451317188926451002620849423314518170658209171671914315184519999959495351937563075042077266900864146159426562183965523296477064353921084645981585062809887031916148806349242025315612913825933164149679421566262446757892475611986630543538188150542432463200651189833933982458007114429715435568714619661080138790893459960671301328455259702189597680258358027148120577359065875450633562059381985788036798654456426180261922908112060328808638698523351620789566317389045953829508142189900185007810978556531031234520426854056485675147172190502028351264431318960694075186507102430581156550179324060430995652420952731818727684039692796018771140481392835706804763480391403219506727895338895364591606497253163676677638669786786858737497920439433198267927890300667623673919500396414839378381934354516285899285278671196050670328000271445003863863854641343057226519772851093922041622949244909881042639419520750870739146022239848882362576253955639971615811326995401478442990402656532205515168792715334542129193521733882886780427236290633270965571593377055933030570964314193668632743086843644521712276882644432083012275643889490106050284317873072564495246844741833922331897169054478543498374111011001360629887265387016903
b = 23842135454777432891743223391138265563241799870175456642327123278749657522050965688647025271946838603033997215457359121062031090678062337376719430593135764515364544052891212988546634081941717578522276652565205405071925932782899189391582928430745625545751168223235578140422316604775465116636679365817463642606682382103650151553859378443311951637645862682606805670610169631771916714125895199501221576523042203542953632992797
n = 11325979084644128572298911896847368512066889699114922766957825496829789701040409280284912163337390977205935027654824418075908113980923567819511384456223871894254826496727684822147076089401320253972280078822901143659851738555573580052473815798989309369428595758953805619194262607259107358103749807085316873971927412767250429330952340169403993890298557816024130952523480708504075717017477
c = 91637278981727419311704062766528605893241365739887714388981571071807672497690225964001055671982318124750997320763003521883860470498708606433206468782382765369836856610266602374015551078759628514665188339252922366320922478645026704734702460355236791287112842409076450962765866362852307351865564192898522584768904066046337899302561685937649000409332117647123

tempa = a
coeff = []
A = []
for i in range(6):
    temp = tempa % b
    if int(temp).bit_length() > 32:
        k = temp - b
        coeff.append(k)
    else:
        k = temp
        coeff.append(k)
    tempa = (tempa - coeff[i]) // b
    A.append(tempa)

# print(coeff)

# mayA = sum([coeff[i]*b**i for i in range(6)])
# assert(mayA == a)

R.<m> = PolynomialRing(Zmod(n))
f = (((((coeff[5]*m + coeff[4])*m + coeff[3])*m + coeff[2])*m + coeff[1])*m + coeff[0]) - c
res = f.roots()
# print(res)
for i in res:
    plain = long_to_bytes(int(i[0]))
    flag = b"NSSCTF{" + plain + b"}"
    print(flag)
    # NSSCTF{F1nd_4_M3th0d_70_COPPER5m1th!}

新附件

task.py

from Crypto.Util.number import *
from random import *
from secret import flag

assert flag.startswith(b"NSSCTF{") and flag.endswith(b"}")
assert len(flag) == 37

def gen_data(p,length):
    coeff = [randint(-2**32,2**32) for i in range(length-1)] + [randint(1,2**32)]
    return sum([coeff[i]*p**i for i in range(length)])

b = getPrime(1400)
a = gen_data(b,6)
p = getPrime(256*5)
q = getPrime(256)
n = p*q
m = bytes_to_long(flag[7:-1])

print("a =",a)
print("b =",b)
print("n =",n)
print("c =",a % (b-m) % p)


'''
a = 5549997533567190765451060003378594328208085965171057613046272782399320385801262427125465925310587069826816190505343998268891453664853919954972318043604177749860432778530185933735996050024160286370510179686746394158379258246587487978911503057556662561587215910791569507689015766531668277131113986057590781396398336299292315557904756600303993655014781202374308079885517355500419820878630803963625154724593589268277135757575099029314373537333985928427361897778453968429622806601778705482232467565493789524705788745221275426482603133790789320192127238641529684801868328091692081269798378555677980295282241736002111769899269365161305274768242912746034221266737507823710607682307448305506469386320122162063129111963956813928790055972563594890074229166442357508298255754150913934863439503751818506701092029312330070104636530223422238884679342877228773018649571938389437053258838947075103547766682006907290041060099030401078504154580918834901230411520541473984503892569919351799880236285333890681120340758177935223362561618860440679402085624994947954310720781671847323988290985994849577007330168617301104973145130975458942852068773890456852008660678772797081769299221752824132395057925957966236190693386264986627705062247274388532481890731361579962994281795847973719352965725024336536011747744286094626784548450945808977185031072003163884715639335582500821735372264778337277968982744615544014751382104123657815885683865159874330848264901320900587726777026680111663529893241507534145907710815328515080873983547987954554660585289621642017226020909406358582195295944513518489513783744170261194300084082634297086645338918551616443632828664857206551814971287007726341429714596407033649324399745531577851802389713905682407743356548494218886990858323750912334486066574949941863337284447418868362349705104596997062541665923824132293441261853623963153677146052741893849156220411360012198280306111549261407941431691085949136294791896025980996617245031309439043593114299292206028201810212469726512376109348231607843056259556121448353511032010729667364764526544162088652166231118576736952880650975321889920727908566750809108688218503956
b = 19088700216864219992000481909154962955010217153589993304722719340884054355376558326105036947257582728860147557431276912919643940358478125733042829478349114754313750607492935206321298801011776939307313478546331523512938761672813983870399597182080005906066953602228332948790458576153448761425614070248334986663583719133564252378947422392557755444674008030141846366476287826338519233008704965899055639264609925259823048079319
n = 1698281899194715114165111012319277103359733674717346894156321734086384210027912893592223341535254583183189375047805019470712423207121454213625786296403115965465797639874678119529865412063714723513964182015925137173277042639307327631371055326412204990172328114832185024332076266014268385262996787504249248741895102659976146333218908476195041388126877183421158327681480273218635257896126985050902620483850502219753728842322424353423665711001628722961510508066740039
c = 53146904354859601599585110457067111012858829248246133531123405294986679458995718625053726629192021849150034273282207940006128865030953003797480171720673649060942787124637476440400908506795533118278613492356804275358218541297790334587524059713360959881377651255593428483947657195937373058321156413003347566693680573881827047037751088091600420762361729539354
'''

一样的思路，只不过最后不能直接用f.roots()函数，需要用small_roots

exp

from Crypto.Util.number import *

a = 5549997533567190765451060003378594328208085965171057613046272782399320385801262427125465925310587069826816190505343998268891453664853919954972318043604177749860432778530185933735996050024160286370510179686746394158379258246587487978911503057556662561587215910791569507689015766531668277131113986057590781396398336299292315557904756600303993655014781202374308079885517355500419820878630803963625154724593589268277135757575099029314373537333985928427361897778453968429622806601778705482232467565493789524705788745221275426482603133790789320192127238641529684801868328091692081269798378555677980295282241736002111769899269365161305274768242912746034221266737507823710607682307448305506469386320122162063129111963956813928790055972563594890074229166442357508298255754150913934863439503751818506701092029312330070104636530223422238884679342877228773018649571938389437053258838947075103547766682006907290041060099030401078504154580918834901230411520541473984503892569919351799880236285333890681120340758177935223362561618860440679402085624994947954310720781671847323988290985994849577007330168617301104973145130975458942852068773890456852008660678772797081769299221752824132395057925957966236190693386264986627705062247274388532481890731361579962994281795847973719352965725024336536011747744286094626784548450945808977185031072003163884715639335582500821735372264778337277968982744615544014751382104123657815885683865159874330848264901320900587726777026680111663529893241507534145907710815328515080873983547987954554660585289621642017226020909406358582195295944513518489513783744170261194300084082634297086645338918551616443632828664857206551814971287007726341429714596407033649324399745531577851802389713905682407743356548494218886990858323750912334486066574949941863337284447418868362349705104596997062541665923824132293441261853623963153677146052741893849156220411360012198280306111549261407941431691085949136294791896025980996617245031309439043593114299292206028201810212469726512376109348231607843056259556121448353511032010729667364764526544162088652166231118576736952880650975321889920727908566750809108688218503956
b = 19088700216864219992000481909154962955010217153589993304722719340884054355376558326105036947257582728860147557431276912919643940358478125733042829478349114754313750607492935206321298801011776939307313478546331523512938761672813983870399597182080005906066953602228332948790458576153448761425614070248334986663583719133564252378947422392557755444674008030141846366476287826338519233008704965899055639264609925259823048079319
n = 1698281899194715114165111012319277103359733674717346894156321734086384210027912893592223341535254583183189375047805019470712423207121454213625786296403115965465797639874678119529865412063714723513964182015925137173277042639307327631371055326412204990172328114832185024332076266014268385262996787504249248741895102659976146333218908476195041388126877183421158327681480273218635257896126985050902620483850502219753728842322424353423665711001628722961510508066740039
c = 53146904354859601599585110457067111012858829248246133531123405294986679458995718625053726629192021849150034273282207940006128865030953003797480171720673649060942787124637476440400908506795533118278613492356804275358218541297790334587524059713360959881377651255593428483947657195937373058321156413003347566693680573881827047037751088091600420762361729539354

tempa = a
coeff = []
A = []
for i in range(6):
    temp = tempa % b
    if int(temp).bit_length() > 32:
        k = temp - b
        coeff.append(k)
    else:
        k = temp
        coeff.append(k)
    tempa = (tempa - coeff[i]) // b
    A.append(tempa)

# print(coeff)

# mayA = sum([coeff[i]*b**i for i in range(6)])
# assert(mayA == a)

R.<m> = PolynomialRing(Zmod(n))
f = (((((coeff[5]*m + coeff[4])*m + coeff[3])*m + coeff[2])*m + coeff[1])*m + coeff[0]) - c
res = f.monic().small_roots(X=2^232)
# print(res)
for i in res:
    plain = long_to_bytes(int(i))
    flag = b"NSSCTF{" + plain + b"}"
    print(flag)
    # NSSCTF{F1nd_4_M3th0d_70_COPPER5m1th!}

New

task.py

from Crypto.Util.number import *
from random import *
from secret import flag

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = getPrime(64)
y = randint(1,n-1)

enc1 = (2*m-y) % n
enc2 = (pow(m,77797,n) + pow(y,99979,n)) % n
enc3 = pow(m,e,n)

print("n =",n)
print("e =",e)
print("enc1 =",enc1)
print("enc2 =",enc2)
print("enc3 =",enc3)

'''
n = 76872387040750711481695319401891869626298496663646007263288276139803465174191619475578815032952443203999946699619608754927636370391246490295956452060825811360926535639727959065085635402043793275726052846175221486805222409683084378230128154083002112846152190212694232389840072355634181701857657577960411085259
e = 14517388807167131843
enc1 = 19213647953546586813751931693460486705316820636833688608407262969993305550190515799445697110862170481321445758341265947662491571281415560933543802686341056655845941023814132630911172219968724648296386656509780411068123126907152609816769183723220406500826584521854091009068387452960067689901073297355379376650
enc2 = 41309784323401556509919411158619675494401312743968664871351005321825946336419346171729550397729015447843446439316783536928978720667483042894083901161351778024546449398408687548988372884497056689076401193266593308119390079388063732765647979034151645849711498507121333352813347722601858039222174242024754526177
enc3 = 40215346797451341366110429565410506405087881188979429246210656472049768863342867107822157793213647190781259031396522353468032932444111047062331098663770863899989642120510241978959999422946056719571060584302019946120565256634031773214192658744910338839324078360060011146756744005062513730484541461016184938685
'''

第一反应是相关消息攻击，从enc1 = (2*m - y) % n可知$y \equiv 2m - enc_1 \mod n$，以及
$$
g = enc_2 \equiv m^{77797} + (2m - enc_1)^{99979} \mod n
$$

$$
f = enc_3 \equiv m^e \mod n
$$

因为e比较大，直接用拿$f,g$相关消息攻击是不可的。

因为$(f,g) = (g,f \mod g)$，我们可以构造模g的商环来求得$f \mod g$，然后再用$g,f \mod g$相关消息攻击

exp

from Crypto.Util.number import *
import sys

sys.setrecursionlimit(500000)

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

n = 76872387040750711481695319401891869626298496663646007263288276139803465174191619475578815032952443203999946699619608754927636370391246490295956452060825811360926535639727959065085635402043793275726052846175221486805222409683084378230128154083002112846152190212694232389840072355634181701857657577960411085259
e = 14517388807167131843
enc1 = 19213647953546586813751931693460486705316820636833688608407262969993305550190515799445697110862170481321445758341265947662491571281415560933543802686341056655845941023814132630911172219968724648296386656509780411068123126907152609816769183723220406500826584521854091009068387452960067689901073297355379376650
enc2 = 41309784323401556509919411158619675494401312743968664871351005321825946336419346171729550397729015447843446439316783536928978720667483042894083901161351778024546449398408687548988372884497056689076401193266593308119390079388063732765647979034151645849711498507121333352813347722601858039222174242024754526177
enc3 = 40215346797451341366110429565410506405087881188979429246210656472049768863342867107822157793213647190781259031396522353468032932444111047062331098663770863899989642120510241978959999422946056719571060584302019946120565256634031773214192658744910338839324078360060011146756744005062513730484541461016184938685

R.<x> = PolynomialRing(Zmod(n))
g = x^77797 + (2*x - enc1)^99979 - enc2
PR.<y> = R.quotient(g)

h = y^e - enc3
f = h.lift()

res = GCD(f,g)
m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)
# H&NCTF{Rem0Ve_y_4nD_C0mb1n3_HGCD_4nD_Euclid}

最后要用lift函数，把商环下的元素提升到原始环中的元素，再HGCD