# A game of square root modulo n

recently there was a CTF competition with a challenge which basically goes like this:

Choose two primes $$p, q > 2$$. The opponent then selects a random number $$r \ \epsilon \ [0, n]$$ with $$n = pq$$ and calculates $$s = r^2\ mod\ n$$.

Now, given $$s$$ we have to tell a number $$\hat{r}$$ such that $$s = \hat{r}^2 \ mod \ n$$

The opponent now calculates $$\hat{p} = GCD (n, (r - \hat{r})\ mod\ n)$$ and $$\hat{q} = n / \hat{p}$$ (GCD being the greatest common divisor).

You lose if $$\hat{p} > 1$$ and $$\hat{q} > 1$$ (i.e. your opponent is able to factorize n). Otherwise you win.

The tasks were to a) always win and b) always lose.

Task a) was not that hard: Simply by choosing $$p = q$$ the possible $$\hat{r}$$ shrink down to 2 which always allow your opponent to factorize n.
Calculating $$\hat{r}$$ boils down to using the tonelli shanks algorithm alongside the chinese remainder theorem.

However I have no idea for task b). Can someone point me in a direction?

Also note that the original opponent uses a miller rabin primality test to check if you are cheating. I was wondering if one could use this to cheat and select non-primes which pass the test? Though this did not seem feasible as the primes had to be very large.

Here is the link to the original challenge

• Miller Rabin is not a surefire test, but with enough random bases it almost surely will give the correct result. But even a primality proof is feasible in polynomial time. Adleman-Pomerance-Rumely would be my suggestion. Sep 10 '19 at 9:35

# 1. General Strategy for Task b.

If $$p,q$$ are two distinct odd, large primes, then with very high probability you will have $$\gcd(r,n)=1$$ so you may as well assume that.

In such cases, there will be 4 distinct solutions in $$[1,n]$$ to $$x^2\equiv s\pmod n$$

Two of the solutions will factor $$n$$ and there is no way to know which are the two without knowing $$r$$. (If $$r\equiv u\pmod p,r\equiv v\pmod q$$, then $$x=r$$ and $$x\equiv -u\pmod p,x\equiv -v\pmod q$$ are the two that fails to factor. $$(u,-v)$$ and $$(-u,v)$$ works.) So your chances to lose is only $$50\%$$. You need to lose $$0.9$$ of the $$42$$ runs, so the odds are very low.

This means that to solve task (b) you must cheat the primality test.
If you are able to use $$n$$ such that it comprises of $$k$$ different distinct odd primes, then there are $$2^k$$ possible solutions. Once again we can show that a factorization fails for only $$2$$ of those solutions, so the chances to lose increases to $$(2^k-2)/2^{k}$$.

If you can find many $$p,q$$ each a composite of 2 primes that passes the primality test, then $$k=4$$ and the probability is $$87.5\%$$, already almost $$90\%$$. You'll probably pass the challenge if given a few tries.

# 2. Passing the Primality Test

Looking at the code, the Miller-Rabin test uses base in the range $$[1,314]$$. An integer that passes the MR test with base $$a$$ is known as a Strong Pseudoprime to base $$a$$, so you are looking for integers that are Strong Pseudoprime to bases $$1$$ to $$314$$.

One example that you can find online that is Strong Pseudoprime to bases up to $$306$$ is \begin{align*} n = \;&28871482380507712126714295971303939919776094592797227009265160241974323037991527\\ & 33116328983144639225941977803110929349655578418949441740933805615113979999421542\\ & 41693397290542371100275104208013496673175515285922696291677532547504444585610194\\ & 94042000399044321167766199496295392504526987193290703735640322737012784538991261\\ & 20309244841494728976885406024976768122077071687938121709811322297802059565867 \end{align*}

If you try the primality test in the python code on this number, you'll see that it passes frequently, failing only for $$a=307,311$$ and $$313$$.

# 3. Generating Strong Pseudoprimes to Several Bases

So the problem boils down to constructing the Strong Pseudoprimes. One such algorithm can be found in Arnault's paper: "Rabin-Miller Primality Test: Composite Numbers Which Pass It" and it seems to be available publicly. However I'm not sure if it's efficient enough to solve the current problem without trying it. You may need a better algorithm if it finds solutions too slowly.

The idea of the algorithm is to find primes $$p_1,p_2$$ such that

(Arnault Strong Pseudoprime) Let $$p_1,p_2$$ be odd primes satisfying $$p_1=2q+1,\;\; p_2=4q+1$$ for some positive integer $$q$$. For a given integer $$b>1$$ (the base), if $$b$$ is a square but not 4th power modulo $$p_2$$ and $$b$$ is not a square modulo $$p_1$$, then $$n=p_1p_2$$ is a Strong Pseudoprime to base $$b$$.

Hence we can search for $$p=p_1p_2$$ being a Strong Pseudoprime to all bases $$b<314$$, after which it can be used for cheating.

We can brute force and try all $$q$$'s, using Jacobi Symbols to test for squares, but that would be inefficient. The paper gives steps to finding them faster using some Number Theory.