Total views : 104

Algebraic Analysis of a Rabin-Like Cryptosystem and Its Countermeasures


  • Al-Kindi Cryptography Research Laboratory, Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Malaysia
  • Mathematics Department, Faculty of Science, Universiti Putra Malaysia, Malaysia


Objective: In this paper, we present two algebraic analyses upon a new Rabin-like public key cryptosystem namely the Rabin-p cryptosystem. Methods/Analysis: We show that by using the continued fraction’s method and the Coppersmith’s theorems, there exists inappropriate parameter’s size that can affect the security of Rabin-p cryptosystem. Findings: The first analysis proved that the prime factors of its public key can be found amongst the list of the continued fraction expansion of the ciphertext c and the modulus in polynomial time. For the second analysis, by using the Coppersmith’s theorems we showed that the message m can be retrieved in polynomial time provided some condition on the message length. We also propose a countermeasure to avoid both analyses. Novelty/Improvement: The purpose of this work is to offer suggestions for a countermeasure for the aforementioned analysis upon implementing the Rabin-p cryptosystem. Hence, all the parameters should be chosen carefully.


Algebraic Analysis, Continued Fraction, Coppersmith’s Theorems, Rabin-p Cryptosystem.

Full Text:

 |  (PDF views: 150)


  • May A. New RSA vulnerabilities using lattice reduction methods [Doctoral dissertation]. Germany, University of Paderborn; 2003 Oct 19. p. 6–151.
  • Nitaj A. Diophantine and lattice cryptanalysis of the RSA cryptosystem. In Artificial Intelligence, Evolutionary Computing and Metaheuristics, Springer Berlin Heidelberg; 2013. p. 139–68.
  • Nitaj A. A new vulnerable class of exponents in RSA. JP Journal of Algebra, Number Theory and Applications.2011; 21:203–20.
  • Boneh D. Simplified OAEP for the RSA and Rabin functions.In Annual International Cryptology Conference Springer Berlin Heidelberg; 2001 Aug 19. p. 275–91.
  • Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology. 1997 Sep 1; 10(4):233–60.
  • Hardy GH, Wright EM. An introduction to the theory of numbers. Oxford University Press; 1979.
  • Asbullah MA, Ariffin MR. New attacks on RSA with modulus N= p2q using continued fractions. Journal of Physics: Conference Series, IOP Publishing. 2015; 622(1):012019.
  • Asbullah MA, Ariffin MR. Design of Rabin-like cryptosystem without decryption failure. Malaysian Journal of Mathematical Sciences. 2016 August; 10(S):1–18.
  • Rabin MO. Digitalized signatures and public key cryptosystems as intractable as factorization. MIT/LCS/TR-212, Technical Report MIT; 1979.
  • Koblitz N, MenezesAJ. Another look at provable security.Journal of Cryptology. 2007 Jan 1; 20(1):3–7.
  • Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems.Communications of the Association for Computing Machinery (ACM). 1978 Feb 1; 21(2):120–6.
  • Galbraith SD. Mathematics of public key cryptography.Cambridge University Press; 2012 Mar 15.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.