我们首先得到一个加密程序
# !/usr/bin/env python3
from Crypto.Util.number import getStrongPrime, bytes_to_long
from flag import flag
if __name__ == "__main__":
e = 3
m = bytes_to_long(flag)
print(m)
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
c = pow(m, e, n)
print(f"c1 = {c}
n1 = {n}")
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
c = pow(m, e, n)
print(f"c2 = {c}
n2 = {n}")
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
c = pow(m, e, n)
print(f"c3 = {c}
n3 = {n}")
然后一个输出结果
c1 = 17539961945253373331398829582415575036612590036028757160772244972941908466194620745487023767352926635453129673400947551800570434953767905902511379295345136570451295489004354977126089417697594812125862100295615892308145313262857527278337604392345816174840378652211171638690235768088513635252024385701456197867071483547776503865408409665095139733362063385643440859866760991522192617240460504557499194128504331507032560630787690799469014901580657128316778018414925198950809650404230359744912206082228624165856464258230573588957481525576839241810430236093217199856740231709797084566663183618816179247665234718539862375401
n1 = 25954427034636580488688831489560115961069472666415079273188034049008164292940982483612692501107292736442028702125249540852911969436468068247311640975480854492713351976176525107812421379597665083397176515413434794308159396038186056408397306479209393999454750519928895047459076589767348484006913759151416548823334675582153771760249016389971299782988978062163676178221833040970770232195936409272958856175588744276987268446839438228569198582572605622120469636250653620089140773532878971104036436080460912344807135105729626088120725564796123320176046591333153953156273882667280324378550802455223461937451841750073937989983
c2 = 19539433379216375750218779547809435082376062229344477092200871020606061269432023167855101557680750544416015137722429840602008656509188763841543689135752445081445085769419299442034779615280240976402031241423972293205872765805658756654762675178901338870755503879710815288905412632689902066516703213400579816331631896382153898787960802955572920035926336038746837415149996536394565793517378707048820536682814580494351837890938696637346974833887793018590409840667797035121476421376800944840299969820809315976451914567085976886787797952235847848303316051413592902451221192422759665784806839017636325833553952683415622277952
n2 = 28977092400787747945291214910953475539397234633352432488666947740932896707746402087821613046855183575993557568941158781622249869105260289295489171383139731429934283214540710808914967126144590911898223369390321872883938655216721369282084455732783931981613818631966554624868638800456323235693804356430288896569110909336549599272178314914621792570786164871693373909365501287006142071973005860686344874538143943409429678311737686588867879332895264597392666663429379812688533242656808653123802278526421662344107299830146336834937141923350992781402666027186207135144811802279179093695687133335834251524227256015307192667513
c3 = 2918771551109062192743205470533564743530056495509371083790131677186017377366876762293882312559301769357307295816292413881152560132690342974420494635750769296910584532596145872019444918884467672570317268685540399444720264635786588214509564818842868742697904854444519509240580449289880213055809856384077365925988427171564956047955329734920817815060202824430450606090801964935340359511488077057357948109798343529542672715979068275244032300296615263045889742363640538553080156092612057664163330784377800571208069910607577769286608705780510252727167158433741629217121035911007985869067181230135673920332673026493205578621
n3 = 24190274092630151926687108793524797704176150214559782896709114566936770947792315485598948092406603301001115324838577933772803761602741194516662266729209957846204581131810722907796267901163277374210255586883616164601148068628640292710177535651254874024209722605833909278514127991673090395029685984076324965718786722675755176835689645547154439390446344335367504783824259324152050501491588000676038321288448646330542896345041295625635250852659692178192868571083100117948063254735996935227555828339364201830194807935109124187509333776751082631706013914267005054512697140686858570500070125114765551217478594770260412263351
首先我们可以从这个代码中得到这样的一个方程
[m equiv c_1 pmod{n_1} \
m equiv c_2 pmod{n_2} \
m equiv c_3 pmod{n_3}
]
这个方程我们一看就是可以用中国剩余定理的求解程序来解决
#!/usr/bin/env python
from functools import reduce
import sys
import math
sys.setrecursionlimit(1000000) #1000000 为设置的栈大小
#gcd,求最大公约数函数，递归算法，有了扩展欧几里得算法之后，此函数可以不用
def _g_c_d(a,b):
if 0==b:
return a
return gcd(b,a%b)
#扩展欧几里得算法,返回值列表中,x是a的逆元(mod b),q是gcd(a,b),若x是0,则表示没有逆元
#y是计算过程中的迭代的参数,可以不用管
#此算法实质上是广义欧几里得除法的逆运算,用递归可以体现出这个逆运算的过程
def Ex_Euclid(a,b):
if 0==b:
x=1;y=0;q=a
return x,y,q
xyq=Ex_Euclid(b,a%b)
x=xyq[0];y=xyq[1];q=xyq[2]
temp=x;x=y;y=temp-a//b*y
return x,y,q
#获取a的逆元(mod b)的函数，目的是为了封装获取逆元的功能
def Get_Inverse(a,b):
return Ex_Euclid(a,b)[0]
#获取a和b的最大公约数函数，目的是为了封装获取最大公约数的功能
def gcd(a,b):
return Ex_Euclid(a,b)[2]
#判断所有的mi是否两两互质
def Is_Coprime(m_list):
for i in range(len(m_list)):
for j in range(i+1,len(m_list)):
if 1!=gcd(m_list[i],m_list[j]):
return 0 #返回0表示不是两两互质的
return 1 #返回1表示是两两互质的
#获取所有的Mi
def Get_Mi(m_list,M):
Mi_list=[]
for mi in m_list:
Mi_list.append(M//mi)
return Mi_list
#获取所有的Mi的逆元
def Get_Mi_inverse(Mi_list,m_list):
Mi_inverse=[]
for i in range(len(Mi_list)):
Mi_inverse.append(Get_Inverse(Mi_list[i],m_list[i]))
return Mi_inverse
#中国剩余定理,返回值为最终的x
def C_R_T():
while True:
#两个空列表，分别用来保存mi和bi
m_list=[]
b_list=[]
while True: #输入mi
m_i=input("请输入mi,以'.'结束输入:")
if m_i=='.':
break
elif False==m_i.isnumeric():
print("输入有误，请输入数字:")
m_i=input()
continue
else:
m_list.append(int(m_i))
while True: #输入bi
b_i=input("请输入bi,以'.'结束输入:")
if b_i=='.':
break
elif False==b_i.isnumeric():
print("输入有误，请输入数字！
")
b_i=input()
continue
else:
b_list.append(int(b_i))
if len(m_list)!=len(b_list):
print("错误！mi的个数和bi的个数不相同，请重新输入
")
elif 0==Is_Coprime(m_list):
print("错误！输入的mi并不是两两互质的，请重新输入mi
")
else:
break
M=1 #M是所有mi的乘积
for mi in m_list:
M*=mi
Mi_list=Get_Mi(m_list,M)
Mi_inverse=Get_Mi_inverse(Mi_list,m_list)
x=0
for i in range(len(b_list)): #开始计算x
x+=Mi_list[i]*Mi_inverse[i]*b_list[i]
x%=M
return x
if __name__=='__main__':
print("同余式组的解为：x=%d" % C_R_T())
上面这个程序提示输入 mi 的时候依次输入 n1 n2 n3 (除数) 提示输入 bi 的时候输入 c1 c2 c3（余数）
最后得到结果
13300111372637798836274976682144446509249794411171607231640782913245024173962466004292866985899729515808184933243237326004265637144765366861084718602875719527046873973359778034344146364012933067459384416621759467127821535377201109408331587913873296647694635603042192149698759322765328687652278208955183403077834629074089263092559468278392142063653712833649825799471418185195013022018496220617491452938072824035167931991183649387408139606194566747383443816272040215588825127855198539624005305754876178598872414420646223633314181764188358947904734577809610534805388737695068419034529721647865993400155405434082802625126299880466501676428337217444066497292225119328808196107193774854486141759870113608597589672237612091931089778968950797586565210403183163252658223652812196847281238844204951051419182479556217362993824614939179736342014536633342096306781633729610353231878979280868735934512936546633439381984121607130961777082332302552495730333385926449294917228954165038846331324617025953125
最后我们对这个数开三次方，然后就可以还原出原来的句子了。开三次方可以采用二分法，这样就能秒出结果。最后从 m 还原出字符串看程序就可以了
from math import pow
from time import sleep
x = 13300111372637798836274976682144446509249794411171607231640782913245024173962466004292866985899729515808184933243237326004265637144765366861084718602875719527046873973359778034344146364012933067459384416621759467127821535377201109408331587913873296647694635603042192149698759322765328687652278208955183403077834629074089263092559468278392142063653712833649825799471418185195013022018496220617491452938072824035167931991183649387408139606194566747383443816272040215588825127855198539624005305754876178598872414420646223633314181764188358947904734577809610534805388737695068419034529721647865993400155405434082802625126299880466501676428337217444066497292225119328808196107193774854486141759870113608597589672237612091931089778968950797586565210403183163252658223652812196847281238844204951051419182479556217362993824614939179736342014536633342096306781633729610353231878979280868735934512936546633439381984121607130961777082332302552495730333385926449294917228954165038846331324617025953125
l = 0
r = x
mid = 0
while l <= r:
mid = int((l + r) >> 1)
# print(mid) # debug
# sleep(0.001)
if mid * mid * mid == x:
#print(mid)
break
elif mid * mid * mid < x:
l = mid + 1
else:
r = mid - 1
ans = mid
ansArr = []
while ans != 0:
ansArr.append(chr(ans % (2 ** 8)))
ans = ans >> 8
len = len(ansArr)
for i in range(len - 1, -1, -1):
print(ansArr[i], end='')
print()