# Is a cryptographic key of size $N$ equivalent to $N$ bits of entropy?

Are there any caveats to the claim that a cryptographic key of size $N$ bits and $N$ bits of entropy are equivalent?

• It is not the same, to,compare key length formdifferent encryption schemes you have to,compare,the complexity equivalent (and then it is still only a rough estimate).:For Prime based scenarios the keys must be much bigger, not only to.compensate for fast attacks but also because the key space is less dense than a purely random symmetric key or a large ECC subgroup. – eckes Apr 10 '18 at 16:24

Yes, there are caveats.

The key 982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224 is 256 bits long but has zero bits of entropy to anyone who knows you are using it.

Suppose you designed a cryptosystem where every legitimate user's secret AES-256 key started with a 192-bit prefix known to you, the designer, which which you chose uniformly at random. To an adversary who doesn't have access to the system, the keys have 256 bits of entropy. But to you, each key has at most 64 bits of entropy. The United States government imposed this kind of requirement on Lotus in the international editions of its proprietary Lotus Notes software system in the 1980s, albeit with much smaller key sizes, back in the days when men were men and they all agreed that encryption was a munition used outside the United States only by terrorists and that 56 bits oughta be enough for anyone who's not a terrorist.

The number of bits in an RSA modulus may be 2048 (not counting the exponent bits, the private key, and any ASN.1 formatting or what-have-you to store it in a practical system), but it may reasonably be generated from a 256-bit seed.

Entropy is a property of a process or state of knowledge when the process or unknown may have many possible outcomes. For a cryptosystem to be useful, from the adversary's perspective, in the adversary's state of knowledge, the legitimate user's key has to have a distribution of possible values with a nonnegligible min-entropy, which is formally defined as $-\max_k \log p(k)$ where $k$ ranges over all possible keys and $p(k)$ is the probability of the key $k$. If the min-entropy is too small, then the adversary has a good chance of guessing the key on the first try.

But the length of the key is necessarily related to its entropy only in that the length in bits cannot be smaller than the entropy in bits, because you need to have at least $2^n$ possibilities in order to have an entropy of $n$ bits.

• crypto.SE really needs to sort this entropy definition thing out once and for all. It's causing a mass of confusion and leading to dodgy and inconsistent answers. For instance, your paras. 2 and 4 clearly contradict each other. We had the same with the recent $\pi$ thing. If your 9828... key has zero entropy, you'll be able to store it in 0 bytes and transmit it with 0 effort, energy or time. All the related answers showing up suffer from the same issues. – Paul Uszak Apr 10 '18 at 16:48
• @PaulUszak: a large part of the problem is that "entropy" is somewhat of a humpty-dumpty word; it tends to mean different things depending on what the speaker intends. Squeamish uses one definition (where it depends on the process that generated it; I would use that same definition); others appear to use a definition based on statistical tests (when they're talking about tools that claim to measure entropy), that is, how random it looks. Statements depending on one definition make no sense when applied to meanings of the other definition. – poncho Apr 10 '18 at 17:24
• @PaulUszak There is no contradiction. In the distribution $p$ on 256-bit strings with $p(\text{982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224})=1$ and $p(x)=0$ for any other $x$, the min-entropy of $p$ is 0, where we take $\log0=-\infty$ to be less than all finite real numbers. If the receiver already knows that the message I'm sending is 982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224, then I don't need to send the message. If the receiver has to be prepared for other options, then that's not the distribution of the receiver's state of knowledge. – Squeamish Ossifrage Apr 10 '18 at 17:32
• @poncho There's only two precise definitions here, depending on whether you mean Shannon entropy or min-entropy, nothing humpty-dumptish about it unless you deliberately ignore the standard definitions and run off into the weeds of unintelligible nonsense. They are both defined in terms of probability distributions. What the entropy estimation tools spit out is an average or minimum of values of this quantity for each of various particular (families of) probability distributions, with family parameters inferred from a sample, always using the same definition of entropy. – Squeamish Ossifrage Apr 10 '18 at 17:36