Another Look at RSA Signatures With Affine Padding
Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi
Abstract
Affine-padding {\sc rsa} signatures consist in signing instead of the message for some fixed constants . A thread of publications progressively reduced the size of for which affine signatures can be forged in polynomial time. The current bound is where is the {\sc rsa} modulus' bit-size. Improving this bound to has been an elusive open problem for the past decade.\smallskip
In this invited talk we consider a slightly different problem: instead of minimizing 's size we try to minimize its {\sl entropy}. We show that affine-padding signatures on entropy-bit messages can be forged in polynomial time. This problem has no direct cryptographic impact but allows to better understand how malleable the {\sc rsa} function is. In addition, the techniques presented in this talk might constitute some progress towards a solution to the longstanding forgery open problem.\smallskip\smallskip
We also exhibit a sub-exponential time technique (faster than factoring) for creating affine modular relations between strings containing three messages of size and a fourth message of size .\smallskip
Finally, we show than -relations can be obtained in specific scenarios, {\sl e.g.} when one can pad messages with two independent patterns or when the modulus' most significant bits can be chosen by the opponent.\smallskip
Note: Authors were missing in the previous submission. Got that fixed.
@misc{cryptoeprint:2011/057,
author = {Jean-Sébastien Coron and David Naccache and Mehdi Tibouchi},
title = {Another Look at {RSA} Signatures With Affine Padding},
howpublished = {Cryptology {ePrint} Archive, Paper 2011/057},
year = {2011},
url = {https://eprint.iacr.org/2011/057}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.