农商1号的网站建设费,网站建设一定要域名吗,vivo浏览器下载,成都网站搭建公司哪家好今天遇到一个RSA题#xff0c;给出n和pq求分解#xff0c;翻箱倒柜也没找着原来写的程序#xff0c;这里重写一下。都是编程的活。
第1种情况#xff0c;给出p^q
这种情况当p,q相同位相同时为0#xff0c;不同时为1#xff0c;爆破的时候只需要逐位判断两种情况#x…今天遇到一个RSA题给出n和pq求分解翻箱倒柜也没找着原来写的程序这里重写一下。都是编程的活。
第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*tqN:return if (tp(2idx))*(tq(2idx))N:return if idx400:try:f tp x rr f.monic().small_roots(X2^400, beta0.4)if rr ! []:print(rr)print(tp)print(p ,f(rr[0]))ok Truereturnexcept:passreturnidx -1b (gift idx)1one 1idx if b0:pq_xor(tp,tq,idx) pq_xor(tpone,tqone,idx) else: #1pq_xor(tpone,tq,idx)pq_xor(tp,tqone,idx)#N.nbits()2048 gift.nbits()1023 p,q的1024位为1
tp 11023
tq 11023
pq_xor(tp,tq,1023)第2种情况给出pq
也就是今天遇到的这个题程序前边基本相同只在处理下一步分支时有区别。
因为加法有进位所以两数相加时有8种情况从高位开始爆破会涉及到有进位的情况
对应的和有3种情况0123两数都是1还有1个进位然后反过来
当gift当位剩余b
b0p,q都不变进行下一步
b1三种情况(p1,q,gift-1)(p,q1,gift-1)(p,q,gift)
b2三种情况(p1,q,gift-1)(p,q1,gift-1)(p1,q1,gift-2)
b3最后一种(p1,q1,gift-2)
这个理起来很绕好在绕过来了
N 19913283586978731272870374837854045562790864804312115658302463830117436116219931849180682454814957654994095500743161455669517742683196683945049694888375426558735311269294662060482717191409995553476857418604462748567614908456839975140435522714312533340013676955820372105156740228641356206825881138276471973278761948406726062399175269553184359236859175084438349221553915085882218661560890322526503741457647907788204833926214096369428913779871365689037671018942683561649187089844083798834324075157252488088496084629641115161544547506935703532950490109236586524242732310854674446718076810611730874295399180178401471353663
gift 112012823249741273956420414320152024086394551241563686416444057368708038459572554871491781707278127933195689073127882065060125127295041489653572915729848455155059117821290550157606860744547
gift gift400PR.x PolynomialRing(Zmod(N))
ok False
def pq_add(tp,tq,tgift,idx):global ok if ok:return if tp*tqN:#print()return if (tp(2idx))*(tq(2idx))N:#print(, hex((tp(1(idx2))))[:20], hex(tq(2idx))[:20], hex(N)[:20])return if idx400:try:f tp x rr f.monic().small_roots(X2^400, beta0.4)if rr ! []:print(rr)print(tp)print(p ,f(rr[0]))ok Truereturnexcept:passreturnidx -1b tgift idx one 1idx#print(hex(tp)[:20],hex(tq)[:20],hex(tgift)[:20],idx,b)if b0 or b1:pq_add(tp,tq,tgift,idx) if b1 or b2:pq_add(tpone,tq,tgift-one,idx)pq_add(tp,tqone,tgift-one,idx)if b2 or b3:pq_add(tpone,tqone,tgift-(one1),idx)tp 11023
tq 11023
tgift gift -tp -tq
pq_add(tp,tq,tgift,1023)第三个小题是p^rev(q)
就是把q反过来再和p异或这里为了迷惑人用pq-2*(pq)来代替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(fn {n})print(fe {e})print(fct {ct})# what if q is reversed?q int(0b .join(reversed(bin(q)[2:])), 2)hint p q - 2 * (p q) # hint p^qprint(fhint {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 idxbits//2:return Falseif t n:return Falseif ((t^n)((1idx)-1)) ! 0:return False#中间全写1不能小于nk (1(bits - idx) ) - (1idx)if (pk)*(qk) n:return False b1 int(hint[idx])b2 int(hint[-idx-1])bleft 1(bits-idx-1)bright 1idxif (b1 1) and (b2 1):get_pq(p bleft bright, q, idx1)get_pq(p bleft, q bleft, idx1)get_pq(p bright, q bright, idx1)get_pq(p, q bleft bright, idx1)elif (b1 0) and (b2 0):get_pq(p bleft bright, q bleft bright, idx1)get_pq(p bleft, q bright, idx1)get_pq(p bright, q bleft, idx1)get_pq(p, q, idx1)elif (b1 1) and (b2 0):get_pq(p bleft bright, q bleft, idx1)get_pq(p bleft, q, idx1)get_pq(p bright, q bleft bright, idx1)get_pq(p, q bright, idx1)elif (b1 0) and (b2 1):get_pq(p bleft bright, q bright, idx1)get_pq(p bleft, q bleft bright, idx1)get_pq(p bright, q, idx1)get_pq(p, q bleft, idx1)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*2b2]:get_pq(p v[0]*bleft v[1]*bright, q v[2]*bleft v[3]*bright, idx1)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)
第四个小题给出pq,p*q都是10进制无进位
这里运算的时候直接用ascii码运算然后模1024
def add(a,b):if(ab):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*10a0[i]-48for i in range(len(b0)):ans ans*10(a0[ilen(a0)-len(b0)]b0[i]4)%10return ansdef mul(a,b):if(ab):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[ilen(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[(ij)%10][(i*j)%10] ! 0:a[(ij)%10][(i*j)%10].extend([i,j])else:a[(ij)%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])][j1] * 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])][j1] * mask)p tmpq tmq# print(i, len(p), len(q))mask * 10for i in qp:if i ! 0 and n % i 0:p iq n // ibreak
