Custom Certificate Authority

Need to build a custom Certificate Authority to generate millions of self signed certificates for a unique web application. Can be built upon existing open source technology. Will operate against a database with millions of records, like MySQL. When a digital certificate attached to a record is consumed by a application, it will be flagged as needing a replacement certificate from the Certificate Authority. The certificate would be generated at various strengths as dictated by a configuration file. At the lowest level, the certificate would be exportable through US export regulations, but could be configured for much stronger certificates. For testing purposes, a very vanilla application which would randomly choose unused certificates/database records would be needed for testing.