出题加测题
ps: 星盟安全团队密码纳新
前言
在比赛前几天被拉去出道简单的密码题，然后顺便帮adwa和wbuildings师傅演了个题，就各验了一个，adwa剩下的两篇论文没做出来，然后在后面放一道isctf我出的那一道简单题吧。
ps：星盟安全团队密码招新
蜀道山-Crypto
xorrsa
from Crypto.Util.number import *
from gmpy2 import *
import uuid
flag='LZSDS{'+str(uuid.uuid4())+'}'
while True:
p=getPrime(512)
if p.bit_length()==512:
break
mask=??????
q=p^mask
hint1=p^q
hint2=q
n=p*q
e=2026
m=bytes_to_long(flag.encode())
c=pow(m,e,n)
print("c =",c)
print("n =",n)
print("hint1 =",hint1)
print("hint2 =",hint2)
'''
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
hint2 = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647
'''
我出的一道非常非常简单的基础题，不会做可以不用做密码了，hint1=p^q=p^p^mask,hint2=p^mask,相同的数据xor为0，所以我们很容易得到了p，然后解密个eh和phi不互素的rsa就行
from Cryptodome.Util.number import *
from gmpy2 import *
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
hint2 = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647
p=hint2^hint1
q=n//p
print(p)
d=inverse(1013,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(iroot(m,2)[0]))
签到!?
from Crypto.Util.number import *
flag = b''
m = bytes_to_long(flag)
a = getPrime(1024);b = getPrime(1024);c = getPrime(1024);d = getPrime(128);n = getPrime(1024)
y = 0
for i in range(n+1):
x = a*i+b
y += (x//c)*i
if isPrime(y):
pass
else:
y = gmpy2.next_prime(y)
tmp = hashlib.md5(str(y).encode()).hexdigest()
cc = pow(d,int(tmp,16),n)
e = 52595
c3 = pow(m,e,y)
c4 = pow(a*m+b,e,y)
print('a =',a)
print('b =',b)
print('c =',c)
print('d =',d)
print('n =',n)
print('cc =',cc)
print('c3 =',c3)
print('c4 =',c4)
# a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
# b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
# c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
# d = 229823065384822950015724955215847476631
# n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
# cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
# c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
# c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093
类欧几里得算法照着ctfwiki复现就好了
https://oi-wiki.org/math/number-theory/euclidean/
最后e和y互素，求逆元直接pow(c3,inverse(e,y-1),y)即可
exp：
import sys
import hashlib
import functools
from Cryptodome.Util.number import *
from gmpy2 import *
sys.setrecursionlimit(5000)
@functools.lru_cache(None)
def f(a, b, c, n):
if a==0:
return (n+1)*b//c
m=(a*n+b)//c
if a<c :
return n*m-f(c,c-b-1,a,m-1)
else:
return n*(n+1)*(a//c)//2+(n+1)*(b//c)+f(a%c,b%c,c,n)
@functools.lru_cache(None)
def h(a, b, c, n):
if a == 0:
return (b // c) ** 2 * (n + 1)
m = (a * n + b) // c
if a < c:
return n * m * (m + 1) - 2 * g(c, c - b - 1, a, m - 1) - 2 * f(c, c - b - 1, a, m - 1) - f(a, b, c, n)
if a>=c:
return 2*(b//c)*f(a%c,b%c,c,n)+2*(a//c)*g(a%c,b%c,c,n)+(a//c)**2*(n*(n+1)*(2*n+1))//6+(b // c) ** 2 * (n + 1)+(a//c)*(b//c)*n*(n+1)+h(a%c,b%c,c,n)
@functools.lru_cache(None)
def g(a, b, c, n):
if a == 0:
return (n * (n + 1) * b // c) // 2
m = (a * n + b) // c
if a < c:
return (m * n * (n + 1) - h(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1)) // 2
else:
return g(a%c,b%c,c,n)+(a//c)*(n*(n+1)*(2*n+1))//6+(b//c)*(n*(n+1))//2
a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
d = 229823065384822950015724955215847476631
n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093
y=g(a,b,c,n)
y=next_prime(y)
tmp = hashlib.md5(str(y).encode()).hexdigest()
assert cc == pow(d,int(tmp,16),n)
e = 52595
print(long_to_bytes(pow(c3,inverse(e,y-1),y)))
Something like coppersmith
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib
from secret import flag
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
g = 37
x = getRandomRange(1, p)
key = hashlib.md5(str(x).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(f"y = {pow(g, x, p)}")
print(f"xl = {x & (2**404 - 1)}")
print(f"enc = {aes.encrypt(pad(flag, 16))}")
"""
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
"""
首先分析题目，他给我们返回的信息是经过aes加密之后的flag，并且告诉我们key是x，并且给我了我们pow(g, x, p)与x的低位，首先我们先去分析p，发现p-1为光滑数，不过测题的时候数据用http://www.factordb.com/
分解得到的数据不多，后面可能被分解开了，就按照后面没被分解开做吧得到的是那么我们就可以想到使用pohlig_hellman，但是这时候直接算是肯定算不出来的，我们这时候可以想到根据我们分解得到的数据然后根据这个去取x的高位，因为是指数形式所以我们要将gxl mod p除一下y，要取得高位的值我们就可以把我们经过前一步得到值o，pow(o,inverse(2404,(p-1)//2),p),我们就可以得到x的高位,不过注意的是我们是求取的高位所以我们需要将里面的modp做下改变，需要根据分解出来的数据将其除f，这样我们pohlig_hellman得到的就是关于模掉f的x的高位
具体详细理解可以看一下la佬的博客
https://lazzzaro.github.io/2020/05/07/crypto-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0/
其实就是p-1素因子分解后我们将我们的已知素因子剔除我们对剩余的进行pohlig_hellman
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib
from gmpy2 import *
import gmpy2
from tqdm import *
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
print(isPrime(727646221919))
print(isPrime(11247577139973709667751898859218729686439398162234784309680985177149060797612355055258831046770798104717979839034759009750778402252837593))
print(p-1)
print(isPrime(385057))
print(isPrime(2))
f=[2,385057,727646221919]
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
g = 37
o=pow(g,xl,p)
o=inverse(o,p)
o=y*o%p
print(o)
print(inverse(2**404,p))
print(inverse(2**404,(p-1)//2))
d=inverse(2**404,(p-1)//2)
o=pow(o,d,p)
print(o)
def babystep_giantstep(g, y, p, q=None):
if q is None:
q = p - 1
m = int(q**0.5 + 0.5)
# Baby step
table = {}
gr = 1 # g^r
for r in range(m):
table[gr] = r
gr = (gr * g) % p
# Giant step
try:
gm = pow(g, -m, p) # gm = g^{-m}
except:
return None
ygqm = y # ygqm = y * g^{-qm}
for q in range(m):
if ygqm in table:
return q * m + table[ygqm]
ygqm = (ygqm * gm) % p
return None
# Pohlig–Hellman法
def pohlig_hellman_DLP(g, y, p,f):
crt_moduli = []
crt_remain = []
for q in f:
x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
if (x is None) or (x <= 1):
continue
crt_moduli.append(q)
crt_remain.append(x)
x = crt(crt_remain, crt_moduli)
return x
x = pohlig_hellman_DLP(g, o, p,f)
print("x=",x)
得到了x的高位还有x的低位，但是中间可以发现有五十bit的长度大小仍不知道，这时候直接mitm就ok了
vv=o*inverse(pow(g,x,p),p)%p
dic={}
x1=0
x2=0
for i in tqdm(range(3,2**24)):
dic[int(gmpy2.powmod(vv,gmpy2.invert(i,(p-1)//gmpy2.gcd(i,p-1)),p))]=i
for j in tqdm(range(2**25)):
if gmpy2.powmod(g,f[2]*f[1]*j,p) in dic:
print(j)
x1=j
print(dic[gmpy2.powmod(g,f[2]*f[1]*j,p)])
x2=dic[j]
break
在最后恢复的时候要注意的是因为在pohlig_hellman我们提取的素因子是f，所以我们要将f里面的值作为模去恢复一下，就是可以理解为f为分割出来的每一块，而我们得到的其实就是多少块这个f，所以在最后我们可以得到x_h=x+x1x2f[1]*f[2]，然后我们就可以解密了
完整exp：
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib
from gmpy2 import *
import gmpy2
from tqdm import *
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
print(isPrime(727646221919))
print(isPrime(11247577139973709667751898859218729686439398162234784309680985177149060797612355055258831046770798104717979839034759009750778402252837593))
print(p-1)
print(isPrime(385057))
print(isPrime(2))
f=[2,385057,727646221919]
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
g = 37
o=pow(g,xl,p)
o=inverse(o,p)
o=y*o%p
print(o)
print(inverse(2**404,p))
print(inverse(2**404,(p-1)//2))
d=inverse(2**404,(p-1)//2)
o=pow(o,d,p)
print(o)
def babystep_giantstep(g, y, p, q=None):
if q is None:
q = p - 1
m = int(q**0.5 + 0.5)
# Baby step
table = {}
gr = 1 # g^r
for r in range(m):
table[gr] = r
gr = (gr * g) % p
# Giant step
try:
gm = pow(g, -m, p) # gm = g^{-m}
except:
return None
ygqm = y # ygqm = y * g^{-qm}
for q in range(m):
if ygqm in table:
return q * m + table[ygqm]
ygqm = (ygqm * gm) % p
return None
# Pohlig–Hellman法
def pohlig_hellman_DLP(g, y, p,f):
crt_moduli = []
crt_remain = []
for q in f:
x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
if (x is None) or (x <= 1):
continue
crt_moduli.append(q)
crt_remain.append(x)
x = crt(crt_remain, crt_moduli)
return x
x = pohlig_hellman_DLP(g, o, p,f)
print("x=",x)
vv=o*inverse(pow(g,x,p),p)%p
dic={}
x1=0
x2=0
for i in tqdm(range(3,2**24)):
dic[int(gmpy2.powmod(vv,gmpy2.invert(i,(p-1)//gmpy2.gcd(i,p-1)),p))]=i
for j in tqdm(range(2**25)):
if gmpy2.powmod(g,f[2]*f[1]*j,p) in dic:
print(j)
x1=j
print(dic[gmpy2.powmod(g,f[2]*f[1]*j,p)])
x2=dic[j]
break
x_h=x+x1*x2*f[1]*f[2]
x=x_h*2**404+xl
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
key = hashlib.md5(str(x).encode()).digest()
print(key)
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(aes.decrypt(enc))
isctf-小蓝鲨的方程
from Cryptodome.Util.number import *
from random import *
from gmpy2 import *
import uuid
flag1='ISCTF{'+str(uuid.uuid4())+'}'
m1=bytes_to_long(flag1.encode())
def get_p():
BITS = 256
bits = 777
oder = 4
a = randint(1 << bits, 1 << bits + 1)
p=getPrime(BITS)
p1 = p**oder+a
return p,p1
p,p1=get_p()
s=getPrime(1024)
q=getPrime(512)
n=p*q**4
e=65537
c1=pow(s,e,n)
c=pow(s**3+1,m1,s**5)
print("c1=",c1)
print("c =",c)
print("n =",n)
print("p1 =",p1)
'''
c1= 671390498592586008552998377599101093977542184109077889081448730480869018650843045119891777468161631085086340705902115332025675787789530562679603254577287153918966364523848382506106179394235772395029788721306186952016420794804145631124905952103136061076643266886961178241381892015555099638200222249447194504082451341122502519637821695210573997670753981061458264118355417889153180841281073262935937836447460470926729282834006229571453935760593644658459098721652426154970766417292435960463905367868753821950303919781798234432998272038029063155193184039985018137026245365188171178677898869374676546799536208952198558258306460302868688355653022725288744014143221560882404431652751343944983442109327
c = 8641190030376811670503537177719719233418166235794962118828671236836174132083208517733734760455990850156371205118391537919769888760384574011411232571257192285256730733174399297826587479261381970232162702657952399683882650083181048279650913795429823628186888540572704055008102853692060360140858142686334722286525699998854566609078547487420929457446776757558492454916447188774943818970599916514467335772992690805247630814156710861067503956707301402347944233660194395192354000788262111000900574820275786269075882923600474781645848712157460135387134196156906258218217831988828360827613420801773911833194097791649069743116686685667300622630909231822986237104627385544169938138006242341269672868611269202418482629393372933567053272565557137741441902377611003983050084491513897727856173625922194300103448148829004025229567101761111396110940066254801762424343522707712480796358754008120503317686600144600226149617189681233392693738216138797012278242152852923361635415564580582002132107424154426980566696622448291815571736676562214017436
n = 1076246859437269645898003764327104347852443049519429833372038915264009774423737482018987571807662568251485615769880354898666799006772572239466617428164721157850526408878346223839884319846641438292436373441749602341461361190584638190903978829024853974880636148520803145113551453821058269641304504880310836801494499720662704717315748614372503735165114899680682056477494953525794354656896362929510309669119173103242509398650608116835276076364248473952717811633756784397347121601006659623317417388283638159905288128181587304367489096254611610975352096229116491567502061775862811850081040850421151385474249060884479729988512713640536139010928836126719149031115182144744359297169350288886555784650111
p1 = 145356063641618996012874664536921616978986640263438210169671010403677822239343590475177543891188656103067696467174379510912427160232486984044862545338401652910975162942038201716552753723984593267892098222213049269335313670049037479410635628460505327693176152061750827570561482918795206276991967169087371403553
'''
解题过程：
很常见的rsa加一些高中方程知识
首先我们先看p的生成
def get_p():
BITS = 256
bits = 777
oder = 4
a = randint(1 << bits, 1 << bits + 1)
p=getPrime(BITS)
p1 = p**oder+a
return p,p1
在这里可以看到这个函数会返回p和p ** oder+a，因为a的大小远远比p ** oder小，所以我们开order方可以得到一个近似于但是略微大于p的值，这时候我们将得到的值稍微减少一下取nextprime就可以得到p了。
接下来看第二步，给了两个值，一个c一个c1
c1=pow(s,e,n)
c=pow(s ** 3+1,m1,s ** 5)
可以发现我们跟flag有关的信息在c的生成里面，可能会有师傅想到dlp，其实哪有这么麻烦，其实就是一个高中知识辣，大家知道方程不，知道(x+1) ** 2等于什么吧，知道(x+1) ** 3等于什么吧，知道(x+1) ** 4，那师傅们展开看
(x+1) ** 2=x ** 2+2x+1,(x+1) ** 3=x ** 3+3x*2+3x+1,接下来不多说，可以很容易的发现我们展开的多项式系数其实就是从C_0_n到C_n_n嘛，其实就是高中的排列组合
那我们们根据这个就可以知道了pow(s ** 3+1,m1,s ** 5)，在多项式倒数第二项得到的系数就是我们的m1，然后我们首先利用得到的c1，解密rsa得到s，然后我们展开c1，c1 + ks ** 5=s ** (3m1)+…+m1s ** 3+1,两边同时减1,这时候我们可以发现等式右面剩下s* m1+…+m1s，这时我们想获取m1,我们可以直接将式子整除s，这样我们就可以的到式子（c1+k s ** 5-1)// s ** 3=s ** (3*(m1-1))+…+m1，同时mod s得到(c1-1) mod s = m1,所以我们就得到答案了
很简单吧是不是就是最基础的rsa加一个高中学的方程呢，exp如下：
from Cryptodome.Util.number import *
from gmpy2 import *
c1= 671390498592586008552998377599101093977542184109077889081448730480869018650843045119891777468161631085086340705902115332025675787789530562679603254577287153918966364523848382506106179394235772395029788721306186952016420794804145631124905952103136061076643266886961178241381892015555099638200222249447194504082451341122502519637821695210573997670753981061458264118355417889153180841281073262935937836447460470926729282834006229571453935760593644658459098721652426154970766417292435960463905367868753821950303919781798234432998272038029063155193184039985018137026245365188171178677898869374676546799536208952198558258306460302868688355653022725288744014143221560882404431652751343944983442109327
c = 8641190030376811670503537177719719233418166235794962118828671236836174132083208517733734760455990850156371205118391537919769888760384574011411232571257192285256730733174399297826587479261381970232162702657952399683882650083181048279650913795429823628186888540572704055008102853692060360140858142686334722286525699998854566609078547487420929457446776757558492454916447188774943818970599916514467335772992690805247630814156710861067503956707301402347944233660194395192354000788262111000900574820275786269075882923600474781645848712157460135387134196156906258218217831988828360827613420801773911833194097791649069743116686685667300622630909231822986237104627385544169938138006242341269672868611269202418482629393372933567053272565557137741441902377611003983050084491513897727856173625922194300103448148829004025229567101761111396110940066254801762424343522707712480796358754008120503317686600144600226149617189681233392693738216138797012278242152852923361635415564580582002132107424154426980566696622448291815571736676562214017436
n = 1076246859437269645898003764327104347852443049519429833372038915264009774423737482018987571807662568251485615769880354898666799006772572239466617428164721157850526408878346223839884319846641438292436373441749602341461361190584638190903978829024853974880636148520803145113551453821058269641304504880310836801494499720662704717315748614372503735165114899680682056477494953525794354656896362929510309669119173103242509398650608116835276076364248473952717811633756784397347121601006659623317417388283638159905288128181587304367489096254611610975352096229116491567502061775862811850081040850421151385474249060884479729988512713640536139010928836126719149031115182144744359297169350288886555784650111
p1 = 145356063641618996012874664536921616978986640263438210169671010403677822239343590475177543891188656103067696467174379510912427160232486984044862545338401652910975162942038201716552753723984593267892098222213049269335313670049037479410635628460505327693176152061750827570561482918795206276991967169087371403553
print(iroot(p1,4))
c0=iroot(p1,4)[0]
for i in range(2000):
b=c0-i
x=next_prime(b)
if n%x==0:
print(x)
print(iroot((n // x), 4))
q=iroot((n // x), 4)[0]
d=inverse(65537,(x-1)*(q-1)*q3)
s=int(pow(c1,d,n))
m=((c-1)//s**3)%s
print(long_to_bytes(m))
m1=long_to_bytes(m)
break