Lattice-Based Cryptanalysis of RSA with Implicitly Related Keys

Mengce ZHENG  Noboru KUNIHIRO  Honggang HU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.8   pp.959-968
Publication Date: 2020/08/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019EAP1170
Type of Manuscript: PAPER
Category: Cryptography and Information Security
RSA,  implicitly related keys,  cryptanalysis,  factorization,  lattice,  

Full Text: PDF(1.3MB)>>
Buy this Article

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.