Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant

Abderrahmane Nitaj; Maher Boudabra

doi:10.1007/978-3-031-37679-5_11

Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant

Abderrahmane Nitaj^*
, Maher Boudabra

^*Corresponding author for this work

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

The multi-power RSA cryptosystem is a variant of RSA where the modulus is in the form N= p^rq^s with max (r, s) ≥ 2. In the multi-power RSA variant, the decryption phase is much faster than the standard RSA. While RSA has been intensively studied, the security of the multi-power RSA variant needs to be deeply investigated. In this paper, we consider a multi-power RSA cryptosystem with a modulus N= p^rq^s, and propose a method to solve the modular polynomial equations of the form F(x)≡0(modWpuqv) where F(x) is a polynomial with integer coefficients, W is a positive integer, and u, v are integers satisfying 0 ≤ u≤ r, 0 ≤ v≤ s, and su- rv≠ 0. Our method is based on Coppersmith’s method and lattice reduction techniques. We show that the new results retrieve or supersede the former results. Moreover, we apply the new method to study various instances of the multi-power RSA cryptosystem, especially when the private exponent is small, when the prime factors have a specific form, and when the least significant or the most significant bits of the private exponent are known.

Original language	English
Title of host publication	Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings
Editors	Nadia El Mrabet, Luca De Feo, Sylvain Duquesne
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	252-269
Number of pages	18
ISBN (Print)	9783031376788
DOIs	https://doi.org/10.1007/978-3-031-37679-5_11
State	Published - 2023
Event	14th International Conference on Cryptology in Africa, AFRICACRYPT 2023 - Sousse, Tunisia Duration: 19 Jul 2023 → 21 Jul 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14064 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Cryptology in Africa, AFRICACRYPT 2023
Country/Territory	Tunisia
City	Sousse
Period	19/07/23 → 21/07/23

Bibliographical note

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

Coppersmith’s method
Factorization
Lattice reduction
RSA

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-37679-5_11

Cite this

Nitaj, A., & Boudabra, M. (2023). Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant. In N. El Mrabet, L. De Feo, & S. Duquesne (Eds.), Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings (pp. 252-269). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14064 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-37679-5_11

Nitaj, Abderrahmane ; Boudabra, Maher. / Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant. Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings. editor / Nadia El Mrabet ; Luca De Feo ; Sylvain Duquesne. Springer Science and Business Media Deutschland GmbH, 2023. pp. 252-269 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{405c8f3954ee4b1d93de7690ad9094aa,

title = "Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant",

abstract = "The multi-power RSA cryptosystem is a variant of RSA where the modulus is in the form N= prqs with max (r, s) ≥ 2. In the multi-power RSA variant, the decryption phase is much faster than the standard RSA. While RSA has been intensively studied, the security of the multi-power RSA variant needs to be deeply investigated. In this paper, we consider a multi-power RSA cryptosystem with a modulus N= prqs, and propose a method to solve the modular polynomial equations of the form F(x)≡0(modWpuqv) where F(x) is a polynomial with integer coefficients, W is a positive integer, and u, v are integers satisfying 0 ≤ u≤ r, 0 ≤ v≤ s, and su- rv≠ 0. Our method is based on Coppersmith{\textquoteright}s method and lattice reduction techniques. We show that the new results retrieve or supersede the former results. Moreover, we apply the new method to study various instances of the multi-power RSA cryptosystem, especially when the private exponent is small, when the prime factors have a specific form, and when the least significant or the most significant bits of the private exponent are known.",

keywords = "Coppersmith{\textquoteright}s method, Factorization, Lattice reduction, RSA",

author = "Abderrahmane Nitaj and Maher Boudabra",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 14th International Conference on Cryptology in Africa, AFRICACRYPT 2023 ; Conference date: 19-07-2023 Through 21-07-2023",

year = "2023",

doi = "10.1007/978-3-031-37679-5\_11",

language = "English",

isbn = "9783031376788",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "252--269",

editor = "\{El Mrabet\}, Nadia and \{De Feo\}, Luca and Sylvain Duquesne",

booktitle = "Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings",

address = "Germany",

}

Nitaj, A & Boudabra, M 2023, Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant. in N El Mrabet, L De Feo & S Duquesne (eds), Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14064 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 252-269, 14th International Conference on Cryptology in Africa, AFRICACRYPT 2023, Sousse, Tunisia, 19/07/23. https://doi.org/10.1007/978-3-031-37679-5_11

Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant. / Nitaj, Abderrahmane; Boudabra, Maher.
Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings. ed. / Nadia El Mrabet; Luca De Feo; Sylvain Duquesne. Springer Science and Business Media Deutschland GmbH, 2023. p. 252-269 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14064 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant

AU - Nitaj, Abderrahmane

AU - Boudabra, Maher

PY - 2023

Y1 - 2023

N2 - The multi-power RSA cryptosystem is a variant of RSA where the modulus is in the form N= prqs with max (r, s) ≥ 2. In the multi-power RSA variant, the decryption phase is much faster than the standard RSA. While RSA has been intensively studied, the security of the multi-power RSA variant needs to be deeply investigated. In this paper, we consider a multi-power RSA cryptosystem with a modulus N= prqs, and propose a method to solve the modular polynomial equations of the form F(x)≡0(modWpuqv) where F(x) is a polynomial with integer coefficients, W is a positive integer, and u, v are integers satisfying 0 ≤ u≤ r, 0 ≤ v≤ s, and su- rv≠ 0. Our method is based on Coppersmith’s method and lattice reduction techniques. We show that the new results retrieve or supersede the former results. Moreover, we apply the new method to study various instances of the multi-power RSA cryptosystem, especially when the private exponent is small, when the prime factors have a specific form, and when the least significant or the most significant bits of the private exponent are known.

AB - The multi-power RSA cryptosystem is a variant of RSA where the modulus is in the form N= prqs with max (r, s) ≥ 2. In the multi-power RSA variant, the decryption phase is much faster than the standard RSA. While RSA has been intensively studied, the security of the multi-power RSA variant needs to be deeply investigated. In this paper, we consider a multi-power RSA cryptosystem with a modulus N= prqs, and propose a method to solve the modular polynomial equations of the form F(x)≡0(modWpuqv) where F(x) is a polynomial with integer coefficients, W is a positive integer, and u, v are integers satisfying 0 ≤ u≤ r, 0 ≤ v≤ s, and su- rv≠ 0. Our method is based on Coppersmith’s method and lattice reduction techniques. We show that the new results retrieve or supersede the former results. Moreover, we apply the new method to study various instances of the multi-power RSA cryptosystem, especially when the private exponent is small, when the prime factors have a specific form, and when the least significant or the most significant bits of the private exponent are known.

KW - Coppersmith’s method

KW - Factorization

KW - Lattice reduction

KW - RSA

UR - https://www.scopus.com/pages/publications/85169018804

U2 - 10.1007/978-3-031-37679-5_11

DO - 10.1007/978-3-031-37679-5_11

M3 - Conference contribution

AN - SCOPUS:85169018804

SN - 9783031376788

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 252

EP - 269

BT - Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings

A2 - El Mrabet, Nadia

A2 - De Feo, Luca

A2 - Duquesne, Sylvain

PB - Springer Science and Business Media Deutschland GmbH

T2 - 14th International Conference on Cryptology in Africa, AFRICACRYPT 2023

Y2 - 19 July 2023 through 21 July 2023

ER -

Nitaj A, Boudabra M. Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant. In El Mrabet N, De Feo L, Duquesne S, editors, Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 252-269. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-37679-5_11