# 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

As in @Guut Boy's answer it may be possible to brute force the remainder of the key bits.

Another technique would be to find another multi round linear characteristic which can be used to brute force another subset of key bits. Of course your success probability in doing this would depend on the overall probability of the new linear characteristic, but if the key bits determined by the new characteristic overlap some of the key bits already guessed, this may speed up your attack.

It may be possible to brute force the remainder of the key bits (i.e., guess at all possible values).

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$.