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?

enter image description here

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)

enter image description here

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

  • 1
    $\begingroup$ You need to provide more details to make a self contained question and provide the equation you are referring to. Don't expect others to do your work for you. $\endgroup$
    – kodlu
    Feb 11, 2016 at 7:37
  • $\begingroup$ Tried to clear the question. $\endgroup$
    – levi1696
    Feb 11, 2016 at 10:22

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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