Background info:
I am planning on making a filehost with which one can encrypt and upload files. To protect the data against any form of hacking, I'd like not to know the encryption key ($K$) used for a file, so the user will have to asymmetrically encrypt $K$ and send it as well. The reason for this double encryption is that you can still share (individual!) files with other accounts by encrypting $K$ with the public keys of those users, too.

My problem is: How can a user can get a public and private key without the server saving/knowing the private key and without the user having to remember a passphrase of 250 hex characters?

Question:
Is there a way to derive a key pair from a password, like PBKDF-2 does for symmetric encryption?
Suggestions on rearranging the cryptographic steps in an easier way are welcome, too.

Alternatively:
It is also possible to encrypt the private key with a PBKDF-applied password and store it on the server, but I'd like to keep things 'simple'. ;)

Note: At this point I don't care if it requires RSA, ECC or an obscure cryptography scheme.

The best you can hope for is the following:


You derive the password into a "big enough" (e.g. 128 bits) secret key $K$ with a Key Derivation Function like PBKDF2. There are some details to be aware of (see below).
You use the secret key $K$ as seed for a Pseudorandom Number Generator. The PRNG is deterministic (same seed implies same output sequence) and produces random bits.
You use the PRNG in the key pair generation algorithm for whatever asymmetric algorithm you want to use. This step is cheap and simple for discrete-logarithm based algorithms like DSA, ElGamal, Diffie-Hellman, and their elliptic-curve variants, provided that the group parameters are known in advance (e.g. it is hardcoded in all relevant pieces of software that you are doing ECDSA / ECDH with the standard P-256 elliptic curve defined by NIST). For RSA, this is less cheap and simple, because the key generation process entails generating random integers until primes are reached. This is still doable.


Since this procedure is deterministic (for a given source password), you can run it again every time you need the private key.



Now the trouble with passwords is that they are from the relatively small and non-uniform space of "things which fit in the mind of an average user". They are vulnerable to exhaustive search, which, for passwords, is traditionally named dictionary attack. There are three generic ways to cope with that problem:


Do not let the attacker learn any piece of data which allows him to verify a password guess. In the usual context of storing password hashes in a server for user authentication, this means that you do not want attackers to be able to read the database; this is why Unix-like systems have switched to shadow passwords about 15 years ago. You still want to store hashed passwords, and use the two other protections, because illicit read-only access does happen in the real world.
Use a configurably slow key derivation function. This makes dictionary attacks proportionally slower -- but also normal usage slower, by the same factor. This is why KDF such as PBKDF2 or bcrypt include an iteration count. You want to raise that count up to the highest value which is still tolerable for your users.
Use a salt to prevent attack parallelism. Parallelism is about attacking N passwords (not necessarily simultaneously) for less than N times the cost of attacking one (precomputed tables are a kind of parallelism). The salt is a public piece of data which acts as a variation to the KDF; this is equivalent to saying that there are many distinct KDF, and the salt says which one you use.


In your scenario, you do not have the first protection: the resulting public key is, by nature, public, and thus can serve for offline dictionary attacks. The attacker just has to try possible passwords until he finds the same public key. That's intrinsic to what you want to achieve.

The third protection (the salt) could also prove difficult. The salt needs not be secret, but it still must have some level of integrity. Wherever the salt is stored, the user who wants to recompute his private key must be reasonably assured that he is using the right salt (otherwise he will compute the wrong private key). Depending on the usage scenario, it may or may not be easy to have such a storage space. A partial solution is to use the user name as salt (presumably, the user will be able to remember his own name); as salts go, user names are less than ideal, because:


two users on two distinct server installations (using the same software) may have the same name;
when a user changes his password, he does not change his name;


and this breaks the "unicity" property that the salt tries to achieve. Still, the user name as salt is much better than no salt at all (better yet, use the user's email address as salt: users remember their own address, and email addresses are, by nature, unique worldwide). If you do not use any salt at all, then two distinct users on the same system, who happen to choose the same password, will end up with the same key pair, and simply listing the public keys will show it immediately.



Note: deriving the private key from the password means that when the user changes his password, he also changes his private key. Chances are that this is a problem. This is one of the reasons why you could prefer an indirect system, where a totally normal key pair is stored somewhere, symmetrically encrypted with a password-derived key. Thus, when the password is changed, you just decrypt the key with the old password, and encrypt again with the new password. But this requires an available storage area. This model is directly supported by, e.g., GnuPG.
