>
>
unusual rsa和密码挑战writeup
vincent
直接贴的md也不知道格式咋样
[toc]
1. unusual rsa 系列
- 放在时至今日, 这几个考点应该说已经是常规范畴了
- 相关思路分析翅膀大佬博客有给出,详情可参考大佬博客
1.1. unusual rsa 1
- sorce
# ******************** # @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- Attacking RSA with small e by knowing parts of the message. coppersmith小e部分明文泄露攻击
- $假设已知m的高位为M, 未知部分x_0, 则m=M+x_0. 如果x_0满足|x_0|\le N{\frac{1}{e}}, 那么可在多项式时间内恢复出x_0$
- 事实上, $x_0$不局限于低位,中间位置也是可以的
- 本题$x_0为315位,明显小于上界(2048//3 = 682)$
- exp
#exp.sage #coding:utf-8 #已知明文的高位 #https://sagecell.sagemath.org n = e = 3 beta = 1 epsilon = 1/7 nbits = n.nbits() kbits = floor(nbits*(beta^2/e-epsilon)) mbar = 1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136 c = 6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819 print("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)) PR.<x> = PolynomialRing(Zmod(n)) f = (mbar + x)^e - c x0 = f.small_roots(X=2^kbits, beta=1)[0] m = int(mbar+x0) mhex = '%x'%m print('hex m = ',mhex) mhex = '0'*(len(mhex)%2)+mhex print('str m = ', bytes.fromhex(mhex))- 后记
- 在执行coppersmith已知明文泄露攻击时, 通常脚本会取$\epsilon=\frac{1}{7}$, 这时候sage的small_roots实际可恢复的$x_0上界为\frac{1}{2}N{\frac{\beta2}{\delta}-\epsilon}\approx \frac{1}{2}N{0.19}$
- 若使用sage中small_roots函数,在一定程度内通过减小epsilon的值, 可以提高上界大约到1/4左右(e=3), 如何达到paper里的1/e可能需要其它实现方法
1.2. unusual rsa 2
- source
# ******************** # @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- 首先求得x和y的值(简单,略)
x = [2,3] y = [4,11] - 可知实际上已知明文的两个线性关系对应的密文
- $m_1{17} = c_1\ mod\ N, m_1=2m+3$
- $m_2{17} = c_2\ mod\ N,m_2=4m+11$
- 使用FR相关攻击
- 首先考虑$m_2 = m_1+d（d已知）的情况$
- $m_1e = c_1\ mod\ N$
- $m_2e = (m_1+d)e =c_2\ mod\ N$
- 则多项式$f_1=x_1e - c_1\ mod\ N与f_2=(x_1+d)e-c_2\ mod\ N有共同的一个根m_1$
- 也就是有共同的因式$(x-m_1), 所以只需对f_1\ f_2求多项式gcd即可恢复出m_1$
- 然后考虑$m_2 = km_1+d（k,d已知）的情况$
- 由于RSA满足乘法同态,$不妨令m_1'=km_1,可先求c_1' = (m_1')e\ mod\ N = ((ke\ mod\ N)\cdot c_1)\ mod\ N$
- 问题转化为上述已知d的情况, $m_2=m_1'+d$
- 求得$m_1'之后, 乘上逆元即可恢复出m=k{-1}\cdot m_1'\ mod\ N$
- 问题还可以进一步扩展,这里不再展开
- exp过程:
- 由于$m_2 = 2m_1+5= (4m+6) +5$
- 可利用FR相关攻击求得$m_1'=4m+6,则m = (m_1'-6)\cdot 4{-1}\ mod\ N$
- exp:多项式求GCD的部分sage有现成的实现可以用，懒得开sage了，在Python里手写了一个
#exp.py #FR相关攻击 def related_message_attack(c1,c2, di, e,n): from Crypto.Util.number import GCD #展开(x+a)^e的系数,杨辉三角 def poly_coef(a, e): assert e >= 0 if e == 0: return 1 elif e == 1: return [1,1] else: res = [1] coe_prev = poly_coef(a, e-1) for i in range(len(coe_prev)-1): res.append(sum(coe_prev[i:i+2])) res.append(1) return res def poly_extend(a, e, n,c): coef = poly_coef(a, e) res = [a**i * coef[i] for i in range(len(coef))] res[-1] = res[-1] + c res = [x%n for x in res] return res #化首1 def poly_monic(pl,n): from gmpy2 import invert for p in pl: if p!=0: inv = invert(p,n) break return [int((x*inv)%n) for x in pl] #模运算,这部分写的不是很好,待优化 def poly_mod(pl1,pl2,n): from functools import reduce assert len(pl1) == len(pl2) pl1 = poly_monic(pl1,n) pl2 = poly_monic(pl2,n) for i in range(len(pl1)): if pl1[i] > pl2[i]: break elif pl1[i] < pl2[i]: return poly_mod(pl2,pl1,n) else: return 0 idx = -1 for i in range(len(pl1)): if pl1[i] == 1: idx = i break for i in range(idx,len(pl2)): if pl2[i] == 1: pl2 = pl2[:idx] + pl2[i:] pl2 += [0]*(len(pl1)-len(pl2)) break res = [] for i in range(len(pl1)): if pl2[i] == 0: res.append(pl1[i]) else: res.append(pl1[i]-pl2[i]) res = [int(x%n) for x in res] g = int(reduce(GCD,res)) if g > 1: res = [x//g for x in res] return res #最大公因式 def poly_gcd(pl1,pl2,n): while pl2 != 0: pl1,pl2 = pl2, poly_mod(pl1,pl2,n) pl1 = poly_monic(pl1,n) return pl1 #x^e-c1 #(x+di)^e-c2 pl1 = poly_extend(0,e,n,-c1) pl2 = poly_extend(di,e,n,-c2) pl_d = poly_gcd(pl1,pl2,n) #求得(x-m),所以取负数即为m m = n - pl_d[-1] return m def exp(): from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long n = 23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699 c1 = 10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841 c2 = 17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450 e = 17 c11 = (pow(2,e,n) * c1) % n diff = 5 m1 = related_message_attack(c11, c2, diff, e, n) print("4m+6 =", m1) m = (m1 - 6) * inverse(4,n) % n print(long_to_bytes(m)) if __name__ == '__main__': exp()1.3. unusual rsa 3
- 常规多项式rsa, 分解N求解,还没仔细研究
- exp
#多项式rsa def main(): p = 2470567871 R.<x> = PolynomialRing(GF(p)) 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 S.<x> = R.quotient(N) 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 P, Q = N.factor() P, Q = P[0], Q[0] phi = (p**P.degree()-1)*(p**Q.degree()-1) e = 0x10001 d = inverse_mod(e, phi) m = c^d m = "".join([chr(c) for c in m.list()]) print(m) if __name__ == '__main__': main()1.4. unusual rsa 4
- source
from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes from gmpy2 import invert from secret import flag m = bytes_to_long(flag) p = getPrime(1024) q = getPrime(1024) n = p*q print(invert(q,p)) e = 0x10001 d = invert(e,(p-1)*(q-1)) print(d) c = pow(m,e,n) print(c) #113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512 #27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137 #619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291- 分析过程大佬博客已经很详细,这里不再赘述,仅做简要分析
- 简单来说,就是已知$q{-1} mod\ p, 和d恢复p,q的攻击$,使用类似于已知n,e,d分解n的思路
- $设x=q{-1}\ mod\ p$
- $由\phi=(p-1)\cdot(q-1)=N - (p+q)+1$ , 模上p
- $\phi\ mod\ p = -q+1\ mod\ p$ , 乘以x,有
- $x\cdot\phi \equiv -xq + x \equiv -1+x\ mod\ p$
- 从而$x\phi-x+1\equiv0\ mod\ p,即 x\phi-x+1为p的倍数$
- 不妨令$k_p=x\cdot\phi-x+1$
- $对任意的g,(g,p)=1, 有g\phi \equiv1\ mod\ p\rightarrow (g\phi\ mod\ k_p) \equiv1\ mod\ p$
- $即(g\phi mod\ k_p)-1为p的倍数$,那么只需求得多个值,取GCD即可
- exp
from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes from gmpy2 import invert def exp(): from gmpy2 import gcd,next_prime e = 0x10001 x = 113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512 d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137 c = 619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291 ed = e*d for i in range(1,e-1): if (ed-1) % i == 0: phi = (ed-1)//i kp = x*phi - x + 1 tp = [] g = 3 for j in range(999): t = pow(g,phi,kp) - 1 if t > 0 and (t not in tp): tp.append(t) g = next_prime(g) if len(tp) >= 2: break if len(tp) >= 2: p = gcd(tp[0],tp[1]) print(i,'p = ',p) if gcd(x,p) != 1 or p < x: continue else: break q = invert(x,p) n = p*q m = pow(c,d,n) print(long_to_bytes(m)) if __name__ == '__main__': exp()1.5. unusual rsa 5
- 有限域开方的问题,AMM算法
- 求得所有mod p和mod q的根之后,使用剩余定理求出所有可能值
- 求单个根:
- $xe\equiv c\ mod\ p$其中p,e为素数
- $把p-1写成p-1=et\cdot s,(e,s)=1事实上当t=1时,可以很轻易的求出一个根$
- $若t=1, 则p-1=e\cdot s,(e,s)=1$
- $记\delta \equiv\ c\ mod\ p,则x{p-1}=x{es}\equiv \deltas \equiv 1\ mod\ p$
- $取\alpha=r{-1}\ mod\ s,则有s|(\alpha\cdot r-1)\rightarrow\alpha r-1=ks$
- $即\delta{\alpha r-1}\equiv 1\ mod\ p\rightarrow(\delta\alpha)r\equiv \delta\ mod\ p$
- $求得\delta\alpha即为一个根$
- 求所有的根:
- 利用上一步求出的一个根,记作$x_0$
- 取一些小素数$g \in {3,5,7....}(这里满足(g,p)=1即可,我比较习惯取小素数)$
- $求d=g{\frac{\phi}{e}}\ mod\ p, 显然de\equiv1\ mod\ p$
- 可知$x'\equiv x_0\cdot d\ mod\ q$也是满足$xe\equiv c\ mod\ p$的根
- 反复求不重复的e个根即可
- 本题中$e=20=22\cdot 5$
- 可先求5次方根,然后分别求两次2次方根
- 其实由于m足够小也没有填充,求完5次方根直接用iroot开4次方也可求出flag
- 后记:
- 其实当t>1时,也不复杂,paper里写的很清楚了,这里不再赘述分析,仅给出脚本
- exp:
#解剩余定理,r=[余数],m=[模数] def crt(r, m): from functools import reduce from Crypto.Util.number import inverse from operator import mul assert len(r) == len(m) M = reduce(lambda x,y:x*y, m) #M = [M//mi for mi in m] t = [inverse(M//x,x)*(M//x) for x in m] res = sum(map(mul,r,t)) % M return res #求解x^e = c mod p^order def nthRoot_amm(c,e,p,order=1): from gmpy2 import is_prime from Crypto.Util.number import getRandomRange, inverse, GCD assert is_prime(p) and is_prime(e) and (p-1)%e==0 cp = c%p**order if c>p**order else c phi = (p - 1) * p**(order-1) mod = p**order for i in range(9999): rho = getRandomRange(1, mod) if pow(rho, phi // e, mod) != 1: #print(f'i = {i}') break s = phi t = 0 while s % e == 0: s //= e t += 1 assert GCD(s, e) == 1 #print(f't = {t} ') alpha = inverse(e, s) a = pow(rho, s*e**(t-1), mod) b = pow(cp, e*alpha-1, mod) c = pow(rho, s, mod) h = 1 for i in range(1, t): d = pow(b, e**(t-1-i), mod) if d == 1: j = 0 else: j = e - next(filter(lambda x: pow(a,x,mod)==d, range(e))) b = b * pow(c, e*j, mod) % mod h = h * pow(c, j, mod) % mod c = pow(c, e, mod) root = pow(cp, alpha, mod) * h % mod #找到其它根 from gmpy2 import next_prime all_roots = set() all_roots.add(root) g = 3 while len(all_roots) < e: newRoot = root g = int(next_prime(g)) u = pow(g, phi//e, mod) for i in range(e-1): newRoot = (newRoot * u) % mod all_roots.add(newRoot) return list(all_roots) def expUnrsa5(): from Crypto.Util.number import GCD, long_to_bytes from itertools import product from gmpy2 import iroot e = 0x14 p = 733089589724903586073820965792963746076789390539824437962807679954808310072656817423828613938510684864567664345751164944269489647964227519307980688068059059377123391499328155025962198363435968318689113750910755244276996554328840879221120846257832190569086861774466785101694608744384540722995426474322431441 q = 771182695213910447650732428220054698293987458796864628535794956332865106301119308051373568460701145677164052375651484670636989109023957702790185901445649197004100341656188532246838220216919835415376078688888076677350412398198442910825884505318258393640994788407100699355386681624118606588957344077387058721 n = p*q c = 406314720119562590605554101860453913891646775958515375190169046313074168423687276987576196367702523895650602252851191274766072774312855212771035294337840170341052016067631007495713764510925931612800335613551752201920460877432379214684677593342046715833439574705829048358675771542989832566579493199671622475225225451781214904100440695928239014046619329247750637911015313431804069312072581674845078940868349474663382442540424342613429896445329365750444298236684237769335405534090013035238333534521759502103604033307768304224154383880727399879024077733935062478113298538634071453067782212909271392163928445051705642 print('gcd(e,p-1)',GCD(e,p-1)) print('gcd(e,q-1',GCD(e,q-1)) e1 = 5 cp1 = nthRoot_amm(c,e1,p) cq1 = nthRoot_amm(c,e1,q) cp1 = [nthRoot_amm(x,2,p) for x in cp1] cq1 = [nthRoot_amm(x,2,q) for x in cq1] mp = [] mq = [] for cp in cp1: for cpp in cp: mp.extend(nthRoot_amm(cpp,2,p)) for cq in cq1: for cqq in cq: mq.extend(nthRoot_amm(cqq,2,q)) for m1,m2 in product(mp,mq): m = crt([m1,m2],[p,q]) flag = long_to_bytes(m) if b'flag' in flag: print(flag) break if __name__ == '__main__': expUnrsa5()2. 密码挑战系列
2.1. 真·Beginner
- 这题还真没做出来
2.2. 真·guessguess
- 利用已知的部分明文,使用z3求出key,然后解密即可
2.3. Lousy RSA
- 盲猜flag格式为flag{.*}那么第一位为f第二位为l
- 利用同余关系求出r,然后逐位爆破即可
- 部分exp
ct = c[0] c0 = c[1] c1 = c[2] m0 = ord('f') m0 = pow(m0,3,n) m1 = ord('l') m1 = pow(m1,3,n) c0 = (c0 - pow(m0,3,n) - ct) * invert(3,n) * invert(m0,n) % n c1 = (c1 - pow(m1,3,n) - ct) * invert(3,n) * invert(m1,n) % n b0 = invert(m0,n) * m0**2 % n b1 = invert(m1,n) * m1**2 % n r = (c0 - c1) * invert(b0-b1,n) % n2.4. Not That Right Use
- 做出来之后发现可能是非预期解,因为flag为
flag{NTRU_..........} - 这里分享下我的解法
- 分析可知,解密的关键在于f和g必须小于一定的值,从而使得gr+mf<q
- 只要f和g足够小,就可以完成解密,并不需要使用加密时候的值
- f,h,g,q四个数满足关系:
- $f\cdot h = g\ mod\ q$
- h和q是已知确定的
- 可以通过辗转取余的方法,来约束g的值,从而求出f的值
- 部分exp
s = q % h g = h % s for i in range(10000): g, s = g%s, s%g if g <2**4000: print(i) break f = h * gmpy2.invert(g,q) % q f = gmpy2.invert(f,q) d = gmpy2.gcd(f,g) assert d == 1 flen = len(f"{f:b}") print('flen =',flen) print(decrypt(c,f,g,h,q))2.5. so Damn big e?
- 这里走了不少弯路
- e除了过小意外,e再大都是没有攻击方式的,有攻击方式只可能是d出了问题
- 这题三组n,e,c根据提示, 为共享d攻击
- 没仔细研究,直接抄的脚本
- 部分exp
#sage n = [n0,n1,n2] e = [e0,e1,e2] c = [c0,c1,c2] M = isqrt(max(n)) A = Matrix(ZZ, len(e) + 1, len(e) + 1) A[0] = [M] + e for i in range(len(e)): A[i + 1, i + 1] = -n[i] AL = A.BKZ() d = abs(AL[0, 0]) // M print(f'found d with {d.nbits()} bits') print(long_to_bytes(pow(c[0], d, n[0])))2.6. Hammingway
- 直接爆破翻转, parity一致即为正确的值
- 部分exp
def unparity(slist): res = '' res = [slist[2]] + slist[4:7] + slist[8:] return ''.join(res) def strparity(slist): for i in [0,1,3,7]: slist[i] = '0' parity = reduce(lambda a, b: a^b, [j+1 for j, bit in enumerate(slist) if int(bit)]) parity = list(reversed(list(str(format(parity, "04b"))))) return parity def exp(): from itertools import product c = open("enc", "r").read() c = [list(c[i:i+15]) for i in range(0,len(c),15)] strBin = '' for cc in c: for idx in range(len(cc)): flip_cc = cc.copy() flip_cc[idx] = str(1^int(flip_cc[idx])) p1 = flip_cc[:2] + [flip_cc[3]] + [flip_cc[7]] p2 = strparity(flip_cc) if p1 == p2: strBin +=unparity(flip_cc) break plain_str = ''.join([chr(int(strBin[i:i+8],2)) for i in range(0,len(strBin),8)]) print(plain_str) if __name__ == '__main__': exp()2.7. o
- 简单,略
2.8. rsa-rsa-rsa-rsa
- 这题可能也是非预期解
- 直接套的类似d泄露的方法,解同余方程组, 感觉有点傻
- 四个方程跑出来几分钟到一个小时不等..
- 主要也是太菜了,没想到别的更好的方法
- 部分exp
#sage def find_p(d0, kbits, e, n,r=1): X = var('X') nn = n//r assert nn * r == n for k in range(1, e+1): results = solve_mod([e*d0*X - k*(r-1)*(nn*X-X^2-nn+X) == X], 2^kbits) #results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)#p700*q1400 #results = solve_mod([e*d0*X - k*(X*nn-nn-X^2+X)*(r-1)== X], 2^kbits) for x in results: p0 = ZZ(x[0]) print(k,'p0 = ',p0.nbits(),gcd(p0,nn)) if gcd(p0,nn) != 1: return p0 if __name__ == '__main__': e = 1667 c = 4863472644674217870502565424693713184000486927536995099651919590240866271469253214344182197334842137507506086858073884082195321114866653889949375924127756080834433032454456087411507323678798402153608823661022078160023141062260191255620270915331691502139415828179122879192294099884444457864136735926806260011876510858736421882145300532909608975279197160825647548849553174913916658119199697996174288038879828745214652265872117421930778762203853307243931789294163101430752597851152391642867666313642265617715322464199460030394197177929755093316075034884004768661209784916266357741690678348488199658622049287166258613947571770322996041 beta = 0.5 n = 3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591 r = 304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421 d0 = 6868327978266104802989981973163703169084555636189784576185238791210063194494388661448473806872716472633244760268088234379444819398858802986829208689016378717268858566806477769143597241086404105945418733687540225015490422345056492001144261514258758982987176876603622870246393409441550222724784227760607803005148775595 d0 = d0 % 2**700 nbits = n.nbits() kbits = d0.nbits() #kbits = 1050 print("lower %d bits (of %d bits) is given" % (kbits, nbits)) p = int(find_p(d0, kbits, e, n,r)) print("found p: %d" % p)2.9. EasyBits
- 这题本身的逻辑倒是不难
- 只是分解密文的时候factordb有一个大合数没有分解成功,需要使用yafu本地分解,小跑一段时间即可
- 部分exp
-def baseTx(n,base): res = [] for i in range(9999): a = n % base b = n//base res.append(a) n = b if n == 0: break return res[::-1] def getstr(sq): sq0, sq1 = sq res = [] for i in range(len(sq0)): res.append(sq0[i]) if i < len(sq1): res.append(sq1[i]) if len(sq1) > len(sq0): res.append(sq1[-1]) res_bin = '' bin_str = 0 for r in res: res_bin += str(bin_str)*r bin_str ^= 1 return ''.join([chr(int(res_bin[i:i+8],2)) for i in range(0,len(res_bin),8)]) c0 = open('ciphertext','rb').read() c0 = bytes_to_long(c0) from operator import mul clist = c = reduce(mul,clist) print(c==c0) from itertools import combinations,product for k in range(1,len(clist)): for sq in combinations(clist,k): n0 = reduce(mul,sq) n1 = c//n0 for n0_base,n1_base in product(range(5,8),range(5,8)): sq = [baseTx(n0,n0_base),baseTx(n1,n1_base)] flag = getstr(sq) if checkflag(flag): print('find flag',flag)
- 做出来之后发现可能是非预期解,因为flag为
- 这题还真没做出来
- source
- 首先求得x和y的值(简单,略)
- 后记
Lazzaro
赞！
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论