plain textbook RSA signature with a fixed format input We have an old system using the following algorithm related to authentication:


input: a fixed format integer (hex): &lt;user-id&gt;0000f000&lt;device-id&gt;


user-id: 4 bytes
device-id: 4 bytes

algorithm: textbook RSA 2048, sign with (N, d).


and assumes that an attacker can request limited times (5 times per account per day) with arbitrary device-ids, or try with different user-ids.

Update


sign with (N, d), not (d, e), already updated above;
the background is, logged-in users can apply for usage of a device, if the device is not in use, the user will get a QR code containing the info of the signature. The device will check it (user-id and device-id), if succeeded, the device will unlock automatically.


Question: is it possible that an attacker without login can generate a QR code to unlock any device (device-id is right on the device, and is a random number each time)?

by the way, the device does not deserve much cost. We consider it is not safe when there is an easily-adopted hacking method. And also ignore the case that one can remember the corresponding QR code.
That signature system is insecure assuming that the adversary


can obtain a few signatures for &lt;user-id&gt; and &lt;device-id&gt; which s/he can choose (with perhaps &lt;user-id&gt; constrained, e.g. in a list),
is deemed to succeed if creating a valid signature for some &lt;user-id&gt; for which s/he was not given signature (perhaps with some constraint) and &lt;device-id&gt; s/he can choose,
knows the public key $(N,e)$.


In a simple form of the attack, the adversary restricts to suitably smooth values of $m_i=$&lt;user-id&gt;0000f000&lt;device-id&gt;, and finds a set of these $m_i$ and associated $k_i\in\mathbb Z$ (with $k_0=1$, $k_i\ne0$) such that
$$1=\prod m_i^{k_i}$$
which, when there are enough smooth $m_i$, essentially reduces to solving a system of linear equations (obtained by considering the multiplicity of each prime factor of each smooth $m_i$). It is then easy to compute the signature $s_0$ for $m_0$ from the signatures $s_i$ for other $m_i$, as
$$s_0=\prod_{i&gt;0}s_i^{-k_i}\bmod N$$

Improvements replace the constraint $k_0=1$ with $\gcd(k_0,e)=1$, and exploit very low $e$ like $e=3$, by noticing that a signature can still be forged if the linear equations on multiplicities are satisfied modulo $e$.

How hard the attack is depends primarily on the width of the $m_i$ (here modest with at most 96 bits, perhaps 65 or 48 with enough freedom &lt;user-id&gt;) and on the maximum number of signatures that can be obtained; on the freedom there is on the choice of &lt;user-id&gt;; and to some degree on $e$. Critically, the size of $N$ is immaterial.

The attack is often designated the Desmedt and Odlyzko attack, with reference  to Y. Desmedt and A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985. A modern re-exposition is in section 3 of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (in proceedings of Crypto 2009
then Journal of Cryptology, 2016).

Exhibiting actual values of &lt;user-id&gt; and &lt;device-id&gt; allowing the attack is an interesting exercise.