It sounds like you're trying to set up a "host-proof" system.
( How can one share information using the 'host-proof' paradigm? ; Encryption scheme for social-network-like data sharing data via untrusted server? ; host-proof etc. ).
Sounds like a fascinating problem.
I'm assuming you're trying to set things up so that no data is stored on the client -- not even encrypted.
(That makes things much more difficult, compared to storing the user's private key on the user's client).
encrypted public keys
All the asymmetric systems I've been involved in are careful to generate the private key inside one box and never, ever let that key outside the box, even in encrypted form.
So I'm a little uncomfortable with storing the (encrypted) private key on the server.
However, I'm almost convinced that is excessive paranoia -- several people I respect seem to think it's OK to let a encrypted form of that private key outside the box -- a private key encrypted using a well-vetted algorithm such as AES, encrypted using a key generated from some key-stretching KDF (S2K) such as scrypt or PKDF2, giving the KDF a long passphrase. (Perhaps What is the harm if I publish an encrypted RSA private key publicly? is a better place to talk about encrypted private keys, and How can one securely generate an asymmetric key pair from a short passphrase? is a better place for comparing "encrypted private keys" to the various other ways of obtaining a private key from a passphrase).
You may want to add some sort of message authentication code (MAC) or digital signature to the data.
After you do that, there's really no need for another process to check whether the password (or the key generated from it) is valid (see Sending KCV (key check value) with cipher text , Can I determine if a user has the wrong symmetric encryption key? ).
So your server blindly sends (encrypted) files to any person who requests them?
Then the local client does the check to see if the password(s) that person has are valid are performed locally?
I suspect there may be a better way of handling this.
Perhaps some sort of zero-knowledge challenge-response protocol?
So when Bob wants to send a message to Alice,
- Bob types up his message on his own local machine.
- Bob somehow obtains that Alice's public encryption key. (This can be a tricky -- how do you keep Charley from tricking Bob into using Charley's public encryption key?).
- Bob encrypts his message with Alice's public encryption key (locally), and then sends the encrypted file to your server
- Later, Alice pulls a bunch of files from your server:
- her encrypted private key
- the file Bob posted
- some client code. (This is the really tricky bit -- is there any way for Alice to confirm that this code hasn't been maliciously modified, either modified in-flight while it's being transferred from your host to Alice's machine, or worse -- modified by some malicious attacker who has compromised your host?)
- (optional) Alice unplugs her local machine from the Internet
- Alice types in her passphrase on her local machine into your client code.
- The client code runs Alice's passphrase through a slow KDF to get a (symmetric) key, then uses that (symmetric) key to decrypt her private key, and then uses that private key to decrypt Bob's file. (Typically there's yet another file-specific symmetric key involved in that decryption).
- Finally, Alice reads the message Bob typed.
other things to think about
Rather than writing new crypto code from scratch,
you might consider using code that other people have already written, debugged, and vetted for security flaws. a b c d
You seem to think that PKDF2 and AES is better than whatever algorithms were around when OpenPGP was standardized.
Rather than completely writing an entirely new system from scratch,
perhaps it would be better to incrementally improve some OpenPGP implementation
so it supports PKDF2 and other things you feel are important.
Most open-source software writers would be happy to receive your improvements.
OpenPGP files generated according to the latest standards (RFC4880)
already support AES.
Perhaps you might find convergent encryption ( convergent-encryption ) interesting.