SHA256 signing stops working in .NET 4.5

While this question was asked almost a year ago, it has received some up votes recently which may indicate that some other people are getting the same problem. Hopefully this answer can help :) Briefly speaking, the error doesn't happen in all machines but only in some of them. I guess it depends on what CSPs have been registered on a specific machine. Anyway, in my specific case, the certificate was generated with either "Microsoft RSA SChannel..." or "Microsoft strong cryptographic provider" as the CSP. I generated a new certificate but used "Microsoft Enhanced RSA and AES Cryptographic Provider" as the CSP and it SHA256 signing started working for me.

Some references:

https://social.msdn.microsoft.com/Forums/vstudio/en-US/e391ba75-ce6e-431c-bfc9-26a71ae1b033/sha256-signing-stops-working-in-net-45?forum=Geneva (as you can see, million thanks to Paul who helped me solve this issue)

http://hintdesk.com/c-how-to-fix-invalid-algorithm-specified-when-signing-with-sha256/

Had the same problem with XmlDsig (trying to make enveloping signature of xml document with RSA-SHA256 algorithm). First I were getting exception

System.Security.Cryptography.CryptographicException: SignatureDescription could not be created for the signature algorithm supplied.

Then I found mention of RSAPKCS1SHA256SignatureDescription - signature description implementation for RSA-SHA256 signatures.
Full implementation here:
http://clrsecurity.codeplex.com/SourceControl/changeset/view/47833#269110
or here: https://gist.github.com/sneal/f35de432115b840c4c1f

You have to manually call once per appdomain:

CryptoConfig.AddAlgorithm(typeof(RSAPKCS1SHA256SignatureDescription), "http://www.w3.org/2001/04/xmldsig-more#rsa-sha256");

After that I got a new exception:

System.Security.Cryptography.CryptographicException: Invalid algorithm specified.

This brought me to your question. After reading suggested article I have made a new key and certificate (with OpenSSL) using Microsoft Enhanced RSA and AES Cryptographic Provider.
To my surprise, this new certificate allowed me to successfully make a signature.

After some more investigation I have found interesting answer of Andrew here https://stackoverflow.com/a/17285774/328785, where he used RSACryptoServiceProvider to prepare SecretKey for SignedXml class. Specifically this part (my interpretation):

var store = new X509Store(StoreName.My, StoreLocation.CurrentUser);
store.Open(OpenFlags.OpenExistingOnly | OpenFlags.ReadOnly);
var certificates =  store.Certificates.Find(X509FindType.FindBySerialNumber,  "54dba096", true);
var certificate = certificates[0];

// next three lines
var cspParams = new CspParameters(24) { KeyContainerName = "XML_DSIG_RSA_KEY" };
var key = new RSACryptoServiceProvider(cspParams);
key.FromXmlString(certificate.PrivateKey.ToXmlString(true));

SignedXml sxml = new SignedXml(doc);
sxml.SigningKey = key;

And this solutions worked fine even with old key!