The Rabin cryptosystem uses modular squaring with public modulus , where and are distinct odd prime numbers kept secret. The raw encryption map sends a message representative to
Knowing the prime factorization lets the receiver compute modular square roots modulo each prime and combine them by the Chinese remainder theorem. For a message coprime to , its ciphertext has exactly four roots modulo , corresponding to the two sign choices modulo each prime. A full encryption scheme therefore needs a specified message encoding or other rule to select the intended root; raw modular squaring by itself is four-to-one on the units.[ref]
For example, and give . Its four roots are modulo . The relation to integer factorization is especially direct: two roots that differ by more than an overall sign reveal a nontrivial factor through a greatest common divisor. The Rabin-Williams scheme is a more specific variant, rather than another name for every Rabin cryptosystem.
The Rabin-Williams scheme is a family of modified Rabin cryptosystem constructions using a modulus with distinct prime numbers and . 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 modulo , exactly one of is a quadratic residue modulo both primes: the two signs change both Legendre symbols, while multiplication by changes only one of them. For the toy modulus and , the adjustment has square root , since .
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.[ref]
For coprime moduli and , the Chinese remainder theorem recovers the integer uniquely in from the two ciphertexts. An ordinary integer square root then recovers the message. If distinct semiprime moduli share a factor, their greatest common divisor instead reveals factors of both moduli. Learning one message in the coprime case does not by itself give a general factoring algorithm or a decryption key for other ciphertexts.
If and while , then
and is a nontrivial factor of .
For with distinct odd primes, choose a uniform unit and give only to an oracle returning any square root . Conditional on this square, is uniform among four roots and independent of the oracle's choice. With probability one half, is not , and is a nontrivial factor. Thus full inversion of the squaring map yields randomized integer factorization; this reduction does not equate arbitrary partial leakage with full inversion.
If a purported authentication service returns a square root of every chosen square modulo a Rabin modulus, a verifier who knows one root obtains a different root with substantial probability and can factor the modulus. Repeating the challenge therefore reveals the private key.

Articles by others on the same topic (0)

There are currently no matching articles.