[Byte Bandits CTF 2018]R u Ronald Rivest?

[Crypto]R u Ronald Rivest? 70p

문제이름은 Are you Ronald Rivest?이다. Ronald Rivest가 누구지? 하고 검색해보았다.

RSA 암호 체계를 발명하신 분이다. 왠지 문제와 엄청 관계있을것같다.

이제 문제에서 주어진 파일을 보자.

text.txt 파일과 lol_pub.pem 파일이 주어진다. 

이 pem포맷파일은 문제이름에 나오는 RSA창시자 이름을 볼 때 RSA 공개키파일로 추측된다.

각각을 살펴보면 아래와 같다.

------------------------------------------------------------------------------------------------------------------------

PEM(Privacy-enhanced Electronic Mail)

여기서 준 lol_pub.pem 파일은 이름에서 유추해볼때 public_key파일이라는 것과 파일을 열어봤을때 첫줄과 마지막에 보이는 PUBLIC KEY로 이 파일이 공개키파일임을 알 수 있다.

RSA에서 쓰이는 공개키는 숫자인데, base64로 인코딩된 듯한 문자와 위아래로 텍스트 문자열(-----public ----)이 들어가 있다.

이러한 형태를 띄고 있는 파일은 PEM(Privacy Enhanced Mail) 포맷 파일로, 공개키를 암호화한 파일이다.

openssl을 이용해 개인키 및 공개키를 생성하면 위와 같은 파일을 자주 볼 수 있다.

비교해보기 위해 임의로 mykey.pem을 생성해보았다.

같은 형식인 걸 알 수 있었다.

그럼 openssl로 분석해볼까.. -noout -text 옵션으로 PEM 인코딩된 인증서를 파싱해서 정보를 출력해보겟다.

n = 225bit이고 e=65537인것을 알 수 있다. 

n을 좀 더 숫자로 표현해서 보고 싶다면 방법이 있다. ( https://stackoverflow.com/questions/3116907/rsa-get-exponent-and-modulus-given-a-public-key )

PUBKEY=`grep -v -- ----- lol_pub.pem | tr -d '\n'`  
echo $PUBKEY | base64 -d | openssl asn1parse -inform DER -i  

환경변수로 문자열을 파싱하고 base64 디코딩해 openssl을 통해 정보를 읽는다.

n이랑 e가 BIT STRING, offset 17에 들어있ㄷ. -strparse을 추가해서 파싱해주자.

아니면 그냥 openssl rsa -in pubkey.pem -pubin -text -modulus 로만 해줘도 잘나온다 (2018.12.07 추가)

n=0x013269DC2680BC64277889DC6A101ED6F13DD07498F13A4818474C2069

(32269109513264378873151120068074444086989044741418671122338798116969)

e=0x10001 (65537)

n을 찾았다!!

이제 소인수 분해를 하면 되겠다. 이 때 좋은 사이트가 있다는 것을 알았다.

FatorDB : http://factordb.com/    

이 사이트에 넣으면 만약 DB에 이미 소인수분해한 값이 있다면 그대로 알려준다. 매우 좋은 사이트다...!!

오옹... 감사합니다...

p,q = 1796360473659570891671495336244551, 17963604736595708916714953362445519

이제 p,q를 구했으니 개인키 d를 구하면 되겠다. 이 때 좋은 툴 rsatool 이 있다. 이걸 활용하자.

아 그놈의 gmpy... 다른 서버로 가야겠다.

n =

13269dc2680bc64277889dc6a101ed6f13dd07498f13a4818474c2069

e = 65537 (0x10001)

d = 24628356329157132106384879910356205355957782278135706168828095323773

(0xe9dc37c53f2e09f6c21dde172931a8e35ec454f10fb39c15a38f5e7d)

p = 1796360473659570891671495336244551 (0x589141bcf7bfd38312fcb363b547)

q = 17963604736595708916714953362445519 (0x375ac9161ad7e431ebddf01e514cf)

구할건 다 구했다.

text.txt에 있는 값들이 base64인코딩되있으니 디코딩해주자.

echo "AGRPJtAkcHxM5h9RiMMECc9KdKeXRuVvP5XlgsI=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt

echo "AAqhlINL/9sBf80jq9qgdHO+yXR1O0zyljGDzCo=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt

echo "AIV/vkErNAGt0j37090nxhiwwQyjtXcDugLTKDE=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt

뭐가 출력되는지 보자

좀 엉망이지만... 순서를 조금 정리해보자.

flag{u  

_n00b}

n0_10ng3r

flag{un0_10ng3r_n00b} 인것 같다... 굿!