Another approach (besides hashing) that has been tried to construct secure RSA-based signatures is to encode the message before applying the RSA permutation. Here the signer xes a public encoding function enc : {0,1}^L Z^*_N as part of its public key, and the signature on a message m is := [enc(m)^d mod N].

(a) Show that encoded RSA is insecure if enc(m) = 0x00 || m || 0^k/10 (where K = || N ||, L =|m| = 4/5, and m is not the all-0 message). Assume e = 3.

(b) Show that encoded RSA is insecure for enc(m) = 0 || m || 0 || m (where L = |m| = (||N||1)/2 and m is not the all-0 message). Assume e = 3.