[HackCTF] RSA3

 

n = 10283681839193276126097189449431804469761940095295471888398234447479454966284763902940257262270896218602885591849219329295416054197234326881779747263501982465102957508563705432633950651360492963151374387619070656704554971992649022858286686244477458518219811343940208016922937570643216329114427596008380607613093481777894261584227765149699743645734317383348201997748556656749211035951710759363655486663011079526697122026161182876988679088458171192764980121987583057238040415225285169219391637708267493561674900564748140379192079752942242600521017002960185256025253900075152690586476143729320416895984549165574371936823

 

c = 0x5c93ba85692a8b3981a5d47be0e80d129b8a2f6cf4dc134547aa7e1620f6691513b1dc1d69e085c39e261c2b49026436bb243dba70a86f7fcd1a3a7e6b0f0ecfac015becad0a76e9cf208d5d31e2b4865

 

e = 3

 

 

문제에서 주어진 값들은 n ,c ,e이다. 보통 3가지 값으로는 복호화가 불가능하지만 e가 매우 작다면 n이 매우 크므로 뒤에 mod n이 의미가 없어지므로 평문 = 암호문**(1/3)이라는 식으로 복호화가 가능하다.

 

 

 

 

 

 

 

---

from gmpy2 import *

 

c=0x5c93ba85692a8b3981a5d47be0e80d129b8a2f6cf4dc134547aa7e1620f6691513b1dc1d69e085c39e261c2b49026436bb243dba70a86f7fcd1a3a7e6b0f0ecfac015becad0a76e9cf208d5d31e2b4865

 

e=3

 

with local_context() as ctx:

    ctx.precision = 3000

    m=cbrt(c)

 

#print(hex(int(c**(1/3))))       // 0x4861636b4353a00000000000000000000000000000000000000000

print(hex(int(m)))            // 0x4861636b4354467b48336c6c305f4d795f337870306e336e74217dL

 

 

 

 

---

위 코드와 같이 일반적인 방식으로 세제곱근을 구하면 중간에 값이 짤리므로 gmpy2를 이용해 세제곱근을 해야한다. gmpy2를 사용하기 위해서는 몇가지 라이브러리를 설치해야하므로 구글에 검색하면 알 수 있다. 결과를 아스키코드 문자로 변환하면 플래그가 출력된다.