ssl 证书链的验证主要分为两种方式，自上而下和自下而上，其中自上而下又可以分为两种方式，其中一种就是 openssl 的实现方式，也就是《 openssl 的证书链的验证 》中介绍的其中一种方式，另一种是自上而下与自下而上结合的方式；在自下而上的验证方式中也可以分为两种方式，一种是平坦遍历的方式，另一种是分级别的遍历方式。鉴于自上而下的单链方式和基于等级的自下而上的方式已经在《 openssl 的证书链的验证 》中有所介绍，本文仅介绍余下来的另外两种方式，首先看看自上而下与自下而上结合的方式，下图为一个 CA 体系的真实逻辑结构：
root[a1[b1[c1],b2,b3[c2],b4],a2[b5],a3[b6,b7[c3]]]
下面是 openssl 框架将上述结构载入内存的实际结构，可以看出，具体的颁发关系已经没有了，只剩下了一个只有级别的吊链结构，我们要做的就是在这个吊链结构中遍历，而且是自上而下的遍历，寻找一切有可能的验证路径，这就涉及到了图算法，也就是图的遍历算法，但是实际上这个图并没有想象的那么复杂，而可以被看做是一棵树，具体的算法见下面的伪代码和文字解释：
root
a1-a2-a3
b1-b2-b3-b4-b5-b6-b7
c1-c2-c3
伪代码如下，如不具体，请指导或添加，可以道明的是，肯定不完整，我真心希望有志同道合的家伙和我一起探讨linux内核或者openssl的点点滴滴：
Root->A1->B1->C2(failed)
B2->C2(failed)
…. （可能导致复杂的回溯算法，见下面的解释）
B3->C2(right)
Get upper level and set to A
Set B3 to To_cert
RETRY:
For-each in A as a
If a can verify To_cert
Get upper level and set to A
Set a to To_cert
RETRY.
If all upper failed
Failed!
首先从 root 依次往下验证，每一层按照从链表头到尾的顺序，直到验证失败，然后回到验证方的兄弟，将之作为新的验证方重新验证被验证方，如果所有兄弟都已用尽，也就是说全部验证失败，那么被验证方做上标记，作废之，并且回到全军覆没的兄弟的再上一层的已经参加过验证的兄弟，然后将之作为新的验证方，重新开始验证全军覆没的兄弟的第一个，依次类推！注意有个例外情况，那就是验证最下层用户证书的时候，因为用户证书只有一个，并且是确定的一个，那么如果上层的所有兄弟都验证失败，就可以证明结果的失败，没有必要往上继续回溯了，否则就要回溯。只要在回溯的过程中有验证正确的，那么就要开始向上验证，一直到根，如果到不了根，那么这条回溯路径上的所有的证书将被做上标记，以后不再参与验证，全部作废，因为一个证书只能由一个 ca 颁发，所以从 root 到用户证书的路径如果有的话只有一条，这个看似复杂的基于图的回溯算法实际上很少有需要完全遍历的情况。
最后一种方式就是平坦的验证方式，就是针对每个证书，都要尽可能遍历store中的所有证书进行验证，代码如下，比较简单，但是对于用int类型做depth来说，最大的证书链深度也就限定为了32
static int OpenSSL_VerifyChain(X509 **chain, int n, X509 *cert)
{
int i;
unsigned long flag = 0;
int rv = 0;
X509_NAME *name1, *name2;
EVP_PKEY *pkey;
...
while(1) {
if(i == n)
return -rv;
name1 = X509_get_issuer_name(cert);
name2 = X509_get_subject_name(cert);
if(OpenSSL_X509NameEqual(name1,name2)) {
pkey = X509_get_pubkey(cert);
if(!X509_verify(cert, pkey))
return -rv;
return rv;
}
for(i = 0; i < n; i++) {
if(flag & (1<<i)) //跳过已经验证过的证书
continue;
name2 = X509_get_subject_name(*(chain+i));
if(OpenSSL_X509NameEqual(name1,name2)){
if(!OpenSSL_CertValidity(*(chain+i)))
return -rv;
pkey = X509_get_pubkey(*(chain+i));
if(!X509_verify(cert, pkey))
return -rv;
//一个位作为索引，以该索引取得的证书以后不用再参与验证了，已经完成关于它的验证了
flag |= 1<<i;
cert = *(chain+i); //继续下一个
break;
}
}
rv++;
}
}
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1273299
