17

Day 17: Faster KEy Exchange

In this challenge we get a python program that performs a key exchange. Furthermore we know the parameters that were used and the message that was transmitted:

a = 17577019968135092891915317246036083578063875217491307011102321322815719709605741738459191569497548099944025771002530369133716621942963853230082186943938164591230020725702755002287589522851172217336150522367152517270250629688405924844750026155547199020780202996200555426652190631837288299999083335649923708175859594750237448640513280683859296367607523542293538555215282798100455110266565881599829107971869244773384413618546118850868579583095489023778055976570366853411496753062216229293710557686212314300848121614558806328788578096144576605248971916454783615989429937555579437307320472405217413938048149254574677430624
b = 15228628318558071728245462802366236848375416102820239825350329247148900182647243994904519787528142824353837070194785550898962097219309344881183948914850354340893035399529028331238911753358245357848436203268982345430735846016484221944423499956958406189854969330305125479065873712331269870135028162018087451460656203085824963123310757985362748654204595136594184636862693563510767025800252822776154986386637346156842972134635578534633722315375292616298410141343725683471387328655106920310236007034951004329720717533666052625540760911360823548318810161367913281234234193760867208897459774865037319252137821553407707977377
message = jqMYIn4fzSqzIXArwJm/kPitNhf4lwhL0yPRKpF+NYXyPmhoEwNG/k2L5vCZqFWNPvTzisnu93/8uK/PZnnCGg== 

The server uses those formulas to calculate the key:

key = b * x mod p
a = g * x mod p

We only know a, b, g and p but to calculate the key we need x. To find x we can rearrange the second formula:

a * g^-1 = x mod p

Now we can calulcate the key directly:

key = b * a * g^-1 mod p

The following Java program calculates the key and decrypts the message:

public static void main(String[] args) throws Exception {
    BigInteger g = new BigInteger("3");
    BigInteger p = new BigInteger("28485108048483664993555355548035280166222198895946001666176121626771296893249218737525397077847205668764480554612368693880365185901557208043000358783461327101490457849680507507328413906935238470600946894126028970738464658429417189298670225371208820807229458233765994963670464288033097820224657998869577152100773636751931664064681999115918785970221555076712326560102320184503893421537140609300213936571475982401475428083617012249514547394698764059628437049495276392667030591072895287238072475746662904967506303623654151867511895994963725102852006831097845186247182085468334772849374015522514204172587601623615066592937");

    BigInteger a = new BigInteger("17577019968135092891915317246036083578063875217491307011102321322815719709605741738459191569497548099944025771002530369133716621942963853230082186943938164591230020725702755002287589522851172217336150522367152517270250629688405924844750026155547199020780202996200555426652190631837288299999083335649923708175859594750237448640513280683859296367607523542293538555215282798100455110266565881599829107971869244773384413618546118850868579583095489023778055976570366853411496753062216229293710557686212314300848121614558806328788578096144576605248971916454783615989429937555579437307320472405217413938048149254574677430624");
    BigInteger b = new BigInteger("15228628318558071728245462802366236848375416102820239825350329247148900182647243994904519787528142824353837070194785550898962097219309344881183948914850354340893035399529028331238911753358245357848436203268982345430735846016484221944423499956958406189854969330305125479065873712331269870135028162018087451460656203085824963123310757985362748654204595136594184636862693563510767025800252822776154986386637346156842972134635578534633722315375292616298410141343725683471387328655106920310236007034951004329720717533666052625540760911360823548318810161367913281234234193760867208897459774865037319252137821553407707977377");

    BigInteger x = a.multiply(g.modInverse(p));
    String key = b.multiply(x).mod(p).toString();

    byte[] hashedKey = MessageDigest.getInstance("MD5").digest(key.getBytes());
    SecretKey aesKey = new SecretKeySpec(bytesToHexString(hashedKey).getBytes(), "AES");

    Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
    cipher.init(Cipher.DECRYPT_MODE, aesKey, new IvParameterSpec(key.substring(0, 16).getBytes()));

    byte[] cipherText = Base64.getDecoder().decode("jqMYIn4fzSqzIXArwJm/kPitNhf4lwhL0yPRKpF+NYXyPmhoEwNG/k2L5vCZqFWNPvTzisnu93/8uK/PZnnCGg==");
    byte[] clearText = cipher.doFinal(cipherText);

    System.out.println(new String(clearText));
}

private static String bytesToHexString(byte[] bytes) {
    StringBuilder out = new StringBuilder();

    for (byte aByte : bytes) {
        out.append(String.format("%02x", aByte));
    }

    return out.toString();
}