TLDR: the attack considered is not easy. It's possible, or not, depending on unstated hypothesis.
First we'll rephrase the question¹.
We assume an asymmetric encryption system, similar to textbook RSA, with
- key generation of a public/private key pair $(\mathrm{pk},\mathrm{sk})$,
- encryption $c:=E_\mathrm{pk}(p)$ where $p$ is the plaintext, $c$ is the ciphertext
- matching decryption $p:=D_\mathrm{sk}(c)$ that works for all $c$ obtained as $E_\mathrm{pk}(p)$
- where $p$ and $c$ are from a common interval $[0,n)$, with $n$ embedded in $\mathrm{pk}$ and $\mathrm{sk}$.
We assume this encryption system is secure under known plaintext attack.
We assume an ideal hash function $\operatorname{Hash}$ with output in $[0,h)$, with $h\le n$ for all $(\mathrm{pk},\mathrm{sk})$ the encryption system generates.
We derive a digital signature scheme where
- key generation is as in the encryption
- the signature of message $m$ is $s=D_\mathrm{sk}(\operatorname{Hash}(m))$
- the verification procedure $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ outputs Pass if $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$, or Fail otherwise.
I stress this is not a usual way to construct signature: no signature scheme in wide use quite matches², and many like DSA, ECDSA, EdDSA are very different.
The question asks if a hacker can select $m$ and $s$ such that $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ output Pass, that is such that $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$.
Good news: the signature system verifies successfully when message and signature are unaltered. Argument: since the input and output set of encryption $E_\mathrm{pk}$ are the same, and there is a decryption function $D_\mathrm{sk}$ that inverts $E_\mathrm{pk}$ for all $p$, both $E_\mathrm{pk}$ and $D_\mathrm{sk}$ are permutations of that set, one the inverse of the other. Thus for all $c$ in that set it holds $E_\mathrm{pk}(D_\mathrm{sk}(c))=c$. Applying this with $c=\operatorname{Hash}(m)$, which the condition $h\le n$ makes possible for all $m$, we get that $E_\mathrm{pk}(s)=E_\mathrm{pk}(D_\mathrm{sk}(\operatorname{Hash}(m)))=\operatorname{Hash}(m)$, therefore $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ output Pass.
More good news: it is not easy for adversaries holder of $\mathrm{pk}$ to select $m$ and $s$ such that $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$. Nothing straightforward seems to work:
- When adversaries first choose arbitrary $m$, and compute $c=\operatorname{Hash}(m)$, that $c$ is random-like, except for being in the lower subset $[0,h)$ of $[0,n)$. When they next try to find $s$ with $c=E_\mathrm{pk}(s)$, they are essentially facing the problem of decrypting arbitrary ciphertext, and that's hard (it can be proven that deciphering an arbitrary cipertext must be hard under the KPA hypothesis we made about the cipher).
- When adversaries first choose arbitrary $s$ and compute $E_\mathrm{pk}(s)$, they get an arbitrary value $c$ in $[0,n)$. There's no insurance that $c$ is in range $[0,h)$ (and if not it can't be the hash of any message $m$). Even if adversaries can work around that hurdle by choosing $s$ so that $c$ is in range $[0,h)$ (which textbook RSA allows, e.g. by making $s=0$ or $s=1$), an ideal hash function is such that it's computationally hard to find $m$ that hashes to an arbitrary given value $c$ in the hash's output range: that's first preimage resistance of the hash.
- When adversaries get hold of a $(m,s)$ pair that passes verification, they could attempt to find $m'$ other than $m$ with $\operatorname{Hash}(m')=\operatorname{Hash}(m)$, which would ensure that $(m',s)$ passes verification. But an ideal hash function is such that it's computationally hard to do this: that's second preimage resistance of the hash.
- Adversaries could attempt to craft two distinct messages $m$ and $m'$ with $\operatorname{Hash}(m)=\operatorname{Hash}(m')$, obtain the signature $s$ of $m$, and would thus have forged another $(m',s)$ that passes verification. That's much easier than the previous attacks (for example that's feasible with SHA-1 as the $\operatorname{Hash}$, when none of the previous attack is feasible), but still an ideal hash function is such that it's computationally hard to do this: that's collision resistance of the hash.
The above does not constitute a valid proof of security, and worse: it would be demonstrably wrong to conclude the signature system is secure. In particular, with $h=2^{256}$ (e.g. the hash is SHA-256) and when the encryption system is textbook RSA, this signature system is vulnerable to a conceivable forgery. Assume a system with coupons $m$ of the form
Coupon worth $123,456.78, reference 4C0D5F62CAF6AF32
Assume the signer checks that a proposed $m$ is a well-formatted coupon, that its reference is unique, gets payment of the price indicated, and under these conditions signs $m$. The Desmedt and Odlyzko attack let adversaries game that system, by purchasing signatures of low-worth coupons and using these signatures to find the signature of a high-worth coupon.
Better news: with some added hypothesis it's possible to prove that this signature system is secure. An hypothesis that works for RSA is that $h$ has nearly as many bits as $n$. This signature system is known as Full Domain Hash. The proof is hard, so much that when FDH was first considered by Mihir Bellare and Peter Rogaway: the Exact Security of Digital Signatures - How to Sign with RSA and Rabin, in proceedings of Eurocrypt 1996, they could not prove a satisfactory security level (and devised a more complex signature system: RSA-PSS, the basis of the widely used RSASSA-PSS). A better security level was obtained years later by Jean-Sébastien Coron: On the Exact Security of Full Domain Hash, in proceedings of Crypto 2000 (but RSA signature had already stabilized and FDH is not in wide use).
¹ Main differences with the question's formulation:
- We sign with the decryption, not the encryption, because encrypting with the private key and being able to decrypt with the public key contradicts the goal of encryption. Also it does not work in practice, including with RSA as implemented, even if we remove padding steps: the format of the public key is $(n,e)$ often with a size limit for $e$, the format of the private key is $(n,e,d,p,q,d_p,d_q,q_\text{inv})$, and trying to shove the public key where the private key is expected, or vice versa, will fail.
- We specify a ciphertext finite set of same size as the plaintext set, hence deterministic encryption, else signature generation or verification would sometime fail under normal use.
- We make the message an input of the verification procedure, because that's how signature is defined in theory and modern practical implementations.
² RSASSA-PKCS1-v1_5 is the only one I know that comes close, however it's $\operatorname{Hash}$ is constructed by concatenating a prefix depending on the bit size of $n$ and $H(m)$, where $H$ is a standard hash such as SHA-256, thus $\operatorname{Hash}$ is not an ideal hash function, since that's expected to appear random-like on it's output domain.
