1
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ Recent related question. $\endgroup$
    – fgrieu
    Jan 22, 2023 at 10:01

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.