Does a public key absolutely need to be used to initiate an encrypted session? I am a software developer working on an application with the .NET platform.  This application needs to provide a secure connection and encrypt all data between the client and the server.  It is a standaone app that does not use a web browser and will be using a symmetrical key for the vast majority of the messages for best perfomance.  Sessions can be expected to last between a few minutes to more than 24 hours.  I am somewhat of a beginner when it comes to cryptography, but I have done some research.

From the research I have done, it appears that the current thinking is to use a public/private pair of keys to initiate the session.  The first message sent by the client is encrypted with the public key, which is then decrypted by the server with a private key.  In the first message to the server, a random symmetric session key is also transmitted which is then used for the rest of the session and then discarded after use.  All this seems to be quite reasonable, but I do have some questions and concerns:


If public/private keys are to be used for the initial message, then should the same public client / server private key be used for all clients?  Or, should each user have a separate public / private key?  The application client would not need to maintain a private key for decrypting public key messages from the server since all further messages would be using symmetric encryption.  My concern is that if only one key pair is used and someone does somehow manage to figure out that private 2048-bit key, then all the users of the application would be vulnerable...
From research I have done, it looks like some are recommending that nothing less than 2048 bit RSA keys should be used.  If this application takes off, it could easily have 500,000 users within 5 years or so.  Generating public/private 2048 bit key pairs takes some time (if you know how much time it takes - please let me know along with the hardware) and with 500,000 users, could cause some serious time delays in the future.  Imagine a scenario where all of the 500,000 key pairs need to be regenerated.  How long woutd that take?  So, I'm wondering if there is another way of initiating the session that is just as good and circumvents the need to use public / private key pairs to initiate the session...
The application will have a website assocatiated with it that will allow users to register with a user id and password.  What I am thinking about doing is to apply the password to generate the initial symmetric key that would be used to encrypt the first message to the server.  The random session key would still be transmitted and used after the first message.  To identify the user, a unique user token would be supplied to the client installation upon registration that would be appended to the first encrypted message and the user token would not be encrypted.  Once the server receives the first message, it looks up the token and obtains the password.  The symmetric key for that password is then generated on the server exactly the same way as was done on the client.  The .NET platform provides a way to generate keys from a password with the PasswordDeriveBytes class.  So, this approach seems like it will work, but I am not an expert on this topic and would appreciate hearing from others who are more experienced and are in a position to point out anything that I might be missing...
I have also researched symmetric ciphers.  Since performance is an issue as well as security, I am thinking of going with CAST-128 instead of Rijndael which is now being used by just about everyone as the AES.  The reason for this is because according to some benchmarks, CAST-128 is faster on Windows systems.  Also, from a security point of view, I would much prefer to use a much less popular cipher than one that is being used by the US, other governments, and most companies.  There is much more interest in breaking Rijndael than CAST-128 which is only being used by the Canadian govt and PGP.
First recommendation: Don't invent your own protocol, but use an existing one. Use SSL/TLS, in the newest version possible if you don't have to provide downwards compatibility to existing clients. This will take care of most problems here, you simply put in a pair of plaintext data streams, and get a pair of encrypted streams. There are TLS implementations for most programming languages available, I'm quite sure that .NET has one, too.
TLS is quite flexible about the key exchange, authentication and encryption algorithms (bundled together as &quot;cipher suite&quot;). You'll have a public key for the server (usually with a certificate, whose subscribing key can already be embedded in the client application), and then use (for example) Diffie-Hellman key exchange with public-key authentication. There are also password-based key exchange algorithms, then you even don't need a public key (but client and server need some other way to first get the common password).
To your questions:

SSL/TLS works fine with a constant public key, not a different one per-client. Of course, if the private key gets leaked, all future connections are broken. If you did use the simple &quot;encrypt session key by public key&quot; model (RSA key exchange), also all past connections can be decrypted. Diffie-Hellman provides forward-secrecy, as the key is generated from random input of both sides, and the public key is only used for authentication.
If you create a new key pair per-client, you'll need some way of the client to tell its name (or key ID or similar) before the actual connection.

I have no data about how long key generation nowadays takes, sorry. You also have to take care of having enough entropy for your keys. But as said before, there is no need to generate new keys regularly.

Instead of doing this yourself, have a look on the secure remote password protocol for generating a shared session key authenticated by a password. This is also available (standardized) as a key exchange method for TLS, though I'm not sure if it is supported by .NET's implementation.

You can use whatever cipher you want, but as said by others, AES is actually more likely to be secure than other ciphers. Also, modern processors have actually AES-instructions build in, which could make the performance difference quite small or even negative (i.e. AES-128 could be faster than CAST-128), if you use a library which actually can make use of these.