티스토리에서 백업한 글.
from Crypto.Util.number import *
from flag import flag
p = bytes_to_long(flag)
assert isPrime(p)
q = getPrime(256)
d = pow(65537, -1, (p - 1) * (q - 1))
print(d)
# 22800184635336356769510601710348610828272762269559262549105379768650621669527077640437441133467920490241918976205665073
p는 소수
어떤 거 구해서 마지막에 long_to_bytes하면 그게 flag
de=1(mod pq)
이걸 좀 풀어서 쓰면
de-1=n(q-1)(p-1)이다(n은 자연수)
factorint로 소인수분해 하면 아래와 같다.
일단 가장 큰 수는 256비트이기 때문에 조합할 경우의 수가 많지 않다.
그래서 직접 prime인지 체크해봤더니 모두 false -> n에 들어가는 인수이다.
ai의 도움을 받아 가장 큰 인수 빼고 코드를 짜보면…
from itertools import combinations
from sympy import isprime
def find_valid_p(n_factors):
valid_p = set()
factors = []
for base, exp in n_factors.items():
factors.extend([base] * exp)
for r in range(1, len(factors) + 1):
for combo in combinations(factors, r):
p = 1
for factor in combo:
p *= factor
if p % 2 == 0 and isprime(p + 1):
valid_p.add(p)
return sorted(valid_p)
n_factors = {
2: 3, 3: 1, 5: 2, 37: 1, 1117: 1, 4029461: 1,
1403014978139: 1, 284368748316481195117: 1
}
valid_p = find_valid_p(n_factors)
print(valid_p)
가능한 인수들을 모두 출력해준다.
위에 넣고 p-1을 p로 바꾼 후 long_to_bytes하여 경우의 수를 모두 출력해주면, DH 플래그가 나온다.