We should go for a modified Diffie-Hellman Key Exchange, where we encrypt their shared private key with an internal key that is NEVER stored on the database but given to the user to store upon signing up.

This will work in 3 stages:

1: User 1 initializes contact with user 2

• a. Sets public prime, and base
• b. Sets their (user 1) private key
• c. Compute their (user 1) solution
• d. Create their (user 1) contact map
  • their (user 1) username
  • the public prime, base
  • their (user 1) solution
  • their (user 1) public RSA key
• e. Send them (user 2) their (user 1) contact map

2a: User 2 denies user 1's contact

• a. Removes user 1's contact map

2b: User 2 accepts user 1's contact

• a. Set's their (user 2) private key
• b. Computes their (user 2) solution
• c. Create their (user 2) contact map
  • their (user 2) username
  • the public prime, base
  • their (user 2) solution
  • their (user 2) public RSA key
• d. Send them (user 1) their (user 2) contact map
• e. Compute their (user 1 & user 2) shared private key
• f. Encrypt the shared private key with internal key
• g. Store shared private key in their (user 2) contact map of user 1

3: User 1 confirms user 2 as a contact

• a. Compute their (user 1 & user 2) shared private key
• b. Encrypt the shared private key with internal key
• c. Store shared private key in their (user 1) contact map of user 2

Now user 1 and user 2 share a private key to decrypt each other's messages.