Cryptology I.9 Linear Encryption

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. Matrices over Rings [PDF].
2. Elimination over the Integers [PDF].
3. The Linear Cipher [PDF].
4. The Number of Invertible Matrices over a Residue Class Ring [PDF].
5. Cryptanalysis of the Linear Cipher [PDF].

The complete section is available as one PDF file.

• Appendix: Euclidean Algorithm, Chinese Remainder Theorem, and Residue Class Rings.

Introduction

In 1929 the mathematician Lester HILL proposed the use of matrices for encryption in an article published in the American Mathematical Monthly. This cryptographic application of linear algebra piqued the curiosity of mathematicians. But its obvious weaknesses soon became evident, so it never found a serious application. The true importance of the method relied on the fact that it was the first systematic use of algebraic methods in cryptology. And by the way it made clear how dangerous linearity in encryption functions is.

Jack LEVINE later mentioned that he used this kind of cipher already in 1924 for a contribution to a youth magazine when he was a high-school student.

This kind of ciphers uses linear algebra (or matrix calculus) over the ring of integers Z and over its finite residue class rings Z/nZ. Some of the mathematical foundations are in the Appendix.

Conclusion

Linearity makes a cipher extremely vulnerable for a known plaintext attack. The reason is that systems of linear equations are easily solved, also over rings that allow practical calculations.

In constructing secure ciphers on wants to prevent known plaintext attacks. Therefore one has to bring in nonlinearity: Solving algebraic equation of higher degree is much more complex. Hence the memento: