# HackZone IX CTF: Likkrid’s Crypto writeups

Hello again, here we are at another edition of HackZone HZIX. Today, I am happy to share with you 2 writeups for Cryptography challenges that I prepared for the CTF. This isLikkrid,and this will be theauthor’s writeup, Let’s go ..

# BabeRSA [10 Solves-449 Points]

This challenge is intended to be the typical *easy* “BabyRSA” challenge. Python source code is provided and it seems quite over-complicating a straightforward logic (or maybe it’s hiding a deadly mistake too 😈). Let’s break it down.

“keys” function:

This functions creates keys as follows:

- Generates 2 1024-bits prime numbers p, q and calculates modulus = p * q
- Generates 3 random numbers (b, rand1, rand2) and calculates:

- Based on Fermat’s little theorem we have:

- Generates another 2 random numbers, modulo the “modulus”, rand_b1 and rand_b2 and return private and public keys.

“encrypt” function:

- This function simply returns two parts of the ciphertext:

“decrypt” function:

This part was omitted from the source code because:

- You can solve this problem with a one liner due to parameters “over-sharing” in the public key (sharing is caring 👀😝)
- Based on
*figure 1.3,*it is quite obvious that solving the system of 2 linear congruences will provide the plaintext:

## Solutions:

The “Cheesy” solution..

- Based on
*figure 1.3 we have:*

The modular inverse exists since, “by design”:

*GCD(X, modulus) = GCD(Y, modulus) = 1*

The “Smart” solution:

- Based on
*figure 1.2 we have:*

The first relation is based on Fermat’s little theorem, the second one “most likely (∗)” stands true (else we are facing a corner case where both partial ciphers are congruent to the modulus and can be read without factoring the modulus). We recover p with the GCD, then we use the Chinese remainder theorem to solve the system in *figure 1.4*.

That was mainly it for the first challenge, fairly easy but still a highly valuable one. Kudos to those who smashed this challenge with the cheesy solution 🧀

# My ECC For Dummies [3 Solves-498 Points]

This Challenge provides us with a source code of a cryptosystem and a link to a paper. After reading this paper and, keeping in mind that the cryptosystem used is a variant of ElGamal ECC , we conclude that we are dealing with *MV-ElGamal.*

After some Google-Fu and source code exploration, We can summarize the key generation, encryption and decryption steps as follows:

The implementation seems legit and sticks to the description so let’s dive deeper and specific aspects of the source code.

The Flag <Plain_message> is divided in two parts and converted to integers and both are smaller than <p> so we have no data loss in the encryption process. But what is this ID variable 🧐 Seems sus..

It seems like a unique identifier for the encryption but it is tightly related to the second part of the flag (the bitwise shift operation is equivalent to powers of 2) so we have:

This is a very bad choice for the function, because it introduces a simple *modular e’th root **problem*** . **We can calculate successive square roots modulo the prime <p> for all possible powers of 2 and we should recover the m2 value.

## Okay why does the author take us in this direction and how can we efficiently use the m2 value to recover the whole flag?

Let’s get back to the *figure 1.2 and focus on the S point’s coordinates used to craft the ciphertext components, we have the following:*

We know that the point S satisfies the curve equations, so we can inject the S coordinates in the equation:

We end up with a polynomial in m1 and m2 so if we know one of them we can recover the second part:

- In our case, we have the m2 so we can to solve the cubic root modulo <p> and we should recover the first part of the flag associated with one of the roots.
- I decided to use sage for this specific use-case because it felt easier to me!! We ended up solving modular square root for pow(2,20)

- Hopefully this was of any help for you if you had fun participating in HackZone IX, struggled to solve one of this crypto challenges or just seeking a hint to dive deeper into the details.
*You can find challenges source code and solvers***here**.

If you made it this far, thank you for your interest in this humble Crypto writeup. Looking forward to hearing from you about topics/ideas/feedback regarding this post. Feel free to reach out if you found any other/unintended solutions and as usual stay safe and hack carefully 🧡🧡

Used embed.fun to embed all the beautiful formulas in this writeup !!