0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure if this helps / works, but have you tried $r=r^2\bmod n$ in between "randomize" and "invert"? This should construct a square IIRC saves you one jacobi computation because $J_n(r^2)=1$ and $J_n(x)=J_p(x)*J_q(x)$ if $n=pq$ $\endgroup$ – SEJPM Jun 14 '15 at 10:57
  • 1
    $\begingroup$ Actually, if you take SOJPM's suggestion, you needn't check the Jacobi's explicitly at all, as they'd always be 1 (the squaring implies that they can't be -1, as $r$ would not be a Quadratic nonresidue modulo $p$ or $q$, and they can't be 0 because if they were, the multiplicative inverse wouldn't exist). As for efficiency, this would reduce the number of loops to 1 (except in the extremely unlikely case you picked an integer that isn't coprime to $n$). $\endgroup$ – poncho Jun 14 '15 at 15:32
1
$\begingroup$

What you are doing is the following:

  1. Choose a random number $r$ in $[1,2^n-1]$.
  2. 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.
  3. 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:

  1. Choose a random number $r$ in $[1,2^n-1]$.
  2. Set $r \gets r^2 \bmod n$
  3. 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.
|improve this answer|||||
$\endgroup$
  • $\begingroup$ Does it need to be $(\frac{r}{p})=1$, or can it be $(\frac{r}{p}) != -1$? $\endgroup$ – user10496 Jun 14 '15 at 12:37
  • $\begingroup$ @jww $(\frac{r}{p})=1$ is basically the same as $(\frac{r}{p})\neq -1$, as $(\frac{r}{p})=0$ only happens if $r$ is a divisor of $p$ which only holds for $r=p$ which is eliminated by checking that the inverse exists. $\endgroup$ – SEJPM Jun 14 '15 at 12:39
  • $\begingroup$ It is easy to show that if $r$ is a uniformly distributed value in $Z^*_n$ (that is, relatively prime to $n$), then $r^2$ is a uniformly distributed value in the subgroup of Quadratic residues relatively prime to $n$. $\endgroup$ – poncho Jun 14 '15 at 15:36

Your Answer

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