Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Applicable Algebra in Engineering, Communication and Computing
Published in: Applicable Algebra in Engineering, Communication and Computing 3/2015

01-06-2015 | Original Paper

The Rabin cryptosystem revisited

Authors: Michele Elia, Matteo Piva, Davide Schipani

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 3/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 \(4k+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.
previous article Self-dual codes from 3-class association schemes
next article Modelling algebraic structures and morphisms in ACL2

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Apostol, T.M.: Introduction to analytic number theory. Springer, New York (1976)MATH
2.
Bach, E., Shallit, J.: Algorithmic number theory. Cambridge Mass, MIT (1996)MATH
3.
Bernstein, D.J.: Proving tight security for Rabin–Williams signatures. In: Smart, NP. (ed.), EUROCRYPT 2008, LNCS, vol. 4965, pp. 70–87. Springer, New York (2008)
4.
Buchmann, J.A.: Introduction to cryptography. Springer, New York (1999)MATH
5.
6.
Dedekind, R.: Schreiben an Herrn Borchardt. J. Reine Angew. Math. 83, 265–292 (1877)MATH
7.
Eisenstein, G.: Über einige allgemeine Eigenschaften der Gleichung, von welcher die Theilung der ganzen Lemniscate abhängt, nebst Anwendungen derselben auf die Zahlentheorie. J. Reine Angew. Math. 39(224–274), 275–287 (1850)CrossRefMATH
8.
9.
Elia, M., Schipani, D.: Improvements on the Cantor–Zassenhaus factorization algorithm, to appear in Math. Bohem
10.
Freeman, D.M., Goldreich, O., Kiltz, E., Rosen, A., Segev, G.: More constructions of lossy and correlation-secure trapdoor functions, PKC 2010, Springer LNCS 6056, 279–295 (2010)
11.
Fröhlich, A., Taylor, M.J.: Algebraic number theory. Cambridge Univ. Press, Cambridge (1994)
12.
Galbraith, S.: The mathematics of public key cryptography. Cambridge Univ. Press, Cambridge (2012)CrossRef
13.
Grosswald, E.: Topics from the theory of numbers. Birkhäuser, Basel (2009)MATH
14.
Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. Oxford at the Clarendon Press, Oxford (1971)
15.
Hoffstein, J., Pipher, J., Silverman, J.H.: An introduction to mathematical cryptography. Springer, New York (2008)MATH
16.
Ireland, K., Rosen, M.: A classical introduction to modern number theory. Springer, New York (1998)
17.
Kaiblinger, N.: Cyclotomic rings with simple Euclidean algorithm. JP J. Algebra Number Theory Appl. 23(1), 61–76 (2011)MATHMathSciNet
18.
Kurosawa, K., Itoh, T., Takeuchi, M.: Public key cryptosystem using a reciprocal number with the same intractability as factoring a large number. CRYPTOLOGIA XII, 225–233 (1988)CrossRef
19.
Kurosawa, K., Takagi, T.: One-wayness equivalent to general factoring. IEEE Trans. on Inform. Theory 55(9), 4249–4262 (2009)CrossRefMathSciNet
20.
21.
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of applied cryptography. CRC Press, Boca Raton (1997)MATH
22.
Monico, C., Elia, M.: On the representation of primes in \(\mathbb{Q}(\sqrt{2})\) as sums of squares. JP J. Algebra Number Theory Appl. 8(1), 121–133 (2007)MATHMathSciNet
23.
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern J (ed) Advances in Cryptology—EUROCRYPT ’99. Lecture Notes in Computer Science, vol 1593. Springer, Berlin, pp 223–238 (1999)
24.
Paillier, P., Pointcheval, D.: Efficient public-key cryptosystems provably secure against active adversaries, advances in cryptology—ASIACRYPT99. Lect. Notes Comput. Sci. 1716, 165–179 (1999)CrossRef
25.
Pieprzyk, J., Hardjono, T., Seberry, J.: Fundamentals of computer security. Springer, New York (2003)CrossRefMATH
26.
Rabin, M.: Digitalized signature as intractable as factorization, technical report MIT/LCS/TR-212, MIT Laboratory for Computer Science, January (1978)
27.
Rademacher, H., Grosswald, E.: Dedekind sums. MAA, New York (1972)MATH
28.
Schneier, B.: Applied cryptography. Wiley, New York (1996)
29.
Takagi, T., Naito, S.: Extension of Rabin cryptosystem to Eisenstein and Gauss Fields. IEICE Trans. Fundam. E80–A(4), 753–760 (1997)
30.
von zur Gathen, J., Gerhard, J.: Modern computer algebra. Cambridge Univ. Press, Cambridge (1999)MATH
31.
Williams, H.C.: A modification of the RSA public-key encryption procedure. IEEE Trans. Inf. Th. IT–26(6), 726–729 (1980)CrossRef
Metadata
Title
The Rabin cryptosystem revisited
Authors
Michele Elia
Matteo Piva
Davide Schipani
Publication date
01-06-2015
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 3/2015
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-014-0237-0

Premium Partner

    Image Credits