Extracting key bits from linear cryptanalysis equation for SDES

Question

From the linear cryptanalysis of SDES, we get a linear equation consisting the K[1, 3] of the round key 1 and 2. From this how will I retrieve the key bit?

How do we solve the linear equation we get from the linear cryptanalysis to predict the key bits?

The 1 and 3 bits of the round key 1 and 2 are present in the final relation. Form this we apply the algorithm 1, as stated in the paper by Matsui on linear cryptanalysis(The second image)

But from this how do we predict the bits of the actual/original key?

Answer 1

The attack, as stated in sections 6.2 & 6.3, actually can only recover the quantity $K_1[1,3]\oplus K_2[1,3]$.

What you would hope to do is, to use a similar approach via another high probability linear relation [usually there is more than one] and recover more relations between subkey bits. Eventually, the goal is recovering all the original key bits. Assuming enough relations between pairs of key bits are recovered, then you can use take one variable in each relation as an unknown, and use more plaintext/ciphertext pairs, by brute forcing over those values, and select the values that give the highest bias. This is quite tiresome for DES.

I suggest reading Howard Heys' tutorial on linear and differential cryptanalysis [google it], which now appears as part of Stinson's Crypto book (3rd ed.) as well, where a more clear examples of targeting subkey bits is given, for both linear and differential cryptanalysis.