Score:1

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

sz flag

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 ?

fgrieu avatar
ng flag
Recent related [question](https://crypto.stackexchange.com/q/103830/555).
Score:2
my flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.