对于e与$\phi(n)$不互素的情况，如果e与$\phi(n)$的公因数比较小（比如2，遇到过类似的，在前文RSA题型总结里有），直接开方即可，但如果公因数比较大一点（遇到过公因数为14、35的），直接开方肯定就不行了，需要构造新的RSA解密，这里单独记录，不放在RSA题型总结这篇里。
simple RSA
源码：
import gmpy2
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from secret import FLAG, E1, E2, P, Q1, Q2
def next_prime(num: int) -> int:
num = num + 2 if num % 2 else num + 1
while not isPrime(num):
num += 2
return num
p = getPrime(1024)
q = next_prime(getPrime(16) * p + 38219)
n = p * q
c = pow(E1, 65537, n)
print(f'n = {n}')
print(f'c = {c}')
# n = 1605247600724752598798254639224215706171506359654961357324428027985787942008103766562745464838961569081446916113769517713344420113584254259000172572811154232107339480903672251992191997458469905064423618888336088652352540882576826988355783159237971043770132628344798937353150930071309347972804118952814447576207066147031238749098842662046825743988208813903138796789940911515825517078554074496474819128789835309636804325132602557092847746454786387067599510769382078521691609970320528531270474091713477040343897269903489441410062592732302402854035415438078656688806905350495825334584533345448091335565792091890185673190424063
# c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861
assert E2.bit_length() == 69
ns = [getPrime(1024) * getPrime(1024) for _ in range(3)]
cs = [pow(E2, 89, n) for n in ns]
print(f'ns = {ns}')
print(f'cs = {cs}')
# ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
# cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]
qq = getPrime(1024)
nn = P * qq
qqq = qq >> 460 << 460
print(f'nn = {nn}')
print(f'qqq = {qqq}')
# nn = 16851735797771199659625936797279158526379741298692339786049494329385618191510929735113284926125682522862667382938603116481087115598324232020838136618518964343752653000145611092980612556947954728339508416646035295651852840099205127587606898235203114875942637900167644300657599966420459187131027117268004042708998239798434578246497419547543598779697909298102358128788120332794123690714647499091326245022977970510468925837363300545900657420134894815246189043375619879915523611890538142257042753868665844692029124229028056547096764320547579965641276151760507921199827910445919017775913411823263307923216323527883262438117
# qqq = 121042531930820997492656296084544616958724191434895945419858099204426898711413526806300854553993738803031497438495403291406481997877273916883918253302909196533823945327277312672931819555344139777992801106437643790498379469530787985051569590331291422592393540391481519004782904598710037907420679190942964514816
assert len(FLAG) == 42
n1 = P * Q1
n2 = P * Q2
c1 = pow(bytes_to_long(FLAG), E1, n1)
c2 = pow(bytes_to_long(FLAG), E2, n2)
print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
# n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549
# n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309
# c1 = 2615722342860373905833491925692465899705229373785773622118746270300793647098821993550686581418882518204094299812033719020077509270290007615866572202192731169538843513634106977827187688709725198643481375562114294032637211892276591506759075653224150064709644522873824736707734614347484224826380423111005274801291329132431269949575630918992520949095837680436317128676927389692790957195674310219740918585437793016218702207192925330821165126647260859644876583452851011163136097317885847756944279214149072452930036614703451352331567857453770020626414948005358547089607480508274005888648569717750523094342973767148059329557
# c2 = 6769301750070285366235237940904276375318319174100507184855293529277737253672792851212185236735819718282816927603167670154115730023644681563602020732801002035524276894497009910595468459369997765552682404281557968383413458466181053253824257764740656801662020120125474240770889092605770532420770257017137747744565202144183642972714927894809373657977142884508230107940618969817885214454558667008383628769508472963039551067432579488899853537410634175220583489733111861415444811663313479382343954977022383996370428051605169520337142916079300674356082855978456798812661535740008277913769809112114364617214398154457094899399
只记几个需要注意的点。
第一步，p、q是相近的，q的得到过程是在p的基础上乘上一个16的素数再加上一个数，可以爆破出来：
$n = p(ip+j) = p^2i + pj \approx p^2j$
$\Rightarrow p \approx (n//i)^{0.5}$
for i in range(2**15,2**16):
if isPrime(i):
p = iroot((n // i),2)[0]
if n % p == 0:
print(p)
break
第一步得到E1 = 377312346502536339265。
第二步用中国剩余解，用脚本解出的结果开89次方，这里需要注意。
解出E2 = 561236991551738188085
第三步应该是由p的高位解出p来，但我不知道上界怎么确定，报了list index out of range的错：
n = ...
p4 = ...
pbits = 1024
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^460, beta=0.4)
p = p4+int(roots[0])
print(str(n))
print(str(p))
print(str(n//p))
后面看了佬的wp才发现，n1、n2有公因数P，直接gcd就行了，应该是出题失误？
最后来到关键的一步，两组关于flag加密，相关条件都有了，常规思路是选择一个方程直接求解，题目显然不会让你这么舒服，发现E1与$\phi(n1)$和E2与$\phi(n2)$均不互素，存在公因数且均为35。直接开方显然也得不到flag，所以需要降幂运算，推导如下：
$两flag加密式拆开来 \Rightarrow$
$c1 \equiv m^{E1} \space mod \space P$
$c1 \equiv m^{E1} \space mod \space Q1$
$c2 \equiv m^{E2} \space mod \space P$
$c2 \equiv m^{E2} \space mod \space Q2$
$取第二个式子与第四个式子 \Rightarrow$
$c1 \equiv m^{E1} \space mod \space Q1$
$c2 \equiv m^{E2} \space mod \space Q2$
为何只选择与Q有关的式子呢，因为上面计算e与欧拉函数的公因数时，发现P与$\phi(n)$的公因数更大，故为了方便计算舍弃含P的式子。通过中国剩余解出来构造出的RSA解密中的c，以7为新的e，以Q1*Q2为新模数，如此便能解出flag：
def CRT(a, n):
sum = 0
N = reduce(lambda x, y: x * y, n)
for n_i, a_i in zip(n, a): # zip()
N_i = N // n_i
sum += a_i * N_i * invert(N_i, n_i)
return sum % N
E1 = 377312346502536339265
E2 = 561236991551738188085
nn = ...
qqq = ...
n1 = ...
n2 = ...
c1 = ...
c2 = ...
P = gcd(n1,n2)
Q1 = n1 // P
Q2 = n2 // P
c1 = pow(c1, invert(E1 // 35, (P-1)*(Q1-1)),n1)
c2 = pow(c2, invert(E2 // 35, (P-1)*(Q2-1)),n2)
#注意这里不能单纯的c2 = c2%Q2 c1 = c1%Q1
new_n = [Q1,Q2]
new_c = [c1,c2]
res = CRT(new_c,new_n)
d0 = inverse(7,(Q1-1)*(Q2-1))
m0 = pow(res,d0,Q1*Q2)
flag = iroot(m0,5)[0]
print(long_to_bytes(flag))
以7为e，是为了后面开方简单点。
还有一题中的最后一步与这题是一样的思路，来自buu里的[De1CTF2019]babyrsa。是之前做过的，在CSDN有记有详细的推导过程。
贴下地址：[(4条消息) [De1CTF2019]babyrsa_Luino！的博客-CSDN博客](https://blog.csdn.net/Luiino/article/details/126159821)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com