# Repeated modular square roots to recover original base

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"?

• Is e larger than $\phi(p)$? – SEJPM Sep 20 at 17:48
• @SEJPM No, $\phi(p) > 2^{1029}$. – PolarBITS Sep 20 at 17:51

Define the set s := [ c ], that is, s initially consists of a single element c.
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) • Indeed there are typically less than$e$solution, and this finds them all. The check can be made: if$i=63$or$b^{(p-1)/2}\bmod p=1$, then add$b$,$-b$to the set$t\$; this avoids entering elements in the set that will be found useless on the next pass. – fgrieu Sep 21 at 12:34