unusual rsa和密码挑战writeup

admin 2022年1月5日22:48:13CTF专场评论23 views32072字阅读106分54秒阅读模式

>

>

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) % n

                    2.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)

Lazzaro

赞!


特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月5日22:48:13
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  unusual rsa和密码挑战writeup http://cn-sec.com/archives/719349.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: