HackTM CTF 2020

This CTF I played as a part of Team Shakti. Must say , the team must really love the Rubik’s cube . There were a lot of challenges based on it. But I attempted only the ones without the cube while my teammates were wrecking their heads off. In this post I shall be covering three challenges from the Crypto section :

RSA is easy #1

Given an array of cipher texts and the encryption algorithm. We have n and e . Taking a look at the script we see that it is a character by character encryption of the flag. So you just use a dictionary encrypt each character and map it.

RSA is Easy #2

There are two ways to solve this challenge – 1. GCD , 2. Frequency Analysis
The second one is not related to RSA at all but it takes a shorter time.

GCD

Given the cipher texts. Like the first challenge this is a character by character encryption of the flag but n is not given. So we recover n. We do not know which plain text maps to which cipher text so we guess two random characters that might be there( My teammate guessed a comma and a space) . So we calculate c = m**e – c1. There are 31 unique cipher texts. So there are 31 values for c1. Two lists are created for the two characters . Now, for the correct values of c’s for the two characters their GCD would be equal to n. So we brute force :

(Disclaimer : Snippet took almost an hour to finish execution)

Now the problem becomes same as the previous one and hence we recover the flag.

Frequency Analysis

This one is pretty simple. Just forget about RSA. Given a paragraph, each character subsituted with a unique number. So you replace these 31 characters + some extra characters(like ‘,’,’.’ which you have to guess) then treat it as a substitution cipher . Put it in some site like https://quipqiup.com/ and you get the solution.

when it comes to crypto or carpet never roll your own

So the flag is HackTM{when_it_comes_to_crypto_or_carpet_never_roll_your_own}

Bad keys

Basically you connect to a service which generates (e,n) and (d,n) on prompt. This can be done any number of times. So we guessed that it must be some problem with the generation of keys. We collected a few values of (n,e ,d) and factorized n. One of the factors p or q of the first collected value is : p=12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163L

And the next values are p = next_prime(p) and so on. So our target is to find the value of p from which it started. The exploit script can be accessed here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s