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

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

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)

  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Sep 21 '20 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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