RSA Signing - Existential forgery and message prefix question. It's a weird one

I'm new to this. Please be kind. I have a theoretical question that I would like sanity checked:

Bob and Alice are doing RSA signing without a hash function -- just putting a message in, and getting a signature out.

The messages Bob and Alice are sending each other are random numbers.

Without a hash function involved an attacker can create a message with the signature they want. But they can't control the message.

However because Bob and Alice are sending each other random numbers, this attacker could create a valid looking message. That is, a valid signature on a seemingly random looking number.

But Bob and Alice want to make this scheme secure, so they add a known prefix to their messages. They add some structure.

So instead of a message looking like: 484262 It looks like: prefix_484262

Here's the thing I want sanity checked:

By adding the known prefix, an attacker can only forge messages by brute force, and as a result the security of this scheme is proportional to the length of the prefix.

That is to say, the length of the prefix matters. For instance if the prefix was just one octet, presumably the attacker would just need about 255 tries to forge a message that works. But, if the prefix was two octets The attacker would need 65,536 tries.

The other thing I want sanity checked is:

Knowing the prefix is not an advantage to brute forcing the messages (other than the fact that the attacker knows what the output needs to look like).

Thanks for any help. I appreciate it.

I assume the signature system proposed takes a message $M$, converts it to an integer $m$ less than $n$ by somewhat adding a fixed constant $c$ on the left of the expression of $M$ of as $i$ digits in some base $b\ge2$ (base 10 in the question) thus $m:=c\,b^i+M$, then builds the signature $\sigma=\mathrm{Sig}(M)$ per textbook RSA with private key $(n,d)$, that is $\sigma:=m^d\bmod n$; and the verifier given $(n,e)$ and $(M,\sigma)$ (or just $\sigma$) computes $\sigma^e\bmod n$ then checks that's $c\,b^i+M$. For now, I leave it unspecified if $i$ is fixed, or depends on $M$ (and how).

By adding the known prefix, an attacker can only forge messages by brute force, and as a result the security of this scheme is proportional to the length of the prefix.

For this proposition to have any chance of standing true, we must add "up to the point the prefix $c$ becomes so large that factorization of $n$ becomes the easiest attack". I assume this in the following.

That proposition appears true (but we don't have a proof) if we take as definition of security for signature Existential Un-Forgeability under Known Message Attack, in which adversaries have the public key $(n,e)$ plus a number of valid $(M_j,\sigma_j)$ pairs for random $M_j$, and try to exhibit a $(M,\sigma)$ pair for $M$ none of the $M_j$.

But that's incorrect if we take Existential Un-Forgeability under Chosen Message Attack, in which the adversary is allowed to query for signature $\sigma_j$ of any message $M_j$ of their choice, before exhibiting $(M,\sigma)$ as above. Problem is, under this model of security there are attacks better than brute-force.

• Attack is easy if we allows $i$ to be the number of digits of $M$ in base $b$ (be it with or without suppressing leading zeroes), and use a small public exponent $e$ (e.g. 3): an attacker finds the signature of any message $M$ it sees fit (up to some size limit) from the signature of message $M'=M\,b^e$ if $M$ is short enough to meet the $c\,b^{i'}+M'=c\,b^{i+e}+M\,b^e<n$ requirement, since $\mathrm{Sig}(M')\,b^{-1}\bmod n=\mathrm{Sig}(M)$.
• For fixed $i$, things are harder, but the Desmedt and Odlyzko attack allows forgery with difficulty much lower than brute force, far from doubled when we allow $c$ to be twice as large, and even sub-exponential with $\log_2(c)$.
• The previous attack becomes easier if we allow $i$ fixed for a given $c$, but equal to the size of $c$ in base $b$.

Knowing the prefix is not an advantage to brute forcing the messages (other than the fact that the attacker knows what the output needs to look like).

The motivation of signature is to allow verification with no secret information, and making the prefix secret goes against that. I'll assume it nevertheless.

Then, that statement is correct except under the unrealistic Key-Only Attacks, but moot for the very reason that makes it correct: adversaries know at least one $(M_0,\sigma_0)$ pair in addition to the public key $(n,e)$, and they can thus easily find the prefix $c$ by computing ${\sigma_0}^e\bmod n$.