My root certificates are stored as several files in ASN.1 format.
Assume I have a chained end entity certificate in the same format. How do I efficiently determine the root certificate of this certificate?
Currently I have to take a brute force approach which extracts the public key of the end entity certificate and validates that against all root certificates and the first match is considered the root certificate. Is this the right approach??
To find the issuer of a certificate, you should use the "Issuer DN" and match it with the "Subject DN" of the certificates in your CA store. This should reduce significantly the number of signature verification.
It is possible to have different CA certificates with the same "Subject DN" (with different public keys, validity dates, etc.), so your algorithm should be prepared to handle that. The "Subject Key Identifier" and "Authority Key Identifier" can also help to reduce the number of candidates.
Finding the issuing authority is only a small part of the "right approach" to validating certificates. I would advise you to look at part 6 of http://www.ietf.org/rfc/rfc5280.txt "Certification Path Validation". Some parts are most probably overkill (i.e. most things having to do with policies).