在近几个月的比赛里，经常遇见给出 \(p \oplus q\) 的题型，在此总结一下。
核心思路就是对p、q逐位进行剪枝爆破，从高到低或者从低到高都可以（根据题目自行选择），并加上以下约束条件：
\(leak = p \oplus q\)，p、q每个二进制位之间的关系都可以根据异或值来调整。
如果从高位开始，当定下了p、q的高位，如果低位全部补0，\(pq < n\)；全部补1，\(pq > n\)。
如果从低位开始，p、q的低位应满足 \(p_{low} \times q_{low} \equiv n \mod{2^i}\)，其中i是指低位的位数。
注意：一般来说，用从高到低的方法能算出唯一解；而用从低到高的方法可能算出一大堆解，所以还要加个n % p来判断。
核心函数pq_high_xor和pq_low_xor如下：
def pq_high_xor(p="", q=""):
lp, lq = len(p), len(q)
tp0 = int(p + (512-lp) * "0", 2)
tq0 = int(q + (512-lq) * "0", 2)
tp1 = int(p + (512-lp) * "1", 2)
tq1 = int(q + (512-lq) * "1", 2)
if tp0 * tq0 > n or tp1 * tq1 < n:
return
if lp == leak_bits:
pq.append(tp0)
return
if xor[lp] == "1":
pq_high_xor(p + "0", q + "1")
pq_high_xor(p + "1", q + "0")
else:
pq_high_xor(p + "0", q + "0")
pq_high_xor(p + "1", q + "1")
def pq_low_xor(p="", q=""):
lp, lq = len(p), len(q)
tp = int(p, 2) if p else 0
tq = int(q, 2) if q else 0
if tp * tq % 2**lp != n % 2**lp:
return
if lp == leak_bits:
pq.append(tp)
return
if xor[-lp-1] == "1":
pq_low_xor("0" + p, "1" + q)
pq_low_xor("1" + p, "0" + q)
else:
pq_low_xor("0" + p, "0" + q)
pq_low_xor("1" + p, "1" + q)\(leak = p \oplus q\)
题目源码
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
n = p * q
leak = p ^ q
print(f"n = {n}")
print(f"leak = {leak}")分析
p、q直接异或，因为p、q的高1位肯定是1，所以异或后的leak肯定没有512位，为了方便使用脚本，可以用zfill在前面补0
解法一
leak_bits = 512
xor = bin(leak)[2:].zfill(512)
pq = []
pq_high_xor()
print(pq)解法二
leak_bits = 512
xor = bin(leak)[2:].zfill(512)
pq = []
pq_low_xor()
# print(pq)
for p in pq:
if n % p == 0:
print(p)
break\(leak = p \oplus (q >> 16)\)
题目源码
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
n = p * q
leak = p ^ (q >> 16)
print(f"n = {n}")
print(f"leak = {leak}")分析
p、q错位异或，这样处理后leak和p的高16位是相同的，直接传入leak的高16位作为初始的p。而且leak肯定是512位，这里就不需要补0了
解题
leak_bits = 512
xor = bin(leak)[2:]
p_high_16 = xor[:16]
pq = []
pq_high_xor(p_high_16)
print(pq)\(leak = (p \oplus q) >> 100\)
题目源码
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
n = p * q
leak = (p ^ q) >> 100
print(f"n = {n}")
print(f"leak = {leak}")分析
这个leak不全，少了低100位，这样解出来的p、q也会少了相应的位数，剩余位数用coppersmith恢复即可
解题
leak = leak << 100
leak_bits = 412
xor = bin(leak)[2:].zfill(512)
pq = []
pq_high_xor()
# print(pq)
for p_high in pq:
x = PolynomialRing(Zmod(n), 'x').gen()
f = p_high + x
res = f.monic().small_roots(X=2**100, beta=0.4)
if res:
p = int(f(res[0]))
print(p)
break\(leak = (p \oplus q)\ \%\ 2^{412}\)
题目源码
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
n = p * q
leak = (p ^ q) % 2**412
print(f"n = {n}")
print(f"leak = {leak}")分析
少了高100位，用coppersmith恢复
解题
leak_bits = 412
xor = bin(leak)[2:].zfill(412)
pq = []
pq_low_xor()
# print(pq)
for p_low in pq:
x = PolynomialRing(Zmod(n), 'x').gen()
f = x * 2**412 + p_low
res = f.monic().small_roots(X=2**100, beta=0.4)
if res:
p = int(f(res[0]))
if n % p == 0:
print(p)
break\(leak = (p \oplus (q >> 8))\ \%\ 2^{504} >> 100\)
题目源码
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
n = p * q
leak = (p ^ (q >> 8)) % 2**504 >> 100
print(f"n = {n}")
print(f"leak = {leak}")分析
q有偏移，并且删去了p的高8位，所以需要爆破这8位，然后用coppersmith恢复低位
解题
leak = leak << 100
leak_bits = 412
for i in range(2**7, 2**8): # 爆破 p 的高位
p_high_8 = bin(i)[2:]
xor = p_high_8 + bin(leak)[2:].zfill(512-8)
pq = []
pq_high_xor(p_high_8)
# print(pq)
for p_high in pq:
x = PolynomialRing(Zmod(n), 'x').gen()
f = p_high + x
res = f.monic().small_roots(X=2**100, beta=0.4)
if res:
p = int(f(res[0]))
print(p)
exit()\(leak = (p \oplus (q >> 8))\ \%\ 2^{412}\)
题目源码
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
n = p * q
leak = (p ^ (q >> 8)) % 2**412
print(f"n = {n}")
print(f"leak = {leak}")分析
因为只泄露了低位，采用从低到高的方法，但是q有偏移，需要爆破q的低8位，同时pq_low_xor函数也要改一改剪枝条件
解题
def pq_low_xor(p="", q=""):
lp, lq = len(p), len(q)
tp = int(p, 2) if p else 0
tq = int(q, 2) if q else 0
# if tp * tq % 2**lp != n % 2**lp:
# return
if tp * (tq%(2**lp)) % 2**lp != n % 2**lp:
return
# if lp == leak_bits:
# pq.append(tp)
# return
if lq == leak_bits: # lp < lq
pq.append(tq)
return
if xor[-lp-1] == "1":
pq_low_xor("0" + p, "1" + q)
pq_low_xor("1" + p, "0" + q)
else:
pq_low_xor("0" + p, "0" + q)
pq_low_xor("1" + p, "1" + q)
leak_bits = 412+8
xor = bin(leak)[2:].zfill(412)
for i in range(2**8): # 爆破 q 的低位
q_low_8 = bin(i)[2:].zfill(8)
pq = []
pq_low_xor("", q_low_8)
# print(pq)
for q_low in pq:
x = PolynomialRing(Zmod(n), 'x').gen()
f = x * 2**(412+8) + q_low
res = f.monic().small_roots(X=2**(100-8), beta=0.4)
if res:
q = int(f(res[0]))
if n % q == 0:
print(q)
exit()转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com