On the security of RSA with primes sharing least-significant bits
type: Item
instance of: scholarly article
title: On the security of RSA with primes sharing least-significant bits
zbMATH Open document ID: 1065.94008
author: Ron Steinfeld
author: Yuliang Zheng
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2005-02-09T00:00:00Z
review text: An \((\alpha,\beta,\gamma)\)-LSBS-RSA system is one that satisfies the following conditions. (1) The prime factors \(p\) and \(q\) of the public RSA modulus \(N=pq\) have exactly \(\alpha\) equal least-significant bits, that is, \(p-q=r\cdot2^\alpha\) for some odd integer \(r\). An RSA modulus \(N\) with this property is called an \(\alpha\)-Least-Significant-Bit-Symmetric modulus, or simply, \(\alpha\)-LSBS. (2) The \(\beta\) least-significant bits of the RSA secret exponent \(d\) are available to the attacker (e.g. they are included as part of the public-key). For this reason, this setting is called a Partial Key Exposure (PKE) attack scenario. (3) The RSA public-exponent \(e\) has bit length \(\gamma\). When the length \(\gamma\) of the public exponent \(e\) is a small constant, the system is called a low-public-exponent system. The authors show that the latter system is resistant to the PKE attacks in which least-significant bits of the secret exponent are revealed to the attacker. When \(\gamma\) is a constant fraction of the modulus length \(n\), the system is called a large-public-exponent system. The authors show that this type of system is more vulnerable to the PKE attacks than standard RSA.
reviewed by: Richard A. Mollin
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 94A62
zbMATH DE Number: 2133268
zbMATH Keywords: RSA cryptosystem
zbMATH Keywords: communications security
zbMATH Keywords: cryptanalysis
zbMATH Keywords: partial key exposure
zbMATH Keywords: Boneh-Durfee-Frankel attack
zbMATH Keywords: Coppersmith algorithm
zbMATH Keywords: least-significant bits
zbMATH Keywords: server-aided signature generation
MaRDI profile type: Publication
full work available at URL: s00200-004-0164-6
OpenAlex ID: W2062099180
cites work: Q4888749
cites work: The Exact Security of Digital Signatures-How to Sign with RSA and Rabin
cites work: Advances in Cryptology - CRYPTO 2003
cites work: Q4229172
cites work: Q4249286
cites work: Small solutions to polynomial equations, and low exponent RSA vulnerabilities
cites work: Cryptanalysis of RSA with small prime difference
cites work: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
cites work: Q4249250
cites work: Q4474166
cites work: Q4718481
cites work: Q4249280
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: Q2724423
DOI: 10.1007/S00200-004-0164-6
description: scientific article; zbMATH DE number 2133268