Correct me if I am wrong, digital certificates require the user to have the public key for the certificate in their web browser, right?
You are wrong, but in a way you're indirectly right. You're wrong because the browser doesn't need to have a pre-shared public key for the site's certificate. The site will send its certificate along with the response, and that certificate will be signed by a certification authority (CA), whose certificate is attached as well.
This shifts the problem—as long as the CA's signature of the server's certificate checks out, now the browser has to check the authenticity of the CA certificate. Which normally is itself signed by another CA, which shifts the problem one more layer. This is called a chain of certificates.
Your operating system or browser vendor bundles a collection of root certificates, and every certificate chain must end in one of those certificates for your browser to recognize it as authentic. So some pre-shared public keys are necessary as you suspected, but you don't need to arrange pre-shared public keys with the sites that you visit. (Instead you need to trust the certification authorities and your OS or browser vendor, which has its own host of problems.)
How can I make this cryptosystem's authentication work if I allow my clients to create their own servers for direct end-to-end encryption?
You would need to do something along these lines:
- Create a CA for your application. Either:
- A standalone one, in which case you'd have to bundle the root certificate with your app. (In that case the private key for this certificate is the keys to the kingdom, and needs to be protected with paranoid zeal.)
- One certified by a third party your clients will recognize (e.g., the certificate comes bundled in their OS or browser).
- Have clients privately generate their key pairs and associated certificates, and securely submit the latter for signature by your CA. (This is a potential weak spot—authenticating clients securely is critical here!)
- Clients can now use their signed certificates to establish authenticated, end-to-end encrypted sessions with their peers.
Some reading to get you started, but you'll want to read more than these two links: