题目源码
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
bits = 1024
lbits = 727
p = getPrime(bits)
q = getPrime(bits)
r = getPrime(bits)
n = p * q * r
leak1 = (p ^ q) & ((1 << lbits) - 1)
leak2 = (p ^ r) & ((1 << lbits) - 1)
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print('e = %d' % e)
print('n = %d' % n)
print('c = %d' % c)
print('leak1 = %d' % leak1)
print('leak2 = %d' % leak2)
"""
e = 65537
n = 1788485365971167139893976906995201599393991984730899739160710674777347503264990436377925016407467205562818673582884591093334742911296215438134392163621071216597239424167461640156243867007799848069640765458953799357090481384070656485639260354680104576859762742406179822759588985026256682521122918260248188943170906364668880900389721037712147697968842251371800322257909074895166286731090600795397079743517569826508772622673188453246690438271487306785398984736870717326368570396504028787676569871895082188940448260121434898226689994421287087972092995874799564845403786011487127989625066205672887331142149114508908796736726306648414611051829775590084949607823908798126165790554952500212854407379390318504882338212271542332798222698822087545611811034575838828651215938733920629226894510641783869825156723491408324639208336361754500958396307785361835670569766837213412973923647677105282688965951154274654343911853657430444492785123
c = 1078589324773767953473759512827608820495855687588804241774570338199816192245246945655423884421968881815026745434531917679093453140825006911450356790077888790622370812871115852459528002467186637293402465584745754099967482815269328812022616916977103430759309858624665169897639104927941330243454380400842761382443280820636043298545631686307555050868196903943079467782866667252042167199806068944033224857861174338859558383522930904107201540947686285781563193057611007020075192651346489604982063300279039295967529688464035783949701840882155119903012356069850656951389232310697772834360597371258435804013918531653289990482056791319073716271066840368428213479355811554805632696492409180961462749083358184755813094938321172199412926968725896617862738453158306885238038585777519825810362378224313745472168020943062302426574423438604186343565471299100384224950976588796352886076890807833277535113775312453569491592577033233977480008109
leak1 = 488269416710560600828802453589788752554845853211480832349238055736908292717162055356440046013400904563050150488789394892307126473011104585301981785809125147008394648945737600216051446563643365501993320947091643963593566
leak2 = 303943197493421459259815118733411019037231391415726394765369263625985425775543920421794250357974063051629312885056512805804258920164317820406672326172387545965590065358003572572488475642063442608145972094732177497155756
"""分析
异或
给出了 \(p \oplus q\) 和 \(p \oplus r\) 的低位，参考之前的文章RSA-p^q，这道题只是多了一个因子，原理还是一样，稍微调整一下pq_low_xor函数即可
def pqr_low_xor(p="", q="", r=""):
lp, lq, lr = len(p), len(q), len(r)
tp = int(p, 2) if p else 0
tq = int(q, 2) if q else 0
tr = int(r, 2) if r else 0
if tp * tq * tr % 2**lp != n % 2**lp:
return
if lp == leak_bits:
pqr.append(tp)
return
if xor1[-lp-1] == "1" and xor2[-lp-1] == "1":
pqr_low_xor("1" + p, "0" + q, "0" + r)
pqr_low_xor("0" + p, "1" + q, "1" + r)
elif xor1[-lp-1] == "0" and xor2[-lp-1] == "0":
pqr_low_xor("1" + p, "1" + q, "1" + r)
pqr_low_xor("0" + p, "0" + q, "0" + r)
elif xor1[-lp-1] == "1" and xor2[-lp-1] == "0":
pqr_low_xor("1" + p, "0" + q, "1" + r)
pqr_low_xor("0" + p, "1" + q, "0" + r)
elif xor1[-lp-1] == "0" and xor2[-lp-1] == "1":
pqr_low_xor("1" + p, "1" + q, "0" + r)
pqr_low_xor("0" + p, "0" + q, "1" + r)coppersmith恢复高位
出题人故意卡了coppersmith的下界，需要用epsilon参数来提高界限的精度，参考2023鹏城杯
用coppersmith恢复p之后，根据leak1 = (p ^ q) & ((1 << lbits) - 1)，将p和leak1异或得到q的低位，再用一次coppersmith就可以恢复q，算出n的全部因子
解题
from Crypto.Util.number import *
from sage.all import *
e = 65537
n = 1788485365971167139893976906995201599393991984730899739160710674777347503264990436377925016407467205562818673582884591093334742911296215438134392163621071216597239424167461640156243867007799848069640765458953799357090481384070656485639260354680104576859762742406179822759588985026256682521122918260248188943170906364668880900389721037712147697968842251371800322257909074895166286731090600795397079743517569826508772622673188453246690438271487306785398984736870717326368570396504028787676569871895082188940448260121434898226689994421287087972092995874799564845403786011487127989625066205672887331142149114508908796736726306648414611051829775590084949607823908798126165790554952500212854407379390318504882338212271542332798222698822087545611811034575838828651215938733920629226894510641783869825156723491408324639208336361754500958396307785361835670569766837213412973923647677105282688965951154274654343911853657430444492785123
c = 1078589324773767953473759512827608820495855687588804241774570338199816192245246945655423884421968881815026745434531917679093453140825006911450356790077888790622370812871115852459528002467186637293402465584745754099967482815269328812022616916977103430759309858624665169897639104927941330243454380400842761382443280820636043298545631686307555050868196903943079467782866667252042167199806068944033224857861174338859558383522930904107201540947686285781563193057611007020075192651346489604982063300279039295967529688464035783949701840882155119903012356069850656951389232310697772834360597371258435804013918531653289990482056791319073716271066840368428213479355811554805632696492409180961462749083358184755813094938321172199412926968725896617862738453158306885238038585777519825810362378224313745472168020943062302426574423438604186343565471299100384224950976588796352886076890807833277535113775312453569491592577033233977480008109
leak1 = 488269416710560600828802453589788752554845853211480832349238055736908292717162055356440046013400904563050150488789394892307126473011104585301981785809125147008394648945737600216051446563643365501993320947091643963593566
leak2 = 303943197493421459259815118733411019037231391415726394765369263625985425775543920421794250357974063051629312885056512805804258920164317820406672326172387545965590065358003572572488475642063442608145972094732177497155756
def pqr_low_xor(p="", q="", r=""):
lp, lq, lr = len(p), len(q), len(r)
tp = int(p, 2) if p else 0
tq = int(q, 2) if q else 0
tr = int(r, 2) if r else 0
if tp * tq * tr % 2**lp != n % 2**lp:
return
if lp == leak_bits:
pqr.append(tp)
return
if xor1[-lp-1] == "1" and xor2[-lp-1] == "1":
pqr_low_xor("1" + p, "0" + q, "0" + r)
pqr_low_xor("0" + p, "1" + q, "1" + r)
elif xor1[-lp-1] == "0" and xor2[-lp-1] == "0":
pqr_low_xor("1" + p, "1" + q, "1" + r)
pqr_low_xor("0" + p, "0" + q, "0" + r)
elif xor1[-lp-1] == "1" and xor2[-lp-1] == "0":
pqr_low_xor("1" + p, "0" + q, "1" + r)
pqr_low_xor("0" + p, "1" + q, "0" + r)
elif xor1[-lp-1] == "0" and xor2[-lp-1] == "1":
pqr_low_xor("1" + p, "1" + q, "0" + r)
pqr_low_xor("0" + p, "0" + q, "1" + r)
leak_bits = 727
xor1 = bin(leak1)[2:].zfill(727)
xor2 = bin(leak2)[2:].zfill(727)
pqr = []
pqr_low_xor()
# print(pqr)
for p_low in pqr:
x = PolynomialRing(Zmod(n), 'x').gen()
f = x * 2**727 + p_low
res = f.monic().small_roots(X=2**(1024-727), beta=0.33, epsilon=0.01)
if res:
p = int(f(res[0]))
if n % p == 0:
print(p)
q_low = (p ^ leak1) & ((1 << 727) - 1)
x = PolynomialRing(Zmod(n//p), 'x').gen()
f = x * 2**727 + q_low
res = f.monic().small_roots(X=2**(1024-727), beta=0.4)
if res:
q = int(f(res[0]))
if n % q == 0:
print(q)
r = n // p // q
print(r)
assert p * q * r == n
phi = (p-1) * (q-1) * (r-1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))
# b'ayyctf{57592640dfec4971879852f069aa37e7}'最后发现这个flag太小了（比p还小），直接用p就可以解出
d = inverse(e, p-1)
print(long_to_bytes(pow(c, d, p)))
# b'ayyctf{57592640dfec4971879852f069aa37e7}'转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com