1
$\begingroup$

I'm trying to study a simplified TLS-style protocol, including verifying RSA signatures. It's an attempt to verify using only a valid certificate. However, I can't manage to get anything to verify properly. I have a modulus, exponent, signature, and hash of the message. With the following parameters:

modulus = 28459 = n
exponent = 7 = e
signature = 5128 = s
hash(m) = 4085 = x

As I see it, I should be able to take the following

s^e mod n = 5128^7 mod 28459

and see if it equals

x mod n = 4085 mod 28459

If the equations are equal, I'm all set. However, they're not equal! I get 18044 != 4085. Am I missing something here?

|improve this question
$\endgroup$
3
$\begingroup$

Your parameters are incorrect. I don't know how you got them, so I don't know which one is in error; however at least one of them is wrong.

You have $n = 149 \times 191$. The decryption exponent satisfies: $$ed \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)},$$that is, $7d \equiv 1 \pmod{14060}$; the minimal $d$ that satisfies this is $d = 10043$.

Now, if the hash is 4085 (and we'll assume you aren't doing any padding; for a normal sized RSA modulus, you would, however things are too small in this toy example), and so we have:

$S = 4085^{10043} \bmod 28459 = 5023$

With this value of $S$, we see that the signature verifies:

$5023^7 \bmod 28459 = 4085 = X$

Hence, assuming that you got the modulus, exponent and the hash correct, this is the correct value for the signature, not the value you have listed.

|improve this answer
$\endgroup$
  • $\begingroup$ Going through again, it may look like, based on your description, that something is else is fundamentally wrong. I'll go back through with your suggestions in mind and see if something occurs. I'll follow with any significant updates $\endgroup$ – HiVoltRock Dec 15 '13 at 3:15
  • $\begingroup$ Although that does beg the question, if those are the correct parameters (which will involve more work on my part), is my approach correct? That would mean it doesn't verify (which would be expected in that case) $\endgroup$ – HiVoltRock Dec 15 '13 at 3:41
  • $\begingroup$ @HiVoltRock: Yes your approach is correct. In toy-RSA, $s^e\bmod n$ is $18044$, that's not the hash $x$, thus the signature $s$ should be rejected as the signature of the message from which the hash was computed. As shown in the answer, $5023$ is the/an acceptable signature. $\endgroup$ – fgrieu Dec 15 '13 at 11:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.