Max

I agree, I was trying to respond without getting too much in the weeds. The argument being made was that the entropy (information content) of the key itself is the problem. I was saying that isn’t true because entropy is defined differently.

But there is a lower bound for any algorithm who’s output produces something with a certain amount of information, and that’s the information->energy cost of that output. The specifics of the algorithm being irrelevant. I believe even with something like thermodynamically reversible computing you still pay the cost at the end for storing your result? (Which gets into one of the most mind blowing things I remember from stat mech about Szilard engines. Essentially that if I know the microstate of a system [or even a macrostate I believe?] I can slowly burn that information to extract energy from the system equal to the information I had)

You’re right that in the classical case with irreversible computation you can argue that there’s a thermodynamic impossibility to the brute forcing based on the Landauer limit.

I think you’re almost right about the high level principles, you’ve just forgotten that entropy scales as the log of the combinations not linearly.

So the entropy of a 128 bit key is not 2^128, it’s just 128 and therefore the fundamental limit on the cost required to recover it that you’re talking about is very small.

See landauer limit (which isn’t quite the same thing since it’s about irreversible computers which some quantum computers might not be, but gets at the idea of there being an energy cost to have information)

I believe the specifics of your thoughts about entropy of public vs private keys is also incorrect but not necessary to the core of what you’re saying.