Total views : 104
Algebraic Analysis of a Rabin-Like Cryptosystem and Its Countermeasures
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.
- 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.
This work is licensed under a Creative Commons Attribution 3.0 License.