On Tue, 13 Apr 1999, James H. Cloos Jr. wrote:

Given a recipient with only an RSA keypair (algo 1), and a sender with
only a DSA/Elgamal pair (algos 17 and 16), should the sender
encrypt+sign, will any extant software be able to decrypt and verify?

Yes. The encryption is done using the RSA algorithm, but the signing is
done using DSA. The recipient can decrypt using his RSA key and verify
from the DSA from a keyserver or keyring.
The encryption algorithm is separate and thus can be different from any
signature algorithm.
My test suite generates every possible combination, so I know it is
possible for this to work. Whether any particular implementation handles
this depends on that implmementaiton, but there should not be any problems
if they simply did things in an obvious manner.