How to properly do private key management

I'm familiar with the pain you're going through. We struggled to update an old EFT system towards PCI compliance. Key management was certainly (from my software point of view) the most challenging part.

I think I also stumbled into the NIST Recommendations for Key Management that Martin posted, and got incredibly frustrated with the lack of concrete examples.

ANSI X9.17 - Financial Institution Key Management is probably the most relevant to your needs, with PCI-DSS. Good luck reading it though, the document is a massive collection of TLA's which I know I certainly struggled to read. (X9.17 is updated yearly, and latest version is now: NIST SP 800-57 Pt. 1 Rev. 4 )

When frustration turned to desperation I stumbled into The Electronic Money Mill which is a fictional tale, with a good number of relevant technical references. Chapter 17 discusses X9.17 and may help with the understanding.

From all this reference material I designed a key management system that our auditor was pleased with. The design documents are fairly lengthy, but in summary the idea is that you have your Data Encrypying Key protected by a Key Encrypting Key, and the Key Encrypting Key is stored on a physically separate box, itself protected by a Master Key.

My implementation was to have a Key Server application running on a windows box. This application required entry of two separate 'key server master keys' before it could be used. These keys would be known only to the key server administrators. These keys are xor'd together to generate the Master Key, which is stored only in protected memory whilst the application is running. Application can then automatically generate cryptographically strong Key Encrypting Keys, which are stored in encrypted form using the Master Key.

Applications that have a need for encryption will request a Key Encrypting Key from the Key Server. The KEK is used by the application to encrypt/decrypt the Data Encrypting Key, which can be stored securely with the application data.

Good luck. I hope you also find it an interesting challenge!

Have you seen NIST SP 800-57, Recommendation for Key Management?