一个RSA中分解的题
from sage.all import *
from Crypto.Util.number import *flag = b'COMPFEST16{REDACTED}'while True:p = next_prime(randrange(10*299, 10**300))if len(str(p)) != 300:continueq = Integer(int(str(p)[200:] + str(p)[100:200] + str(p)[:100]))if is_prime(q):if len(str(p*q)) == 600:n = p*qbreakct = pow(bytes_to_long(flag), 65537, n)print("ct =", ct)print("n =", n)break
其中 p = int(str(a)+str(b)+str(c)), q=int(str(c)+str(b)+str(a))弄了半天没出来，问了问小鸡块师傅，师傅说大概就是这个算法。然后慢慢整理了一下，主要是讨论这个进位。
对于p*q可以看成小学数学里的拖式乘法，这样这个题就可以整理成以下形式：
'''a b c c b a ach aclabh abl aah aalbch bclbbh bbl abh ablcch cclbch bcl
ach acl j0 j1 xx j3 0
'''每100位看成进制，相乘以后分成高位和低位。同样把n也分成6段，也就对着相乘的结果，不过这里在竖式相加的是个可能会形成进位。还要讨论一下进位的情况。
先看j4这是从个位（10^100）进到10位，由于讨论的b*c的低位和高位是直接切开，所以不存在进制这个位是0
j0,j1,j3分别是后位向前位的进位。根据相加将数可以确定最大进位是2,4,2，虽然运算的时候会很慢，但由于规模过于小只有16所以爆破还是可以的。
j0这个数看第5段 a*b+b*c的低位由于a,c都出现在过尾部，所以对于素数来说一个是奇数，b*(a+c)一定是偶数，而第5段n是偶数，所以abh是偶数(abh+bcl+abl=ns[4])而第1段是奇数，所以肯定存在一个进制。而后边是3个数的和那也就只能是1了。
j2这个进位可能存在，但由于最后只判断a^2+b^2+c^2，也就是3，4两块同时考虑，变成了内部所以不用考虑。
在重新整理了进位以后很快就出了结果。
ns = [int(str(n)[i:i+100]) for i in range(0,600,100)]
mod = 10**100
#ach 可能存在1-2的进位
a,b,c = var('a b c', domain=ZZ)
f0 = (a*mod*mod+b*mod+c)*(c*mod*mod+b*mod+a) - n
acl = ns[5]
for j0 in range(3):ach = ns[0]-j0 #ach+abl+bcl 其中b(a+c)是偶数 ns[4]是偶数,所以ach是偶数j0=1f1 = a*c - (ach*mod+acl)#ach有1个进位,出自abh+bch+acl = mod+ns[1]for j1 in range(5): #ns[2]的进位abh_bch = j0*mod + ns[1] - j1 - acl #abh+bch+acl = j0 ns[1] j1for j3 in range(3):print(j0,j1,j3)abl_bcl = j3*mod + ns[4]-ach #ach + abl+bcl = j3 ns[4] 0f2 = a*b+b*c - (abh_bch*mod + abl_bcl) abc = j1*mod^2 + ns[2]*mod + ns[3] - j3 -abl_bcl*mod -abh_bch #aa+bb+cc+abl+bcl产生的进位f3 = a*a+b*b+c*c - abcres = solve([f1,f2,f3],[a,b,c])if res != [] and '*' not in str(res[0]):print(res)#a == 3384534193501166567813394469004882760437480998536914912385664351589949548679751224744895524812033689, b == 8813261234769988078773624745788094330236326796754123647564613204982832546333762842695148993523803193, c == 9991244426324910253248758649201577124946964687906374352986952736768966919904674450505237017789484311
#p = res[0][0].rigth()*mod^2 + res[0][1].right()*mod + res[0][2].right()
p = 338453419350116656781339446900488276043748099853691491238566435158994954867975122474489552481203368988132612347699880787736247457880943302363267967541236475646132049828325463337628426951489935238031939991244426324910253248758649201577124946964687906374352986952736768966919904674450505237017789484311from gmpy2 import *
from Crypto.Util.number import *
m = pow(ct,invert(65537,(p-1)*(q-1)),n)
#114898570474263717714227747141272014778503789859070229630273200303976818910065535984911749011343545726084057785880900024080814701873981376617981079892081012886339175643046745686070775227720265100609389691782780199626437338848603534186418085900413
long_to_bytes(m)
b'COMPFEST16{numb3r_th30ry_1s_qu1t3_fun_1snt_1t_h3h3h3_th1s_fl4g_1s_qu1t3_l0ng_n0t_g0nn4_l1e_718109abe0}'