Path processing algorithm

A certification path is a sequence of n certificates where:

     * for all x in {1,(n-1)}, the subject of certificate x is the
     issuer of certificate x+1.
     * certificate x=1 is the the self-signed certificate, and
     * certificate x=n is the end entity certificate.

  This section assumes the following inputs are provided to the path
  processing logic:

     (a)  a certification path of length n;

     (b)  a set of initial policy identifiers (each comprising a
     sequence of policy element identifiers), which identifies one or
     more certificate policies, any one of which would be acceptable
     for the purposes of certification path processing, or the special
     value "any-policy";

     (c)  the current date/time (if not available internally to the
     certification path processing module); and

     (d)  the time, T, for which the validity of the path should be
     determined.  (This may be the current date/time, or some point in
     the past.)

  From the inputs, the procedure intializes five state variables:

     (a)  acceptable policy set:  A set of certificate policy
     identifiers comprising the policy or policies recognized by the
     public key user together with policies deemed equivalent through
     policy mapping. The initial value of the acceptable policy set is
     the special value "any-policy".

     (b)  constrained subtrees:  A set of root names defining a set of
     subtrees within which all subject names in subsequent certificates
     in the certification path shall fall. The initial value is
     "unbounded".

     (c)  excluded subtrees:  A set of root names defining a set of
     subtrees within which no subject name in subsequent certificates
     in the certification path may fall. The initial value is "empty".

     (d)  explicit policy: an integer which indicates if an explicit
     policy identifier is required. The integer indicates the first
     certificate in the path where this requirement is imposed. Once
     set, this variable may be decreased, but may not be increased.
     (That is, if a certificate in the path requires explicit policy
     identifiers, a later certificate can not remove this requirement.)
     The initial value is n+1.

     (e)  policy mapping: an integer which indicates if policy mapping
     is permitted.  The integer indicates the last certificate on which
     policy mapping may be applied.  Once set, this variable may be
     decreased, but may not be increased. (That is, if a certificate in
     the path specifies policy mapping is not permitted, it can not be
     overriden by a later certificate.) The initial value is n+1.

  The actions performed by the path processing software for each
  certificate i=1 through n are described below.  The self-signed
  certificate is certificate i=1, the end entity certificate is i=n.
  The processing is performed sequentially, so that processing
  certificate i affects the state variables for processing certificate
  (i+1). Note that actions (h) through (m) are not applied to the end
  entity certificate (certificate n).

The path processing actions to be performed are:

     (a)  Verify the basic certificate information, including:

        (1) the certificate was signed using the subject public key
        from certificate i-1 (in the special case i=1, this step may be
        omitted; if not, use the subject public key from the same
        certificate),

        (2) the certificate validity period includes time T,

        (3) the certificate had not been revoked at time T and is not
        currently on hold status that commenced before time T, (this
        may be determined by obtaining the appropriate CRL or status
        information, or by out-of-band mechanisms), and

        (4) the subject and issuer names chain correctly (that is, the
        issuer of this certificate was the subject of the previous
        certificate.)

     (b)  Verify that the subject name and subjectAltName extension
     (critical or noncritical) is consistent with the constrained
     subtrees state variables.

     (c)  Verify that the subject name and subjectAltName extension
     (critical or noncritical) is consistent with the excluded subtrees
     state variables.

     (d)  Verify that policy information is consistent with the initial
     policy set:

        (1) if the explicit policy state variable is less than or equal
        to i, a policy identifier in the certificate shall be in the
        initial policy set; and

        (2) if the policy mapping variable is less than or equal to i,
        the policy identifier may not be mapped.

     (e)  Verify that policy information is consistent with the
     acceptable policy set:

        (1) if the certificate policies extension is marked critical,
        the intersection of the policies extension and the acceptable
        policy set shall be non-null;

        (2) the acceptable policy set is assigned the resulting
        intersection as its new value.

     (g) Verify that the intersection of the acceptable policy set and
     the initial policy set is non-null.

     (h)  Recognize and process any other critical extension present in
     the certificate.

     (i) Verify that the certificate is a CA certificate (as specified
     in a basicConstraints extension or as verified out-of-band).

     (j)  If permittedSubtrees is present in the certificate, set the
     constrained subtrees state variable to the intersection of its
     previous value and the value indicated in the extension field.

     (k)  If excludedSubtrees is present in the certificate, set the
     excluded subtrees state variable to the union of its previous
     value and the value indicated in the extension field.

     (l)  If a policy constraints extension is included in the
     certificate, modify the explicit policy and policy mapping state
     variables as follows:

        (1) If requireExplicitPolicy is present and has value r, the
        explicit policy state variable is set to the minimum of its
        current value and the sum of r and i (the current certificate
        in the sequence).

        (2) If inhibitPolicyMapping is present and has value q, the
        policy mapping state variable is set to the minimum of its
        current value and the sum of q and i (the current certificate
        in the sequence).

     (m) If a key usage extension is marked critical, ensure the
     keyCertSign bit is set.

  If any one of the above checks fail, the procedure terminates,
  returning a failure indication and an appropriate reason.  If none of
  the above checks fail on the end-entity certificate, the procedure
  terminates, returning a success indication together with the set of
  all policy qualifier values encountered in the set of certificates.