Assymetric key encryption for securing SOAP webservice
===

I'd like to authenticate the caller of my SOAP webservice (deployed in Ruby 1.8.7/Rails 2.3.5using datanoise gem in Red Hat enterprise linux 5) using some encrypted tag in the XML requests. Normally the client is a windows program (maybe C#/.Net windows programs - not Java/Ruby) which should generate a varying encrypted key in each call to the webservice based on a key/salt - while my server side would always be able to decode it with the private key. Knowledge of the encrypted token on the wire should not allow a third-party program to simply replicate the fully encrypted token and access the webservice. I am looking into OpenSSL but am a newbie to cryptography. The string being encrypted for identification could be (among other items) the MAC ID of the trusted client, which when decrypted would match the stored value on the server side of the trusted hosts.

I've found lots of possibilities on the Ruby side, but need to ideally ensure that the solution does not impose (or minimizes) any library or installation requirement on the windows client side. What i'm most struggling with is a way to generate a new key each time the call is made, so that anyone sniffing the traffic cannot simply infer the mode to create the encrypted tag by getting access to the key.