Analytical cryptanalysis upon N = p2q utilizing Jochemsz-May strategy

Abstract

Nurul Nur Hanisah Adenan, Muhammad Rezal Kamel Ariffin Roles Conceptualization, Formal analysis, Funding acquisition, Investigation, Project administration, Validation, Writing – review & editing * E-mail: [email protected] Affiliations Institute for Mathematical Research, Universiti Putra Malaysia, Serdang, Selangor, Malaysia, Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, Serdang, Selangor, Malaysia ORCID logo https://orcid.org/0000-0001-5000-354X Faridah Yunos Roles Validation, Writing – review & editing ¶‡ These authors also contributed equally to this work. Affiliations Institute for Mathematical Research, Universiti Putra Malaysia, Serdang, Selangor, Malaysia, Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, Serdang, Selangor, Malaysia Abstract This paper presents a cryptanalytic approach on the variants of the RSA which utilizes the modulus N = p2q where p and q are balanced large primes. In 2014, [15] presented his proof that N = p2q can be factored by using lattice reduction techniques provided d < N0.395. 1.1 Our contribution We are working on the same purpose as the previous researchers which is to find other weakness of the RSA in order to enhance its security. [...]in this paper, we present an attack on the modulus N = p2q where the primes share a known amount of LSB(s). The reduced basis produced by the LLL algorithm satisfiesfor all 1 ≤ i ≤ ω. Since its invention, LLL algorithm has been extensively applied in order to find reduced basis vectors in a lattice.

About the Authors:

Nurul Nur Hanisah Adenan

Contributed equally to this work with: Nurul Nur Hanisah Adenan, Muhammad Rezal Kamel Ariffin

Roles Formal analysis, Methodology, Writing – original draft, Writing – review & editing

Affiliation: Institute for Mathematical Research, Universiti Putra Malaysia, Serdang, Selangor, Malaysia

ORCID logo https://orcid.org/0000-0002-5957-1524

Muhammad Rezal Kamel Ariffin

Contributed equally to this work with: Nurul Nur Hanisah Adenan, Muhammad Rezal Kamel Ariffin

Roles Conceptualization, Formal analysis, Funding acquisition, Investigation, Project administration, Validation, Writing – review & editing

* E-mail: [email protected]

Affiliations Institute for Mathematical Research, Universiti Putra Malaysia, Serdang, Selangor, Malaysia, Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, Serdang, Selangor, Malaysia

ORCID logo https://orcid.org/0000-0001-5000-354X

Faridah Yunos

Roles Validation, Writing – review & editing

¶‡ These authors also contributed equally to this work.

Affiliation: Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, Serdang, Selangor, Malaysia

Siti Hasana Sapar

Roles Validation, Writing – review & editing

¶‡ These authors also contributed equally to this work.

Affiliations Institute for Mathematical Research, Universiti Putra Malaysia, Serdang, Selangor, Malaysia, Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, Serdang, Selangor, Malaysia

Muhammad Asyraf Asbullah

Roles Validation, Writing – review & editing

¶‡ These authors also contributed equally to this work.

Affiliations Institute for Mathematical Research, Universiti Putra Malaysia, Serdang, Selangor, Malaysia, Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, Serdang, Selangor, Malaysia

Abstract

This paper presents a cryptanalytic approach on the variants of the RSA which utilizes the modulus N = p2q where p and q are balanced large primes. Suppose satisfying gcd(e, ϕ(N)) = 1 where ϕ(N) = p(p − 1)(q − 1) and d < Nδ be its multiplicative inverse. From ed − kϕ(N) = 1, by utilizing the extended strategy of Jochemsz and May, our attack works when the primes share a known amount of Least Significant Bits(LSBs). This is achievable since we obtain the small roots of our specially constructed integer polynomial which leads to the factorization of N. More specifically we show that N can be factored when the bound . Our attack enhances the bound of some former attacks upon N = p2q.

Figures

Table 1

Table 2

Table 1

Table 2

Table 1

Table 2

Citation: Adenan NNH, Kamel Ariffin MR, Yunos F, Sapar SH, Asbullah MA (2021) Analytical cryptanalysis upon N = p2q utilizing Jochemsz-May strategy. PLoS ONE 16(3): e0248888. https://doi.org/10.1371/journal.pone.0248888

Editor: Pandi Vijayakumar, University College of Engineering Tindivanam, INDIA

Received: September 27, 2020; Accepted: March 6, 2021; Published: March 24, 2021

Copyright: © 2021 Adenan et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Data Availability: All relevant data are within the manuscript and Supporting information files. Datasets can be generated or analyzed by the reader from the characteristics of the data set as mentioned in the article. The characteristics can be found from the hypothesis and assumptions stated in the results within the article.

Funding: The research was supported by Ministry of Higher Education Malaysia with Fundamental Research Grant Scheme (FRGS/2/2013/SG04/UPM/02/2).

Competing interests: The authors have declared that no competing interest exist.

1 Introduction

Secure communication up till the 70’s was executed through symmetrical ways. In other word, both of the encryption and decryption processes used the same key. Later in 1978, the first assymetric cryptosystem went public and solved the problematic issue of distributing keys. This cryptosystem used different keys to encrypt and decrypt the data. It is known as the RSA cryptosystem [1]. The construction of the RSA algorithms comprise of key generation, encryption and decryption. During the key generation process, two large balanced primes p and q are generated and the modulus N = pq is computed. Next, let e be a random integer such that gcd(e, ϕ(N)) = 1 where ϕ(N) = (p − 1)(q − 1) is the Euler totient function. Let d be its multiplicative inverse of e such that ed ≡ 1 mod ϕ(N). Let (N, e) be publicised for encryption purpose while p, q, ϕ(N), d are kept private. For decryption process, private parameter d is needed. The mathematical difficulty of the RSA cryptosystem relies on the hardness of solving the integer factorization problem on N = pq, solving the key equation ed − kϕ(N) = 1 and solving the RSA diophantine key equation that is, C ≡ Me mod N. Up until today, the RSA cryptosystem has remained secure.

In 1990, [2] found out a potential weakness on this cryptosystem. He proved that if , then one can factor N by using the continued fractions expansion method. In the following years, more resarchers worked on the same objective as [2] and managed to enhance the bound d. Later in 1996, [3] came out with an astounding method that is very useful to find the roots of either univariate or multivariate polynomial. Since then, this method has been used extensively in both cryptography and cryptanalysis. [4] utilized this method in their attack and they improved the bound of [2] up to d < N0.292.

Another potential weakness upon the RSA cryptosystem is when there is leaked information regarding either the MSB(s) or LSB(s) of the private keys which is known as partial key exposure attack. In 1998, [5] proved that the whole value of d could be retrieved if a quater of d is known [6], and [7] also showed that if the primes share either MSB(s) or LSB(s), then the modulus can be factored in polynomial time. Later in 2014, [8] published an attack on RSA cryptosystem when the primes share the LSB(s) and there exists two public exponents such that their private exponents share their MSB(s).

Multi-Power RSA is one of the variants of the RSA whereby the modulus N = pr q for r ≥ 2 is utilized. This type of modulus provides advantage for both key generation and the decryption algorithms provided the Chinese Remainder Theorem is utilized [9]. Among cryptosystems that utilize this fact are designs by [10–12]. Through their papers, the designers managed to show that their cryptosystems had low computing costs compared to the standard RSA.

As such, the study of the Integer Factorization Problem of N = pr q becomes important. [13] proved that N = pr q is factorable for large r, when r ≅ log p. Since then, many attackers made an attempt to cryptanalyse the multi-power RSA modulus. For instance, [14] showed that the modulus N = pr q is more vulnerable compared to N = pq. For r = 2, the author proved that N can be factored if d < N0.292. In 2014, [15] presented his proof that N = p2q can be factored by using lattice reduction techniques provided d < N0.395.

1.1 Our contribution

We are working on the same purpose as the previous researchers which is to find other weakness of the RSA in order to enhance its security. Therefore in this paper, we present an attack on the modulus N = p2q where the primes share a known amount of LSB(s). Note that this is an extended result from [8]. We apply the strategy of Jochemsz and May to find small roots of our integer polynomial and show that the modulus N can be factored when d < Nδ where

The construction of this paper is as follows. In Section 1, we intoduce the mechanisms and some results that will be used throughout this paper. In Section 2, we present the result on our attack theoretically. We also make a comparison with the previous attacks. Finally we conclude in Section 4.

2 Materials and methods

This section will discuss briefly on lattice basis reduction, Howgrave-Graham theorem, and useful lemmas that will be needed in this study.

2.1 Lattice

Suppose with ω ≤ n. Let v1, ⋯, vω be linearly independent vectors in real numbers field. A lattice is spanned by a set of linear combination {v1, ⋯, vω} in the formwith the dimension of ω. The lattice is called full rank if the dimension ω = n. Thus, the determinant is calculated by taking the absolute value of the determinant of the matrix whose rows consist of {v1, ⋯, vω} [16]. [17] formulated LLL algorithm to find a short basis vector in time polynomial.

Theorem 1 [17] Let be the lattice generated by a set of basis and has the dimension ω. The reduced basis produced by the LLL algorithm satisfiesfor all 1 ≤ i ≤ ω.

Since its invention, LLL algorithm has been extensively applied in order to find reduced basis vectors in a lattice. For instance, [3] introduced a method to find a small roots of modular polynomial. Applying the LLL algorithm to find a reduced basis of the lattice generated by the modular polynomial, [3] managed to obtain the roots of the polynomial. Later, [18] described an alternative to Coppersmith’s method and he came out with the following theorem.

Theorem 2 [18] Let be a polynomial with at ω monomials. Suppose that where for and . Then holds over integers.

Remark that our attack relies on a notable assumption that also had been used in some earlier proposed attacks such as [4, 15, 19].

Assumption 1. The construction of LLL algorithm produces a number of coprime polynomials. The roots of these polynomials can be computed efficiently using the resultant technique.

2.2 Approximation of primes in RSA

The following results by [20] show an approximation of the size of the primes and approximation of N − ϕ(N). These results will be used to approximate the bound for one of the variables in our polynomial.

Lemma 1 Let N = p2q with q < p < 2q. Then

Lemma 2 Let N = p2q with q < p < 2q. Then

2.3 Prime sharing bits

The following lemma is reformulated from result [8]. It considers the case when the modulus N = p2q consists of two primes that share a known amount of their LSBs.

Lemma 3 Let N = p2q be the modulus and suppose that p − q = 2b u for a known value of b. Let p = 2b p1 + u0 and q = 2b q1 + u0 where u0 is a solution to p3 ≡ N (mod 2b). If then p2 + pq − p = 23b s + s0 − v where

Proof. Suppose that p − q = 2b u. Then q = p − 2b u and(1)Hence, from (1), we obtain p3 ≡ N (mod 2b). Let u0 be a solution of the modular form p3 ≡ N (mod 2b). Then, p ≡ u0 (mod 2b) is a solution which implies that p = 2b p1 + u0 where p1 is a positive integer. Now we have,where q1 = p1 − u. Using N = p2q, we get(2)

From (2) we deduce(3)Suppose gcd(u0, 23b) = 1, we multiply (3) with and getwhich can be rewritten aswhere . Finally we have,(4)where

3 The new attack

This section presents the attack on modulus N = p2q which works when there has a known amount of LSBs shared between the primes p and q.

Theorem 3 Let N = p2q be modulus such that p − q = 2b u where 2b ≈ Nα. Let e be a public exponents satisfying e ≈ Nγ and ed − kϕ(N) = 1. Suppose that d < Nδ. Then N can be factored in time polynomial if

Proof. Suppose we have public exponent e and key equation(5)Suppose that p − q = 2b u. Then, from Lemma 3, p2 + pq − p can be rewritten in the form p2 + pq − p = 23b s + s0 − v where and u0 is a solution of the modular equation p3 ≡ N (mod 2b). Thus, substitutes (4) from Lemma 3 into (5), we getRearranging the equation,(6)We transform (6) intoand we fix the coefficients and the variables of the polynomial as follows:Now, we consider the polynomialThen (d, k, 23b s − v) is a root of f(x1, x2, x3) and can be solved by using Coppersmith’s technique [3]. However, we choose to use the extended strategy of Jochemsz and May [21] due to its easier implementation. The following bounds will be needed:

* max(e1, e2) = Nγ.

* max(d) < X1 = Nδ.

* .

* p − q = 2b u with 2b ≈ Nα and .

* p2 + pq − p = 23b s + s0 − v with 23b s − v < X3 = N2/3.

The bounds of the variables are fixed as follows:Let . The set S and M be defined as:and the setNeglecting the coefficients, we find the expansion of polynomial fm−1(x1, x2, x3) satisfies(7)The monomials in (7) can be categorised as:Consequently, the monomials for set M areDefineThen W satisfies(8)Next, defineSuppose that a4 is coprime with R. We want to work with a polynomial that has constant term 1, thus we define . Next, define the polynomials g and h as:The basis of a lattice is built by using the coefficients of polynomials g and h with dimensionIn order to construct an upper triangular matrix, we perform the following ordering of the monomials: if then and the monomials are lexicographically ordered if . The diagonal entries of the matrix are of the formRefer S1 Table in S1 Appendix for the coefficient matrix of m = 3 and t = 1.

Next, define(9)The determinant of is thenwhich can be simplified intoAll the polynomials g(x1, x2, x3) and h(x1, x2, x3) and their combinations share the root (d, k, 23b s − v) modulo R. A new basis with short vectors is produced after applying the LLL algorithm to the lattice . For i = 1, 2, let fi(x1 X1, x2 X2, x3 X3) be two short vectors of the reduced basis. Each fi shares the roots (d, k, 23b s − v). Then by Theorem 3, we haveIn order to fulfill the condition of the bound proposed by [18], we force the polynomials fi for i = 1, 2 to fulfill the condition ofwhich then can be transformed into det , that is

Using ω = |M| and |M| − |M∖S| = |S|, we get(10)Using (9), we getCorrespondingly, we getSet t = τm, then,Using this, and after simplifying by m3, the inequality (10) transform intoSubstituting the values of X1, X2, X3 and W from (8) we getor equivalently,Differentiate the equation above with respect to τ, we get the optimal value , this reduces towhich is valid ifUnder this condition of δ, we find our reduced polynomials f, f1, f2 with the root of (d, k, 23b s − v). By Assumption 1 in Section 2, the solution of the roots can be extracted using resultant technique. By using the third root 23b s − v, we compute p2 + pq − p = 23b s + s0 − v. This value is then used to find ϕ(N) and since ϕ(N) = p(p − 1)(q − 1) we can factor out p by taking the gcd(N, ϕ(N)). By knowing the value of p, we can factor the modulus N.

3.1 Comparison with the former attack

We compare our bounds with these three former attacks, [14, 15 and 19] that also work on modulus N = pr q but we specifically consider the case when r = 2. Their attacks focused on the RSA key equation ed − kϕ(N) = 1 where ϕ(N) = pr−1(pr − 1)(q − 1). Note that in these former attacks, their primes do not share any amount of LSBs. Their bounds depend only on the value of r. We compare the results with various values of γ = logN(e). Our corollary is as follow.

Corollary 1 Let N = p2q be the modulus where q < p < 2q. Let e be a public exponent satisfying ed − kϕ(N) = 1 for ϕ(N) = p(p − 1)(q − 1). Suppose that d < Nδ. Then N can be factored in time polynomial if

Note that the bounds for δ of [14, 15 and 19] remain fixed because their bounds only depend on the value of r = 2. We describe their bound for d as in the Table 1 below.

[Figure omitted. See PDF.]

Table 1. Bounds for d from the former attacks.

https://doi.org/10.1371/journal.pone.0248888.t001

Table 2 shows that our bound improves the previous bounds. The value of δ increases inversely proportional to the value of γ.

[Figure omitted. See PDF.]

Table 2. Comparison of the new result with methods from [14, 15, 19].

https://doi.org/10.1371/journal.pone.0248888.t002

Remark 1 In Corollary 1, it states that N can be factored ifSuppose e = Nγ. We havethenFrom the fact thatand combining it with results from Corollary 1, , we haveFrom here, we can find the bound for the positive value of γ. A direct calculation shows that . For small values of γ, this translates into d ≈ N.

4 Conclusion

We describe an attack related to partial key exposure. Our attack works upon the modulus N = p2q where the primes share an amount of LSB(s). Based on the result of Nitaj et al. [8], we reformulate their lemma within our theorem and find the substitution for p2 + pq − p which is the value of N − ϕ(N). We use the result from our lemma in our theorem which then yields a set of integer polynomials. By applying the extended strategy of Jochemsz and May, one is able to determine the small roots of our integer polynomial and thus factoring the modulus N. We show that N can be factored when d < Nδ for where . As such, we manage to improve the bounds of some previous attacks on the modulus N = p2q.

Supporting information

S1 Appendix.

https://doi.org/10.1371/journal.pone.0248888.s001

(PDF)

Citation: Adenan NNH, Kamel Ariffin MR, Yunos F, Sapar SH, Asbullah MA (2021) Analytical cryptanalysis upon N = p2q utilizing Jochemsz-May strategy. PLoS ONE 16(3): e0248888. https://doi.org/10.1371/journal.pone.0248888

References

1. Rivest RL, Shamir A, and Adleman L, A method for obtaining digital signatures and public-key cryptosystems Comm. of the ACM. 1978;21:120–126.

2. Wiener MJ. Cryptanalysis of short RSA secret exponents. IEEE T. Inform. Theory. 1990;36:553–558.

3. Coppersmith D, Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J Cryptology,1997; 233–260.

4. Boneh D, and Durfee G. Cryptanalysis of RSA with private key d less than N0.292. IEEE Trans. Inform. Theory. 2000; 46:1339–1349.

5. Boneh D, Durfee G, and Frankel Y. An attack on RSA given a small fraction of the private key bits. ASIACRYPT. 1998; 25–34.

6. Sun HM, Wu ME, Steinfeld R, Guo J, and Wang H. Cryptanalysis of short exponent RSA with primes sharing least significant bits CANS.2008; 49-63. https://doi.org/10.1007/978-3-540-89641-8_4

7. Zhao YD, and Qi WF. Small private-exponent attack on RSA with primes sharing bits Proc. ISC, 2007; 221-229. https://doi.org/10.1007/978-3-540-75496-1_15

8. Nitaj A, Ariffin MRK, Nassr DI, Bahig HM. New attacks on the RSA cryptosystem. Proc AFRICACRYPT. 2014; 178–198.

9. Hinek MJ, Cryptanalysis of RSA and its variants pp. 155. CRC, London, NY, USA (2010).

10. Takagi T. A fast RSA-type public-key primitive modulo pk q using Hensel lifting. IEICE Transactions. 2004; 87-A:94–101.

11. Ariffin MRK, Asbullah MA, Abu NA, Mahad Z. A new efficient asymmetric cryptosystem based on the integer factorization problem of N = p2q. MJMS. 2013 7:19–37.

12. Asbullah MA, Ariffin MRK. Design of Rabin-like cryptosystem without decryption failure. MJMS. 2016; 10:1–18.

13. Boneh D, and Durfee G, and Howgrave-Graham N. Factoring N = pr q for large r. CRYPTO. 1999; 326–337.

14. May A. A secret exponent attacks on RSA-typer schemes with moduli N = pr q. Proc IACR-PKC. 2004; 218–230.

15. Sarkar S. Small secret exponent attack on RSA variant with modulus N = pr q. Des. Codes Cryptogr. 2014; 73:383–392.

16. Nitaj A. An attack on RSA using LSBs of multiples of the prime factors. Proc AFRICACRYPT. 2013; 297–310.

17. Lenstra AK, Lenstra HW, Lovasz HW, Factoring polynomials with rational coefficients. Math Ann. 1982; 261: 515–534.

18. Howgrave-Graham N. Finding small roots of univariate modular equations revisited. IMA Conference on Cryptography and Coding. 1997; 131–142.

19. Lu Y, Zhang R, Peng L, and Lin D. Solving linear equations modulo unknown divisors: revisited. Proc ASIACRYPT. 2015; 189–213.

20. Asbullah MA. New attacks on RSA with modulus N = p2q using continued fractions. Journal of Physics: Conference Series. 2015 622:191–199.

21. Jochemsz E, May A, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants Proc ASIACRYPT 2006. 2006; 267-282. https://doi.org/10.1007/11935230_18