Two's complement addition (and multiplication) are non-linear with respect to XOR and AND. This means that for bit vectors over $\mathbb{Z}_2$, the operation $a + x$ cannot be expressed as the matrix multiplication $Ax$, where $A$ is some constant matrix derived from $a$.

Because of this non-linear property, why is a LCG often regarded as having bad cryptographic properties? Would it not make a good non-linear step in a cipher?

  • 2
    $\begingroup$ An LCG does not invoke bitwise XOR or bitwise AND; only (modular) addition and multiplication by some constant; that has to do with why, in isolation, it is a bad crypto primitive (combined with XOR and rotation, modular addition is a very useful primitive; ARX ciphers are made of this). Another issue is that many proposed LCGs are not wide enough. $\endgroup$ – fgrieu Jul 11 '16 at 21:03

Your Answer

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