Header

UZH-Logo

Maintenance Infos

The Rabin cryptosystem revisitet


Elia, Michele; Piva, Matteo; Schipani, Davide (2015). The Rabin cryptosystem revisitet. Applicable Algebra in Engineering, Communication and Computing, 26(3):251-275.

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.

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.

Statistics

Citations

2 citations in Web of Science®
2 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

11 downloads since deposited on 07 Dec 2016
11 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:June 2015
Deposited On:07 Dec 2016 07:50
Last Modified:21 Apr 2017 06:55
Publisher:Springer
ISSN:0938-1279
Publisher DOI:https://doi.org/10.1007/s00200-014-0237-0

Download

Download PDF  'The Rabin cryptosystem revisitet'.
Preview
Content: Accepted Version
Language: English
Filetype: PDF
Size: 243kB
View at publisher