剪枝

简单的剪枝比较容易看出来，看过类似的套个脚本就出了

p^q

就像这种类型的，给出了p*q和p^q，对于每一位p^q的结果来说，该位的组合情况有 4 种1^0,0^1,1^1,0^0

搜索方式是从低位开始搜索,根据条件限定，并且需要满足

将p和q剩下位全部填充为1，需要满足 p*q > n

将p和q剩下位全部填充为0，需要满足 p*q < n

脚本：

pbits=
xor = str(bin(xor)[2:]).zfill(pbits)
ph = ''
qh = ''

def find(ph,qh):
    l0 = len(ph)
    l1 = len(qh)
    tmp0 = ph + '0' * (pbits-l0)
    tmp1 = ph + '1' * (pbits-l0)
    tmq0 = qh + '0' * (pbits-l1)
    tmq1 = qh + '1' * (pbits-l1)
    if int(tmp0,2) * int(tmq0,2) > n:#剪枝条件1
        return
    if int(tmp1,2) * int(tmq1,2) < n:#剪枝条件2
        return
    
    if l0 == pbits:#结束条件
        if int(ph,2) * int(qh,2) == n:
            print(f'p = {int(ph,2)}')
            print(f'q = {int(qh,2)}')
            return
    
    else:
        if xor[l1] == '1':
            find(ph+'0',qh+'1')
            find(ph+'1',qh+'0') 
        else:
            find(ph+'1',qh+'1')
            find(ph+'0',qh+'0')    

find(ph,qh)

例题

帕鲁杯江枫渔火对愁眠

from Crypto.Util.number import *
flag = b'paluctf{******************}'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p * q
e = 0x10001
c = pow(m, e, n)
leak1 = p & q
leak2 = p | q
print(n)
print(leak1)
print(leak2)
print(c)
# 116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
# 8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
# 13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
# 77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658

看起来非常简单，结果卡住了，我印象里|和^都是按位异或，但试了一下才发现实际上是

| 按位或：对应位有一个为1则为1。

^按位异或：对应位不同则为1，相同则为0。（我是笨蛋，这都会记错

所以leak1^leak2=p^q，常规剪枝

import gmpy2
from Crypto.Util.number import*

n=116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
leak1=8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
leak2=13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
xor=leak1^leak2
pbits=512
xor = str(bin(xor)[2:]).zfill(pbits)
ph = ''
qh = ''

def find(ph,qh):
    l0 = len(ph)
    l1 = len(qh)
    tmp0 = ph + '0' * (pbits-l0)
    tmp1 = ph + '1' * (pbits-l0)
    tmq0 = qh + '0' * (pbits-l1)
    tmq1 = qh + '1' * (pbits-l1)
    if int(tmp0,2) * int(tmq0,2) > n:#剪枝条件1
        return
    if int(tmp1,2) * int(tmq1,2) < n:#剪枝条件2
        return
    
    if l0 == pbits:#结束条件
        if int(ph,2) * int(qh,2) == n:
            print(f'p = {int(ph,2)}')
            print(f'q = {int(qh,2)}')
            return
    
    else:
        if xor[l1] == '1':
            find(ph+'0',qh+'1')
            find(ph+'1',qh+'0') 
        else:
            find(ph+'1',qh+'1')
            find(ph+'0',qh+'0')    

find(ph,qh)

p=8765698777357218895930455433534622474349736018036786722894513584283441223303812128653973162721831346202633677284766954990094900299096944074318482652846369
q=13246755426378578729876630630718068462717569987788401039611945190239825377062020349346567434694413153125153375769817998716719780574738862166452227093778437
e=0x10001
c=77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658
d=gmpy2.invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
#b'paluctf{&&&|||&&&|||&&&&&&&&&&&&|||||||||}'

首尾剪枝(p^q_rev)

已知p与反方向二进制的q异或的值和p*q

从两端向中间搜索，每次搜索利用p^q_rev当前位数（与p^q_rev当前最高位有关的是当前p的最高位和q的最低位，p^q_rev当前最低位有关的是当前p的最低位和q的最高位）

如果当前搜索的最高位为”1”，则可能是：p该位为1，q对应低位为0；p该位为0，q对应低位为1。

如果当前搜索的最高位为”0”，则可能是：p该位为0，q对应低位为0；p该位为1，q对应低位为1。

搜索最低位也一样

从以下几个限定剪枝：

将p、q未搜索到的位全填0，乘积应该小于n;

将p、q未搜索到的位全填1，乘积应该大于n;

p、q低k位乘积再取低k位应该和n的低k位相同

脚本：

def find(ph,qh,pl,ql):
    l = len(ph)
    tmp0 = ph + (256-2*l)*"0" + pl
    tmp1 = ph + (256-2*l)*"1" + pl
    tmq0 = qh + (256-2*l)*"0" + ql
    tmq1 = qh + (256-2*l)*"1" + ql
    if(int(tmp0,2)*int(tmq0,2) > n):
        return 
    if(int(tmp1,2)*int(tmq1,2) < n):
        return
    if(int(pl,2)*int(ql,2) % (2**(l-1)) != n % (2**(l-1))):
        return

    if(l == 128):
        pp0 = int(tmp0,2)
        if(n % pp0 == 0):
            pf = pp0
            qf = n//pp0
            phi = (pf-1)*(qf-1)
            d = inverse(e,phi)
            m1 = pow(c,d,n)
            print(long_to_bytes(m1))
            exit()

    else:
        if(pxorq[l] == "1" and pxorq[255-l] == "1"):
            find(ph+"1",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "1" and pxorq[255-l] == "0"):
            find(ph+"1",qh+"0","0"+pl,"0"+ql)
            find(ph+"0",qh+"0","0"+pl,"1"+ql)
            find(ph+"1",qh+"1","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","1"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "1"):
            find(ph+"0",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "0"):
            find(ph+"0",qh+"0","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","0"+pl,"1"+ql)
            find(ph+"0",qh+"1","1"+pl,"0"+ql)
            find(ph+"1",qh+"1","1"+pl,"1"+ql)

p ^ (q >> kbits)

思路一

已知n=p*q和p^(q>>kbits)

从高位向低位搜索，p的高kbits位已知（与给出的p^(q>>kbits)值的高kbits位相同），那搜索就从p^(q>>kbits)的kbits位后开始，即p的第kbits位，q的第1位。

若p^(q>>kbits)搜索的当前位值为1，则可能为：p为1，q为0 或者 p为0，q为1；反之若p^(q>>kbits)当前位为0，则p为1，q为1 或者 p为0，q为0。（p,q指的都是对应位的）

剪枝条件：

将p和q剩下位全部填充为1，需要满足 p*q > n

将p和q剩下位全部填充为0，需要满足 p*q < n

要注意把p的已知的高kbits位加上

结束条件是

脚本：

n = 
xor = 
kbits = 
pbits = 
xor = str(bin(xor)[2:])
ph = xor[:kbits]
qh = ''
xor = xor[kbits:]
qh = ''
def find(ph,qh):
    l0 = len(ph)
    l1 = len(qh)
    tmp0 = ph + '0' * (pbits-l0)
    tmp1 = ph + '1' * (pbits-l0)
    tmq0 = qh + '0' * (pbits-l1)
    tmq1 = qh + '1' * (pbits-l1)
    if int(tmp0,2) * int(tmq0,2) > n:#剪枝条件1
        return
    if int(tmp1,2) * int(tmq1,2) < n:#剪枝条件2
        return
    
    if l0 == pbits:#结束条件
        if n % int(ph,2) == 0:
            print(f'p = {int(ph,2)}')
            return
    
    else:
        if xor[l1] == '1':
            find(ph+'0',qh+'1')
            find(ph + '1',qh+'0') 
        else:
            find(ph+'1',qh+'1')
            find(ph + '0',qh+'0')    
find(ph,qh)

思路二

因为异或后的高 kbits 位就是 P 的高 kbits 位。用 N 除以 P 后得到的就是 Q 的高位，再次利用 Q 的高位和 gift，可以求出 P 的 kbits ～ 2*kbits 位，以此类推来恢复 P、Q。

例如下面这个：

P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)


pbar = gift >>(512-16)

while True:
    try:
        qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
        qbar = qbar>>6
        gifts = gift^(qbar<<(512-16-qbar.bit_length()))
        pbar = gifts >> (512-16-qbar.bit_length())
    except:
        break

for i in range(64):
    if N%((pbar<<6)+i) == 0:
        p = (pbar<<6)+i
        q = N//p
        print("[+] p =",p)
        print("[+] q =",q)
        break

来源：一些关于p^q问题剪枝算法 _

我一开始不明白右移6位这个6是怎么来的，下面那个左移的位数和上面那个右移的联系是啥

后面貌似想明白了

直接说结论吧：上面那个6取别的值也是可以的，不能大于kbits，下面那个值则是最后的pbits-kbits-qbar.bit_length()

也就是说这个脚本也可以写成这样：

n = 
xor = 
kbits = 
pbits = 
pbar = xor >>(pbits-kbits)

while True:
    try:
        qbar = (n>>(n.bit_length() - pbar.bit_length()*2))//pbar
        qbar = qbar>>kbits-1
        xors = xor^(qbar<<(pbits-kbits-qbar.bit_length()))
        pbar = xors >> (pbits-kbits-qbar.bit_length())
    except:
        break

for i in range(n.bit_length()//kbits):
    if n%(pbar+i) == 0:
        p =pbar+i
        q = n//p
        print("[+] p =",p)
        print("[+] q =",q)
        break

（更好套一点，原博客的别的题不能直接套）

例题

DASCTF 2023 & 0X401七月暑期挑战赛 ezRSA

from Crypto.Util.number import *
from secret import secret, flag
def encrypt(m):
    return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)
print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
c1 = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
c2 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
c3 = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

P,Q的获取可用剪枝获得，得到之后可得n

from Crypto.Util.number import*
import gmpy2
N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
xor = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
c1 = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
kbits = 16
pbits = 512
pbar = xor >>(pbits-kbits)
e=11

while True:
    try:
        qbar = (N>>(N.bit_length() - pbar.bit_length()*2))//pbar
        qbar = qbar>>kbits-1
        xors = xor^(qbar<<(pbits-kbits-qbar.bit_length()))
        pbar = xors >> (pbits-kbits-qbar.bit_length())
    except:
        break

for i in range(N.bit_length()//kbits):
    if N%(pbar+i) == 0:
        p =pbar+i
        q = N//p
        d=gmpy2.invert(e,(p-1)*(q-1))
        print("n=",pow(c1,d,N))
        break
#n= 8410363083727227985204019150296233995423906412694890252698371563789022268553444336554986979907257458547381598181369620318848637391220240378808211998052306324620364339595355706922325759625785590466818309839146408927226283350419069859849879835884942537531811470537915106995685907400782213608736735862576031042

结果一看，发现求出的n结尾居然是2，并且长度只有1020位，所以可以想到是因为n>N导致结果-N，所以真实的n应该再加上N,验算位数正好是1024位，然后是Franklin-Reiter攻击解flag

from Crypto.Util.number import*

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
n1= 8410363083727227985204019150296233995423906412694890252698371563789022268553444336554986979907257458547381598181369620318848637391220240378808211998052306324620364339595355706922325759625785590466818309839146408927226283350419069859849879835884942537531811470537915106995685907400782213608736735862576031042
n=n1+N
c2 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
c3 = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

def GCD(a,b):
    if b == 0:
        return a.monic()
    else:
        return GCD(b,a % b)
PR.<x> = PolynomialRing(Zmod(n))
for i in range(50):
    f1 = x ^ 11 - c2
    f2 = (bytes_to_long(b'dasctf{' + b'\x00' * i + b'}') + 256 * x) ^ 11 - c3
    if GCD(f1,f2)[0] != 1:
        print(long_to_bytes(int(n - GCD(f1,f2)[0])))
#b'C0pper_Sm1th_Mak3s_T1ng5_Bet4er'

nextprime剪枝

from sympy import *
from Crypto.Util.number import *
from secret import flag

def gen():
    p = getPrime(512)
    q = nextprime(int(str(p)[::-1]))
    a = p&(10**6)
    b = q%(10**6)
    return p, q, a, b

p, q, a, b = gen()
n = p * q
e = 65537
c = pow(flag, e, n)

print('a =', a)
print('b =', b)
print('n =', n)
print('c =', c)

'''
a = 393792
b = 657587
n = 369861662178631957928245949770898273807810914183024109983427665445735262653137205864716795669578458854257293391751966280054435051199001813062804877555180285022533020724584142987601931508644551710279816508694942797383860411279321090090880184911983657558416043011288974643282183209071299542379616927857228873411
c = 71672159337725868237152385281240906653912972455699529924728534161923598107229667985188160316648005550663968313537597184857765083556920840254397949219027087098695062021613177519248117588571374167137534818793726427056016629301262986053118989821488864074425276527050110912787300008659230186841168308795745942580
'''

可以看出来关键就在于gen函数

def gen():
    p = getPrime(512)
    q = nextprime(int(str(p)[::-1]))
    a = p&(10**6)
    b = q%(10**6)
    return p, q, a, b

与普通首尾剪枝的区别在于这边逆序是十进制而普通的是二进制，且取逆序之后还进行了一次nextprime

那么首先，因为p、q乘积的低六位一定与n的低六位相等。因此我们可以爆破出p的低六位，相应的，我们也就有了q的高六位。

而由于给出的额外信息b暴露了q的低六位，并且我们知道，nextprime一般最多也就产生不超过两千的偏移，因此我们可以对偏移量进行爆破，从而得到正确的p的高六位的逆序。爆破的依据为：

对可能的p高六位后面填充全0，与q高六位后面填充全0，乘积应小于n
对可能的p高六位后面填充全9，与q高六位后面填充全9，乘积应大于n

这一步解决后，问题就变成了：已知p、q的高六位和低六位以及p、q的乘积n，要求还原p、q，并且他们之间存在逆序关系，因此用与第一题相似的方法进行深搜，具体如下：

已知条件：

p、q的高六位与低六位(十进制位)

因此当我们爆破出p的低六位，相应的，我们也就有了q的高六位。而由于给出的额外信息b暴露了q的低六位（自行计算位数），因此我们可以对偏移量进行爆破，从而得到正确的p的高六位的逆序。爆破的依据为：

对可能的p高六位后面填充全0，与q高六位后面填充全0，乘积应小于n
对可能的p高六位后面填充全9，与q高六位后面填充全9，乘积应大于n

这一步解决后，问题就变成了：已知p、q的高六位和低六位以及p、q的乘积n，要求还原p、q，并且他们之间存在逆序关系。

搜索方式：

从两端向中间搜索
每一次搜索10x10种可能，分别对应高位部分的一个十进制位和低位部分的一个十进制位

剪枝条件：

将p、q未搜索到的位全填0，乘积应小于n
将p、q未搜索到的位全填9，乘积应大于n
p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位相同

与普通首尾剪枝的区别在于这边逆序是十进制而普通的是二进制，且这题取逆序之后还进行了一次nextprime

如果能爆破出p的低6位，也就有了q的高6位，因为给的b泄露了q的低6位，n的低6位一定等于p*q的低6位，所以可以爆破得到p的低6位从而得到q的高6位。

#find plow
for i in range(1000000):
    if(i*b % (10**6) == n % (10**6)):
        plow = str(i)

qhigh = plow[::-1]

因为nextprime偏移很小一般不会超过2000，且q的低6位泄露，q是p十进制逆序的下一个值，所以q的低6位偏移不超过2000再倒序就是p的高6位，可以爆破得到。

爆破的依据是：

对可能的p高六位后面填充全0，与q高六位后面填充全0，乘积应小于n

对可能的p高六位后面填充全9，与q高六位后面填充全9，乘积应大于n

#find phigh
for i in range(2000):
    phigh = str(b-i)[::-1]
    if(int(phigh + "0" * (dec_len-6)) * int(qhigh + "0" * (dec_len-6)) < n and int(phigh + "9" * (dec_len-6)) * int(qhigh + "9" * (dec_len-6)) > n):
        break

至此已知条件就成了已知p、q的高六位与低六位(十进制位)和p*q,并且p,q互为逆序，要还原p,q

搜索方式：从两端向中间搜索，每次搜索有10×10种可能

剪枝条件：

p,q未搜索到的位全填0，乘积应该小于n

p,q未搜索到的位全填9，乘积应该大于n

p,q低k位的乘积取低k位，应该和n的低k位相同

def dec(p,q,c,n):
    phi = (p-1)*(q-1)
    d = inverse(65537,phi)
    print(long_to_bytes(pow(c,d,n)))

def find(ph,qh,pl,ql):
    #条件1，2
    padding0 = (dec_len-len(ph)-len(pl))*"0"
    padding9 = (dec_len-len(ph)-len(pl))*"9"
    if(int(qh+padding0+ql)*int(ph+padding0+pl) > n or int(qh+padding9+ql)*int(ph+padding9+pl) < n):
        return

    #条件三
    mask = 10**len(pl)
    if(int(ql)*int(pl) % mask != n % mask):
        return
    
    for i in range(10):
        if(n % int(ph+str(i)+pl) == 0):
            p = int(ph+str(i)+pl)
            q = n // p
            dec(p,q,c,n)
            exit()

    #search  
    for i in range(10):
        for j in range(10):
            find(ph + str(i), qh + str(j), str(j) + pl, str(i) + ql)

好难想到

到这步接下来就能得到flag了

部分参照：

Crypto趣题-剪枝

Crypto-剪枝

CTF_Crypto_剪枝

剪枝

p^q

例题

首尾剪枝(p^q_rev)

p ^ (q >> kbits)

思路一

思路二

例题

nextprime剪枝

评论

相关阅读

【2018年网鼎杯CTF 第四场】部分题目WP

ByteCTF 2019 线上赛 Writeup By ROIS

【原创】Pwnhub会员日一题引发的思考

35C3 POST Web 题目详解

SCTF 2018 Writeup — De1ta

评论

相关阅读

【2018年网鼎杯CTF 第四场】部分题目WP

ByteCTF 2019 线上赛 Writeup By ROIS

【原创】Pwnhub会员日一题引发的思考

35C3 POST Web 题目详解

SCTF 2018 Writeup — De1ta

剪枝

p^q

例题

首尾剪枝(p^q_rev)

p ^ (q >> kbits)

思路一

思路二

例题

nextprime剪枝

评论

相关阅读

【2018年 网鼎杯CTF 第四场】部分题目WP

ByteCTF 2019 线上赛 Writeup By ROIS

【原创】Pwnhub会员日一题引发的思考

35C3 POST Web 题目详解

SCTF 2018 Writeup — De1ta

评论

相关阅读

【2018年 网鼎杯CTF 第四场】部分题目WP

ByteCTF 2019 线上赛 Writeup By ROIS

【原创】Pwnhub会员日一题引发的思考

35C3 POST Web 题目详解

SCTF 2018 Writeup — De1ta

【2018年网鼎杯CTF 第四场】部分题目WP

【2018年网鼎杯CTF 第四场】部分题目WP