I am facing this question about RSA signatures and I understand that a hash encode is secure, but I was asked this:

Given the scheme based on RSA assumption. Consider the RSA function f with some modulus $N$ of 1024 bits and an exponent $e = 3$, satisfying $\operatorname{gcd}(3, Φ(N)) = 1$; let $d$ be the inverse of $e$, $ed = 1 \mod Φ(N)$. The RSA signature has verification key $vk = (N, e)$ and signing key $sk = (N, d)$. The signing algorithm first encodes the message using some encoding algorithm $\operatorname{encode}(m)$ and then simply computes $π = \operatorname{encode}(m) d \mod N$ and sets $π$ to be the signature of $m$.

We know that if $\operatorname{encode}(m) = \operatorname{H}(m)$, where $\operatorname{H}$ is as good as a random oracle (i.e., a public random function), then RSA signature is secure. Here consider a different encoding algorithm $\operatorname{encode}(m) = 0||m||0^{99}$, where $|m| = 1024 − 100 = 924$. Show that when this encoding algorithm is used, the RSA signature is insecure.

  • 2
    $\begingroup$ what research have you done? Where are you stuck solving this? $\endgroup$ – axapaxa Mar 12 '17 at 2:04
  • $\begingroup$ Hint: Consider what happens when the messages are short big-endian integers. $\endgroup$ – SEJPM Mar 12 '17 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.