Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at http://www.ucl.ac.uk/finance/research/post_award/post_award_contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
Extension of de Wegers Attack on RSA with Large Public Keys
  • Publication Type:
  • Authors:
    Courtois N, Mourouzis T, Le PV
  • Publisher:
  • Pagination:
    145, 153
  • Published proceedings:
    SECRYPT 2012
  • ISBN-13:
  • Name of conference:
    SECRYPT 2012
  • Conference place:
    Rome, Italy
  • Conference start date:
  • Conference finish date:
  • Keywords:
    RSA, Wiener attack, De Weger attack
RSA cryptosystem (Rivest et al., 1978) is the most widely deployed public-key cryptosystem for both encryption and digital signatures. Since its invention, lots of cryptanalytic efforts have been made which helped us to improve it, especially in the area of key selection. The security of RSA relies on the computational hardness of factoring large integers and most of the attacks exploit bad choice parameters or flaws in implementations. Two very important cryptanalytic efforts in this area have been made by Wiener (Wiener, 1990) and de Weger (Weger, 2002) who developed attacks based on small secret keys (Hinek, 2010).The main idea of Wiener’s attack is to approximate the fraction e j(N) by eN for large values of N and then make use of the continued fraction algorithm to recover the secret key d by computing the convergents of the fraction eN. He proved that the secret key d can be efficiently recovered if d < 1 3N 1 4 and e < j(N) and then de Weger extended this attack from d < 1 3N 1 4 to d < N 3 4−b, for any 1 4 < b < 1 2 such that |p−q| < Nb. The aim of this paper is to investigate for which values of the variables s and D = |p−q|, RSA which uses public keys of the special structure E = e+sj(N), where e < j(N), is insecure against cryptanalysis. Adding multiples of j(N) either to e or to d is called Exponent Blinding and it is widely used especially in case of encryption schemes or digital signatures implemented in portable devices such as smart cards. We show that an extension of de Weger’s attack from public keys e < j(N) to E > j(N) is possible if the security parameter s satisfies s ≤ N 12 .
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
UCL Researchers
Dept of Computer Science
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by