RSA攻击
ctf中常见的rsa攻击方式有以下几种
- 低加密指数攻击
- 低加密指数广播攻击
- 低解密指数攻击
- 共模攻击
- 已知高位攻击
0x00 低加密指数攻击
当e过小时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。
如果明文的三次方比n大，但不够大，那么设k，有：
c= m^e+kn
爆破k，如果 c-kn 能开三次根式，那么可以直接得到明文。
# 低加密指数攻击
import gmpy2
import time
n = 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737
c = 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741
e = 3
i = 0
s = time.clock()
while 1:
m, b = gmpy2.iroot(c+i*n, e)
if b:
print('[-]m is:', m)
print('[!]Timer:', round(time.clock()-s, 2), 's')
break
i+=1
0x01 低加密指数广播攻击
如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文
c1 = m^e mod n1
c2 = m^e mod n2
c3 = m^e mod n3
可对上述等式运用中国剩余定理进行求解
0x02低解密指数攻击
这里看不懂了，运用wienerAttack，如果e看起来很大，那么d就可能会小
# 低解密指数攻击
import gmpy2
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 + numerator
return (numerator, denominator)
def calculateFrac(x, y):
cF = continuedFra(x, y)
cF = list(map(Simplify, (cF[0:i] for i in range(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):
print(e)
print(d)
print(k)
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!')
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
p, q = wienerAttack(e, n)
print('[+]Found!')
print('[-]p =', p)
print('[-]q =', q)
d = gmpy2.invert(e, (p-1)*(q-1))
print('[-]m is:', pow(c, d, n))
0x03共模攻击
在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值
c1 = m^e1 mod n
c2 = m^e2 mod n
# 共模攻击
import gmpy2
n = 158052722013789461456896900244510199169216575693048895162538548356466884311543740968048825149608833390255268602486435690724338965409521812963337715301197225841194835534751041470231293288252951274190599189716955573428884560130364021535005115652592074445852835422027406556727605302404510264249211145063332337043
e1 = 665213
e2 = 368273
c1 = 16698617641888248664694980135332125531792692516788088682722832061393117609508765284473236240256421599515450690670639565968165473479697383505401285976148490839526672808730165847471005704945978274496508928460578173068717106075169723401049489389383596761956301440156581021583368058047939083755488885694261340425
c2 = 59192887933967939708054321952273893559113509451228797382728687616356609407020086787061368452871936378934964292805289941535766263083244529814852043063188312786173717046316177403357053871483983775362121186037776932260378728059531236711960979620603784044468207000654149190295060179235411429700710154759043236436
s0, s1, s2 = gmpy2.gcdext(e1, e2)
if s1 < 0:
s1 = -s1
c1 = gmpy2.invert(c1, n)
elif s2 < 0:
s2 = -s2
c2 = gmpy2.invert(c2, n)
m = gmpy2.powmod(c1, s1, n)*gmpy2.powmod(c2, s2, n) % n
print('[-]m is:', m)