728x90
반응형
이번에는 드림의 "d"문제를 풀어 볼 것이다.
일단 아래 문제코드를 살펴보자.
반응형
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
위 파이썬 코드의 내용을 정리하면 아래와 같다.
d = 22800184635336356769510601710348610828272762269559262549105379768650621669527077640437441133467920490241918976205665073
e = 65537
q는 256비트
처음에는 어떤 방법으로 할 지 전혀 모르겠는 것 같아서 rsa 위키백과를 보다가 우연히 아래와 같은 부분을 확인했다.
이걸 보고 ed-1이 소인수분해가 가능하면 p나 q를 구할 수 있을 것이라고 알게 되었다.
그래서 아래의 두 사이트를 참고하여 ed-1를 소인수분해 했다.
https://www.alpertron.com.ar/ECM.HTM
소인수 분해 결과
2 * 2 * 2 * 2 * 3 * 5 * 5 * 37 * 1117 * 4029461 * 1403014978139 * 284368748316481195117 * 18741210882440665187461519398960291465361283084482741278982029639876282810203
그러면 이를 조합하여 ed-1의 모든 인수를 구한 뒤, int를 bytes로 바꿨을때 "DH{"를 포함하는 숫자가 p, int의 길이가 256비트인 숫자가 q가 되는 수를 구하는 python 으로 아래와 같이 구현 가능하다.
from Crypto.Util.number import *
factors = [(2, 4), (3, 1), (5, 2), (37, 1), (1117, 1), (4029461, 1), (1403014978139, 1), (284368748316481195117, 1), (18741210882440665187461519398960291465361283084482741278982029639876282810203, 1)]
all_factors = [1]
for (prime, power) in factors: # <- 인수 구하기
new_factors = []
for factor in all_factors:
for i in range(1, power+1):
new_factors.append(factor * prime**i)
all_factors += new_factors
for i in all_factors:
num = i+1
if isPrime(num):
num_bytes = long_to_bytes(num)
if b'DH{' in num_bytes: # <- p 즉 flag 판별
print("FLAG : "+num_bytes.decode('utf-8'))
print("p = " + str(num))
elif num.bit_length() == 256: # <- q 판별
print("q = " + str(num))
이 프로그램을 실행하면 아래와 같이 flag(p), q를 구할 수 있다.
728x90
반응형
'Cryptography' 카테고리의 다른 글
Dreamhack - Robot Only(writeup) (0) | 2023.02.22 |
---|---|
Dreamhack - ICM2022(writeup) (0) | 2023.02.22 |
Dreamhack - darimchal_001(writeup) (0) | 2023.02.22 |
Cryptography(암호학) - Hash(해시) (0) | 2021.12.26 |
Cryptography(암호학) - RSA(공개키 암호) (0) | 2021.12.23 |