2024-NSSCTF-密码工坊非官方dlc-wp-crypto

那天在NSS的工坊群里，看见群友聊天刚好聊到了一个和我出的题目很类似的问题，就突发奇想开个坑，把自己想到的一些题目整合一下，当成NSS密码工坊的扩展包，给一些需要的工坊群友当练习题用。

题目内容都是基于已有工坊内容的变形，不会有缺少基本知识这样的问题，主要是拓展一点思路和巩固一下操作，从难度上来说都比较基础。

缓慢更新中。

easy_mod 系列(已完结)

总体介绍：

整个easy_mod系列其实都基于以下问题的求解：

$$c = m \quad(mod\;p)$$

其中m大于p，且大于的较多所以没办法爆破求解。同时还有一个相同点，就是m均具有一定特殊性。

easy_mod

题目：

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的特殊性在于：除了NSSCTF{}组成的前后缀以外，仅由0-7的数字拼接而成，一共有70个数字。

那么思路首先肯定是把前后缀给去掉，从而减小明文数量级。由字节转数字的方式可以知道m其实可以写成如下形式(其中pre指”NSSCTF{“，suf指”}”，m0就是中间的长为70数字串)：

$$m = 256^{71}pre + 256m_0 + suf$$

那么就有：

$$c = (256^{71}pre + 256m_0 + suf) \quad(mod\;p)$$

就可以得到m0模p的值：

$$m_0 = 256^{-1}(c - 256^{71}pre - suf) \quad(mod\;p)$$

接下来的问题是如何利用m0的特殊性去求解他，由于m0仅由0-7的数字组成，用ASCII码的角度去看就是48-53，所以一个很自然的思路是把m0写成如下形式(记m0的每个字节值为si)：

$$m_0 = \sum_{i=0}^{69}256^is_i =s_0 + 256s_1 + 256^2s^2 + ... + 256^{69}s^{69} \quad (mod\;p)$$

那么可以写成一个等式即：

$$m_0 = \sum_{i=0}^{69}256^is_i + kp$$

这个等式就给造格提供了一个依据，可以造出如下格：

$$\left(\begin{matrix} 1 &&& &&1\\ &1&& &&256\\ &&\ddots& &&\vdots\\ &&&1 &&256^{69}\\ &&& &1&-m_0\\ &&& &&p\\ \end{matrix}\right)$$

具有的线性关系是：

$$(s_0,s_1,...,s_{69},1,k) \left(\begin{matrix} 1 &&& &&1\\ &1&& &&256\\ &&\ddots& &&\vdots\\ &&&1 &&256^{69}\\ &&& &1&-m_0\\ &&& &&p\\ \end{matrix}\right) = (s_0,s_1,...,s_{69},1,0)$$

那么如果界符合的话，用这个等式去造格，规约出来的向量预期应该是由48-53的一系列值组成的短向量，但一做就知道这样并不能得到预期结果。

然后一个朴素的优化想法就是，不妨新令一组变量：

$$t_i = s_i - 48$$

那么就可以将刚才的等式做如下处理：

$$m_0 = \sum_{i=0}^{69}256^i(t_i+48) \quad(mod\;p)$$

那么减去48(也就是0对应的ASCII码值)之后，预期规约出的向量就都变成了0-7的短向量，机会就大很多。并且由于48与256^i的乘积都可以计算，所以可以仅处理上面格中的m0项而不需要改动其他地方，也就是：

$$m_1 = m_0 - 48\sum_{i=0}^{69}256^i$$

此时造格的等式为：

$$m_1 = \sum_{i=0}^{69}256^it_i + kp$$

然后是做一些老生常谈的使格规约本身更有利的一些优化，比如说，现在目标向量为：

$$(t_0,t_1,...,t_{69},1,0)$$

为了保证规约出0，就要给格的最后一列配上个大系数。同时，ti的取值为0-7，也就是说平均值在3、4左右，因此给倒数第二列配上个3、4能使目标向量中值的数量级更加接近。

exp：

from Crypto.Util.number import *


p = 501785758961383005891491265699612686883993041794260611346802080899615437298977076093878384543577171
c = 327005346153237517234971706274055111857447948791422192829214537757745905845319188257204611848165263
prefix = b"NSSCTF{"
suffix = b"}"
length = 78 - len(prefix) - len(suffix)

#part1 remove prefix and suffix
c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
c -= bytes_to_long(suffix)
c = c * inverse(256,p) % p

L = Matrix(ZZ,length+2,length+2)
for i in range(length):
    L[i,i] = 1
    L[i,-1] = 256^i
    c -= 256^i*48

L[-2,-2] = 4
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()
flag = ""
for i in res[:-1]:
    if(abs(i[-2]) == 4 and all(abs(j) < 8 for j in i[:-2])):
        for j in i[:-2][::-1]:
            flag += chr(48 + abs(j))
print(flag)


#NSSCTF{5036541772751046406531362142757356307107252723754051320011253505562041}

easy_mod2

题目：

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
'''

和mod1唯一的区别就是，m0的长度变成了80。而不调blocksize等参数/不爆破一些字节的话，可以测试出70就是上一个题目的极限了，因此本题的预期是想展示一种更优的构造。

而更优的构造思路也很简单，注意到上题是新令了如下一组变量，使得48-53的目标向量变到了0-7：

$$t_i = s_i - 48$$

而其实仅仅改动这个48，改成52，就可以使得目标向量变到-4到3这个更小的数量级了，格的构造和上一题没有任何区别。

需要注意的一小点是，这一题倒数第二列不再需要配3或4，因为目标向量的值已经在-4到3这个范围里了，所以平均差不多在-1，所以就配1就很合理。

exp：

from Crypto.Util.number import *


p = 324556397741108806830285502585098109678766437252172614832253074632331911859471735318636292671562523
c = 141624663734155235543198856069652171779130720945875442624943917912062658275440028763836569215230250

prefix = b"NSSCTF{"
suffix = b"}"
length = 88 - len(prefix) - len(suffix)

#part1 remove prefix and suffix
c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
c -= bytes_to_long(suffix)
c = c * inverse(256,p) % p

L = Matrix(ZZ,length+2,length+2)
for i in range(length):
    L[i,i] = 1
    L[i,-1] = 256^i
    c -= 256^i*48
    c -= 256^i*3

L[-2,-2] = 1
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()

flag = ""
for i in res[:-1]:
    if(all(abs(j) <= 4 for j in i[:-2])):
        if(i[-2] == 1):
            for j in i[:-2][::-1]:
                flag += chr(48 + 3 + j)
        else:
            for j in i[:-2][::-1]:
                flag += chr(48 + 3 - j)
if(flag != ""):
    print(flag)

#NSSCTF{25350625451533421162474265547571536103420331260232652121722452361537257541460235}

easy_mod3

题目：

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
'''

这题相比于前面的题目有两处改动：

• table仅有N和s两种值
• 长度增加到100

既然又增加了明文串的长度，那么不考虑调参/爆破的情况下，自然规约出的向量中的值要比前面两问更小才行。而由于只有两种值，所以也很容易将他与背包问题里的0、1联系起来。所以本题的核心思路在于：如何将N和s转化为0、1？

由于N的ASCII码值为78，而s为115，所以我们不妨新令一组变量为：

$$t_i = s_i - 78$$

那么再回看上面的式子：

$$m_0 = \sum_{i=0}^{99}256^is_i \quad(mod\;p)$$

就有：

$$m_0 = \sum_{i=0}^{99}256^i(t_i+78) \quad(mod\;p)$$

然后做类似的处理，把所有78移到等式左侧去得到m1，就有：

$$m_1 = \sum_{i=0}^{99}256^it_i \quad(mod\;p)$$

现在的问题是ti由0和37(115-78)组成，离我们预想的0、1还有点差距。但处理方法也很简单，只需要做个如下的变换即可：

$$37^{-1}m_1 = \sum_{i=0}^{99}256^i(37^{-1}t_i) \quad(mod\;p)$$

此时规约出来的就是0、1向量了，格的构造和前面并没有大的区别，依然仅需要修改m0那个位置的值。

exp：

from Crypto.Util.number import *

p = 421384892562377694077340767015240048728671794320496268132504965422627021346504549648945043590200571
c = 273111533929258227142700975315635731051782710899867431150541189647916512765137757827512121549727178

a = inverse(ord("s")-ord("N"),p)

prefix = b"NSSCTF{"
suffix = b"}"
length = 108 - len(prefix) - len(suffix)

#part1 remove prefix and suffix
c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
c -= bytes_to_long(suffix)
c = c * inverse(256,p) % p

L = Matrix(ZZ,length+2,length+2)
for i in range(length):
    L[i,i] = 1
    L[i,-1] = 256^i
    c -= 256^i*78
    c %= p
c = a*c % p

L[-2,-2] = 1
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()

flag1 = "NSSCTF{"
flag2 = "NSSCTF{"
for i in res[:-1]:
    if(all(abs(j) <= 1 for j in i[:-2])):
        for j in i[:-2][::-1]:
            if(abs(j) == 1):
                flag1 += "N"
                flag2 += "s"
            else:
                flag1 += "s"
                flag2 += "N"
flag1 += "}"
flag2 += "}"

if(bytes_to_long(flag1.encode()) % p == 273111533929258227142700975315635731051782710899867431150541189647916512765137757827512121549727178):
    print(flag1)
elif(bytes_to_long(flag2.encode()) % p == 273111533929258227142700975315635731051782710899867431150541189647916512765137757827512121549727178):
    print(flag2)


#NSSCTF{NNNssNsNNNNsNNNsNNNNNssNNNssNNNsNsNNsNsNNssNNNNNNsNNNssNsNNNNNssNssssNsNNsNsssNNNNssNNNssNsNNssNsNss}

easy_mod_final

原附件为：

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
'''

题目：

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
'''

两个题目本质上解法是没有区别的，只是想了想四个题还是统一队形更美观，所以修改了一下附件。

题目的核心trick和mod3其实一致，回看mod3，我们是找到了一种方法，将N,s的ASCII码值，也就是78、115，分别对应到了0、1，从而减小了目标向量的数量级。而现在值变成了G、A、M、E四个，似乎好像不那么好处理了。

此时就要提取一下把78、115变到0、1的本质，这其实是一个线性变换，也就是：

$$y = ax + b \quad(mod\;p)$$

而(78,0)、(115,1)是这个直线上的两个点，因此可以唯一确定a、b，确定了a、b后就可以对格的各个数值也进行相应的线性变换处理(详见mod3)，从而使目标向量规约出0、1来。

那么对于final这个题目，我们的根本目的也就可以抽象成：找到一个线性变换，使得GAME四个字母均在这条直线上，并且纵坐标均很小，从而可以规约。

但是由于两点就确定了一条直线，所以随意取纵坐标的话似乎很难恰好满足四点共线(不过就单对于这题来说不存在，因为你知道要变到比较小的值，所以可以在0附近的小数字爆破纵坐标来检查共线)。因此，一个合理的办法是检查这四个点横坐标之间的关系来确定线性变换的差值。

听上去可能有点抽象，不妨就以GAME这四个字母展开，我们把他们按顺序排列为A、E、G、M，其ASCII码差值分别为4、2、6，因此一定可以找到一个变换，使得依次排列的四个点，纵坐标差值的比例为2：1：3。

这是为什么呢？可以把四个点在直线上的方程先写出来：

$$y_1 = ax_1 + b \quad(mod\;p)$$ $$y_2 = ax_2 + b \quad(mod\;p)$$ $$y_3 = ax_3 + b \quad(mod\;p)$$ $$y_4 = ax_4 + b \quad(mod\;p)$$

两两作差就有：

$$y_1 - y_2 = a(x_1 - x_2) \quad(mod\;p)$$ $$y_2 - y_3 = a(x_2 - x_3) \quad(mod\;p)$$ $$y_3 - y_4 = a(x_3 - x_4) \quad(mod\;p)$$

纵坐标差值的比例等于横坐标差值的比例，也就是2：1：3。而在此基础上我们可以任意选择最满足规约要求的两个基准点来确定直线，与此同时就能确定另外两点的纵坐标。

比如这题，我们就可以选择(G,0)、(E,1)为两个基准点来确定线性变换，然后就得到另外两个点(A,3)、(M,-3)，此时对格做mod3类似的处理，预期就可以规约出全部由3、1、0、-3组成的短向量了。

exp：

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


p = 2271129678202363707972156644097566224560370806295266873816026779022614695317611229903770390498322537051358521932851893609555063610221
c = 244176818026839545554951436126300508547217557099550914232243928051857553603712968234687200629719468115535825237511413058786560692170
table = [ord(i) for i in "AEGM"]

#part1 linear transformation and remove prefix and suffix
a = 1 * inverse(table[1]-table[2],p)
b = (1 - a*table[1]) % p
prefix = b"NSSCTF{"
suffix = b"}"
length = 108 - len(prefix) - len(suffix)
c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
c -= bytes_to_long(suffix)
c = c * inverse(256,p) % p
c = a*c % p

#part2 BKZ

L = Matrix(ZZ,length+2,length+2)
for i in range(length):
    L[i,i] = 1
    L[i,-1] = 256^i
    c += 256^i*b
    c %= p

L[-2,-2] = 1
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()

flag = ""
for i in res[:-1]:
    if(all(abs(j) <= 3 for j in i[:-2])):
        if(1 in i):
            for j in i[:-2][::-1]:
                if(j == 1):
                    flag += "E"
                elif(j == 3):
                    flag += "A"
                elif(j == 0):
                    flag += "G"
                else:
                    flag += "M"
        else:
            for j in i[:-2][::-1]:
                if(j == -1):
                    flag += "E"
                elif(j == -3):
                    flag += "A"
                elif(j == 0):
                    flag += "G"
                else:
                    flag += "M"
print(flag)


#NSSCTF{GEEGEEEMEEMMAAMGGGGEEGMMAMEGGEEEGAGGMEMEMMAMGGGEAAGMGEAAGEMMEEEMGMAAMMGEAAEEEEEGGEMMMMAEGAAAMEMEAEGE}

easy_copper 系列

总体介绍：该系列基于coppersmith求解小根的一些综合运用。

easy_copper1

题目：

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
'''

题目流程为：

• 生成一个1400bit的素数b
• 生成数字a，其满足：

$$a = k_0 + k_1b + k_2b^2 + k_3b^3 + k_4b^4 + k_5b^5$$

• 其中ki均是-2^32到2^32的值
• 生成256*5bit的素数p以及256bit的素数q，记其乘积为n
• 给出密文值c：

$$a \quad(mod\;b-m) \quad(mod\;p)$$

要求还原明文m。

最大的问题在于，由于并不知道m的值，所以模b-m这一步看上去相当难处理。然而，如果注意到a的特殊性可能就会有进一步的思路。由于a是由b构成的多项式且系数均较小，所以我们可以得到一个结论就是：

• 反复进行如下操作，得到的余数t应该均较小(这里需要注意一点对于负数ki调整的细节)：

t = a % b
a = a // b

那么我们展开一下a模b-m，其实可以看成是进行如下操作：

$$a = s_0b + t_0 = s_0(b-m) + s_0m + t_0$$ $$\rightarrow a = s_0m + t_0 \quad(mod\;b-m)$$

而其中s0、t0都是可以求的，因为实质上只是对a进行一个带余除法得到的商和余数，并且由a的组成可以知道我们可以保持t0为-2^32到2^32的值。那么接下来，我们再继续模：

$$s_0 = s_1b + t_1 = s_1(b-m) + s_1m + t_1$$ $$\rightarrow s_0m + t_0 = (s_1m + t_1)m + t_0 \quad(mod\;b-m)$$

可以发现，如此反复进行下去，最后展开得到的就是a对应的b组成的多项式，只是现在由m组成：

$$f(m) = k_0 + k_1m + k_2m^2 + k_3m^3 + k_4m^4 + k_5m^5$$

由于k5为1-2^32之间的数，flag本身去掉前后缀只有29字节，所以fm的最大值一定小于b-m(约为1400bit)，因此模b-m到这里就可以去掉了，现在就变成：

$$c = k_0 + k_1m + k_2m^2 + k_3m^3 + k_4m^4 + k_5m^5 \quad(mod\;p)$$

所以copper求这个多项式的小根就可以了。

exp：

from Crypto.Util.number import *

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

k1 = a // b
a1 = a % b
K = [k1+1]
A = [a1-b]
while(K[-1] > b):
    tempa = K[-1] % b
    tempk = K[-1] // b
    if(tempa > 2^35):
        A.append(tempa - b)
        K.append(tempk + 1)
    else:
        A.append(tempa)
        K.append(tempk)
print(A)
PR.<x> = PolynomialRing(Zmod(n))
f = K[4]*x^5 + A[4]*x^4 + A[3]*x^3 + A[2]*x^2 + A[1]*x^1 + A[0] - c
f = f.monic()
res = f.small_roots(X=256^29,beta=5/6)
print(res)

flag = long_to_bytes(int(res[0]))
print(flag)

#NSSCTF{F1nd_4_M3th0d_70_COPPER5m1th!}

easy_copper2

题目：

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

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c = pow(m,e,n)

print("n =", n)
print("c =", c)
print("leak1 =", p >> 282)
print("leak2 =", p % 215656441)

'''
n = 83732821313465518052403665361614770500711747426707910445616394700719876467737514967114877768176244233541342950517438107504392659632618504678367884223695674258126620001220856677629607205209582904215330731871567514530350222492246762740556482040907225061791231222448377878854527601783227627969726021295513927063
c = 46663818733755991848242947341712498383456884024793897130170411388799402223110989123025227270450872334684154450132747808192836148157068113180136519163245994436646022864578219391320904777242102617963109623497099134092899460260651347833764105572783843769863133591669278971958095602865992957181139586462882547338
leak1 = 1166802227519044965330497437183661580954600955790078699599066071608461
leak2 = 100652187
'''

这个题目本来打算出给Round19，但是想了很久都没有想到一个特别好的出题方式所以暂且搁置了，最后在dlc这里展示出来。这个题目本身并不难做，主要是有一个很有意思关于爆破+copper的思路想分享出来，就做成了这个题目。

回到题目，题目内容基于RSA，要求分解由两个512bit素数相乘得到的n，为此给出如下两个额外泄露：

• p的高230位
• p模215656441的值

显然，只给230的p高位对于高位泄露copper来说根本不可能，一般来说未知的部分要越少越好，未知256bit已经是copper理论上的极限。同时，由于这个毕竟是理论，实际操作时不加上一些爆破的话，未知250bit已经要把epsilon取到0.01甚至更小，这会使copper速度显著减慢。

因此就要想办法利用上第二个信息，既然给了p模215656441的值，那么p的整个结构可以写为：

$$p = p_h + 215656441x + p_l$$

其中pl就是leak2，而leak1是将ph做了带余除法的处理，使得它是215656441的整数倍。此时x就是我们待求的小根，他的数量级大约为：

$$\frac{2^{282}}{215656441} \approx 2^{255}$$

所以接下来要做的事情也很好想，通过爆破一些比特位，来减小x的数量级，然后用copper把x求出来。假设我们知道了epsilon=0.01可以求解出250bit的小根(可以自己生成点数据测出来)，那么我们就要爆破2^5，大约是32次。这样已经可以解决这个题目了。

但是从现在开始才是这个题目真正想分享的东西，我们首先需要关注一下为什么选择了模215656441这么一个奇怪的数，这其实是一个提示，分解一下可以发现：

215656441 = 7 · 11 · 13 · 17 · 19 · 23 · 29

这是一些小素数的乘积，然而却没有2、3、5。这个提示的本意是：更充分地利用上p是素数这个结构，从而用一种更优的思路去爆破。

这是什么意思呢？观察刚才copper的多项式：

$$p = p_h + 215656441x + p_l$$

按常规的思路爆破bit位，无非在0-2^5内爆破i，然后把式子写成：

$$p = p_h + 215656441(2^5x+i) + p_l$$

正如刚才的分析，这样一共要爆破32种情况。

这种思路和我们常见的p高位泄露、p低位泄露的本质是一样的，比如如果p的高位泄露了256位，那么很自然的想法就是去爆破6位当成一个250bit的低位小根来求解。而这时其实很容易想到一个优化，那就是由于p是个素数，所以p的最低位一定是1，因此其实爆破5位就够了。

想一下这个优化的本质是什么，这个优化的本质其实是利用p是个素数，因此p和2互素，所以能减小爆破的范围！

那么其实仔细思考，p既然是个素数，那么p应该和所有其他素数都互素，也就是说p和3互素，p和5互素之类的信息我们其实都可以用上，来进一步减少需要爆破的范围。而缩小到的范围与原范围的比值其实就是：

$$\frac{\phi(k)}{k}$$

其中k是取的小素数，比如对于刚才举的用2爆破的例子，实质上就是因为phi(2)/2=1/2，从而将需要爆破的范围缩小到了原来的一半。那么既然本题中的模数21565644不含有2、3、5三个素因子，那么我们就可以考虑用如下形式的多项式去爆破+copper：

$$p = p_h + 30*215656441x + 21565644i + p_l$$

此时ph应该对应处理为30*215656441的倍数，由于0-30内，满足21565644i + pl与30互素的值仅有8种，所以将需要花的时间变成了原来的1/4。

exp：

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

num = 215656441
last = 2*3*5
bits = 282

n = 83732821313465518052403665361614770500711747426707910445616394700719876467737514967114877768176244233541342950517438107504392659632618504678367884223695674258126620001220856677629607205209582904215330731871567514530350222492246762740556482040907225061791231222448377878854527601783227627969726021295513927063
c = 46663818733755991848242947341712498383456884024793897130170411388799402223110989123025227270450872334684154450132747808192836148157068113180136519163245994436646022864578219391320904777242102617963109623497099134092899460260651347833764105572783843769863133591669278971958095602865992957181139586462882547338
leak1 = 1166802227519044965330497437183661580954600955790078699599066071608461
leak2 = 100652187

ph = (leak1 << bits) - ((leak1 << bits) % (last*num))
possible_i = []
for i in range(last):
    temp = i*num + leak2
    if(GCD(temp,last) == 1):
        possible_i.append(temp)

PR.<x> = PolynomialRing(Zmod(n))
for i in tqdm(possible_i):
    f = ph + (last*num)*x + i
    f = f.monic()
    res = f.small_roots(X = (2^bits // (last*num)) , beta=0.499,epsilon=0.01)
    if(res != []):
        p = int(ph + (last*num)*int(res[0]) +i)
        q = n // p
        m = pow(c,(inverse(65537,(p-1)*(q-1))),n)
        print(long_to_bytes(int(m)))
        break

同样的，这种爆破思路对普通的p高位泄露、低位泄露当然也成立，时间一般能省下3-4倍。虽然说可以省时间，但是其实开点多进程也是一样的效果，所以本来是想出成一个speedup的限时靶机题，想了想还是不太好出，最后就变成这样了。不过这个思路确实很有意思。

easy_factor 系列

总体介绍：该系列基于RSA的质因数分解，没有新的原理，主要是综合运用工坊中的分解方法。

easy_factor1

题目：

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'
'''

题目任务可以简单描述为：三个256bit的素数p、q、r乘积为n，给出n的值以及以下值，要求分解n得到AES密钥，从而解密flag：

$$hint = k\phi(n)^3$$

其中k是未知的256bit的随机数。

这本身应该可以看作是一个已知n、kphi分解n的问题，是有现成脚本的，不过问题在于本题给出的是kphi^3，所以脚本跑的可能不是那么顺利，这就需要理解原理才行。

而这种分解的原理本身很简单，由欧拉定理我们知道：

$$a^{\phi(n)} = 1 \quad(mod\;n)$$

那么自然也就有：

$$a^{k\phi(n)^3} = 1 \quad(mod\;n)$$

而尝试分解kphi^3，可以得到如下的因子列表：

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

我们的重点在于这些3次方的素因子幂次，比如对于7，他只有3次幂说明什么呢？说明7仅可能是(p-1)、(q-1)、(r-1)三个数中其中一个的因子。由于p、q、r顺序并没有关系，所以我们不妨假设7是p-1的因子，那么如果我们把他完全除掉，得到下面的数字：

$$t = \frac{hint}{7^3}$$

此时就有：

$$t = r\phi(qr)$$ $$t \neq s\phi(n)$$

那么利用欧拉定理也就是：

$$a^{t} = 1 \quad(mod\;qr)$$ $$a^{t} \neq 1 \quad(mod\;n)$$

所以就可以任取a，计算a^t-1与n的GCD得到qr，那么同理也就得到了p；如此重复几次就能得到全部因子了。

exp：

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

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'


p = n // (GCD(pow(2,hint//7**3,n)-1,n))
q = n // GCD(pow(2,hint//248701**3,n)-1,n)
r = n // p // q

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

print(flag)

#NSSCTF{Just_simply_try_t0_divid3_s0m3_f4ct0rs_0f_phi}

easy_factor2

题目：

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

首先，题目生成两个1024bit的素数p、q，保证其高350位相等。并且给出如下式子的低300位：

$$(p^q + q^p) \quad(mod\;n)$$

其实这个式子在以前的一些比赛已经出现过，他其实就是p+q，这是因为比如对于$c = p^q \quad(mod\;n)$，用同余性质就可以写作：

$$c_p = p^q = 0 \quad(mod\;p)$$ $$c_q = p^q = p \quad(mod\;q)$$

然后将两者crt起来就得到c其实在模n下就是p了。对于q^p模n也同理，因此整个式子其实就是p+q。

所以现在我们拥有的就是：

• p和q高350位相同
• p+q的低300位

而p、q高位相同就容易想到是要用费马分解，然而直接分解是不行的，必须把第二个信息同时利用上。回顾一下费马分解的原理：

由于n可以写成一个平方差的形式：$n = pq = (\frac{p+q}{2})^2 - (\frac{p-q}{2})^2$

那么令$a = \frac{p+q}{2},b = \frac{p-q}{2}$，n也就可以写为$n = (a+b)(a-b)$

而费马分解的核心思想就是找到这样的a，他从$a=\sqrt{n}$开始，逐步增加a，一直到发现$a^2-n$是个平方数，就找到了正确的a、b，n也就成功分解了。

回顾一下思路后可以发现，费马分解所需要的时间，依赖于$\frac{p+q}{2}$与$\sqrt{n}$的差值。而p、q高位相等之所以利于费马分解，就是因为p、q高位相等会使得$\frac{p+q}{2}$越来越接近$\sqrt{n}$。

这也就是说，对于题目中，由于p、q高350位相等，因此我们对n开根，其高位就是p+q的高位，此时测试出来仍有325位左右的低位未知，而我们从另一个信息可以得到p+q的低300位，因此爆破25位就可以找到p+q，从而得到n的分解。

exp：

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

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

#part1 factor n by Fermat's_factorization_method(adding bruteforce)
sumhigh = 2*iroot(n,2)[0] >> 325 << 325
for i in trange(2**25):
    pplusq = sumhigh + 2**300*i + leak
    if((pplusq)**2 > 4*n):
        temp = iroot((pplusq)**2-4*n,2)
        if(temp[1]):
            p_q = temp[0]
            p = (pplusq + p_q) // 2
            q = n // p
            break


#part2 get flag
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))


#NSSCTF{JUST_@pply_Fermat's_factorization_method_W1tH_Brut3F0rce!}

easy_factor3

题目：

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

m = 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(m,e,n))

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

题目将两个2048bit的随机数m1、m2表示为p进制的形式：

$$m = ap^n + bp^{n-1} + ... + cp + d$$

并给出各数码的和，但是隐去了这个和模1000的余数，也就是：

$$sum = \frac{a+b+...+c+d}{1000}$$

然而既然只是隐去了模1000的余数，说明只需要在0-1000内爆破，其中有一个值就是原来的sum。将这个sum与m作差得到：

$$m - sum = a(p^n-1) + b(p^{n-1}-1) + ... + c(p-1)$$

右边都有p-1这个因子，所以有：

$$m \equiv sum \quad(mod\;p-1)$$

所以对于两组m1、m2，就有：

$$m_1 - sum_1 = k_1(p-1)$$ $$m_2 - sum_2 = k_2(p-1)$$

因此求解GCD就能恢复p-1的值，进而得到p去得到n的分解从而解密。

exp：

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

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

if(1):
    for i in trange(1000):
        for j in range(1000):
            sum1_ = sum1*1000+i
            sum2_ = sum2*1000+j
            kp_1 = GCD(m1-sum1_,m2-sum2_)
            if(kp_1 > 2**255):
                for k in range(1,10000):
                    if(kp_1 % k == 0):
                        p = kp_1 // k + 1
                        if(isPrime(p) and len(bin(p)[2:]) == 256):
                            q = n // p
                            break

d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

#NSSCTF{M@k3_U53_0F_GCD_beHinD_th3_p-Base!}

easy_factor4

题目：

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 = getPrime(256)
q = getPrime(256)
n = p*q
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)

key = sha256(str(p+q).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
c = enc.encrypt(pad(flag,16))
hint = getPrime(20)*d**3 + getPrime(128)*phi**2

print("n =",n)
print("c =",c)
print("hint =",hint)


'''
n = 8218998145909849489767589224752145194323996231101223014114062788439896662892324765430227087699807011312680357974547103427747626031176593986204926098978521
c = b'\x9a \x8f\x96y-\xb4\tM\x1f\xe6\xcc\xef\xd5\x19\xf26`|B\x10N\xd7\xd0u\xafH\x8d&\xe3\xdbG\x13\x8e\xea\xc0N\n\r\x91\xdc\x95\x9b\xb1Ny\xc1\xc4'
hint = 1860336365742538749239400340012599905091601221664081527583387276567734082070898348249407548568429668674672914754714801138206452116493106389151588267356258514501364109988967005351164279942136862087633991319071449095868845225164481135177941404709110974226338184970874613912364483762845606151111467768789248446875083250614540611690257121725792701375153027230580334095192816413366949340923355547691884448377941160689781707403607778943438589193122334667641037672649189861
'''

题目给出一个hint：

$$hint = ad^3 + t\phi(n)^2$$

其中a、t分别是20bit、128bit的未知素数，要求利用此hint完成RSA的分解。

由于a仅有20bit，是一个可以爆破的范围，所以当前问题是用什么方式去爆破能够确定a的值。由于有d^3的存在，自然可以想到两边同乘e^3：

$$e^3hint = a(ed)^3 + te^3\phi(n)^2$$

又因为：

$$ed = 1 + k\phi(n)$$

所以：

$$e^3hint = a(1 + k\phi(n))^3 + te^3\phi(n)^2$$

也就是：

$$e^3hint = a + K\phi(n)$$

所以对于正确的a，有：

$$2^{e^3hint-a} = 2^{K\phi(n)} = 1 \quad(mod\;n)$$

因此就能确定a的值。

有了a之后，也就有了Kphi(n)的值：

$$K\phi(n) = e^3hint - a$$

所以就变成已知Kphi(n)和n求n的分解的问题了，无论是用factor1的方法去试除小因子，还是用网上的轮子都可以解决。

exp：

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from gmpy2 import *
from tqdm import *

n = 8218998145909849489767589224752145194323996231101223014114062788439896662892324765430227087699807011312680357974547103427747626031176593986204926098978521
c = b'\x9a \x8f\x96y-\xb4\tM\x1f\xe6\xcc\xef\xd5\x19\xf26`|B\x10N\xd7\xd0u\xafH\x8d&\xe3\xdbG\x13\x8e\xea\xc0N\n\r\x91\xdc\x95\x9b\xb1Ny\xc1\xc4'
hint = 1860336365742538749239400340012599905091601221664081527583387276567734082070898348249407548568429668674672914754714801138206452116493106389151588267356258514501364109988967005351164279942136862087633991319071449095868845225164481135177941404709110974226338184970874613912364483762845606151111467768789248446875083250614540611690257121725792701375153027230580334095192816413366949340923355547691884448377941160689781707403607778943438589193122334667641037672649189861

e = 65537

#part1 get a
if(0):
    for a in trange(2**20):
        if(not isPrime(a)):
            continue
        if(powmod(2,e**3*hint-a,n) == 1):
            print(a)
            break
a = 565237


#part2 factor n
kphi = e**3*hint - a
t = 3**3
p = GCD(pow(2,kphi//t,n)-1,n)
q = n // p


#part3 get flag
key = sha256(str(p+q).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
flag = enc.decrypt(c)
print(flag)


#NSSCTF{H0w_70_F4ct0R_N_7h1s_tim3?}

other

总体介绍：一些其他零碎知识点的杂烩。

easy_NTRU

题目：

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

题目基于NTRU，但是问题在于f的数量级过大，甚至超过了p，所以没有办法直接规约。

而处理手段和mod系列其实很类似，由于已知flag的前后缀以及中间一小段的内容，所以可以尝试把flag写成如下形式：

$$f = 256^{58} + 256^rm_1 + 256^smid + 256m_2 + suf$$

这个式子里，m1、m2是未知小量，r、s也是未知数，不过可以注意到的是，一旦中间已知部分!!NSSCTF!!的位置确定下来，r、s的具体值也就随即确定了，而中间部分的位置也仅有几十种，所以可以爆破所有可能的位置得到r、s。

那么就假设我们现在已知r、s，目的是规约出f来，就先回看一下NTRU的模等式：

$$hf = g \quad(mod\;p)$$

转化成等式，并且把f的展开形式代入进来，也就是：

$$h(256^{58} + 256^rm_1 + 256^smid + 256m_2 + suf) + kp = g$$

把常数整合一下，就得到：

$$h256^rm_1 + h256m_2 + C + kp = g$$

虽然g未知，但是他的数量级仅有128，在模p下也是个小量，所以就能造出如下格：

$$\left(\begin{matrix} 1 &&&h256^r\\ &1& &h256\\ &&1 &-C\\ && &p\\ \end{matrix}\right)$$

这个格具有的线性关系是：

$$(m_1,m_2,1,k) \left(\begin{matrix} 1 &&&h256^r\\ &1& &h256\\ &&1 &-C\\ && &p\\ \end{matrix}\right) = (m_1,m_2,1,g)$$

比较关键的是配平数量级的问题，由于中间部分位置确定后，m1、m2各有多少个字节其实也就确定了，所以就能够进行配平。

exp：

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

h = 1756927950546402823211991210884487117388985427696056353000574684529449680817044069252055937789026298359737442776894512901268732373696001068086438971265520
p = 9154925474221530551204374718472364426110749279786123087256403092166680682021327157348820042798042742469289027059354748716972834115194900518063143041804941
flag_len = 65
prefix = bytes_to_long(b"NSSCTF{")*256^(flag_len-7)
suffix = bytes_to_long(b"}")
middle_len = 10

for location in range(1,flag_len-7-middle_len+1):
    middle = bytes_to_long(("!!NSSCTF!!").encode())*256^location
    constant = prefix + middle + suffix

    c2_len = location-1
    c1_len = flag_len - middle_len - 1 - 7 - c2_len
    c2_loc = 1
    c1_loc = 1 + c2_len + middle_len
    
    L = Matrix(ZZ,[[1,0,0,256^c1_loc*h],
                [0,1,0,256^c2_loc*h],
                [0,0,1,constant*h],
                [0,0,0,p]])
    
    T = max(256^c1_len,256^c2_len,2^128)
    Q = diagonal_matrix([T//(256^c1_len) , T//(256^c2_len) , T , T//2^128])
    L = L*Q
    L = L.LLL()
    res = L[0]
    L = L/Q
    res = L[0]
    if((res[2] == 1 or res[2] == -1) and isPrime(int(abs(res[3]))) and int(abs(res[3])).bit_length()==128):
        try:
            print(long_to_bytes(int(abs(res[0]))).decode(),end = "")
            print("!!NSSCTF!!",end = "")
            print(long_to_bytes(int(abs(res[1]))).decode(),end = "")
        except:
            pass


#NSSCTF{Task_1s_to_FinD_where_th3_!!NSSCTF!!_IS_in_thi5_FLAGHhah!}