There are some C examples in MSDN crypto area on Signing and Enveloping
messages. The CryptoAPI message functions mostly use keys that have
associated certificates (and hence reference stores for recipients etc..).
For example, to Envelope (encrypt to a number of recipients) a "hint" to the
recipients is included in the pkcs7 message produced by including the
recipients certificate issuer and serial number.
This page has a good description of the algorithm:
Do you have keypairs without associated certificates?
CryptDecryptMessage requires one or more cert stores be specified in the
pDecryptPara struct. The function internally searches the specified stores
for certs that match the recipients "hint" included in the enveloped message
blob and if a match is found attempts to de-envelope the message using the
private key associated with that "hint" certificate.
Do you mean redistrubuting just the public key? If you key has an associated
cert you should distribute the entire certificate obviously.