(If you are using Oracle's JDK and JBoss 5.1.x you need to copy EJBCA_HOME/lib/bc*.jar to JBOSS_HOME/server/default/lib/. Remember this when it's time for upgrades! This is a bug tracked by JBoss as JBAS-7882. OpenJDK works just fine though, such as the OpenJDK distributed with RedHat, Ubuntu, Debian etc.

The same bug is present on JBoss 6.0, but the workaround is different, the same workaround as for JBoss 5.1 does not work with JBoss 6. The only way to work around this with Oracle JDK and JBoss 6 is to copy ejbca/lib/bc*.jar to $JAVA_HOME/jre/lib/ext, and to remove lib/bc*.jar from the deployed ejbca.ear file. See the JBAS-7882 issue for more information.)