Description
Category: Crypto
Source: PlaidCTF 2019
Points: 150
Author: Jisoon Park(js00n.park)
Description:
Tears dripped from my face as I stood over the bathroom sink. Exposed again! The tears melted into thoughts, and an idea formed in my head. This will surely keep my secrets safe, once and for all. I crept back to my computer and began to type.
Write-up
주어진 텍스트 압축 파일을 풀어보면 CRT를 이용하는 RSA en/decryption 코드가 있다.
[...]
class Key:
PRIVATE_INFO = ['P', 'Q', 'D', 'DmP1', 'DmQ1']
def __init__(self, **kwargs):
for k, v in kwargs.items():
setattr(self, k, v)
assert self.bits % 8 == 0
def ispub(self):
return all(not hasattr(self, key) for key in self.PRIVATE_INFO)
def ispriv(self):
return all(hasattr(self, key) for key in self.PRIVATE_INFO)
def pub(self):
p = deepcopy(self)
for key in self.PRIVATE_INFO:
if hasattr(p, key):
delattr(p, key)
return p
def genkey(bits):
assert bits % 2 == 0
while True:
p = genprime(bits // 2)
q = genprime(bits // 2)
e = 65537
d, _, g = egcd(e, (p-1) * (q-1))
if g != 1: continue
iQmP, iPmQ, _ = egcd(q, p)
return Key(
N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
)
[...]RSA CRT를 위해 다양한 파라미터들을 생성하는데, public key를 export 할때는 P, Q, D, DmP1, DmQ1을 제외하고 N, E, iQmP, iPmQ, bits만 포함된 class instance를 pickle로 serialize 하도록 되어있다.
문제에서 주어진 key.sad.pub 파일이 이렇게 만들어진 파일이다.
일반적인 RSA 공개키 정보에 iPmQ = p-1 mod q와 iQmP = q-1 mod p가 추가로 주어진 셈인데, 이 정보를 이용해서 비밀키 정보를 알아내면 될것 같다.
 |
|---|
| 암호천재님께서 하사하신 메모 |
위와 같이 정리하면 p에 대한 2차 방정식을 구할 수 있다.
ap + bq = 1 (mod q)이므로, 원래 ap + bq = 1 + kn이 되어야 하지만, 0 <= a < q, 0 <= b < p이기 때문에 ap + bq < 2n이라서 k = 1로 확정할 수 있다.
위의 2차 방정식에서 p를 제외한 모든 값을 알고 있으므로 근의 공식을 이용하면 양의 정수 p를 유일하게 얻을 수 있다.
그로부터 q, d, DmP1, DmQ1을 계산하면 주어진 코드의 decryption 함수를 사용하여 flag를 얻을 수 있다.(code)
Flag : PCTF{Rub_your_hands_palm_to_palm_vigorously_for_at_least_20_seconds_to_remove_any_private_information}