What is the instruction count without the message signing?
RSA/SHA256 is pretty heavy, what if you just use a SHA-1 HMAC?