Paper 2011/057
Another Look at RSA Signatures With Affine Padding
JeanSébastien Coron, David Naccache, and Mehdi Tibouchi
Abstract
Affinepadding {\sc rsa} signatures consist in signing $\omega\cdot m+\alpha$ instead of the message $m$ for some fixed constants $\omega,\alpha$. A thread of publications progressively reduced the size of $m$ for which affine signatures can be forged in polynomial time. The current bound is $\log m \sim \frac{N}{3}$ where $N$ is the {\sc rsa} modulus' bitsize. Improving this bound to $\frac{N}{4}$ has been an elusive open problem for the past decade.\smallskip In this invited talk we consider a slightly different problem: instead of minimizing $m$'s size we try to minimize its {\sl entropy}. We show that affinepadding signatures on $\frac{N}{4}$ entropybit 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 $\frac{N}{4}$ forgery open problem.\smallskip\smallskip We also exhibit a subexponential time technique (faster than factoring) for creating affine modular relations between strings containing three messages of size $\frac{N}{4}$ and a fourth message of size $\frac{3N}{8}$.\smallskip Finally, we show than $\frac{N}{4}$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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown status
 Keywords
 RSAdigital signatureforgerypadding
 Contact author(s)
 david naccache @ ens fr
 History
 20160425: last of 3 revisions
 20110131: received
 See all versions
 Short URL
 https://ia.cr/2011/057
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/057, author = {JeanSé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}, note = {\url{https://eprint.iacr.org/2011/057}}, url = {https://eprint.iacr.org/2011/057} }