RSA已知高位攻击
背景：
rsa解密，已知e，n，c（其中n太大，分解不了），和p的高位或m的高位或d的高位
工具：
sage
（沒下載的話，有個在線網站可用：https://sagecell.sagemath.org/）
基礎知識：
PR.<x> = PolynomialRing(Zmod(n))用于生成一個以x為符號的一元多項式環
f = x + p4定義求解的函數
roots = f.small_roots(X=2^kbits, beta=0.4)多項式小值根求解及因子分解，其中X表示求解根的上界
coppersmith的定理:
對任意的a > 0 ， 給定N = PQR及PQ的高位(1/5)(logN,2)比特，我們可以在多項式時間logN內得到N的分解式。這是三個因式的分解。也就是說我們現在是由理論依據的，已知高位是可以在一定時間內分解N。
Coppersmith證明了在已知p和q部分比特的情況下，若q和p的未知部分的上界X和Y滿足XY <= N 0.5則Ｎ的多項式可以被分解。這里的0.5可以替換成其他的數，具體原因不詳。
更多基礎知識參考：https://www.jianshu.com/p/1a0e876d5929
解題代碼
已知p的高位
知道p的高位為p的位數的約1/2時即可
已知e,n爆破 1024的P，至少需要知道前576位二進制，即前144位16進制
已知前144位，則
n= p4= #已知P的高位 e= pbits= #P原本的位數kbits=pbits - p4.nbits() print p4.nbits() p4 = p4 << kbits PR.<x> = PolynomialRing(Zmod(n)) f = x + p4 roots = f.small_roots(X=2^kbits,beta=0.4) # 經過以上一些函數處理后，n和p已經被轉化為10進制 if roots:p= p4 + int(roots([0]))print ("n",n)print ("p",p)print ("q",n/p)只知道前142位
n = p4 = #已知P的高位,最后面8位二進制，也就是兩位十六進制要參與爆破，所以要用00補充 e = pbits = #P原本的位數for i in range(0,256):# 要爆破的8位二進制數，為2**8==256，表示0~255p4 =p4 = p4 + int(hex(i),16)kbits=pbits - p4.nbits()p4 = p4 << kbitsPR.<x> = PolynomialRing(Zmod(n))f = x + p4roots = f.small_roots(X=2^kbits,beta=0.4)# 經過以上一些函數處理后，n和p已經被轉化為10進制 if roots:p= p4 + int(roots([0]))print ("n",n)print ("p",p)print ("q",n/p)已知m高位
def phase2(high_m, n, c):R.<x> = PolynomialRing(Zmod(n), implementation='NTL')m = high_m + xM = m((m^3 - c).small_roots()[0])print(hex(int(M))[2:])n = c = high_m = phase2(high_m, n, c)已知d的低位
如果知道d的低位，低位約為n的位數的1/4就可以恢復d。已知私鑰的512位的低位 Partial Key Exposure Attack(部分私鑰暴露攻擊)
def partial_p(p0, kbits, n): PR.<x> = PolynomialRing(Zmod(n)) nbits = n.nbits() f = 2^kbits*x + p0 f = f.monic() roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3if roots:x0 = roots[0]p = gcd(2^kbits*x0 + p0, n)return ZZ(p)def find_p(d0, kbits, e, n): X = var('X') for k in range(1, e+1): results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits) for x in results: p0 = ZZ(x[0]) p = partial_p(p0, kbits, n) if p: return p if __name__ == '__main__':n = e = d = beta = 0.5epsilon = beta^2/7nbits = n.nbits() #print("nbits:%d:"%(nbits))#kbits = floor(nbits*(beta^2+epsilon)) kbits = nbits - d.nbits()-1 #print("kbits:%d"%(kbits))d0 = d & (2^kbits-1)#print("lower %d bits (of %d bits) is given" % (kbits, nbits))p = find_p(d0, kbits, e, n)print("found p: %d" % p)q = n//pprint(d)print(inverse_mod(e, (p-1)*(q-1)))已知d的低位
[+]n=92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183[+]e=3[+]m=random.getrandbits(512)[+]c=pow(m,e,n)=56164378185049402404287763972280630295410174183649054805947329504892979921131852321281317326306506444145699012788547718091371389698969718830761120076359634262880912417797038049510647237337251037070369278596191506725812511682495575589039521646062521091457438869068866365907962691742604895495670783101319608530[+]d&((1<<512)-1)=787673996295376297668171075170955852109814939442242049800811601753001897317556022653997651874897208487913321031340711138331360350633965420642045383644955[-]long_to_bytes(m).encode('hex')= def getFullP(low_p, n):R.<x> = PolynomialRing(Zmod(n), implementation='NTL')p = x*2^512 + low_proot = (p-n).monic().small_roots(X = 2^128, beta = 0.4)if root:return p(root[0])return Nonedef phase4(low_d, n, c,e):maybe_p = []for k in range(1, 4):p = var('p')p0 = solve_mod([e*p*low_d == p + k*(n*p - p^2 - n + p)], 2^512)maybe_p += [int(x[0]) for x in p0]print(maybe_p) for x in maybe_p:P = getFullP(x, n)if P: break P = int(P)Q = n // P assert P*Q == n d = inverse_mod(e, (P-1)*(Q-1))print(hex(power_mod(c, d, n))[2:])n = c = low_d = phase4(low_d, n, c,e)已知p部分高位，部分低位
from Crypto.Util.number import getPrime, bytes_to_long from secret import flagp = getPrime(1024) q = getPrime(1024) n = p * q e = 65537 hint1 = p >> 724 hint2 = q % (2 ** 265) ct = pow(bytes_to_long(flag), e, n) print(hint1) print(hint2) print(n) print(ct)out
1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479 40812438243894343296354573724131194431453023461572200856406939246297219541329623 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188也就是說，知道p的高300位，和q的低265位
根據
我們可以求出p的低位，然后再進行coppersmith定理求解
參考代碼
from gmpy2 import * from Crypto.Util.number import *p1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479 q0 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623 n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969 mod=pow(2,265) p0=n*invert(q0,mod)%mod pbar=(p1<<724)+p0 PR.<x> = PolynomialRing(Zmod(n))for i in range(32):f=pbar+x*mod*32f=f.monic()pp=f.small_roots(X=2^454,beta=0.4)if(pp):breakpbar+=modp=pbar+pp[0]*32*mod assert n%p==0 print(p)q=n//p phi=(p-1)*(q-1) e=65537 d=invert(e,phi) c=19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188 m=pow(c,d,n) print(long_to_bytes(m)) #flag{ef5e1582-8116-4f61-b458-f793dc03f2ff}參考內容
相關知識點參考
部分代碼參考1
部分代碼參考2
總結
- 上一篇： 2021-09-26
- 下一篇： ByteCTF 2021（Crypto部