I could use a hand in identifying the encryption scheme used in this scenario. (Its from source code known to work)

There is a client connecting to a server such that:

client_private_key = rand
p = 131 # known prime
client_public_key = ((client_private_key ** p) % known_server_public_key)

Client shares its client_public_key to the server, and encrypts and decrypts using its client_private_key which is totally random.

Now, I have a hard time identifying the encryption scheme here and how the server generates its shared key to decrypt/encrypt messages to and from the client knowing that the client uses its private random key. Which to me means the server must be able to recreate this exact secret random key from what is known.

I can see the client_public_key is calculated equivalent to a DSA signing key, but I always though with my limited knowledge that this only could be used for verifying and not decryption.

I am used to the idea that client and servers generate mutual shared keys. This seems outside the realm of Diffie Hellman, and probably more into some DSA branch I do not know about. But it may very well be that its a branch of DH that I do not know about as well. Or even something similar to Clifford Cocks non-secret encryption.

Any nudge in the right direction appreciated, and a readable solution with how the keys are made even more appreciated. Hoping to solve this and learn how to use this method.


It may be assumed that the server knows both $p$ and the prime factorization of known_server_public_key, hence knows an integer $m$ such that $pm\equiv 1\pmod{\phi(\text{known_server_public_key})}$, which allows the server to compute client_private_key from client_public_key. So if client_private_key were really something to be kept private, this is bad code. Instead, it looks rather like the messgae client_public_key is RSA encrypted using the server_public_key and can thus - after transmission to the server - be used as a shared secret among the two parties. Insofar, the names client_private_key and client_public_key may be misleading.

  • $\begingroup$ Yes, the naming is all mine, and I think you are absolutely right that the client_private_key is in fact a shared secret. It couldn't possibly work unless it is. A better name would probably be shared_key or shared_secret. $\endgroup$ – patrick Jan 25 '15 at 14:30
  • $\begingroup$ It is suggested that the key is secretly shared using the Chinese remainder theorem. Which is a bit beyond me anyways. $\endgroup$ – patrick Jan 25 '15 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.