How to generate a matching CA with a different signing algorithm

This is a bit past it's time ever since Google decided to deprecate SHA-1, but there is still a possibility for a site to need a CA with a different signing algorithm to resolve compatibility with some cryptography in an environment. This in general is not something that should be taken as a recommendation, it is something that needs to be determined is an unfortunate circumstance to support some piece of software or hardware in environment.

The first thing to remember is that a certificate can be simplified to (certificate_info, public_key, signature). The first step of verification is to look through the CA data to match strings of issuer and subject, and then start doing the cryptographic validation. This lookup is the piece you are trying to take advantage of to have differing CA's. This can be seen as part of the following steps:

openssl genrsa -out CA.key 2048
openssl req -new -x509 -key CA.key -out CA.sha256.crt -sha256 -subj /C=AB/ST=CD/L=EF/O=G/OU=HI/CN=JK
openssl req -new -x509 -key CA.key -out CA.sha512.crt -sha512 -subj /C=AB/ST=CD/L=EF/O=G/OU=HI/CN=JK
openssl req -new -x509 -key CA.key -out CA.sha512b.crt -sha512 -subj /C=ED/ST=RFR/L=GHH/O=URU/OU=DS/CN=OL

These openssl req can be done how a CA is normally signed or some other CA signing infrastructure. The particular invocation above was only done for illustration. In the end we have certificates that look like this:

$ find -name 'CA.*.crt'  -print -exec openssl x509 -in {} -subject -noout \;
./CA.sha256.crt
subject= /C=AB/ST=CD/L=EF/O=G/OU=HI/CN=JK
./CA.sha512.crt
subject= /C=AB/ST=CD/L=EF/O=G/OU=HI/CN=JK
./CA.sha512b.crt
subject= /C=ED/ST=RFR/L=GHH/O=URU/OU=DS/CN=OL

Then let's sign a new host key with just one certificate from the CA, but using the unique private key for the CA.

openssl genrsa -out host.key
openssl req -new -key host.key -out host.csr
openssl x509 -req -days 3650 -in host.csr -out host.crt -CAkey CA.key -CA CA.sha256.crt  -sha256 -set_serial 2

This is how a normal signing works, and now let's see how it verifies:

$ find -name 'CA.*.crt'  -print -exec openssl verify -CAfile {} host.crt \;
./CA.sha256.crt
host.crt: OK
./CA.sha512.crt
host.crt: OK
./CA.sha512b.crt
host.crt: C = QA, ST = WSD, L = ED, O = RGFG, OU = YHJ, CN = UJ
error 20 at 0 depth lookup:unable to get local issuer certificate

As you can see from the steps above we are using the same private key material in CA.key with several certificates, but at the moment of verification we are only using one of the CA certificates to verify the signature of the host certificate. In practice you should be making sure only one is available in an environment as the verification process will generally take the first match- even if it can't process it. There have been instances in the past where a MD5 based certificate and a SHA-1 certificate were in a CA trust store but because of natural ordering the MD5 certificate was selected first and was rejected on policy grounds since MD5 is deprecated.