Again, I do not know how to solve this problem. Leave it to the future me to digest how to solve lattice problems and understand a bit more about group theory. The original attack is from Shamir et al., but a low-density attack that leverages the LLL algorithm. A version is mentioned in this awesome paper. Sage Implementation: a = [ #public key ] s = #ciphertext n = len(a) N = ceil(sqrt(n) / 2) b = [] for i in range(n): vec = [0 for _ in range(n + 1)] vec[i] = 1 vec[-1] = N * a[i] b.

I did not manage to solve this challenge. The private key is composed by some $f, g$, both smaller than $\sqrt{\frac{q}{2}}$, with the relation that $fh - g = 0 \mod q$ This means that there exists a $k$ such that $fh = qk + g$, since $h$ is about the same size of $q$, we have that $k$ is the same size of $f$. We have the observation that $f \cdot (h, 1) + (-k) \cdot (q, 1) = (g, f - k)$, where both components of the result are small (g is around the square root of $\frac{q}{2}$, and $f$ is approximately $k$).

Googling the name of the challenge should point us to a paper, detailing how Miller-Rabin tests are misused in practice - some strong pseudoprimes can still pass the Miller-Rabin test. Searching for the implementation of this challenge will lead us to this Github repo. Running the script should lead to a pseudoprime n = p1 * p2 * p3. Sending the base as one of the primes and the prime as n will return the flag.

No shot I would get this. This challenge is based on the Paillier cryptosystem, an additive homomorphic cryptosystem. Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily. Indeed, by binomial theorem: $$ (1 + n) ^ x = 1 + nx + {x \choose 2} n ^ 2 + \text{higher powers of n} $$ which, under modulo $n ^ 2$, leads to: $$ (1 + n) ^ x = 1 + nx \mod n^2 $$

I did not know the way to solve the challenge after some naive idea of using Pohlig-Hellman on the smooth prime given. Nonetheless, it was a good try as after peeking at the solution, there is no shot that I can solve this without knowing some group theory of have acute observation of the number patterns. The first way to solve this, and one can look up in this paper, about Genus 0 Curves.