Welcome to the resource topic for 2011/057
Title:
Another Look at RSA Signatures With Affine Padding
Authors: Jean-Sébastien Coron, David Naccache, Mehdi Tibouchi
Abstract:Affine-padding {\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’ bit-size. 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 affine-padding signatures on \frac{N}{4} 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 \frac{N}{4} 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 \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
ePrint: https://eprint.iacr.org/2011/057
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .