Blinding value of particular form I'm working with an implementation that creates a blinding value for RW signatures with the following C++ code:



Integer r, rInv;
ModularArithmetic modn(m_n);

do {
    // Do this in a loop for people using small numbers for testing
    r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
    rInv = modn.MultiplicativeInverse(r);       
} while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));


The Jacobi tests were added to remediate Sidorov's Breaking the Rabin-Williams digital signature system... and CVE-2015-2141.

Instrumentation is showing the loop can execute 1 time to 10 or 12 times (I believe the expected average is 8 times).

I feel like there's a way to speed up the execution of the loop. I started looking in the HAC and Google Scholar, but I did not find a related article or paper. I tried a couple of naive speedups, but they did not produce expected speedups or bound the worse case. The first was to generate a random integer in the range $[1, n - 1]$ that was congruent to $3 mod 4$. The second was to generate two smaller integers in the range $[1, p - 1]$ and $[1, q - 1]$ (both congruent to $3 mod 4$), and then multiply them.

Is there any way to speed up the execution of the loop so that the blinding value $r$ usually satisfies the condition in 1 or 2 tries or so?

Or is the implementation above ideal?



A related question is Rabin-Williams, blinding and size of Integer r? In this question, I explored smaller random integers to mask the operations.
What you are doing is the following:


Choose a random number $r$ in $[1,2^n-1]$.
Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1.
Check if $(\frac{r}{p})=(\frac{r}{q})=1$($(\frac{a}{n})$ denotes the jacobi symbol), if not go to 1.


So in order to speed this algorithm up, one needs to understand what the step #3 does.
"It calculates some Jacobi / Legendre Symbols" is too easy.
This step makes sure that $r$ is a square $\bmod p$ and $\bmod q$. Hence it makes sure that $r$ is a square $\bmod n$, because if r is a square $\bmod$ $p$ and $q$ than it's also a square $\bmod pq$. The calculations are split ub and not performed like $(\frac{r}{n})$ because $(\frac{r}{n})=(\frac{r}{p})*(\frac{r}{q})$ and if $(\frac{r}{p})=(\frac{r}{q})=-1$ then $(\frac{r}{n})=1$. So this doesn't work for optimzation.

But there's another way.
Step #3 makes sure we actually do have a square $\bmod n$, so why don't we construct $r$ to be a square $\bmod n$? Thus the "new" algorithm would look like this (sorry, I forgot the proper functions for Crypto++, post them in the comments please)



Integer r, rInv;
ModularArithmetic modn(m_n);

do {
    // Do this in a loop for people using small numbers for testing
    r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
    r = r*r%n; // square it, there was a better function for this IIRC
    rInv = modn.MultiplicativeInverse(r);       
} while (rInv.IsZero()); // we don't need the symbols because r is always a square


So what are the security implications with this?
I don't know for sure, you should contact the author of the paper in either case and make sure this solution works.
The squaring of $r$ shouldn't harm the randomness / unpredictability as if $r$ is random, $r^2\bmod n$ should be random / unpredictable as well.
Timing attacks? Shouldn't be a concern I think because an attacker may only observe one squaring and after this a related squaring making it really hard to use this. (if it's not impossible)

What else to say?
You even can store the "old" $r$ if you need the square root of the "new" $r$ in a later step.
The new algorithm looks like this: 


Choose a random number $r$ in $[1,2^n-1]$.
Set $r \gets r^2 \bmod n$
Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1.