RSA public key verification based on a secret

Question

I'm attempting to develop my messanging app with encryption evolved. For now I came up with algorithm for authorization and message exchange.

P.S. conneciton between server and client is over https

Auth:

1. User generates his private and public key based on his password
2. User requests authorization
3. Server generates random 64 bytes string
4. Server encrypts string with user’s public key, that was stored in database
5. Server sends challenge to user. Challenge is encrypted string
6. Client decrypts challenge with his private key
7. Client sends server decrypted string
8. Server compares string, if they match user is authorized and granted permissions to exchange messages and/or view old messages

Exchange:

1. User #1 requests User #2 public key
2. Server responds with User #2 public key
3. User #1 encrypts message with User #2 public key
4. User #1 generates a signature based on User #2 username and message body
5. User #1 encrypt signature with his private key
6. User #1 encrypt message with User #1 public key
7. User #1 generate a signature based on his password and message body
8. User #1 sends server a message encrypted with User #2 public key
9. User #1 sends server a signature for message to User #2
10. User #1 sends server a message encrypted with User #1 public key
11. User #1 sends server a signature for message encrypted with his public key

In this case server doesn't user's password, therefore is unable to generate private key. But if someone will have access to the server he can perform attack by faking someone's public keys and therefore will be able to decrypt messages.

1. Server generates fake keys for User #1
2. User #2 requests User #1 public key
3. Server responds with fake public key
4. … User #2 encrypts message …
5. Server retrieves message and is able to decrypt them

So, how can I verify that keys were not faked by the server? I was thinking about user when signing up generating secret string, doing some encryption with it, so server cannot decrypt it and recipient should verify that secret string was used to generate keys without actually knowing secret and private key. But I have no idea how this can be done.

Answer 1

Cryptography is hard for the professionals, never mind for us mere mortals. For real world coding it is important not to try to do it yourself because you will probably make a mistake.

As mentioned the signal protocol should give you the features you require. For instance:

support for asynchronous communication ("offline messages")

Take a look at the Wikipedia article.

Although one thing you mention is resilience to a compromised server. The thing is that at some level there must be a party you trust for the whole thing to work, otherwise key distribution cannot work. We can make sure another party signs all public keys with a pinned certificate but then we must trust them. TLS does this using a hierarchy of certificate authorities of which the root CA we put absolute trust in.