[CISCN 2022 东北赛区]math

Problem: [CISCN 2022 东北赛区]math

思路

两个加密的d是一样的，把那两个ed的公式相减可以得到k * (N_1 + 1) - a_2 * (N_2 + 1)是O(2^{3 \cdot \text{dbit}})，于是格一下（或者用你们说的连分数）可以得到k和a2
把k和a2代回ed那个公式可以得到d的高\frac{\text{nbit}}{2}位，同时k a_2是\varphi(N_1)和\varphi(N_2)的因子，所以可以得到d \equiv e^{-1} \pmod {k a_2}，也就大概相当于O(2^{\frac{\text{nbit}}{2}})的低位
最后根据高位和低位拼拼凑凑就搞出d了
反正其他师傅的wp都写得挺详细了

EXP


e = 86905291018330218127760596324522274547253465551209634052618098249596388694529
n1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
n2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067
enc1 = 71281698683006229705169274763783817580572445422844810406739630520060179171191882439102256990860101502686218994669784245358102850927955191225903171777969259480990566718683951421349181856119965365618782630111357309280954558872160237158905739584091706635219142133906953305905313538806862536551652537126291478865
enc2 = 7333744583943012697651917897083326988621572932105018877567461023651527927346658805965099102481100945100738540533077677296823678241143375320240933128613487693799458418017975152399878829426141218077564669468040331339428477336144493624090728897185260894290517440392720900787100373142671471448913212103518035775

B = matrix(ZZ, [
  [ (n1 + 1), 0],
  [-(n2 + 1), 2^511]
])
L = B.LLL()
v = L[0] * B^(-1)
k, a2 = [Integer(abs(_)) for _ in v]

H = (k * (n1 - 1) + 1) // e
l = e.inverse_mod(k * a2)
x2 = (H - l) % (k * a2)

for k2 in range(5):
  x = k2 * (k * a2) + x2
  d = H - x
  m = pow(enc1, d, n1)
  print(m.to_bytes(1997).replace(b'\x00', b''))

另外给一个测试代码，感觉出题人的数据是精心构造过的，起码gcd(k, a_2) = 1，不然还要枚举一波
还有格的时候也没卡界，不然又要枚举一波


import gmpy2
from Crypto.Util.number import *
nbit = 1024
dbit = 256

if 2*dbit < nbit:
  while True:
    a1 = getRandomNBitInteger(dbit)
    b1 = getRandomNBitInteger(nbit//2-dbit)

    n1 = a1*b1+1

    if isPrime(n1):
      break
  while True:
    a2 = getRandomNBitInteger(dbit)
    b2 = getRandomNBitInteger(nbit//2-dbit)

    n2=a2*b2+1

    n3=a1*b2+1
    if isPrime(n2) and isPrime(n3):
      break
  while True:
    a3=getRandomNBitInteger(dbit)
    if gmpy2.gcd(a3,a1*b1*a2*b2)==1:
      v1=(n1-1)*(n2-1) # phi1
      k=(a3*inverse(a3,v1)-1)//v1  # k * phi1=k * v1 = ed-1
      v2=k*b1+1
      if isPrime(v2):
        e = Integer(a3)
        d = e.inverse_mod(v1)
        N1 = n1*n2
        N2 = n3*v2
        break

print(f'{a1 = }')
print(f'{a2 = }')
print(f'{a3 = }')
print(f'{b1 = }')
print(f'{b2 = }')
print(f'{k = }')
print(f'{e = }')
print(f'{d = }')
print(f'{N1 = }')
print(f'{N2 = }')
print()

assert k * (N1 + 1) - e * d == k * (a1 * b1 + a2 * b2 + 2) - 1
assert a2 * (N2 + 1) - e * d == a2 * (a1 * b2 + k * b1 + 2) - 1
assert k * (N1 + 1) - a2 * (N2 + 1) == k * (a1 * b1 + a2 * b2 + 2) - a2 * (a1 * b2 + k * b1 + 2)
print(f'{(k * (N1 + 1) - a2 * (N2 + 1)).nbits() = }')

err = 2
B = matrix(ZZ, [
  [ (N1 + 1), 0],
  [-(N2 + 1), 2^(nbit//2 - err)]
])
L = B.LLL()
v = L[0] * B^(-1)
print(f'{(Integer(k).nbits(), Integer(a2).nbits()) = }')
print(f'{v = }')
print(f'{gcd(k, a2) = }')
print(f'{(k, a2) = }')
print(f'{gcd(k, a2) * v = }')
print()


err = 4
assert e * d - (k * a2) * (a1 * b1 * b2) == 1
print(hex(((N1 - 1)) // a2 >> (dbit)))
print(hex((a1 * b1 * b2) >> (dbit)))
assert hex(((N1 - 1)) // a2 >> (dbit + err)) == hex((a1 * b1 * b2) >> (dbit + err))
print(hex(((N2 - 1)) // k >> (dbit)))
print(hex((a1 * b1 * b2) >> (dbit)))
assert hex(((N2 - 1)) // k >> (dbit + err)) == hex((a1 * b1 * b2) >> (dbit + err))
print(hex(((k * (N1 - 1) + 1) // e) >> (nbit//2)))
print(hex(d >> (nbit//2)))
assert hex(((k * (N1 - 1) + 1) // e) >> (nbit//2 + err)) == hex(d >> (nbit//2 + err))
H = (k * (N1 - 1) + 1) // e
x = H - d
print(f'{x.nbits() = }')

assert e * d % (k * a2) == 1
l = e.inverse_mod(k * a2)
print(f'{l.nbits() = }')

assert d == H - x
assert d % (k * a2) == l
x2 = (H - l) % (k * a2)
assert (x - x2) % (k * a2) == 0
k2 = (x - x2) // (k * a2)
print(f'{k2 = }')
print(f'{(k * a2).nbits() = }')

总结

有点怀疑2024 qwb的traditional_game，dbt就是从这里抄的（