RSA题型分类

这是一篇关于RSA题型分类的思维导图，主要内容包括：RSA基础题型，n的素因数几种特殊情况的解法，模数n直接分解攻击，共模攻击（模数相同，指数不同分为e1、e2，加密同一明文m，得到不同密文c1,c2），Rabin攻击（e=2的情况），dp泄露攻击，低加密指数攻击（一般e=3）。

RSA题型分类

• RSA基础题型
  • 一般已知p、q、e就可以解出m(p、q也可以换成n)
• n的素因数几种特殊情况的解法
  • 1、n为素数
    • import gmpy2 from Crypto.Util.number import * n = 114904723088242436560222555148424908481775302449678762789112091666971730833042318807316209276538265858810430860188630138345094997413502014629701840292299043867371143866817473689761760188003757165703444485737002808634454042439419243767222693781419170621758982605146916516740572285029340446484523059007717152993 e = 65537 c = 109231975788613157710975932240403105235490178292821559667096694595635756368777710402401959999267918678101575858597927476795280573618413528697437540341427177894264053002305349919954387643558433412486953631676185415528902445397779958802695506641600458837544847993481351893146446656265327835619141817883945604107 phi = n-1 d = gmpy2.invert(e, phi) m = pow(c,d,n) print(long_to_bytes(m).decode())
  • 2、n分解出p、q且p、q相近
  • 3、n分解为三个素数p、q、r
    • phi = (p-1)*(q-1)*(r-1)
  • 4、n分解出素数的多次方（以q的三次方为例）
    • phi = (p-1)*(q**3-q**2)*(r-1)
• 模数n直接分解攻击
  • 暴力破解
    • 由n暴力破解p、q
      • 1、yafu:在yafu文件夹下yafu-x64.exe factor("88503001447845031603457048661635807319447136634748350130947825183012205093541")
      • 2、在线网站http://www.factordb.com/index.php?id=1100000002518112902
    • 由公钥pubkey.pem分别得到e和n
      • 在线网站：http://www.hiencode.com/pub_asys.html
• 共模攻击（模数相同，指数不同分为e1、e2，加密同一明文m，得到不同密文c1,c2）
  • 解题步骤
    • 1、先判断e1、e2是否互素(通过最大公约数判断)
      • import libnum import gmpy2 from Crypto.Util.number import * n = 17752770005959450783368980030043878547535956414119879741453560550701705489806449145991219400638575053529185909550016280513308215017385040463699931951701894554210916071934994522579016557286121819399693223747296718293086175847432934809917559318694792015696754445449090169911052611759269740275932926797176511376184207265987673583880965946906791696307374144274966668681976499889069666816573873429180101133894777446363037698265266769363040459677305869824632204494462866097824280787902105876680951222107761530644357292819483215790868606552029604879053217989241693291353552725151633669823156879311498404663745671588492388939 e = 65537 c = 17215114973697188228039407246534810856664195594190943813088215060573040302874656982718865711472821797706298792012615413421620367364435910565448695441533985668245204354161963958920998821327722363488545595199128223887604206339608823901845352597801014639506279914508269141350896135320522450208970336079282563152913186458859289060342568562329695673546818588161006052780570480494934554029032268444361720329775028337034266866365591838699506418326634782639236557659691322389324900487855512614150815465076893085020543027358714857336681784520429602229455376426822593566388991433069627228944458733892799679195989110824305261985 p1 = libnum.nroot(n,2) p = gmpy2.next_prime(p1) q = n//p phi = (p-1)*(q-1) d = gmpy2.invert(e, phi) m = pow(c,d,n) print(long_to_bytes(m).decode())
      • import gmpy2 e1 = 3247473589 e2 = 3698409173 print(gmpy2.gcd(e1, e2))
    • 2、互素则满足共模攻击条件，接下来求r和s，由e_1×r+e_2×s=gcd(e1,e2)
      • import gmpy2 e1 = 3247473589 e2 = 3698409173 q,r,s = gmpy2.gcdext(e1,e2) print(q,r,s) 1 635749796 -558234791
    • 解出m，由(c1**r)*(c2**s)ºm**gcd(e1,e2)modn得
      • m**gcd(e1,e2)=(pow(C1,r,n)*pow(C2,s,n))%n,当e1,e2互质时gcd(e1.e2)=1,直接有m=(pow(C1,r,n)*pow(C2,s,n))%n,e1,e2不互质时还要再除最大公因数m1=libnum.nroot(m+k*n,11)
• Rabin攻击（e=2的情况）
  • 用中国剩余定理解决
    • import gmpy2 from Crypto.Util.number import * p = 65428327184555679690730137432886407240184329534772421373193521144693375074983 q = 98570810268705084987524975482323456006480531917292601799256241458681800554123 c = 0x4e072f435cbffbd3520a283b3944ac988b98fb19e723d1bd02ad7e58d9f01b26d622edea5ee538b2f603d5bf785b0427de27ad5c76c656dbd9435d3a4a7cf556 n = p*q c1 = pow(c,(p+1)//4,p) c2 = pow(c,(q+1)//4,q) cp1= p-c1 cp2 = q-c2 t1 = gmpy2.invert(p,q) t2 = gmpy2.invert(q,p) m1 = (q*c1*t2+p*c2*t1)%n m2 = (q*c1*t2+p*cp1*t1)%n m3 = (q*cp1*t2+p*c2*t1)%n m4 = (q*cp1*t2+p*cp2*t1)%n #Rabin解密中国剩余定理（CRT）的标准流程 print(long_to_bytes(m1)) print(long_to_bytes(m2)) print(long_to_bytes(m3)) print(long_to_bytes(m4))
• dp泄露攻击
  • 题目一般会给出n,c,e,dp
    • 解题步骤
      • 1、先解x
        • import gmpy2 from Crypto.Util.number import * import libnum e = 65537 n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847 dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825 c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869 for i in range(1,e): if(dp*e-1)%i == 0: if n% (((dp*e-1)//i)+1) == 0: x = i print(x)
      • 2、由dp*e=x*(p-1)+1解出p，又已知n，可以得到q
        • p = (e*dp-1)//x+1 q = n//p print(p,q)
      • 3、现已知p,q,e,c，又回到了最基本的RSA模型
        • phi = (p-1)*(q-1) d = gmpy2.invert(e,phi) m=pow(c,d,n) print(long_to_bytes(m).decode())
• 低加密指数攻击（一般e=3）
  • 解题步骤
    • 1、当m**e明显小于n时
      • e = 3 n = 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737 c = 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741 import gmpy2 from Crypto.Util.number import long_to_bytes m,s = gmpy2.iroot(c,e) if s: print(long_to_bytes(m).decode())
    • 2、判断m**e是否小于n
      • import gmpy2 from Crypto.Util.number import * import libnum m,s = gmpy2.iroot(c,e) if s: print(long_to_bytes(m).decode()) else: print("m**e>n")
    • 3、如果m**e大于n
      • import gmpy2 from Crypto.Util.number import long_to_bytes m,s = gmpy2.iroot(c,e) if s: print(long_to_bytes(m).decode()) else: print("m**e>n") k = 1 while True: m, b = gmpy2.iroot(c + k * n, 3) if b: print(long_to_bytes(m).decode()) break k += 1
• wiener攻击（低解密指数攻击,当发现e非常大时，由edº1mod(phi(n))得，解密指数d很小）
  • 使用工具爆破，在虚拟机wiener_hack文件夹里进入python环境，输入：from RSAwienerHacker import hack_RSA，再输入：d=hack_RSA(e值，n值）显示hacked后，输入d即得到结果
  • 得到d后：m = pow(c,d,n) print(long_to_bytes(m).decode())