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

Question

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 ?

Answer 1

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.