CTFSHOW-unusualrsa
Published in：2021-09-15 | category： 密码学 CTFSHOW

unusualrsa1

题目如下：

# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from random import randint
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

m = bytes_to_long(long_to_bytes(randint(0,30))*208+flag)
assert(m.bit_length()==2044)
print((m>>315)<<315)
c = pow(m,3,n)
print(c)

#14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
#1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
#6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819

经典的CopperSmith攻击，明文是一个随机数*208 + flag后转为长整数，然后泄露了高位，直接使用sage恢复。脚本如下：

m = 1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
n = 14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
c = 6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819
kbits = 315
PR.<x> = PolynomialRing(Zmod(n))
f = (m + x)^ 3 - c
x0 = f.small_roots(X = 2 ^ kbits, beta = 1)[0]
print(m+int(x0))

长整数转字符串，flag在字符串的最后面。

unusualrsa2

题目如下：

# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from functools import reduce
from secret import flag, x, y

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

assert(reduce(lambda x,y:x&y,[(i-5)*i+6==0 for i in x]))
assert(reduce(lambda x,y:x&y,[(j-15)*j+44==0 for j in y]))

print(pow(reduce(lambda x,y:x*m+y,x),17,n))
print(pow(reduce(lambda x,y:x*m+y,y),17,n))

#23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
#10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
#17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450
reduce函数：
reduce(function, iterable[, initializer])

function -- 函数，有两个参数
iterable -- 可迭代对象
initializer -- 可选，初始参数

例子 ：

from functools import reduce

 def add(x, y) :       # 两数相加
   return x + y
 sum1 = reduce(add, [1,2,3,4,5])  # 计算列表和：1+2+3+4+5
 sum2 = reduce(lambda x, y: x+y, [1,2,3,4,5])  # 使用 lambda 匿名函数
 print(sum1)
 print(sum2)
------------------------------------------------------------------------------------------------------------
结果：
15
15

注意：reduce返回的数值类型与第二个函数的运算和列表中数值的类型。

返回到题目，题中的reduce函数的列表中的数值类型为bool类型，这样x,y都是bool类型的值（注意这里的x和y只是reduce函数的表述参数（形参），与后面循环中的x和y无关，for循环中的x和y才是真正的参数）。为了满足assert函数值为True，x和y中的元素都得满足前面的等式。

题目属于Coppersmith’s Short-pad Attack & Related Message Attack（Franklin-Reiter攻击）

算出x = [2, 3]; y = [4, 11]。

把相关参数代入下面的脚本就可以得到flag。

#脚本1
#Sage
import binascii
def attack(c1, c2, n, e):
    PR.<x>=PolynomialRing(Zmod(n))
    # replace a,b,c,d
    g1 = (a*x+b)^e - c1
    g2 = (c*x+d)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
c1 = 
c2 = 
n = 
e = 
m1 = attack(c1, c2, n, e)
print(binascii.unhexlify("%x" % int(m1)))
------------------------------------------------------------------------------------------------------------
#脚本2
#Sage
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+y)^e - c2
    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
    return diff
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
if __name__ == '__main__':
    n =
    e =
    c1 =
    c2 =
    diff = short_pad_attack(c1, c2, e, n)
    print("difference of two messages is %d" % diff)
    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)
    print("m2:", m1 + diff)

unusualrsa3

题目如下：

# ********************
# @Author: Lazzaro
# ********************

p: 
2470567871

N: 
1932231392*x^255 + 1432733708*x^254 + 1270867914*x^253 + 1573324635*x^252 + 2378103997*x^251 + 820889786*x^250 + 762279735*x^249 + 1378353578*x^248 + 1226179520*x^247 + 657116276*x^246 + 1264717357*x^245 + 1015587392*x^244 + 849699356*x^243 + 1509168990*x^242 + 2407367106*x^241 + 873379233*x^240 + 2391647981*x^239 + 517715639*x^238 + 828941376*x^237 + 843708018*x^236 + 1526075137*x^235 + 1499291590*x^234 + 235611028*x^233 + 19615265*x^232 + 53338886*x^231 + 434434839*x^230 + 902171938*x^229 + 516444143*x^228 + 1984443642*x^227 + 966493372*x^226 + 1166227650*x^225 + 1824442929*x^224 + 930231465*x^223 + 1664522302*x^222 + 1067203343*x^221 + 28569139*x^220 + 2327926559*x^219 + 899788156*x^218 + 296985783*x^217 + 1144578716*x^216 + 340677494*x^215 + 254306901*x^214 + 766641243*x^213 + 1882320336*x^212 + 2139903463*x^211 + 1904225023*x^210 + 475412928*x^209 + 127723603*x^208 + 2015416361*x^207 + 1500078813*x^206 + 1845826007*x^205 + 797486240*x^204 + 85924125*x^203 + 1921772796*x^202 + 1322682658*x^201 + 2372929383*x^200 + 1323964787*x^199 + 1302258424*x^198 + 271875267*x^197 + 1297768962*x^196 + 2147341770*x^195 + 1665066191*x^194 + 2342921569*x^193 + 1450622685*x^192 + 1453466049*x^191 + 1105227173*x^190 + 2357717379*x^189 + 1044263540*x^188 + 697816284*x^187 + 647124526*x^186 + 1414769298*x^185 + 657373752*x^184 + 91863906*x^183 + 1095083181*x^182 + 658171402*x^181 + 75339882*x^180 + 2216678027*x^179 + 2208320155*x^178 + 1351845267*x^177 + 1740451894*x^176 + 1302531891*x^175 + 320751753*x^174 + 1303477598*x^173 + 783321123*x^172 + 1400145206*x^171 + 1379768234*x^170 + 1191445903*x^169 + 946530449*x^168 + 2008674144*x^167 + 2247371104*x^166 + 1267042416*x^165 + 1795774455*x^164 + 1976911493*x^163 + 167037165*x^162 + 1848717750*x^161 + 573072954*x^160 + 1126046031*x^159 + 376257986*x^158 + 1001726783*x^157 + 2250967824*x^156 + 2339380314*x^155 + 571922874*x^154 + 961000788*x^153 + 306686020*x^152 + 80717392*x^151 + 2454799241*x^150 + 1005427673*x^149 + 1032257735*x^148 + 593980163*x^147 + 1656568780*x^146 + 1865541316*x^145 + 2003844061*x^144 + 1265566902*x^143 + 573548790*x^142 + 494063408*x^141 + 1722266624*x^140 + 938551278*x^139 + 2284832499*x^138 + 597191613*x^137 + 476121126*x^136 + 1237943942*x^135 + 275861976*x^134 + 1603993606*x^133 + 1895285286*x^132 + 589034062*x^131 + 713986937*x^130 + 1206118526*x^129 + 311679750*x^128 + 1989860861*x^127 + 1551409650*x^126 + 2188452501*x^125 + 1175930901*x^124 + 1991529213*x^123 + 2019090583*x^122 + 215965300*x^121 + 532432639*x^120 + 1148806816*x^119 + 493362403*x^118 + 2166920790*x^117 + 185609624*x^116 + 184370704*x^115 + 2141702861*x^114 + 223551915*x^113 + 298497455*x^112 + 722376028*x^111 + 678813029*x^110 + 915121681*x^109 + 1107871854*x^108 + 1369194845*x^107 + 328165402*x^106 + 1792110161*x^105 + 798151427*x^104 + 954952187*x^103 + 471555401*x^102 + 68969853*x^101 + 453598910*x^100 + 2458706380*x^99 + 889221741*x^98 + 320515821*x^97 + 1549538476*x^96 + 909607400*x^95 + 499973742*x^94 + 552728308*x^93 + 1538610725*x^92 + 186272117*x^91 + 862153635*x^90 + 981463824*x^89 + 2400233482*x^88 + 1742475067*x^87 + 437801940*x^86 + 1504315277*x^85 + 1756497351*x^84 + 197089583*x^83 + 2082285292*x^82 + 109369793*x^81 + 2197572728*x^80 + 107235697*x^79 + 567322310*x^78 + 1755205142*x^77 + 1089091449*x^76 + 1993836978*x^75 + 2393709429*x^74 + 170647828*x^73 + 1205814501*x^72 + 2444570340*x^71 + 328372190*x^70 + 1929704306*x^69 + 717796715*x^68 + 1057597610*x^67 + 482243092*x^66 + 277530014*x^65 + 2393168828*x^64 + 12380707*x^63 + 1108646500*x^62 + 637721571*x^61 + 604983755*x^60 + 1142068056*x^59 + 1911643955*x^58 + 1713852330*x^57 + 1757273231*x^56 + 1778819295*x^55 + 957146826*x^54 + 900005615*x^53 + 521467961*x^52 + 1255707235*x^51 + 861871574*x^50 + 397953653*x^49 + 1259753202*x^48 + 471431762*x^47 + 1245956917*x^46 + 1688297180*x^45 + 1536178591*x^44 + 1833258462*x^43 + 1369087493*x^42 + 459426544*x^41 + 418389643*x^40 + 1800239647*x^39 + 2467433889*x^38 + 477713059*x^37 + 1898813986*x^36 + 2202042708*x^35 + 894088738*x^34 + 1204601190*x^33 + 1592921228*x^32 + 2234027582*x^31 + 1308900201*x^30 + 461430959*x^29 + 718926726*x^28 + 2081988029*x^27 + 1337342428*x^26 + 2039153142*x^25 + 1364177470*x^24 + 613659517*x^23 + 853968854*x^22 + 1013582418*x^21 + 1167857934*x^20 + 2014147362*x^19 + 1083466865*x^18 + 1091690302*x^17 + 302196939*x^16 + 1946675573*x^15 + 2450124113*x^14 + 1199066291*x^13 + 401889502*x^12 + 712045611*x^11 + 1850096904*x^10 + 1808400208*x^9 + 1567687877*x^8 + 2013445952*x^7 + 2435360770*x^6 + 2414019676*x^5 + 2277377050*x^4 + 2148341337*x^3 + 1073721716*x^2 + 1045363399*x + 1809685811

m^0x10001%N:  
922927962*x^254 + 1141958714*x^253 + 295409606*x^252 + 1197491798*x^251 + 2463440866*x^250 + 1671460946*x^249 + 967543123*x^248 + 119796323*x^247 + 1172760592*x^246 + 770640267*x^245 + 1093816376*x^244 + 196379610*x^243 + 2205270506*x^242 + 459693142*x^241 + 829093322*x^240 + 816440689*x^239 + 648546871*x^238 + 1533372161*x^237 + 1349964227*x^236 + 2132166634*x^235 + 403690250*x^234 + 835793319*x^233 + 2056945807*x^232 + 480459588*x^231 + 1401028924*x^230 + 2231055325*x^229 + 1716893325*x^228 + 16299164*x^227 + 1125072063*x^226 + 1903340994*x^225 + 1372971897*x^224 + 242927971*x^223 + 711296789*x^222 + 535407256*x^221 + 976773179*x^220 + 533569974*x^219 + 501041034*x^218 + 326232105*x^217 + 2248775507*x^216 + 1010397596*x^215 + 1641864795*x^214 + 1365178317*x^213 + 1038477612*x^212 + 2201213637*x^211 + 760847531*x^210 + 2072085932*x^209 + 168159257*x^208 + 70202009*x^207 + 1193933930*x^206 + 1559162272*x^205 + 1380642174*x^204 + 1296625644*x^203 + 1338288152*x^202 + 843839510*x^201 + 460174838*x^200 + 660412151*x^199 + 716865491*x^198 + 772161222*x^197 + 924177515*x^196 + 1372790342*x^195 + 320044037*x^194 + 117027412*x^193 + 814803809*x^192 + 1175035545*x^191 + 244769161*x^190 + 2116927976*x^189 + 617780431*x^188 + 342577832*x^187 + 356586691*x^186 + 695795444*x^185 + 281750528*x^184 + 133432552*x^183 + 741747447*x^182 + 2138036298*x^181 + 524386605*x^180 + 1231287380*x^179 + 1246706891*x^178 + 69277523*x^177 + 2124927225*x^176 + 2334697345*x^175 + 1769733543*x^174 + 2248037872*x^173 + 1899902290*x^172 + 409421149*x^171 + 1223261878*x^170 + 666594221*x^169 + 1795456341*x^168 + 406003299*x^167 + 992699270*x^166 + 2201384104*x^165 + 907692883*x^164 + 1667882231*x^163 + 1414341647*x^162 + 1592159752*x^161 + 28054099*x^160 + 2184618098*x^159 + 2047102725*x^158 + 103202495*x^157 + 1803852525*x^156 + 446464179*x^155 + 909116906*x^154 + 1541693644*x^153 + 166545130*x^152 + 2283548843*x^151 + 2348768005*x^150 + 71682607*x^149 + 484339546*x^148 + 669511666*x^147 + 2110974006*x^146 + 1634563992*x^145 + 1810433926*x^144 + 2388805064*x^143 + 1200258695*x^142 + 1555191384*x^141 + 363842947*x^140 + 1105757887*x^139 + 402111289*x^138 + 361094351*x^137 + 1788238752*x^136 + 2017677334*x^135 + 1506224550*x^134 + 648916609*x^133 + 2008973424*x^132 + 2452922307*x^131 + 1446527028*x^130 + 29659632*x^129 + 627390142*x^128 + 1695661760*x^127 + 734686497*x^126 + 227059690*x^125 + 1219692361*x^124 + 635166359*x^123 + 428703291*x^122 + 2334823064*x^121 + 204888978*x^120 + 1694957361*x^119 + 94211180*x^118 + 2207723563*x^117 + 872340606*x^116 + 46197669*x^115 + 710312088*x^114 + 305132032*x^113 + 1621042631*x^112 + 2023404084*x^111 + 2169254305*x^110 + 463525650*x^109 + 2349964255*x^108 + 626689949*x^107 + 2072533779*x^106 + 177264308*x^105 + 153948342*x^104 + 1992646054*x^103 + 2379817214*x^102 + 1396334187*x^101 + 2254165812*x^100 + 1300455472*x^99 + 2396842759*x^98 + 2398953180*x^97 + 88249450*x^96 + 1726340322*x^95 + 2004986735*x^94 + 2446249940*x^93 + 520126803*x^92 + 821544954*x^91 + 1177737015*x^90 + 676286546*x^89 + 1519043368*x^88 + 224894464*x^87 + 1742023262*x^86 + 142627164*x^85 + 1427710141*x^84 + 1504189919*x^83 + 688315682*x^82 + 1397842239*x^81 + 435187331*x^80 + 433176780*x^79 + 454834357*x^78 + 1046713282*x^77 + 1208458516*x^76 + 811240741*x^75 + 151611952*x^74 + 164192249*x^73 + 353336244*x^72 + 1779538914*x^71 + 1489144873*x^70 + 213140082*x^69 + 1874778522*x^68 + 908618863*x^67 + 1058334731*x^66 + 1706255211*x^65 + 708134837*x^64 + 1382118347*x^63 + 2111915733*x^62 + 1273497300*x^61 + 368639880*x^60 + 1652005004*x^59 + 1977610754*x^58 + 1412680185*x^57 + 2312775720*x^56 + 59793381*x^55 + 1345145822*x^54 + 627534850*x^53 + 2159477761*x^52 + 10450988*x^51 + 1479007796*x^50 + 2082579205*x^49 + 1158447154*x^48 + 126359830*x^47 + 393411272*x^46 + 2343384236*x^45 + 2191577465*x^44 + 1281188680*x^43 + 230049708*x^42 + 539600199*x^41 + 1711135601*x^40 + 1659775448*x^39 + 1716176055*x^38 + 904363231*x^37 + 2385749710*x^36 + 567278351*x^35 + 404199078*x^34 + 372670353*x^33 + 1286079784*x^32 + 1744355671*x^31 + 2316856064*x^30 + 2106475476*x^29 + 614988454*x^28 + 2149964943*x^27 + 1065233185*x^26 + 188130174*x^25 + 540415659*x^24 + 1031409799*x^23 + 1067085678*x^22 + 1005161755*x^21 + 249654085*x^20 + 1816791634*x^19 + 1437500292*x^18 + 448596413*x^17 + 2397497659*x^16 + 2353732701*x^15 + 2068949189*x^14 + 1826419168*x^13 + 1265366199*x^12 + 547031306*x^11 + 1016962374*x^10 + 160089486*x^9 + 2264803979*x^8 + 1081806194*x^7 + 824215340*x^6 + 497731793*x^5 + 45017166*x^4 + 317548920*x^3 + 1391127733*x^2 + 1752881284*x + 1290424106

起初的想法是x = 2，但是经过验证不是这样的，不然怎么会叫作不同寻常的RSA呢。看了下别人的博客，里面说是基于多项式的RSA。推导如下：

考虑g(m)与g(n)互素，这样就会有：

参考：https://xz.aliyun.com/t/4545

在求解的过程中，注意φ(n)的计算，并不是通常的φ(n)的计算公式。多项式中每一项都与n互素，而欧拉函数是小于n的与n互素的正整数的个数，所以φ(n) = p ^ 最高次 - 1。sage脚本如下：

p= 2470567871
P = PolynomialRing(Zmod(p), name = 'x')
x = P.gen()
e = 65537
n = 1932231392*x^255 + 1432733708*x^254 + 1270867914*x^253 + 1573324635*x^252 + 2378103997*x^251 + 820889786*x^250 + 762279735*x^249 + 1378353578*x^248 + 1226179520*x^247 + 657116276*x^246 + 1264717357*x^245 + 1015587392*x^244 + 849699356*x^243 + 1509168990*x^242 + 2407367106*x^241 + 873379233*x^240 + 2391647981*x^239 + 517715639*x^238 + 828941376*x^237 + 843708018*x^236 + 1526075137*x^235 + 1499291590*x^234 + 235611028*x^233 + 19615265*x^232 + 53338886*x^231 + 434434839*x^230 + 902171938*x^229 + 516444143*x^228 + 1984443642*x^227 + 966493372*x^226 + 1166227650*x^225 + 1824442929*x^224 + 930231465*x^223 + 1664522302*x^222 + 1067203343*x^221 + 28569139*x^220 + 2327926559*x^219 + 899788156*x^218 + 296985783*x^217 + 1144578716*x^216 + 340677494*x^215 + 254306901*x^214 + 766641243*x^213 + 1882320336*x^212 + 2139903463*x^211 + 1904225023*x^210 + 475412928*x^209 + 127723603*x^208 + 2015416361*x^207 + 1500078813*x^206 + 1845826007*x^205 + 797486240*x^204 + 85924125*x^203 + 1921772796*x^202 + 1322682658*x^201 + 2372929383*x^200 + 1323964787*x^199 + 1302258424*x^198 + 271875267*x^197 + 1297768962*x^196 + 2147341770*x^195 + 1665066191*x^194 + 2342921569*x^193 + 1450622685*x^192 + 1453466049*x^191 + 1105227173*x^190 + 2357717379*x^189 + 1044263540*x^188 + 697816284*x^187 + 647124526*x^186 + 1414769298*x^185 + 657373752*x^184 + 91863906*x^183 + 1095083181*x^182 + 658171402*x^181 + 75339882*x^180 + 2216678027*x^179 + 2208320155*x^178 + 1351845267*x^177 + 1740451894*x^176 + 1302531891*x^175 + 320751753*x^174 + 1303477598*x^173 + 783321123*x^172 + 1400145206*x^171 + 1379768234*x^170 + 1191445903*x^169 + 946530449*x^168 + 2008674144*x^167 + 2247371104*x^166 + 1267042416*x^165 + 1795774455*x^164 + 1976911493*x^163 + 167037165*x^162 + 1848717750*x^161 + 573072954*x^160 + 1126046031*x^159 + 376257986*x^158 + 1001726783*x^157 + 2250967824*x^156 + 2339380314*x^155 + 571922874*x^154 + 961000788*x^153 + 306686020*x^152 + 80717392*x^151 + 2454799241*x^150 + 1005427673*x^149 + 1032257735*x^148 + 593980163*x^147 + 1656568780*x^146 + 1865541316*x^145 + 2003844061*x^144 + 1265566902*x^143 + 573548790*x^142 + 494063408*x^141 + 1722266624*x^140 + 938551278*x^139 + 2284832499*x^138 + 597191613*x^137 + 476121126*x^136 + 1237943942*x^135 + 275861976*x^134 + 1603993606*x^133 + 1895285286*x^132 + 589034062*x^131 + 713986937*x^130 + 1206118526*x^129 + 311679750*x^128 + 1989860861*x^127 + 1551409650*x^126 + 2188452501*x^125 + 1175930901*x^124 + 1991529213*x^123 + 2019090583*x^122 + 215965300*x^121 + 532432639*x^120 + 1148806816*x^119 + 493362403*x^118 + 2166920790*x^117 + 185609624*x^116 + 184370704*x^115 + 2141702861*x^114 + 223551915*x^113 + 298497455*x^112 + 722376028*x^111 + 678813029*x^110 + 915121681*x^109 + 1107871854*x^108 + 1369194845*x^107 + 328165402*x^106 + 1792110161*x^105 + 798151427*x^104 + 954952187*x^103 + 471555401*x^102 + 68969853*x^101 + 453598910*x^100 + 2458706380*x^99 + 889221741*x^98 + 320515821*x^97 + 1549538476*x^96 + 909607400*x^95 + 499973742*x^94 + 552728308*x^93 + 1538610725*x^92 + 186272117*x^91 + 862153635*x^90 + 981463824*x^89 + 2400233482*x^88 + 1742475067*x^87 + 437801940*x^86 + 1504315277*x^85 + 1756497351*x^84 + 197089583*x^83 + 2082285292*x^82 + 109369793*x^81 + 2197572728*x^80 + 107235697*x^79 + 567322310*x^78 + 1755205142*x^77 + 1089091449*x^76 + 1993836978*x^75 + 2393709429*x^74 + 170647828*x^73 + 1205814501*x^72 + 2444570340*x^71 + 328372190*x^70 + 1929704306*x^69 + 717796715*x^68 + 1057597610*x^67 + 482243092*x^66 + 277530014*x^65 + 2393168828*x^64 + 12380707*x^63 + 1108646500*x^62 + 637721571*x^61 + 604983755*x^60 + 1142068056*x^59 + 1911643955*x^58 + 1713852330*x^57 + 1757273231*x^56 + 1778819295*x^55 + 957146826*x^54 + 900005615*x^53 + 521467961*x^52 + 1255707235*x^51 + 861871574*x^50 + 397953653*x^49 + 1259753202*x^48 + 471431762*x^47 + 1245956917*x^46 + 1688297180*x^45 + 1536178591*x^44 + 1833258462*x^43 + 1369087493*x^42 + 459426544*x^41 + 418389643*x^40 + 1800239647*x^39 + 2467433889*x^38 + 477713059*x^37 + 1898813986*x^36 + 2202042708*x^35 + 894088738*x^34 + 1204601190*x^33 + 1592921228*x^32 + 2234027582*x^31 + 1308900201*x^30 + 461430959*x^29 + 718926726*x^28 + 2081988029*x^27 + 1337342428*x^26 + 2039153142*x^25 + 1364177470*x^24 + 613659517*x^23 + 853968854*x^22 + 1013582418*x^21 + 1167857934*x^20 + 2014147362*x^19 + 1083466865*x^18 + 1091690302*x^17 + 302196939*x^16 + 1946675573*x^15 + 2450124113*x^14 + 1199066291*x^13 + 401889502*x^12 + 712045611*x^11 + 1850096904*x^10 + 1808400208*x^9 + 1567687877*x^8 + 2013445952*x^7 + 2435360770*x^6 + 2414019676*x^5 + 2277377050*x^4 + 2148341337*x^3 + 1073721716*x^2 + 1045363399*x + 1809685811
c = 922927962*x^254 + 1141958714*x^253 + 295409606*x^252 + 1197491798*x^251 + 2463440866*x^250 + 1671460946*x^249 + 967543123*x^248 + 119796323*x^247 + 1172760592*x^246 + 770640267*x^245 + 1093816376*x^244 + 196379610*x^243 + 2205270506*x^242 + 459693142*x^241 + 829093322*x^240 + 816440689*x^239 + 648546871*x^238 + 1533372161*x^237 + 1349964227*x^236 + 2132166634*x^235 + 403690250*x^234 + 835793319*x^233 + 2056945807*x^232 + 480459588*x^231 + 1401028924*x^230 + 2231055325*x^229 + 1716893325*x^228 + 16299164*x^227 + 1125072063*x^226 + 1903340994*x^225 + 1372971897*x^224 + 242927971*x^223 + 711296789*x^222 + 535407256*x^221 + 976773179*x^220 + 533569974*x^219 + 501041034*x^218 + 326232105*x^217 + 2248775507*x^216 + 1010397596*x^215 + 1641864795*x^214 + 1365178317*x^213 + 1038477612*x^212 + 2201213637*x^211 + 760847531*x^210 + 2072085932*x^209 + 168159257*x^208 + 70202009*x^207 + 1193933930*x^206 + 1559162272*x^205 + 1380642174*x^204 + 1296625644*x^203 + 1338288152*x^202 + 843839510*x^201 + 460174838*x^200 + 660412151*x^199 + 716865491*x^198 + 772161222*x^197 + 924177515*x^196 + 1372790342*x^195 + 320044037*x^194 + 117027412*x^193 + 814803809*x^192 + 1175035545*x^191 + 244769161*x^190 + 2116927976*x^189 + 617780431*x^188 + 342577832*x^187 + 356586691*x^186 + 695795444*x^185 + 281750528*x^184 + 133432552*x^183 + 741747447*x^182 + 2138036298*x^181 + 524386605*x^180 + 1231287380*x^179 + 1246706891*x^178 + 69277523*x^177 + 2124927225*x^176 + 2334697345*x^175 + 1769733543*x^174 + 2248037872*x^173 + 1899902290*x^172 + 409421149*x^171 + 1223261878*x^170 + 666594221*x^169 + 1795456341*x^168 + 406003299*x^167 + 992699270*x^166 + 2201384104*x^165 + 907692883*x^164 + 1667882231*x^163 + 1414341647*x^162 + 1592159752*x^161 + 28054099*x^160 + 2184618098*x^159 + 2047102725*x^158 + 103202495*x^157 + 1803852525*x^156 + 446464179*x^155 + 909116906*x^154 + 1541693644*x^153 + 166545130*x^152 + 2283548843*x^151 + 2348768005*x^150 + 71682607*x^149 + 484339546*x^148 + 669511666*x^147 + 2110974006*x^146 + 1634563992*x^145 + 1810433926*x^144 + 2388805064*x^143 + 1200258695*x^142 + 1555191384*x^141 + 363842947*x^140 + 1105757887*x^139 + 402111289*x^138 + 361094351*x^137 + 1788238752*x^136 + 2017677334*x^135 + 1506224550*x^134 + 648916609*x^133 + 2008973424*x^132 + 2452922307*x^131 + 1446527028*x^130 + 29659632*x^129 + 627390142*x^128 + 1695661760*x^127 + 734686497*x^126 + 227059690*x^125 + 1219692361*x^124 + 635166359*x^123 + 428703291*x^122 + 2334823064*x^121 + 204888978*x^120 + 1694957361*x^119 + 94211180*x^118 + 2207723563*x^117 + 872340606*x^116 + 46197669*x^115 + 710312088*x^114 + 305132032*x^113 + 1621042631*x^112 + 2023404084*x^111 + 2169254305*x^110 + 463525650*x^109 + 2349964255*x^108 + 626689949*x^107 + 2072533779*x^106 + 177264308*x^105 + 153948342*x^104 + 1992646054*x^103 + 2379817214*x^102 + 1396334187*x^101 + 2254165812*x^100 + 1300455472*x^99 + 2396842759*x^98 + 2398953180*x^97 + 88249450*x^96 + 1726340322*x^95 + 2004986735*x^94 + 2446249940*x^93 + 520126803*x^92 + 821544954*x^91 + 1177737015*x^90 + 676286546*x^89 + 1519043368*x^88 + 224894464*x^87 + 1742023262*x^86 + 142627164*x^85 + 1427710141*x^84 + 1504189919*x^83 + 688315682*x^82 + 1397842239*x^81 + 435187331*x^80 + 433176780*x^79 + 454834357*x^78 + 1046713282*x^77 + 1208458516*x^76 + 811240741*x^75 + 151611952*x^74 + 164192249*x^73 + 353336244*x^72 + 1779538914*x^71 + 1489144873*x^70 + 213140082*x^69 + 1874778522*x^68 + 908618863*x^67 + 1058334731*x^66 + 1706255211*x^65 + 708134837*x^64 + 1382118347*x^63 + 2111915733*x^62 + 1273497300*x^61 + 368639880*x^60 + 1652005004*x^59 + 1977610754*x^58 + 1412680185*x^57 + 2312775720*x^56 + 59793381*x^55 + 1345145822*x^54 + 627534850*x^53 + 2159477761*x^52 + 10450988*x^51 + 1479007796*x^50 + 2082579205*x^49 + 1158447154*x^48 + 126359830*x^47 + 393411272*x^46 + 2343384236*x^45 + 2191577465*x^44 + 1281188680*x^43 + 230049708*x^42 + 539600199*x^41 + 1711135601*x^40 + 1659775448*x^39 + 1716176055*x^38 + 904363231*x^37 + 2385749710*x^36 + 567278351*x^35 + 404199078*x^34 + 372670353*x^33 + 1286079784*x^32 + 1744355671*x^31 + 2316856064*x^30 + 2106475476*x^29 + 614988454*x^28 + 2149964943*x^27 + 1065233185*x^26 + 188130174*x^25 + 540415659*x^24 + 1031409799*x^23 + 1067085678*x^22 + 1005161755*x^21 + 249654085*x^20 + 1816791634*x^19 + 1437500292*x^18 + 448596413*x^17 + 2397497659*x^16 + 2353732701*x^15 + 2068949189*x^14 + 1826419168*x^13 + 1265366199*x^12 + 547031306*x^11 + 1016962374*x^10 + 160089486*x^9 + 2264803979*x^8 + 1081806194*x^7 + 824215340*x^6 + 497731793*x^5 + 45017166*x^4 + 317548920*x^3 + 1391127733*x^2 + 1752881284*x + 1290424106

q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]

phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, phi) == 1
d = inverse_mod(e, phi)
m = pow(c,d,n)

flag = bytes(m.coefficients())
print("Flag: ", flag.decode())

funnyrsa1

题目如下：

e1 = 14606334023791426
p1 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1 = 130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1 = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2 = 13813369129257838
p2 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2 = 94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2 = 7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919

首先看到两个e都不是素数，直接上factordb，两个可以分解为：

14606334023791426 = 2 * 7 * 1043309573127959
13813369129257838 = 2 * 7 * 986669223518417

原本的想法是先求出m^14，再对m开14次方，但指数过大，这个方法是不合理的。题目既然给了两组数据，自然有它的道理。仔细观察发现p1是一样的，又有两组n和e，联想到中国剩余定理， 巧妙之处在于可以把n1和n2拆开，构造出同余方程组，求解m。：

但是这题不能使用：

因为14依然和phin有公约数，所以我们要构造出与14互素的数，参考博客中说到在上面的三个同余方程中的最后两个方程可以合并成：

这样就变成了新的RSA解密了，注意最后的e依然不是素数开拆成：2 * 7，最后开平方就是m，脚本如下：

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

def CRT(a_list, m_list):
    M = 1
    for i in range(len(m_list)):
        M *= m_list[i]

    x = 0
    for i in range(len(m_list)):
        Mi = M // m_list[i]
        M_inverse = inverse(Mi, m_list[i])
        x += a_list[i] * M_inverse * Mi
    x %= M
    return x

e1 = 14606334023791426
p1 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1 = 130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1 = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2 = 13813369129257838
p2 = 121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2 = 94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2 = 7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919

phin1 = (p1 - 1) * (q1 - 1)
tmp = gmpy2.gcd(e1, e2)
e1 = e1// tmp
d = invmod(e1, phin1)
plainer1 = pow(c1, d, p1 * q1)

phin2 = (p2 - 1) * (q2 - 1)
e2 = e2// tmp
d = invmod(e2, phin2)
plainer2 = pow(c2, d, p2 * q2)

m3 = plainer1 % (p1 * q1)
m2 = plainer2 % (p2 * q2)
m1 = plainer1 % q1
alist = [m1, m2, m3]
mlist = [q1, q2, p1]
m = CRT(alist, mlist)

n = q1 * q2
phin3 = (q1 - 1) * (q2 - 1)
d = invmod(7, phin3)
m = pow(m, d, n)
print(long_to_bytes(gmpy2.iroot(m, 2)[0]))

[De1CTF2019]babyrsa

题目如下：

import binascii
from data import e1,e2,p,q1p,q1q,hint,flag

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)

ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))

flag=int(binascii.hexlify(flag),16)
q1=q1p
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

看到最后的加密算法，用到了e1、e2、p、q1、q2等需要求解的数。首先看看p怎么求的吧，map函数将参数应用到f函数，相当于有4个p^4 %n = c，所以这里用到的是中国剩余定理。

转到第二段的e1和e2的加密算法，c1比n小数十个数量级，有可能是因为e1的42次方很小导致模n没有效果，所以直接对c1开42次方。ee2很小，直接用低加密指数攻击获取(e2+tmp)。

看到第三段加密算法，q1q和q1p相乘得到n，对n进行分解就可以得到了。hint内容：orz…you.found.me.but.sorry.no.hint…keep.on.and.enjoy.it!

来到最后一关，前面得到的e1和e2都不是素数，对它们进行分解后是2 x 7 x。。。，下面又只有两个密文，所以它的特征符合RSA相关信息攻击。前几天做到的funnyrsa2就是这种题型，所以可以直接引用前面做过的脚本，完整的脚本如下：

from Crypto.Util.number import *
import gmpy2

def CRT(a_list, m_list):
    M = 1
    for i in range(len(m_list)):
        M *= m_list[i]

    x = 0
    for i in range(len(m_list)):
        Mi = M // m_list[i]
        Mi_inverse = inverse(Mi, m_list[i])
        x += a_list[i] * Mi * Mi_inverse
    x %= M
    return x

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797]
p = gmpy2.iroot(CRT(c, n), 4)[0]

e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
q1p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
q1q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693
phin1 = (q1p - 1) * (q1q - 1)
d = inverse(e, phin1)
m = pow(c, d, n)
print(long_to_bytes(m))

ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
e1 = gmpy2.iroot(ce1, ee1)[0]
#print(m1[0])
#15218928658178
k = 0
while 1:
    ans = gmpy2.iroot(k * n + ce2, ee2)
    if(ans[1] == True):
        sum = ans[0]
        break
    k += 1
sum = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449290342499311738517
e2 = sum - tmp
#print(e2)
#381791429275130

q1 = q1p
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596

assert(gmpy2.gcd(e1, (p - 1) * (q1 - 1)) == gmpy2.gcd(e2, (p - 1) * (q2 - 1)))

tmp = gmpy2.gcd(e1, (p - 1) * (q1 - 1))
e1 = e1 // tmp
e2 = e2 // tmp
d1 = inverse(e1, (p - 1) * (q1 - 1))
d2 = inverse(e2, (p - 1) * (q2 - 1))
m1 = pow(c1, d1, p * q1)
m2 = pow(c2, d2, p * q2)

m3 = m1 % p
m2 = m2 % q2
m1 = m1 % q1
alist = [m1, m2, m3]
mlist = [q1, q2, p]
m = CRT(alist, mlist)

n = q1 * q2
phin = (q1 - 1) * (q2 - 1)
d = inverse(7, phin)
m = pow(m, d, n)
print(long_to_bytes(gmpy2.iroot(m, 2)[0]))

小二难度R54

题目如下：

todo:
x, y = [random_prime(2 ^ 1024 - 1, False, 2 ^ 1023) for _ in range(2)]
x * y, pow(2021 * x + 501 * y, x * y - x - y, x * y), pow(flag, 0o200001, x * y)
------------------------------------------------------------------------------------------------------------
gift:
[20947495659013288660808536751393787394664606045798093048128257278988208709333248671898749660848208653968668634891579612784633367362177864996602736258460476691940723323282467207875842974409286563660436709535601954405015261428106261369927836045794170912665351432105165546188591486357060490032334793140396757102052999128194027485573053073959574695808224922102635888141991154365047911830780778957642166757152369955362399379720841279167832886144458760347392316082994786119404006382441787685301119197529946566027319295285387108473752590621030421978808950305190250697199878929419723511578437404000924310974770501204226510397, 12911378830212711575909332427930495830030418987483519620282504671823307660633472092466534392403086505995560725428252134905285658936113891795434303336259751169171583600394870893708505805256284455729584616439559184469715186920464999723861722097244025658190194027561300165723184060071016117033960821040587421503448139025974851980482004179865110864844573575034406782936965166402665401330436229441569042660851847498727291447251591027480750458209012729510702196684303778564353025395186191064801000127420683298000173389589468742142444444759536629401472836827952997758216526858512433131954439154124668711408079361172485321041, 13390681135321846035598057088735733735860895610541899486616159864716324918810264721878447895634342127744578566110322466944217562868186608760962032192994397783118528288276520451944892998435079744244578731427626946331165523865930693902700790185275273534104979885060728696532991031786741950704918951536399577118136416956670893081637730646528913282395731901667720418372650030593319596584787752412110672058692368924987360383096340538971725402687347195347344826404005229912821371282465882351660619944919637382790572267512735645269618163597227604601321699186335016345484182059187046972681187078878556533926780789183784240737]

看到加密算法：

形式似于欧拉定理：

φ(n) = pq - p - q + 1，根据欧拉定理pow(2021 x + 501 y, x y - x - y，N)等于pow(2021 x + 501 y, -1，N)，那么把它求模N的逆就等于(2021 x + 501 y)。这样子，就有两个关于p和q的方程，使用z3求得p和q。脚本如下：

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

N, a, cipher = [20947495659013288660808536751393787394664606045798093048128257278988208709333248671898749660848208653968668634891579612784633367362177864996602736258460476691940723323282467207875842974409286563660436709535601954405015261428106261369927836045794170912665351432105165546188591486357060490032334793140396757102052999128194027485573053073959574695808224922102635888141991154365047911830780778957642166757152369955362399379720841279167832886144458760347392316082994786119404006382441787685301119197529946566027319295285387108473752590621030421978808950305190250697199878929419723511578437404000924310974770501204226510397, 12911378830212711575909332427930495830030418987483519620282504671823307660633472092466534392403086505995560725428252134905285658936113891795434303336259751169171583600394870893708505805256284455729584616439559184469715186920464999723861722097244025658190194027561300165723184060071016117033960821040587421503448139025974851980482004179865110864844573575034406782936965166402665401330436229441569042660851847498727291447251591027480750458209012729510702196684303778564353025395186191064801000127420683298000173389589468742142444444759536629401472836827952997758216526858512433131954439154124668711408079361172485321041, 13390681135321846035598057088735733735860895610541899486616159864716324918810264721878447895634342127744578566110322466944217562868186608760962032192994397783118528288276520451944892998435079744244578731427626946331165523865930693902700790185275273534104979885060728696532991031786741950704918951536399577118136416956670893081637730646528913282395731901667720418372650030593319596584787752412110672058692368924987360383096340538971725402687347195347344826404005229912821371282465882351660619944919637382790572267512735645269618163597227604601321699186335016345484182059187046972681187078878556533926780789183784240737]
aa = inverse(a, N)

p, q = Ints('p q')
sol = Solver()
sol.add(p * q == N)
sol.add(2021 * p + 501 * q == aa)
if (sol.check() == sat):
    print(sol.model())

p = 118025808013874567502972067396154378205921004159004592806833496003217679639841107629090128959992942958292926872941356148283178987927403535617729247751812776636333788905610726461255956234207606642302396722821445909489968841256943549868105578713493559907241758893208485830735235619636112619927867287431575647321
q = 177482332140024816122816575300851746457741976238942019223639223243373845838446387378093437677008231609976122718397287922224412805145965728166071230572137942154170172214953182121671014605624049869925600226560127948579957435119412752482229481128742488177414523194528098131635883615390771259266866469500527361157
phin = (p - 1) * (q - 1)
e = 0o200001
assert gmpy2.gcd(e, phin) == 1
d = inverse(e, phin)
m = pow(cipher, d, p * q)
print(long_to_bytes(m))

解得的还是一个密文：

emkkocy{lnyu_wp_kxs_kc_ahz_dvjg_by?}

前面几个字符是“ctfshow”，把对应字符的序号写在下面：

明文：

2  19  5  18  7  14  22

密文：

4  12  10 10  14  2  24

有的密文的字符序号比明文的字符序号小，说明经过了模运算，发现前六个字符正好是自己加上自己的序号模26，而第七个字符是加2后模26，与第一个字符加上的数字相同，猜测密钥是以6循环的密钥。脚本如下：

dic = {'0':'a','1':'b','2':'c','3':'d','4':'e','5':'f',
       '6':'g','7':'h','8':'i','9':'j','10':'k','11':'l',
       '12':'m','13':'n','14':'o','15':'p','16':'q','17':'r',
       '18':'s','19':'t','20':'u','21':'v','22':'w','23':'x',
       '24':'y','25':'z'}

redic = dict(map(lambda t:(t[1], t[0]), dic.items()))
cipher = "emkkocylnyuwpkxskcahzdvjgby"
key = [2, 19, 5, 18, 7, 14]
flag = ""
for i in range(len(cipher)):
    flag += dic[str((int(redic[cipher[i]]) - int(key[i % 6]))% 26)]
print(flag)
#ctfshow{sign_in_rsa_do_you_love_it?}
博客
Prev:
伽罗华域
Next:
传统加密技术
catalog
catalog
    •

    Copyright © 2019 - 2020 yuang01 | Powered by Hexo | Theme Bamboo

    Total visits： times |