CTF: How to break large keys

29/01/17 — capitol

channel

name:

Chad - Big Friendly Key

category:

crypto

points:

300

Writeup

The next crypto challenge from xil.se is one called “Big Friendly Key”, and is also about RSA. It can be played here: nc ctf1.xil.se 4200

We are presented with a large public key that we need to factorize in order to calculate the private key, and be able to get the flag.

The public key we get is 2466 characters long, so implementing the factorization with Sieve of Eratosthenes and a for loop is not possible. We need to be smarter than that in order to retrieve the factors.

In RSA the public key (often denominated as ‘n’) is the result of multiplying two large primes together (‘p’ and ‘q’). This means that min(p, q) < sqrt(n), and that the primes will be about the same distance from sqrt(n) on the number line.

So if we start the factorization attempt from sqrt(n) instead of from 0, the number of checks we need to do will be smaller, and this turned out to be the key to solving the challenge.

Solution

public class App {

    public static void main(String[] args) throws IOException {
        BigInteger n = new BigInteger("416169672835081282998769137494773685438037552023727931365543107088305449322247098366362038692812865577864709412723942223262235657896039670548400775875502028244264086890258015614848039147585802253777721057085933553667884397355523033992420423284512368275620282484094800790255015050756472656528857875999415430288567423780696211101919244912731503020484259003956337445150970055069757551101607907780613344889259107459445808657708831819381883285898284907897313618472636990460629017854905120909079954395786865840376714813786450281041170987118610395891985542340051585428437191463408723549970260034504586057040797250819326016820697616235229363296975478685433918791355651467874485746685099986055301279284955200395776734258332572835932083332856553673655850102559207899227139085205860354580779850684429350768269994299853444422476808708374995020858371165582000842160879753115440201557027979009440356196081610804628948780339914622568740577566087705257452487267706177803860765522414266994340984200477614843276175866858932704564210543652217970461273891796710727593851152911486039926569939900592536340038308452714618150868179181006388336269453119942468050655123824437606190555497689932978735733100729454571569556557771448695435528117859363478476323288338512444882311138112761797930425501220150246154689439030391577355501884478973374616451073759109853746483677174774270766488239603018594423965306557818505255243993124125139257139919436717463399671528187365798314738132565884696713061488284993730692922167364349151035630702440112627149237476193121818350316293630392651858322832247517813373131406421917108857822815534220217972051555808348581966584448065510164481154556002780432710646949488310076918006368654072183058127889013653568505330352570061526436992948530207134330408423688546569615629750532701608383701353461837899262357791597625952593072110698318475020884429832660133752929456719383958651179066074022478732887480285411790448473660710941722415189387461675252239724078742557909692093484138954948275709283080017144368633872142836542025748354826963031206732971747529200698437611832101282505298057318219172294987426573876634241665988827454046578492923496729283920998800756322041408438934304101642860537718379580856109416040521527597372118585064105190092935438199571174655466342465334401702047906278349808648695633798302876948729915991836520484724328030526726201691610370037201026223423773609048447805646265048564126073072591007202942226771180473432116602751135532294757300663257956983", 10);
        BigInteger p = new BigInteger("645112139736248710905676333261885435188347497319853763606697604578494999341572061985503959419410566322310156476156532708370066894108978912704095835570392868833208397928599715227100416938948855617976721706666152059398906196547451371132294976690648179164352468186844510815737678942851859362022890784482847574758980008803674772758843737968522391795799201104385009789468663103248453930536139987565601523421164080780964587877154114977309374691939189662099763103839285673927206638757408747159139589670811906179480473019937352377673319453740094148975105063034183547333008036088441459560427579741536617804393215231569845372627149607952334434949008746580225497230343424268239460690071064167808060147354361356353965259468495036682660405631547021679023005834182430173342276893060574471211477101864674832495896494954808679606105893087511442395500662760257637261789415476874532660163983761982977746084239780846131607316690232497385719313120112203549865788731061699332852564753659818450181160926404440143485191554632425853822187540540330875499721577244724605126385483995297255769250448748603906191835581928447198324376499223489573053014677969815076536504143378050499085751727671555574912614578341849411731846770158151769540347683868871667691460197");
        BigInteger q = new BigInteger("645112139736248710905676333261885435188347497319853763606697604578494999341572061985503959419410566322310156476156532708370066894108978912704095835570392868833208397928599715227100416938948855617976721706666152059398906196547451371132294976690648179164352468186844510815737678942851859362022890784482847574758980008803674772758843737968522391795799201104385009789468663103248453930536139987565601523421164080780964587877154114977309374691939189662099763103839285673927206638757408747159139589670811906179480473019937352377673319453740094148975105063034183547333008036088441459560427579741536617804393215231569845372627149607952334434949008746580225497230343424268239460690071064167808060147354361356353965259468495036682660405631547021679023005834182430173342276893060574471211477101864674832495896494954808679606105893087511442395500662760257637261789415476874532660163983761982977746084239780846131607316690232497385719313120112203549865788731061699332852564753659818450181160926404440143485191554632425853822187540540330875499721577244724605126385483995297255769250448748603906191835581928447198324376499223489573053014677969815076536504143378050499085751727671555574912614578341849411731846770158151769540347683868871667691456939");

        BigInteger e = new BigInteger("65537", 10);

        RSA rsa = new RSA(p, q, e);

        Socket attackTarget = new Socket("ctf1.xil.se", 4200);
        PrintWriter out = new PrintWriter(attackTarget.getOutputStream(), true);
        BufferedReader in = new BufferedReader(new InputStreamReader(attackTarget.getInputStream()));

        Pattern messageP = Pattern.compile(".*'(.*)'.*");

        String in1;
        in.readLine();
        in.readLine();
        in.readLine();
        in.readLine();
        in.readLine();
        out.println("2");
        in.readLine();
        in1 = in.readLine();
        Matcher m = messageP.matcher(in1);
        m.matches();
        out.println(new BigInteger(m.group(1).getBytes(StandardCharsets.ISO_8859_1)).modPow(rsa.getD(), n).toString(16));
        in.readLine();
        in.readLine();
        in.readLine();
        in1 = in.readLine();

        System.out.println("flag: " + new String(new BigInteger(in1.substring(6), 16).modPow(rsa.getD(), rsa.getN()).toByteArray()));
    }
}

Image credit