Abstract
The Rabin scheme used in public-key cryptosystem is here revisited with a focus limited to a few specific open issues. In particular, message decryption requires one out of four roots of a quadratic equation in a residue ring to be chosen, and a longstanding problem is to identify unambiguously and deterministically the encrypted message at the decryption side by adding the minimum number of extra bits to the cipher-text. While the question has already been solved for pairs of primes of the type 4$\mathit{k}+3, the general problem is here addressed. As one of the major results, an explicit solution with two extra bits is provided for pairs of primes that are congruent 5 modulo 8. The Rabin signature is also reconsidered from a deterministic point of view: a padding mechanism is proposed that avoids relying on a certain number of attempts until a suitable pad is found.
Elia, Michele