> For the complete documentation index, see [llms.txt](https://docs.cooku222.kr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-uncommon-e.md). # \[DreamHack] uncommon e #### 문제 링크 [uncommon eDescription 아모가 무슨 일이 있었던 건지, RSA에서 절대 평범한 e를 쓰지 않겠다고 하네요. 도대체 무슨 일이 있었던 걸까요?dreamhack.io](https://dreamhack.io/wargame/challenges/982) #### 문제

#### WriteUp \*RSA 암호를 이루는 값들의 오용으로 인한 취약점을 공격하는 Common modulus attack을 실습함. ``` from Crypto.Util.number import getPrime, GCD, bytes_to_long FLAG = b"DH{????????????????????????}" FLAG = bytes_to_long(FLAG) while True: p = getPrime(1024) q = getPrime(1024) N = p * q # e = 0x10001 # assert GCD((p - 1)*(q - 1), e) == 1... Oh, COME ON.. Stop generating that stupid COMMON e. for e1 in range(0x100, 0x10001): if GCD(p - 1, e1) >= 0x100: # much better! break for e2 in range(0x100, 0x10001): if GCD(q - 1, e2) >= 0x100: # This is nice!! break if GCD(e1, e2) == 1: # UN-UN common == common :P break print(f"{N = }") print(f"{e1 = }") print(f"{e2 = }") FLAG_enc1 = pow(FLAG, e1, N) FLAG_enc2 = pow(FLAG, e2, N) print(f"{FLAG_enc1 = }") print(f"{FLAG_enc2 = }") ``` -> 같은 n을 사용하고 서로 다른 서로소인 enc을 이용하여 암호화된 두 암호문이 주어짐. Common modulus attack의 사용 조건과 일치함.

common modulus attack

-> 해당 상황에서 m을 복구하는 것이 목적이고, r\*e1 + s\*e2 = 1을 만족하는 r, s쌍을 찾는 것으로부터 공격이 시작됨\ \- r, s쌍은 확장 유클리드 알고리즘을 사용하여 구할 수 있지만, pow 함수나 PyCryptodome의 inverse 함수를 이용하여 역원을 구하는 과정 또한 확장 유클리드 알고리즘을 사용하기에 결과적으로 동일함. \ \=> pow 함수를 이용하여 r, s쌍을 구해본다면,\ r\*e1 + s\*e2 = 1의 식에서 양식을 mod e2위에서 생각하면 다음과 같이 식이 변형됨

\=> e1^(-1) mod e2, \ \=> pow(e1, -1, e2) 또는 inverse(e1, e2)를 사용하여 원하는 r을 구할 수 있음\ s = (1-r\*e1)/e2를 통하여 원하는 s의 값까지 마저 구하면 r\*e1 + s\*e2 = 1을 만족하는 정수 r,s 쌍을 구할 수 있음\ 그 후, c1^r \* c2^s mod n을 구해 m을 복구할 수 있음\ #### Solve.py ``` from Crypto.Util.number import GCD, long_to_bytes N = ... e1 = 26107 e2 = 416 FLAG_enc1 = ... FLAG_enc2 = ... assert GCD(e1, e2) == 1 r = pow(e1, -1, e2) s = (1 - r * e1) // e2 assert r * e1 + s * e2 == 1 m = (pow(FLAG_enc1, r, N) * pow(FLAG_enc2, s, N)) % N print(long_to_bytes(m).decode()) ``` \ \*RSA의 공개키인 n, e의 오용을 이용해 Common modulus attack을 실습함 --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-uncommon-e.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.