# Linear cryptanalysis complete key guessing

In linear crypt analysis, partial sub keys are guessed and verified for its correctness with the help of plaintext and ciphertext.

From the partial sub key, how it is possible to guess the complete key?

For example, if we are guessing and verifying the key bits $K_5,K_6,\ldots,K_8,K_{13},\ldots,K_{16}$ for its correctness. But how can we get the complete key? That is $K_0, \ldots, K_{16}$.

• You guess the other bits as well, after determining the subkeys. – Henno Brandsma Feb 9 '16 at 7:52

Say you have an $n$ bit key. An attacker then has $2^n$ possible keys to try in a simple brute force attack. However, say he can use differential cryptanalysis to guess and verify $k$ bits of the key. Then he only has $2^{n-k}$ keys to brute force. Or in other words he simplified the brute force attack by a factor of $2^k$.