How do I sign data that's been encrypted using public key? (RSA) I've received a public key to encrypt my data for the other end to decrypt using their private key. Now, they want us to sign the data as well to ensure non-repudiation.

I thought that I should only sign using a private key (which isn't in my possession). How do I sign my encrypted data?
This is impossible - the receiver knows nothing about you so there's no way he can assure that the sender is in fact you.