Repeated modular square roots to recover original base

Question

I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, specifically $\gcd(\phi(p), e) = 2^{30}$. I was thinking of applying repeated modular square-rooting, and since $p \equiv 1 \pmod 8$, I can apply the Tonelli-Shanks algorithm to get two square roots of $c \pmod p$. However, repeating this until I reach $m$ would give me $2^{64}$ possible plaintexts to sift through. I know that the plaintext $m$ is 42 bytes long and I also know the first 6 bytes, and the last byte. How can I eliminate square roots before I go all the way down the "tree"?

Answer 1

How can I eliminate square roots before I go all the way down the "tree"?

The obvious thing to do is eliminate intermediate values that are not quadratic residues. Here is one way to do it:

Define the set s := [ c ], that is, s initially consists of a single element c.
For i := 0 to 63 do
    Set the set t := [], that is, initialize it to be the empty set
    For each element a \in s
        Use the Toneli-Shanks algorithm to find the square roots b, -b of a$
        Check if b*b = a mod p; this cannot hold if a is not a quadratic residue
        If the check holds, then add b, -b to the set t

    Set s := t

At the end, the set s will consist of all the possible $2^{64}$th roots.

This won't iterate through $2^{64}$ values because the Quadratic Residulosity check will reject about half of the incorrect paths (as half the possible values are not Quadratic Residues) . Instead, the sizes of the sets s, t should be reasonable (in my experience based on similar algorithms, possibly hundreds of elements)