The Rabin cryptosystem revisited (Q2349533)

The paper under review revisits the Rabin scheme used in public key cryptosystem. Message decryption requires one out of four roots of a quadratic equation in a residue ring to be chosen. A longstanding problem is to identify deterministically the encrypted message at the decryption side by adding the minimum number of extra bits to the cipher text. In this paper, the Rabin scheme in the standard setting is described, where both prime factors of \(N\) are congruent to 3 modulo 4, and a new identification rule exploiting Dedekind sums is proposed. Furthermore, it addresses the identification problem for any pair of primes, featuring a determinist scheme that works with primes congruent to 5 modulo 8, based on quartic residues of Gaussian integers, and a suboptimal solution for any pair of primes is proposed. Moreover, a Rabin signature is presented having a new padding mechanism that avoids relying on attempts until a suitable pad is found. Some forgery attacks are also examined.