If a system provide n bits of security, it is known that the best possible attack against the system would be 2^n (security parameter). However, why are the key sizes of some cryptosystems much larger than their security parameters? Is it because these cryptosystems have a weak and vulnerable algorithm?
2
-
2$\begingroup$ Welcome to Cryptography Could you list some of them by editting into your question? $\endgroup$– kelalakaNov 8 at 22:09
-
$\begingroup$ Consider participating? You earn 2 reputation points for accepting answers from others in case you haven't visited help center. $\endgroup$– DannyNiuNov 9 at 12:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
This can be either a philosophical question or a empirical question, but answer to both these sides can be similar.
First, the title is correct, higher key sizes corresponds to a higher security level. But that's within the same cryptosystem.
Second, public-key cryptosystems are based on mathematical problems, whose solutions admit more efficient cryptanalytic algorithms than brutal-forcing their symmetric-key counterparts:
- RSA has GNFS,
- Lattice-based ones have BKZ,
- Hash-based signatures trades total number of messages that can be signed with signature size.
Elliptic-Curve Discrete Logarithm comes the closest to comparable with symmetric-key crypto, with Pollard's rho giving half the security level against the order of the base point of the elliptic curve group.
Third, even symmetric-key algorithms have hidden costs that people often assume only public-key algorithms have.
For example, the size of the key schedule of a block cipher, the number of rounds of a permutation, the total number of pre-computed constants, etc.
-
$\begingroup$ nice answer. of course the assumption is that the cryptosystem is correctly implemented and the keys are randomly generated from a uniform distribution or some very close approximation to this $\endgroup$– kodluNov 9 at 1:29