We can factor $N$ using the given phi, or just simply look up the number on FactorDB. If the number returned has the form of $c = g ^ {k}$ with some even number $k$, we have the observation that for every factor of $N$, $c$ is a quadratic residue under that base, whereas the randomly generated number almost never generate a number that is a quadratic residue of all factors.

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 $$