Lattice-Based Cryptanalysis of RSA with Implicitly Related Keys
Summary :
We address the security issue of RSA with implicitly related keys in this paper. Informally, we investigate under what condition is it possible to efficiently factorize RSA moduli in polynomial time given implicit relation of the related private keys that certain portions of bit pattern are the same. We formulate concrete attack scenarios and propose lattice-based cryptanalysis by using lattice reduction algorithms. A subtle lattice technique is adapted to represent an unknown private key with the help of known implicit relation. We analyze a simple case when given two RSA instances with the known amount of shared most significant bits (MSBs) and least significant bits (LSBs) of the private keys. We further extend to a generic lattice-based attack for given more RSA instances with implicitly related keys. Our theoretical results indicate that RSA with implicitly related keys is more insecure and better asymptotic results can be achieved as the number of RSA instances increases. Furthermore, we conduct numerical experiments to verify the validity of the proposed attacks.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.8 pp.959-968
- Publication Date
- 2020/08/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2019EAP1170
- Type of Manuscript
- PAPER
- Category
- Cryptography and Information Security
Authors
Mengce ZHENG
University of Science and Technology of China
Noboru KUNIHIRO
University of Tsukuba
Honggang HU
University of Science and Technology of China
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Mengce ZHENG, Noboru KUNIHIRO, Honggang HU, "Lattice-Based Cryptanalysis of RSA with Implicitly Related Keys" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 8, pp. 959-968, August 2020, doi: 10.1587/transfun.2019EAP1170.
Abstract: We address the security issue of RSA with implicitly related keys in this paper. Informally, we investigate under what condition is it possible to efficiently factorize RSA moduli in polynomial time given implicit relation of the related private keys that certain portions of bit pattern are the same. We formulate concrete attack scenarios and propose lattice-based cryptanalysis by using lattice reduction algorithms. A subtle lattice technique is adapted to represent an unknown private key with the help of known implicit relation. We analyze a simple case when given two RSA instances with the known amount of shared most significant bits (MSBs) and least significant bits (LSBs) of the private keys. We further extend to a generic lattice-based attack for given more RSA instances with implicitly related keys. Our theoretical results indicate that RSA with implicitly related keys is more insecure and better asymptotic results can be achieved as the number of RSA instances increases. Furthermore, we conduct numerical experiments to verify the validity of the proposed attacks.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019EAP1170/_p
Copy
@ARTICLE{e103-a_8_959,
author={Mengce ZHENG, Noboru KUNIHIRO, Honggang HU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Lattice-Based Cryptanalysis of RSA with Implicitly Related Keys},
year={2020},
volume={E103-A},
number={8},
pages={959-968},
abstract={We address the security issue of RSA with implicitly related keys in this paper. Informally, we investigate under what condition is it possible to efficiently factorize RSA moduli in polynomial time given implicit relation of the related private keys that certain portions of bit pattern are the same. We formulate concrete attack scenarios and propose lattice-based cryptanalysis by using lattice reduction algorithms. A subtle lattice technique is adapted to represent an unknown private key with the help of known implicit relation. We analyze a simple case when given two RSA instances with the known amount of shared most significant bits (MSBs) and least significant bits (LSBs) of the private keys. We further extend to a generic lattice-based attack for given more RSA instances with implicitly related keys. Our theoretical results indicate that RSA with implicitly related keys is more insecure and better asymptotic results can be achieved as the number of RSA instances increases. Furthermore, we conduct numerical experiments to verify the validity of the proposed attacks.},
keywords={},
doi={10.1587/transfun.2019EAP1170},
ISSN={1745-1337},
month={August},}
Copy
TY - JOUR
TI - Lattice-Based Cryptanalysis of RSA with Implicitly Related Keys
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 959
EP - 968
AU - Mengce ZHENG
AU - Noboru KUNIHIRO
AU - Honggang HU
PY - 2020
DO - 10.1587/transfun.2019EAP1170
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2020
AB - We address the security issue of RSA with implicitly related keys in this paper. Informally, we investigate under what condition is it possible to efficiently factorize RSA moduli in polynomial time given implicit relation of the related private keys that certain portions of bit pattern are the same. We formulate concrete attack scenarios and propose lattice-based cryptanalysis by using lattice reduction algorithms. A subtle lattice technique is adapted to represent an unknown private key with the help of known implicit relation. We analyze a simple case when given two RSA instances with the known amount of shared most significant bits (MSBs) and least significant bits (LSBs) of the private keys. We further extend to a generic lattice-based attack for given more RSA instances with implicitly related keys. Our theoretical results indicate that RSA with implicitly related keys is more insecure and better asymptotic results can be achieved as the number of RSA instances increases. Furthermore, we conduct numerical experiments to verify the validity of the proposed attacks.
ER -
English
