[Dreamhack] babycrypto3

PEM

Public Key Infrastructure Enhanced Mail

X.509 디지털 인증서와 키를 저장하고 전송하기 위한 표준 형식

텍스트 형식으로 인코딩되어 있으며, 보통 .pem 확장자를 가짐

일반적으로는 인증서, 개인 키, 공개 키 등의 암호학적 자격 증명 요소를 포함

 

RSA

비대칭 키 암호화 방식 (공개 키 - 데이터 암호화 / 개인 키 - 데이터 복호화)소인수분해의 어려움에 기반

 

Key Generation

1. 큰 소수 2개 p와 q를 선택2. n 계산 : n = p*q3. 오일러 파이 함수 계산 : ϕ(n) = (p-1) * (q-1) 4. ϕ(n)과 서로소인 정수 e 선택 5. e의 역원을 계산하여 d를 구함 : e * d ≡ 1 (mod ϕ(n))

→ 공개키 (n,e) / 개인 키 (n,d)

 

Encryption : C ≡ M^e (mod n)

Decryption : M ≡ C^d (mod n)

 

 

RSA 공격기법

 

[참고1] https://blog.naver.com/yjw_sz/221441769257

[참고2] https://velog.io/@pezluna/RSA

 

---

풀이

암호문 파일

공개키 파일

제공된 파일에는 암호문 파일과 공개키 파일이 들어있다.

 

pem 형식으로 된 공개키를 OpenSSL을 사용하여 파싱하여 공개키 (n,e)를 얻었다. 

(dreamhack 툴로 파싱하는 방법을 알고 싶다..)

openssl rsa -pubin -inform PEM -text -noout < pub.pem

 

공개키 n을 10진수로 변환하였다.

hex_string = "0328b14139a2e54b88a4662f1a67cc3acd1929c9b62794bb64916aff02991f80456e4d0eed4d591df7708d5af2e9b4fb5689"
decimal_value = int(hex_string, 16)
print(decimal_value)

 

변환한 10진수를 http://factordb.com/ 에 검색하여 소인수 p와 q를 얻었다.

 

구한 p와 q로 개인키 d를 구하고 hex로 변환한 암호문을 복호화해줬다.

from Crypto.Util.number import *

p = 291664785919250248097148750343149685985101
q = 109249057662947381148470526527596255527988598887891132224092529799478353198637
e = 65537 
c = 0x01141f557861aab3439be1eb87a012601536658a05f4f378f7b9dae54a08436e5c435d56dd1b4896b734aecd838841d59226

phi = (p-1)*(q-1)
d = inverse(e, phi)

print("개인키 : ", d)

m = pow(c, d, p*q)

print("복호화  : ", long_to_bytes(m))

 

복호화된 값을 base64 decoding하면 messge를 얻을 수 있다!

 

공부해볼것

- OpenSSL 사용법

- RsaCtftool  : https://github.com/RsaCtfTool/RsaCtfTool