The search functionality is under construction.

The search functionality is under construction.

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

Mengce ZHENG

University of Science and Technology of China

Noboru KUNIHIRO

University of Tsukuba

Honggang HU

University of Science and Technology of China

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.

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 -