Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Applicable Algebra in Engineering, Communication and Computing
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 3/2015

01.06.2015 | Original Paper

The Rabin cryptosystem revisited

verfasst von: Michele Elia, Matteo Piva, Davide Schipani

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Self-dual codes from 3-class association schemes
Nächster Artikel Modelling algebraic structures and morphisms in ACL2

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
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.
Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comp. 36(154), 587–592 (1981)CrossRefMATHMathSciNet
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
Metadaten
Titel
The Rabin cryptosystem revisited
verfasst von
Michele Elia
Matteo Piva
Davide Schipani
Publikationsdatum
01.06.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 3/2015
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-014-0237-0