关联爆破-RSA分解

今天遇到一个RSA题，给出n和p+q求分解，翻箱倒柜也没找着原来写的程序，这里重写一下。都是编程的活。

第1种情况，给出p^q

这种情况当p,q相同位相同时为0，不同时为1，爆破的时候只需要逐位判断两种情况，

当为0时p,q都置0或者都置1，

当为1时p,q分别置1

如果给出的p^q是全的可以从低位爆破，爆破的同时跟n的尾数位比较。

这个题我按今天这题的样子把后400位删掉，用的同一个N

N有2048位，所以p,q大概都是1024位，而gift给出是1023位，显然p,q首位为1。然后爆破到400位时用coppersmith方法求剩余部分。

N = 19913283586978731272870374837854045562790864804312115658302463830117436116219931849180682454814957654994095500743161455669517742683196683945049694888375426558735311269294662060482717191409995553476857418604462748567614908456839975140435522714312533340013676955820372105156740228641356206825881138276471973278761948406726062399175269553184359236859175084438349221553915085882218661560890322526503741457647907788204833926214096369428913779871365689037671018942683561649187089844083798834324075157252488088496084629641115161544547506935703532950490109236586524242732310854674446718076810611730874295399180178401471353663
#gift = (P^Q)>>400
gift = 24974037914540444972174719514588697024841724043425510822527893809737860155273716656719332610821905216284030065533729927837282940938990333355929462102999310764824139677295638873649726744154
gift <<=400PR.<x> = PolynomialRing(Zmod(N))
ok = False
def pq_xor(tp,tq,idx):global ok if ok:return if tp*tq>N:return if (tp+(2<<idx))*(tq+(2<<idx))<N:return if idx<=400:try:f = tp + x rr = f.monic().small_roots(X=2^400, beta=0.4)if rr != []:print(rr)print(tp)print('p = ',f(rr[0]))ok = Truereturnexcept:passreturnidx -=1b = (gift >>idx)&1one = 1<<idx if b==0:pq_xor(tp,tq,idx)    pq_xor(tp+one,tq+one,idx)    else:   #1pq_xor(tp+one,tq,idx)pq_xor(tp,tq+one,idx)#N.nbits()=2048 gift.nbits()=1023  p,q的1024位为1
tp = 1<<1023
tq = 1<<1023
pq_xor(tp,tq,1023)

第2种情况，给出p+q

也就是今天遇到的这个题，程序前边基本相同，只在处理下一步分支时有区别。

因为加法有进位，所以两数相加时有8种情况（从高位开始爆破会涉及到有进位的情况）

对应的和有3种情况：0，1，2，3（两数都是1，还有1个进位），然后反过来，

当gift当位剩余b

b==0，p,q都不变进行下一步

b==1，三种情况(p+1,q,gift-1)(p,q+1,gift-1)(p,q,gift)

b==2，三种情况(p+1,q,gift-1)(p,q+1,gift-1)(p+1,q+1,gift-2)

b==3，最后一种(p+1,q+1,gift-2)

这个理起来很绕，好在绕过来了

N = 19913283586978731272870374837854045562790864804312115658302463830117436116219931849180682454814957654994095500743161455669517742683196683945049694888375426558735311269294662060482717191409995553476857418604462748567614908456839975140435522714312533340013676955820372105156740228641356206825881138276471973278761948406726062399175269553184359236859175084438349221553915085882218661560890322526503741457647907788204833926214096369428913779871365689037671018942683561649187089844083798834324075157252488088496084629641115161544547506935703532950490109236586524242732310854674446718076810611730874295399180178401471353663
gift = 112012823249741273956420414320152024086394551241563686416444057368708038459572554871491781707278127933195689073127882065060125127295041489653572915729848455155059117821290550157606860744547
gift = gift<<400PR.<x> = PolynomialRing(Zmod(N))
ok = False
def pq_add(tp,tq,tgift,idx):global ok if ok:return if tp*tq>N:#print('>')return if (tp+(2<<idx))*(tq+(2<<idx))<N:#print('<', hex((tp+(1<<(idx+2))))[:20], hex(tq+(2<<idx))[:20], hex(N)[:20])return if idx<=400:try:f = tp + x rr = f.monic().small_roots(X=2^400, beta=0.4)if rr != []:print(rr)print(tp)print('p = ',f(rr[0]))ok = Truereturnexcept:passreturnidx -=1b = tgift >>idx one = 1<<idx#print(hex(tp)[:20],hex(tq)[:20],hex(tgift)[:20],idx,b)if b==0 or b==1:pq_add(tp,tq,tgift,idx)    if b==1 or b==2:pq_add(tp+one,tq,tgift-one,idx)pq_add(tp,tq+one,tgift-one,idx)if b==2 or b==3:pq_add(tp+one,tq+one,tgift-(one<<1),idx)tp = 1<<1023
tq = 1<<1023
tgift = gift -tp -tq 
pq_add(tp,tq,tgift,1023)

第三个小题，是p^rev(q)

就是把q反过来再和p异或，这里为了迷惑人用p+q-2*(p&q)来代替p^q

def system_two(m: bytes):p, q = [getPrime(NBITS // 2) for _ in range(2)]n = p * qe = 0x10001ct = pow(bytes_to_long(m), e, n)print(f"n = {n}")print(f"e = {e}")print(f"ct = {ct}")# what if q is reversed?q = int('0b' + ''.join(reversed(bin(q)[2:])), 2)hint = p + q - 2 * (p & q)   # hint = p^qprint(f"hint = {hint}")    

这个从两端爆破，我分了16种情况，后来整理成一个数组来处理

n = 153342396916538105228389844604657707491428056788672847550697727306332965113688161734184928502340063389805944751606853233980691631740462201365232680640173140929264281005775085463371950848223467977601447652530169573444881112823791610262204408257868244728097216834146410851717107402761308983285697611182983074893
hint = 3551084838077090433831900645555386063043442912976229080632434410289074664593196489335469532063370582988952492150862930160920594215273070573601780382407014bits = 512def get_pq(p,q, idx):t = p*qif t == n:print('!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1')print('p = ', p)print('q = ', q)exit()return Trueif idx>=bits//2:return Falseif t > n:return Falseif ((t^n)&((1<<idx)-1)) != 0:return False#中间全写1，不能小于nk = (1<<(bits - idx) ) -  (1<<idx)if (p+k)*(q+k) < n:return False b1 = int(hint[idx])b2 = int(hint[-idx-1])bleft = 1<<(bits-idx-1)bright = 1<<idx'''if (b1 == 1) and (b2 == 1):get_pq(p + bleft + bright, q,                  idx+1)get_pq(p + bleft,          q + bleft,          idx+1)get_pq(p + bright,         q + bright,         idx+1)get_pq(p,                  q + bleft + bright, idx+1)elif (b1 == 0) and (b2 == 0):get_pq(p + bleft + bright, q + bleft + bright, idx+1)get_pq(p + bleft,          q + bright,         idx+1)get_pq(p + bright,         q + bleft,          idx+1)get_pq(p,                  q,                  idx+1)elif (b1 == 1) and (b2 == 0):get_pq(p + bleft + bright, q + bleft,          idx+1)get_pq(p + bleft,          q,                  idx+1)get_pq(p + bright,         q + bleft + bright, idx+1)get_pq(p,                  q + bright,         idx+1)elif (b1 == 0) and (b2 == 1):get_pq(p + bleft + bright, q + bright,         idx+1)get_pq(p + bleft,          q + bleft + bright, idx+1)get_pq(p + bright,         q,                  idx+1)get_pq(p,                  q + bleft,          idx+1)else:pass'''   way = [[[1,1,1,1],[1,0,0,1],[0,1,1,0],[0,0,0,0]],   #00左右都相同[[1,1,0,1],[1,0,1,1],[0,1,0,0],[0,0,1,0]],   #01左同右不同[[1,1,1,0],[1,0,0,0],[0,1,1,1],[0,0,0,1]],   #10右同左不同[[1,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,1]],   #11左右都不同]for v in way[b1*2+b2]:get_pq(p + v[0]*bleft + v[1]*bright, q + v[2]*bleft + v[3]*bright, idx+1)return Falsehint = bin(hint)[2:].zfill(bits)
print('h:',hint)
p = (1<<(bits-1))+1
q = (1<<(bits-1))+1
get_pq(p,q,1)

第四个小题给出p+q,p*q都是10进制无进位

这里运算的时候直接用ascii码运算然后模10（+2，+4）

def add(a,b):if(a<b):a0 = str(b).encode()b0 = str(a).encode()else:a0 = str(a).encode()b0 = str(b).encode()ans = 0for i in range(len(a0)-len(b0)):ans = ans*10+a0[i]-48for i in range(len(b0)):ans = ans*10+(a0[i+len(a0)-len(b0)]+b0[i]+4)%10return ansdef mul(a,b):if(a<b):a0 = str(b).encode()b0 = str(a).encode()else:a0 = str(a).encode()b0 = str(b).encode()ans = 0for i in range(len(b0)):ans = ans*10+((a0[i+len(a0)-len(b0)]+2)*(b0[i]+2))%10return ans

这个虽然是10进制，但处理方式也一样由于给的倍数是全部（尾部完整）所以直接从尾部爆破，与n进行比较，这样每位都都与n的对应位比较，可以裁剪掉大量错误分支，爆破更快。

ppq = '10399034381787849923326924881454040531711492204619924608227265350044149907274051734345037676383421545973249148286183660679683016947030357640361405556516408'[::-1]
ptq = '06004903250672248020273453078045186428048881010508070095760634049430058892705564009054400328070528434060550830050010084328522605000400260581038846465000861'[::-1]
n = 100457237809578238448997689590363740025639066957321554834356116114019566855447194466985968666777662995007348443263561295712530012665535942780881309520544097928921920784417859632308854225762469971326925931642031846400402355926637518199130760304347996335637140724757568332604740023000379088112644537238901495181p,q = [0],[0]
a = [[0 for i in range(10)] for i in range(10)]for i in range(10):for j in range(10):if a[(i+j)%10][(i*j)%10] != 0:a[(i+j)%10][(i*j)%10].extend([i,j])else:a[(i+j)%10][(i*j)%10] = [i,j]l = len(ptq)
mask = 1
for i in range(0, l):tmp, tmq = [],[]for k in range(len(p)):for j in range(0, len(a[int(ppq[i])][int(ptq[i])]), 2):if (a[int(ppq[i])][int(ptq[i])][j] * mask + p[k]) * \(a[int(ppq[i])][int(ptq[i])][j+1] * mask + q[k]) % mask \== n % mask:tmp.append(p[k] + a[int(ppq[i])][int(ptq[i])][j] * mask)tmq.append(q[k] + a[int(ppq[i])][int(ptq[i])][j+1] * mask)p = tmpq = tmq# print(i, len(p), len(q))mask *= 10for i in q+p:if i != 0 and n % i == 0:p = iq = n // ibreak