在CTF的加解密单元中，RSA是常见的加解密算法。在正确的配置RSA算法的情况下，目前来说还是无法破解的。但也有一些不安全配置或者不安全使用RSA算法的情况，在这些情况下，即使是使用了RSA算法，被加密的内容仍然有可能被破解。在CTF竞赛中，常常会将这种情况作为题目，从而使大家对RSA算法有更深的理解。以下是CTF比赛中常见的RSA算法题型。

题解

如上图题目，len（c）=228,len(n)=512,n远大于c，且e=3较小，因此可以尝试进行开方解密。
from gmpy2 import iroot
import libnum

e = 0x3
n =0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c =0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

def smallEattack(c, e, n):
       for i in range(10 ** 10):
           res = iroot(n * i + c, e)
           if res`1`:
                print(libnum.n2s(int(res`0`)))
                break
smallEattack(c,e,n)

1.2 hastad广播攻击

适用情况

使用相同的加密指数e加密相同的信息，发送给多于e个不同的人，可能收到低加密指数广播攻击，最终具有超过e个的密文。即n,c不同，m,e相同。一般会是e=k，然后给k组数据。

题目说明

题目来源：XCTF 4th-WHCTF-2017
题目描述：有一个年轻人得到了一份密文，身为老司机的你能帮他看看嘛？
题目附件：
`{"c":7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042,"e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c":21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461,"e": 10, "n":23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c":6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983,"e": 10, "n":18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c":4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052,"e": 10, "n":23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c":22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672,"e": 10, "n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c":17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087,"e": 10, "n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c":1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639,"e": 10, "n":25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c":15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352,"e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c":8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797,"e": 10, "n":52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247,"e": 10, "n":30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}`

题解

import gmpy2
import libnum

def crt(b,m):
   '''中国剩余定理'''
    #判断是否互素
   for i in range(len(m)):
       for j in range(i+1,len(m)):
           if gmpy2.gcd(m`i`,m`j`) != 1:
                print("m中含有不是互余的数")
                return -1
    #乘积
    M= 1

   for i in range(len(m)):
       M *= m`i`
    #求M/mi
   Mm = ``
   for i in range(len(m)):
       Mm.append(M // m`i`)
   #求Mm`i`的乘法逆元
   Mm_ = ``
   for i in range(len(m)):
       _,a,_ = gmpy2.gcdext(Mm`i`,m`i`)
       Mm_.append(int(a % m`i`))
    #求MiM'ibi的累加
    y= 0
   for i in range(len(m)):
       print(Mm`i` * Mm_`i` * b`i`)
       y += (Mm`i` * Mm_`i` * b`i`)
    y= y % M
   return y

enc = `{"c":7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042,"e": 10,
    "n":25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
      {"c":21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461,"e": 10,
          "n":23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
      {"c":6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983,"e": 10,
          "n":18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
      {"c":4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052,"e": 10,

       "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
      {"c":22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672,"e": 10,
       "n":31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},

      {"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087,"e": 10,
       "n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
      {"c":1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639,"e": 10,

       "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
      {"c":15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352,"e": 10,

 "n":32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},

      {"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797,"e": 10,
       "n":52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},

{"c":13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247,"e": 10,
       "n":30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}`
 
e = 10
c = ``
n = ``

for i in range(len(enc)):

   c.append(enc`i``"c"`)
   n.append(enc`i``"n"`)

 r = crt(c,n)
res = gmpy2.iroot(r,e)

if(res`1` == True):
   print(libnum.n2s(int(res`0`))) #转为字符串

1.3 CopperSmith部分信息攻击-明文高位泄漏

适用情况

给出了明文的高位数据，求所有明文数据


题目说明


('n=', '0xf85539597ee444f3fcad07142ecf6eaae5320301244a7cedc50b2beed7e60ffa11ccf28c1a590fb81346fb16b0cecd046a1f63f0bf93185c109b8c93068ec02fL')
('e=', '0x3')
('c=','0xa75c3c8a19ed9c911d851917e442a8e7b425e4b7f92205ca532a2ab0f5abe6cb86d164cc61374877f9e88e7bca606b43c79f1d59deadfcc68c3db52e5fc42f0L')
('m=','0x666c6167206973203a746573743132313131313131313131313133343536000000000000000000')

题解

在线网站（https://sagecell.sagemath.org/）上执行

e = 0x3
b=0x666c6167206973203a746573743132313131313131313131313133343536000000000000000000
n =0xf85539597ee444f3fcad07142ecf6eaae5320301244a7cedc50b2beed7e60ffa11ccf28c1a590fb81346fb16b0cecd046a1f63f0bf93185c109b8c93068ec02f
c=0xa75c3c8a19ed9c911d851917e442a8e7b425e4b7f92205ca532a2ab0f5abe6cb86d164cc61374877f9e88e7bca606b43c79f1d59deadfcc68c3db52e5fc42f0
kbits=72
PR. = PolynomialRing(Zmod(n))
f = (x + b)^e-c
x0 = f.small_roots(X=2^kbits, beta=1)`0`
print("x: %s" %hex(int(x0)))

1.4 CopperSmith部分信息攻击-因子高位泄漏

适用情况

给出了p，或者q的部分高位，求完整p/q

题目说明

('n=','0xb50193dc86a450971312d72cc8794a1d3f4977bcd1584a20c31350ac70365644074c0fb50b090f38d39beb366babd784d6555d6de3be54dad3e87a93a703abddL')
('p=','0xd7e990dec6585656512c841ac932edaf048184bac5ebf9967000000000000000L')
('e=', '0x3')
('c=','0x428a95e5712e8aa22f6d4c39ee5ec85f422608c2f141abf22799c1860a5e343068ab55dfb5c99a7085714f4ce8950e85d8ed0a11fce3516cf66a641dca8321eeL')

题解

在线网站（https://sagecell.sagemath.org/）上执行

p = 0xd7e990dec6585656512c841ac932edaf048184bac5ebf9967000000000000000
n =0xb50193dc86a450971312d72cc8794a1d3f4977bcd1584a20c31350ac70365644074c0fb50b090f38d39beb366babd784d6555d6de3be54dad3e87a93a703abdd
kbits = 60
PR. = PolynomialRing(Zmod(n))
f = x + p
x0 = f.small_roots(X=2^kbits, beta=0.4)`0`
print("x: %s" %hex(int(x0)))
p = p+x0
print("p: ", hex(int(p)))
assert n % p == 0
q = n/int(p)
print("q: ", hex(int(q)))

当解密指数d过小时，则可能为低解密指数攻击。反过来，就是e会是比较大。


题目说明

n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e =11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793

题解

# -*- coding: cp936 -*-
import gmpy2
import time

# 展开为连分数
def continuedFra(x, y):
   cF = ``
   while y:
       cF += `x / y`
       x, y = y, x % y
   return cF

def Simplify(ctnf):
   numerator = 0
   denominator = 1
   for x in ctnf`::-1`:
       numerator, denominator = denominator, x * denominator + numerato
   return (numerator, denominator)


# 连分数化简
def calculateFrac(x, y):
   cF = continuedFra(x, y)
   cF = map(Simplify, (cF`0:i` for i in xrange(1, len(cF))))
   return cF


# 解韦达定理
def solve_pq(a, b, c):
   par = gmpy2.isqrt(b * b - 4 * a * c)
   return (-b + par) / (2 * a), (-b - par) / (2 * a)


def wienerAttack(e, n):
   for (d, k) in calculateFrac(e, n):
       if k == 0: continue
       if (e * d - 1) % k != 0: continue


       phi = (e * d - 1) / k
       p, q = solve_pq(1, n - phi + 1, n)
       if p * q == n:
           return abs(int(p)), abs(int(q))
   print 'not find!'


time.clock()
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e =11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
p, q = wienerAttack(e, n)


 

print '`+`Found!'
print ' `-`p =',p
print ' `-`q =',q
print ' `-`n =',p*q
d = gmpy2.invert(e,(p-1)*(q-1))
print ' `-`d =', d
print ' `-`m is:' + '{:x}'.format(pow(c,d,n)).decode('hex')
print ' `!`Timer:', round(time.clock(),2),'s'
print '`!`All Done!'