# Using roots of unity mod n to break rsa when e and phi are not coprime

I am trying to solve an rsa problem where we only know the public key (n,e) and the ciphertext c.

The modulus n is actually a prime number, so we can easily compute phi as phi = n-1.

But the problem is that e shares a common factor with phi, where gcd(e,phi) = 8 , where gcd = greatest common divisor. So this means we can't get the private key d. Also e is a power of 2 (e = 16).

In my research I found that this problem has to do with something called "roots of unity modulo n". So basically if I compute all roots of unity I can get all possible plaintexts. But i can't seem to be able to understand the concept of "roots of unity mod n" and how this helps find all possible plaintexts.

Could someone please explain to me this ?

• Recent related question.
– fgrieu
Jan 22 at 10:01

But i can't seem to be able to understand the concept of "roots of unity mod n"

Well, the concept of "root of unity" is not that difficult.

After all, the $$k$$-th root of a number $$A$$ is a number $$B$$ with $$B^k = A$$ (and since we're working in the "mod n" ring, everything here is taken modulo $$n$$). For example, a 2-nd root (or square root) of $$9$$ is $$3$$ (because $$3^2 = 9$$), and a 3-rd root of $$125$$ is $$5$$ (again, $$5^3 = 125$$).

Now, the $$k$$-th roots of unity are those values $$B$$ with $$B^k = 1$$. Obviously, $$B=1$$ is one; if $$k$$ is even, then $$B=-1$$ is another one; in general, there are others as well.

how this helps find all possible plaintexts

I'm not exactly sure where you read this, or what they were thinking.

Since $$n$$ is prime, the easiest way (for $$e=16$$) is simply take four consecutive square roots. To compute a square root, you can either (if $$n \equiv 3 \pmod 4$$) compute $$\pm (m^{(n+1)/4}) \bmod n$$ (and then checking if that value squared gives you m) or (more generally) use the Tonelli-Shanks algorithm. Note that, in general, there will be either 0 or 2 square roots (there will be 1 only if $$m=0$$, which is presumably not the case).

So, what we do to find the 16th root of a value C is:

• Create a set S of intermediate values, initially consisting of the single value C

• Do the following 4 times:

• Create an empty set S'

• For each element in the set S, compute its square roots. If there are no square roots, skip it. If it does have square roots, add those values to S'

• Set S := S'

At the end, S will hold all the 16-th roots of C.