For this challenge we have some Python code that provides key generation and an encryption function. We also have the output of that script when the flag was encrypted.

The first thing I saw is that gmpy.next_prime() function is used, this is pretty weird as that function provides no randomness, it actually returns the next prime after the input value. After some analysis I realized that the encryption function looks like ElGamal, at that point the solution was pretty obvious:

  1. Write a decryption function

  2. Retrieve the private key from the public key

For writing a decryption function we first check where the message is used: e = divmod(pow(h, k, q)*m, q)[1] From this line we can conclude that if we have pow(h, k, q) we can calculate the inverse and retrieve the message from e. Unfortunately k is random so there is no chance we can get it, however h=g1^z and we also know u1=g1^k, therefore u1^z==h^k. We can compute z from the public key as g1 = next_prime(z), so z is the prime number before g1. Thanks to the Prime Number Theorem we know that if we go back from g1 checking each odd number if it is prime it will not take long.

Summing up, here’s the code that returns the flag ASIS_e4e6417b4baebb748da67e33f6e091d5

fox