1
$\begingroup$

If symmetric cryptosystems have $C^2_n$ keys, and asymmetric systems have $2n$ keys, how many does a hybrid system have? This was in an online quiz from school

Company A is considering to adopt a cryptosystem for secure communications among its employees. Currently it has $5$ employees. Assume that every employee has used the adopted cryptosystem to communicate with all other employees once.

3) c. If the company adopts hybrid cryptosystem, how many keys would be used in this case? Show your working.

My answer was

$C_n^2$ symmetric session key + $2n$ asymmetric keys

$= C_5^2 + 2 \times 5$

$= 20$ keys

This was marked wrong. Where did i go wrong here? As far as i understand, in a hybrid system they make use of asymmetric keys to encrypt the symmetric session key, which is used to encrypt/decrypt the document.

$\endgroup$
  • $\begingroup$ for symmetric key exchange isn't the number of keys n(n-1)/2 which = nC2? $\endgroup$ – Grace Jan 10 at 12:47
  • $\begingroup$ Well, for me many. What if the clients generates symmetric key per session? $\endgroup$ – kelalaka Jan 10 at 12:55
  • $\begingroup$ If you write "nC2" do you mean $2 \times C \times n$ or $n \times C^2$ ? It would help a lot if you would edit your question by using Mathjax: How to use Mathjax $\endgroup$ – AleksanderRas Jan 10 at 13:39
  • $\begingroup$ nC2 not nC squared. $\endgroup$ – Grace Jan 10 at 13:42
1
$\begingroup$

So first, for each employee there is a public-private-key pair, which is $2n$.

For each session one symmetric key is created. Your solution assumes the communication partners initially agree on a symmetric key they both use in the communication with each other.

Considering a session as a communication in just one direction, instead of $n*(n-1)/2$ symmetric keys, there would be $n*(n-1)$ symmetric keys, making a total of $2n + n*(n-1) = 30$ keys

Edit for clarification:

The initial question states "each employee communicated with all other employees once"

This could mean two things:

$A$ sends a message encrypted with $symkey_1$ to $B$
$B$ responds with a message also encrypted with $symkey_1$
So $A$ communicated once with $B$ and $B$ communicated once with $A$

Another interpretation:

$A$ sends a message encrypted with $symkey_1$ to $B$
Two days later, $B$ sends a message to $A$ encrypted with $symkey_2$
So $A$ communicated once with $B$ and $B$ communicated once with $A$

The second interpretation will create $n*(n-1)$ symmetric keys, while the first one created only $n*(n-1)/2$ symmetric keys

$\endgroup$
  • $\begingroup$ Can you simplify your explanation for the session communication going in "one direction" and how it differs from normal symmetric keys? Sorry english is not my first language $\endgroup$ – Grace Jan 10 at 13:54
  • $\begingroup$ @Grace i edited my answer, i hope it helps you to understand what i meant $\endgroup$ – Ceriath Jan 10 at 14:02
1
$\begingroup$

In a typical hybrid system (PGP, S-MIME etc.), a message contains both an encrypted key $k_s$ for the symmetrical system, encrypted by the recipient’s public key. A new $k_s$ is generated per message. So if we have $5 \times 4=20$ messages being sent (the question is somewhat ambiguous in the meaning of “communicated with each other”, but I assume this means that every employee $A$ sent a message to every other employee $B$, $B \neq A$) and so we have $20$ symmetric “one-time” keys and of course the usual $5$ public keys and $5$ private keys (again ambiguity: does a public/private pair consist of two keys, as I just assumed, or is it just one: in most cases the private key leads to a public key in a unique way, so it’s also defensible that also an asymmetric system has just one key per user (his/her private key)). So in that count $30$ keys are used.

One can also assume that each pair of users maintains a symmetric “session key” for the pair of users, like we could do in TLS using user-certificates and in that case we only need 10 session keys ($\binom{5}{2}$) and $10$ (or $5$, see above) assymetric ones. This ignores the “just one” communication part of the question, though, and also does not improve on the $10$ shared symmetric keys we’d need in a fully symmetric version (but with the extra burden of off-line key distribution).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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