# How many keys in a Hybrid Cryptosystem?

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.

$$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.

• for symmetric key exchange isn't the number of keys n(n-1)/2 which = nC2? Jan 10 '19 at 12:47
• Well, for me many. What if the clients generates symmetric key per session? Jan 10 '19 at 12:55
• 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 Jan 10 '19 at 13:39
• nC2 not nC squared. Jan 10 '19 at 13:42

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

• 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 Jan 10 '19 at 13:54
• @Grace i edited my answer, i hope it helps you to understand what i meant Jan 10 '19 at 14:02

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).