Rabin-Williams scheme (source code)

= Rabin-Williams scheme
{c}
{title2=$N=pq$}

The Rabin-Williams scheme is a family of modified <Rabin cryptosystem> constructions using a modulus $N=pq$ with distinct <prime numbers> $p\equiv3\pmod8$ and $q\equiv7\pmod8$. These congruences make sign and doubling adjustments useful for producing <quadratic residues> before taking <modular square roots>. In signature variants, the private <integer factorization> permits root extraction while the public verification uses squaring.

The arithmetic mechanism can be seen without fixing a full message encoding. For a unit $h$ modulo $N$, exactly one of $h,-h,2h,-2h$ is a <quadratic residue> modulo both primes: the two signs change both <Legendre symbols>, while multiplication by $2$ changes only one of them. For the toy modulus $77=11\cdot7$ and $h=5$, the adjustment $-2h\equiv67$ has square root $12$, since $12^2\equiv67\pmod{77}$.

A complete <digital signature> scheme must additionally specify message hashing or redundancy, the selected root, and how the adjustment is encoded and verified. The congruence calculation alone is not such a scheme. A specific modified-Rabin message-recovery construction is given in the primary handbook, rather than being identical to raw four-root Rabin encryption.<Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone>[Section 11.3.4, Fact 11.28 and Algorithms 11.29–11.30; notes to section 11.3 credit Williams]{ref}