System32.kr [RSA105] 풀이

RSA105  풀이 : e가 매우 작은 경우

n : 14563994539777678316321336781712344883711529518189434139233680882263409604514153869699501702104322682479573897503872406635890483506906896813982089686642192006130896329932374470690714494675193648369783731927754727548782563723442681780574596631901415395263336968261396444462141129255716197310580275877681304858562705807686921384452565148850113267428665758030506035314679252439022969913295597306528946210184007253645129375949497711293612867692547866985135149571625792745784234869796370504461309988327790266777539646009367784188629367635437858554533733747458534618750336302736798813966890424262766487012612696221075689613
e : 7
c : 3257687211413179849713234287228115652852064803596545802006316144655701336714918948672668217982037728069055370417273850104541474476810598369542627961429180060096555295519064954697207788677528957569208943432299557549774333187664920215674167987939460257141632237998790136575185293301081863083862494006009415801599660234577382347813571039134562532471377834137776834839392965274882404992875421226913724316557631483699200757

 

e의 값이 7로 매우 작고 N은 매우 크다. 이 경우 M^e mod N = c 에서 mod N 과정을 거치지 않게 되어 M^e = c가 된다. 그럼 c의 e제곱근이 M이 된다.

 

import gmpy2
 
num=3257687211413179849713234287228115652852064803596545802006316144655701336714918948672668217982037728069055370417273850104541474476810598369542627961429180060096555295519064954697207788677528957569208943432299557549774333187664920215674167987939460257141632237998790136575185293301081863083862494006009415801599660234577382347813571039134562532471377834137776834839392965274882404992875421226913724316557631483699200757
k=7
 
result, bool = gmpy2.iroot(num, k)
print(result)

 

나온 값 -> hex -> ascii 로 변환

 

FLAG : FLAG{too_short_too_small}