Another approach (besides hashing) that has been explored to construct secure RSA-based signatures is to encode...

Transcribed Image Text:

Another approach (besides hashing) that has been explored to construct secure RSA-based signatures is to encode the message before applying the RSA permutation. Here the signer fixes a public encoding function enc: {0,1)→ Z as part of its public key, and the signature on a message m is σ := [enc(m) mod N]. (a) How is verification performed in such a scheme? (b) Suggest an appropriate encoding function for << ||N|| that heuris- tically prevents the "no-message attack" described in Section 13.4.1. (c) Show that encoded RSA is insecure if enc(m) = m/|0*/10 (where def def K ||N||, m 4x/5, and m is not the all-0 message). Assume e = 3. (d) Show that encoded RSA is insecure for enc(m) = m/|0||m (where def |m| (||N||-1)/2 and m is not the all-0 message). Assume e = 3. (e) Show attacks in parts (c) and (d) for arbitrary e. Another approach (besides hashing) that has been explored to construct secure RSA-based signatures is to encode the message before applying the RSA permutation. Here the signer fixes a public encoding function enc: {0,1)→ Z as part of its public key, and the signature on a message m is σ := [enc(m) mod N]. (a) How is verification performed in such a scheme? (b) Suggest an appropriate encoding function for << ||N|| that heuris- tically prevents the "no-message attack" described in Section 13.4.1. (c) Show that encoded RSA is insecure if enc(m) = m/|0*/10 (where def def K ||N||, m 4x/5, and m is not the all-0 message). Assume e = 3. (d) Show that encoded RSA is insecure for enc(m) = m/|0||m (where def |m| (||N||-1)/2 and m is not the all-0 message). Assume e = 3. (e) Show attacks in parts (c) and (d) for arbitrary e.

Answer rating: 100% (QA)

a Verification To verify an encoded RSA signature a verifier first decodes the signature using the signers public encoding function enc The verifier t... View the full answer