Cryptanalysis on the modulus N=p2q and design of rabin-like cryptosystem without decryption failure

Rabin cryptosystem has fast encryption and proven as secure as the integer factorization problem. Nonetheless, its decryption produces four possible correct results with no indicator for choosing the right one is given. Therefore, this scenario leads to a decryption failure. In order to engage with this problem and to refine the existing works, further analysis subjected to mathematical proof are needed. This thesis concentrates on an investigation into a new method to overcome all the existing drawbacks of the previous effort to refine the Rabin cryptosystem. One of the ways to achieve this is through the utilization of the modulus N = p2q. The first contribution of this thesis deals with the level of security and the difficulty of factoring the modulus N = p2q. As a consequence, we develop four cryptanalysis methods by which to show that N = p2q can be factored in polynomial time under certain conditions. The second part of this thesis focuses on revisiting the Rabin encryption scheme;with the goal to overcome all the previous drawbacks of its predecessor, including it’s variants. Existing methods exploit some mathematical object or put paddings and redundancies into the message, whilst the new proposed method opens up a refreshing window of research into the problem. The proposed method, called the Rabin-p cryptosystem has recorded an improvement which bears the idea of a failure-free decryption scenario. In this thesis, we also develop a new cryptographic hard problem based on a special instance of a linear Diophantine equation in two variables, with some provided restrictions and carefully selected parameters. We reason that the proposed cryptographic hard problem can be used for developing practical cryptographic constructions. In parallel, we review the AAb cryptosystem based on the design of Rabin-p function over integers and also as a demonstration of the proposed cryptographic hard problem concept. We then put forward an enhancement of the AAb decryption for better efficiency. Additionally, we conduct rigorous mathematical analyses on both cryptosystems introduced in this thesis. Moreover, for the purpose of empirical evidences, some parameters are chosen in the course of the process to validate the efficiency in terms of algorithmic running time and memory consumptions. We then conduct a comparative analysis toward estimating the running time during the encryption and decryption process. We also evaluate the memory cost for system parameters and accumulators. Finally, we study the provable security element for both cryptosystems. Emphasis is given to the standard security goal and the strong attack model, namely the indistinguishability and the chosen-ciphertext attack, respectively.

Preview PDF IPM 2015 9IR.pdf Download (1MB) | Preview

Actions (login required)

View Item