0
$\begingroup$

Quite a simple question though I can't wrap my head around it:

The key size is: $n$

Because it's brute force it tries each possible key once from $0$ to $n$, but in my head that just makes the run time $O(n)$, though it's surely meant to be a polynomial or exponential. The decryption message is of size $x$ though I'm not sure it is relevant. Would it be because the key is of size $n$, but they must also try all keys from $0$ to $n$ make it $2^n$?

$\endgroup$
0
$\begingroup$

When we say key size is $n$, we consider $n$ in bits, n-bit key size. For example, AES has 128, 192 and 256-bit keys sizes. Therefore, we have $2^{128}$ key to search for AES-128 and that is exponential, $ \mathcal{O}(2^n)$


In cryptography, we use also a security parameter that measures the input size of the problem. The security parameter is represented as unary representation ( $\lambda-\text{times }1)$ so that the complexity of the cryptographic algorithms will be polynomial time.

For RSA like systems, when we say the security parameter is $1^\lambda$, the $\lambda$ represents the number of bits of RSA modulus $n$. So the positive integer $n$ must be between $0,\ldots,2^{\lambda-1}$.

Note: We usually don't say AES (and other block ciphers) have security parameter 128, we just say 128-bit key.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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