**Another Look at RSA Signatures With Affine Padding**

*Jean-Sébastien Coron and David Naccache and 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

**Category / Keywords: **RSA, digital signature, forgery, padding

**Date: **received 31 Jan 2011, last revised 25 Apr 2016

**Contact author: **david naccache at ens fr

**Available format(s): **PDF | BibTeX Citation

**Note: **Authors were missing in the previous submission. Got that fixed.

**Version: **20190217:224314 (All versions of this report)

**Short URL: **ia.cr/2011/057

[ Cryptology ePrint archive ]