Batten, Lynn and Wolf, Christopher 2010, The padding scheme for RSA signatures, in ATIS 2010 : Proceedings of the 1st Applications and Techniques in Information Security Workshop, School of Information Systems, Deakin University, Melbourne, Vic., pp. 1-7.
The RSA scheme is used to sign messages; however, in order to avoid forgeries, a message can be padded with a fixed string of data P. De Jonge and Chaum showed in 1985 that forgeries can be constructed if the size of P (measured in bytes) is less than the size of N/3, where N is the RSA modulus. Girault and Misarsky then showed in 1997 that forgeries can be constructed if the size of P is less than the size of N/2. In 2001, Brier, Clavier, Coron and Naccache showed that forgeries can still be constructed when the size of P is less than two thirds the size of N. In this paper, we demonstrate that this padding scheme is always insecure; however, the complexity of actually finding a forgery is O(N). We then focus specifically on the next unsettled case, where P is less than 3/4 the size of N and show that finding a forgery is equivalent to solving a set of diophantine equations. While we are not able to solve these equations, this work may lead to a break-through by means of algebraic number theory techniques.
Field of Research
080402 Data Encryption
Socio Economic Objective
890101 Fixed Line Data Networks and Services
HERDC Research category
E1 Full written paper - refereed
HERDC collection year
Unless expressly stated otherwise, the copyright for items in Deakin Research Online is owned by the author, with all rights reserved.