I think 10.4 only produces 1024bit keys..
My habit is that I create all keys on a 10.6 server, generate the CSR from that machine, get it signed, then import the combo into whatever server I need it for (10.4 through 10.8)
Do you have a 10.5+ server? if so, why not create a new key/csr and get it signed.
Then import in your 10.4 server.