Ruby: Cryptographically sign a string to ensure authenticity?

Lets say I have a origin server which through the act of a redirect with particular query string params needs to provide details to a target server. However, I need to ensure those details came from my origin server only.

Also I can't sure the integrity of the target server. Or specifically, the target server might be compromised so any encryption keys might have been read by a malicious party.

I'm thinking I could sign the query string using some form of public/private keypair. The origin server uses a private key to sign the string, and the target server uses a public key to verify it came from my origin server, and the message hasn't been tampered with.

I'm far from a cryptography expert or anything, so any assumption here I've made might be wrong, please correct me if so :)

I'm basically after a (hopefully) simple way to do this in Ruby.

---