Tweaked Square Roots and Rabin-Williams

Question

I'm reading Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art. In section 6, Bernstein states:

Recall that Rabin’s system needed to try several values of r, on average about 4 values, before finding a square H(r,m) modulo pq. The Rabin–Williams system eliminates this problem by using tweaked square roots in place of square roots. A tweaked square root of h modulo pq is a vector (e, f, s) such that e ∈ {−1, 1}, f ∈ {1,2}, and efs2 −h ∈ pqZ; the signer’s secret primes p and q are chosen from 3 + 8Z and 7 + 8Z respectively. Each h has exactly four tweaked square roots, so each choice of r works, speeding up signatures.

If I control key generation, then I can ensure p and q are chosen from 3 + 8Z and 7 + 8Z respectively, and I can possibly use the tweaked roots. Do tweaked roots violate P1363? What I might be really asking is, does an exponent of 2 run afoul of P1363, but I'm not sure at the moment.

If I cannot use tweaked square roots and/or an exponent of 2, then what are the remaining options? Is it principal roots and Jacobi?

If I load a private key generated by another library and it does not satisfy the conditions on p and q, then what are the remaining options? Is it principal roots and Jacobi?

My apologies for asking. I don't have a copy of the P1363 standard, so I'm not sure what the potential pain points are in using the algorithm described by Bernstein.

---

The ultimate goal of the exercise is to remediate CVE-2015-2141 (Evgeny Sidorov paper here). I'm trying to observe P1363 but avoid Jacobi.

Answer 1

An older copy of P1363 Public Key Cryptography was used below. In may (or may not) reflect the current state of affairs.

It also uses Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art.

---

Do tweaked roots violate P1363? What I might be really asking is, does an exponent of 2 run afoul of P1363, but I'm not sure at the moment.

No. The requirements IEEE places on them in 8.1.3.2 RW key pairs is:

An RW public key consists of a modulus n, which is the product of two odd positive prime integers p and q, such that p ≡⁄ q (mod 8), and an even public exponent e (2 ≤ e < n), which is an integer relatively prime to (p – 1)(q – 1)/4. [Note that these conditions imply that p ≡ q ≡ 3 (mod 4); moreover, one of the primes is congruent to 3 (mod 8) and the other is congruent to 7 (mod 8).]

So IEEE requirements are witness to tweaked roots.

---

If I load a private key generated by another library and it does not satisfy the conditions on p and q, then what are the remaining options? Is it principal roots and Jacobi?

If its satisfies IEEE requirements, then one prime ⊂ 3 + 8Z, and the other prime ⊂ 7 + 8Z.

If I relax requirements to those surveyed by Bernstein, then I only need to satisfy p, q ⊂ 3 + 4Z. In this case, the efficiency of tweaked roots is lost and it looks like Jacobi is needed.

---

While its not readily apparent, Jacobi is needed for the blinding that gets applied. Its not strictly required for the mathematics, but it is needed for the cryptography. You can see an example of it in practice in Sidorov's Breaking the Rabin-Williams digital signature system...:

do
{
    r.Randomize(rng, Integer::One(), m_n - Integer::One());
    rInv = modn.MultiplicativeInverse(r);
}
while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));