一些关于p^q问题剪枝算法

此篇文章针对 RSA 中 p^q 相关问题及变种做一个总结。之前做过很多 p^q 相关的问题，但是思路大差不差，周末打了鹏城杯，复现时发现要结合 copper 和 dfs 来剪枝。

参考文章

https://tangcuxiaojikuai.xyz/post/342113ee.html

https://mp.weixin.qq.com/s/Bi0iQOXwM5UlntrtdRL1oA

p^q

搜索方式

• 从低位搜索，在已知 p^q 和 p*q 的情况下，由于异或是按位进行的，对于每一位异或的结果来说，p、q 该位的组合情况有 4 种[1,0][0,1][1,1][0,0]

剪枝条件

• 利用p*q==n这一条件来进行筛选，由于是从低位开始爆破，因此满足\(p_{low}*q_{low}==n_{low}\)

def get_pq(n, x):
    a = [0]
    b = [0]
    maskx = 1
    maskn = 2
    for i in range(1024):
        xbit = (x & maskx) >> i
        nbit = n % maskn
        t_a = []
        t_b = []
        for j in range(len(a)):
            for aa in range(2):
                for bb in range(2):
                    if aa ^ bb == xbit:
                        tmp2 = n % maskn
                        tmp1 = (aa * maskn // 2 + a[j]) * (bb * maskn // 2 + b[j]) % maskn
                        if tmp1 == tmp2:
                            t_a.append(aa * maskn // 2 + a[j])
                            t_b.append(bb * maskn // 2 + b[j])
        maskx *= 2
        maskn *= 2
        a = t_a
        b = t_b
    for a1, b1 in zip(a, b):
        if a1 * b1 == n1:
            return a1, b1

p^q_rev

p = getPrime(256)
q = getPrime(256)
_q = int(bin(q)[2:][::-1] , 2)
n = p * q
gift = p ^ q_

搜索方式

• 从两端爆破
• 每一次搜索，需利用当前 gift 两端的 bit 位。这是因为，gift 的当前最高位对应 p 的最高位及 q 的最低位，gift 的当前最低位对应 p 的最低位及 q 的最高位

剪枝条件

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

from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

pxorq = 47761879279815109356923025519387920397647575481870870315845640832106405230526
n = 10310021142875344535823132048350287610122830618624222175188882916320750885684668357543070611134424902255744858233485983896082731376191044874283981089774677
c = 999963120986258459742830847940927620860107164857685447047839375819380831715400110131705491405902374029088041611909274341590559275004502111124764419485191
e = 65537
pxorq = str(bin(pxorq)[2:]).zfill(256)

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)

find("1","1","1","1")

p^(q>>nbits)

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

思路

这个其实并不算剪枝了，因为 gift 的高 16 位就是 P 的高 16 位。用 N 除以 P 后得到的就是 Q 的高位，再次利用 Q 的高位和 gift，可以求出 P 的 16 ～ 32 位，以此类推来恢复 P、Q。

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)>>nbits

nbits = 512
p = getPrime(nbits)
q = getPrime(nbits)
leakBits = 262
leak = (p ^ q) >> (nbits - leakBits)

搜索方式

• 从高位搜索
• p 的高位乘 q 的高位的前半部分等于 n 的高位

剪枝条件

• 低位全补 0，相乘结果 < n
• 低位全补 1，相乘结果 > n

p='1'
q='1'

P=[p]
Q=[q]
for i in range(261):
    PP=[]
    QQ=[]
    for a in '01':
        for b in '01':
            for pnew,qnew in zip(P,Q):
                pnew = pnew+a
                qnew = qnew+b
                tmp = int(pnew,2)*int(qnew,2)
                if xor(pnew,qnew) == leak[:2+i] and  tmp>>(tmp.bit_length()-i//2)== n>>(n.bit_length()-i//2) and (int(pnew.ljust(512,'0'),2)*int(qnew.ljust(512,'0'),2) < n)  and (int(pnew.ljust(512,'1'),2)*int(qnew.ljust(512,'1'),2) > n) :
                    PP.append(pnew)
                    QQ.append(qnew)
    print(len(P))
    P = PP.copy()
    Q = QQ.copy()
print(P)

coppersmith

上述剪枝只能求出高 262 位了，有多种组合，但仍缺少低 250 位，因此需要用到 coppersmith 来求解。

在具体应用情景中应当适当调整beta和epsilon。

from tqdm import *
R.<x> = Zmod(n)[]
for pbar in tqdm(P[::-1]):
    for i in range(32):

        tmp = int(pbar,2)<<5
        tmp+=i
        f = tmp*2**245 + x
        xx = f.monic().small_roots(X=2^245,beta=0.47,epsilon=0.02)
        if xx:
            p = f(xx[0])
            print(p)