[hackcon18] Ron, Adi and Leonard (Wiener Attack)

hackon ctf 2018에 나왔던 RSA 문제이다.

딱 봐도 e가 큰게 wiener attack이다!! 라고 생각했는데... 내가 가진 공격소스코드로는 풀리지않아서 굉장히 답답했는데;;

대회가 끝나고 난 후 다른사람들 writeup을 보니

잉... 나만 빼고 다들 wiener attack을 잘해서 풀었다 ㅡㅡ;

역시 이미 존재하는 툴이나 소스코드를 잘 활용해야하는 것인가...

문제는 아래와 같다.

You think you have me figured out don't you!?

n = 744818955050534464823866087257532356968231824820271085207879949998948199709147121321290553099733152323288251591199926821010868081248668951049658913424473469563234265317502534369961636698778949885321284313747952124526309774208636874553139856631170172521493735303157992414728027248540362231668996541750186125327789044965306612074232604373780686285181122911537441192943073310204209086616936360770367059427862743272542535703406418700365566693954029683680217414854103

e = 57595780582988797422250554495450258341283036312290233089677435648298040662780680840440367886540630330262961400339569961467848933132138886193931053170732881768402173651699826215256813839287157821765771634896183026173084615451076310999329120859080878365701402596570941770905755711526708704996817430012923885310126572767854017353205940605301573014555030099067727738540219598443066483590687404131524809345134371422575152698769519371943813733026109708642159828957941

c = 305357304207903396563769252433798942116307601421155386799392591523875547772911646596463903009990423488430360340024642675941752455429625701977714941340413671092668556558724798890298527900305625979817567613711275466463556061436226589272364057532769439646178423063839292884115912035826709340674104581566501467826782079168130132642114128193813051474106526430253192254354664739229317787919578462780984845602892238745777946945435746719940312122109575086522598667077632

푸는 법은 wiener attack!!

여기에 있는 소스코드를 참고하여 문제를 풀었다.

(https://github.com/MxRy/rsa-attacks/blob/master/wiener-attack.py)

아니면 RShack을 이용해서 풀어도 좋다.

이 툴 좋네...

sherlock@ubuntu:~/workstation/crytoTool/RSHack$ ./rshack.py  ######################### #      RSHack v2.1      # #      Zweisamkeit      # #      GNU GPL v3       # ######################### List of the available attacks: 1. Wiener Attack 2. Hastad Attack 3. Fermat Attack 4. Bleichenbacher Attack 5. Common Modulus Attack 6. Chosen Plaintext Attack List of the available tools: a. RSA Public Key parameters extraction b. RSA Private Key parameters extraction c. RSA Private Key construction (PEM) d. RSA Public Key construction (PEM) e. RSA Ciphertext Decipher f. RSA Ciphertext Encipher [*] What attack or tool do you want to carry out? 1 ***** Wiener Attack ***** [*] Arguments ([-h] -n modulus -e exponent): -n 744818955050534464823866087257532356968231824820271085207879949998948199709147121321290553099733152323288251591199926821010868081248668951049658913424473469563234265317502534369961636698778949885321284313747952124526309774208636874553139856631170172521493735303157992414728027248540362231668996541750186125327789044965306612074232604373780686285181122911537441192943073310204209086616936360770367059427862743272542535703406418700365566693954029683680217414854103 -e57595780582988797422250554495450258341283036312290233089677435648298040662780680840440367886540630330262961400339569961467848933132138886193931053170732881768402173651699826215256813839287157821765771634896183026173084615451076310999329120859080878365701402596570941770905755711526708704996817430012923885310126572767854017353205940605301573014555030099067727738540219598443066483590687404131524809345134371422575152698769519371943813733026109708642159828957941 ~~~~~~~~~~~~~~~~~~~~~~~~~       Wiener Attack              Zweisamkeit            GNU GPL v3 License    ~~~~~~~~~~~~~~~~~~~~~~~~~ [+] Private exponent: 108642162821084938181507878056324903120999504739411128372202198922197750954973