What's the least computationally expensive way to verify a message is from who they say they are?

The first step in verifying a signature is to hash the message, which takes a few thousand x86 instructions. Your language doesn't seem to support the logical operations that are common in modern hash functions - implementing those with arithmetic operations will cost you some overhead. So you're talking about hours before you even get to the public key portion of the signature. And you can't use a weak hash function, because your attackers aren't limited to such an under-powered platform to produce their forgeries.

I question if in-game cryptography is the best solution here. Since this is all in a managed environment, it seems like you could simply disallow spoofing of the sender property of these messages.