Cryptanalysis of RSA with small prime difference
type: Item
instance of: scholarly article
title: Cryptanalysis of RSA with small prime difference
zbMATH Open document ID: 1010.94007
author: Benne de Weger
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2002-05-29T00:00:00Z
review text: The author proves that choosing an RSA modulus with a small difference between its prime factors yields improvements on the small private exponent attacks of Wiener and Boneh-Durfee. The following theorem is the main result of this paper. Theorem. Let \(p,q\) be large primes of about the same size, \(n=pq\) and \(\Delta=|p-q|\). Let \(e,d\) be integers \(>1\) and \(<\varphi (n)\), satisfying \(ed\equiv 1\pmod{\varphi (n)}\). Put \(\Delta=n^{\beta}\) and \(d=n^{\delta}\). Given only \(n\) and \(e\), the factors \(p,q\) of \(n\) and the number \(d\) can be recovered efficiently whenever \(2-4\beta<\delta<1-\sqrt{2\beta -\frac 12}\) or \(\delta<\frac 16(4\beta +5)-\frac 13\sqrt{(4\beta +5)(4\beta -1)}\).
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11Y05
zbMATH DE Number: 1747256
zbMATH Keywords: cryptanalysis
zbMATH Keywords: RSA
zbMATH Keywords: factoring large integers
describes a project that uses: PARI/GP
reviewed by: Zhenfu Cao
MaRDI profile type: Publication
full work available at URL: s002000100088
OpenAlex ID: W2156666175
DOI: 10.1007/S002000100088
description: scientific article; zbMATH DE number 1747256