[第五空间 2021]signin imaze的WriteUp

Problem: [第五空间 2021]signin

[[toc]]

思路

• 解题大致思路
  根据x和n的值可以求出可能的p、q低位，因为x和n的低位分别由p和q低位异或、相乘得到，再使用Coppersmith即可。

EXP

• 具体攻击代码

from sage.all import *
from Crypto.Util.number import *
from collections import deque

c = 86415476382906786465939442398992406348852252355326334785583474583480585659663836032856765037225261433532613020730103955916772373674295180495452293421279237222544308971840820110279355118064931506637793547489441433938707518241461449059717326341918746156620038847745542794560335988858156929013492541794032580255
e = 65537
n = 166337085427556441543394334802135957169988266794453522153008810336368247289697353242192853337017363111987395194428553050681210209730724596529629525357502302165396675392000087988956194589350195512264427901330860811469484473725396354231555692283910488095918243519370430703255279433498479943391876108577325840381
x = 2509898544460604898497702985357222191225421344430742181152035006910161802193623236888758239071502008180363546424715261788

def guess(num: int, bits: int) -> int:
    # 猜测低位
    x = PolynomialRing(Zmod(n), 'x').gen()
    f = x * pow(2, bits) + num
    result = f.monic().small_roots(X=pow(2, 512 - bits), beta=0.48)
    if result: return ZZ(f(result[0]))
    return 0

que = deque([(0, 0)]) # (pl, ql)
k = 350 # 想要的低位位数
for bits in range(k):
    target = n % pow(2, bits)
    for _ in range(len(que)):
        pl, ql = que.popleft()
        if pl * ql % pow(2, bits) != target:
            continue

        if x >> bits & 1: # 该位相异
            que.append((pl, ql + (1 << bits)))
            que.append((pl + (1 << bits), ql))
        else: # 该位相同
            que.append((pl, ql))
            que.append((pl + (1 << bits), ql + (1 << bits)))

for pl, _ in que:
    if is_prime(p := guess(pl, k)) and is_prime(q := n // p):
        phi = (p - 1) * (q - 1)
        d = inverse_mod(e, phi)
        m = pow(c, d, n)
        print(long_to_bytes(int(m)).decode())
        exit(0)

总结

• 对该题的考点总结
  Xor, Coppersmith