Mathematical Cryptology

These lecture notes were translated from the Finnish lecture notes for the TUT course ‘Matemaattinen kryptologia’. The laborious bulk translation was taken care of by the students Jussi Kangas (visiting from the University of Tampere) and Paul Coughlan (visiting from the University of Dublin, Trinity College).

The notes form the base text for the course ‘MAT-52606 Mathematical Cryptology’. They contain the central mathematical background needed for understanding modern data encryption methods, and introduce applications in cryptography and various protocols.

Though the union of mathematics and cryptology is old, it really came to the fore in connection with the powerful encrypting methods used during the Second World War and their subsequent breaking. Being generally interesting, the story is told in several (partly) fictive books meant for the general audience.

The area got a whole new speed in the 1970’s when the completely open, fast and strong computerized cryptosystem DES went live, and the revolutionary public-key paradigm was introduced. After this, development of cryptology and also the mathematics needed by it ‘mostly certain fields of number theory and algebra-has been remarkably fast. It is no exaggeration to say that the recent popularity of number theory and algebra is expressly because of cryptology. The theory of computational complexity, which belongs to the field of theoretical computer science, is often mentioned in this context, but in all fairness it must be said that it really has no such big importance in cryptology. Indeed, suitable mathematical problems for use in cryptography are those that have been studied by top mathematicians for so long that only results that are extremely hard to prove still remain open. Breaking the encryption then requires some huge theoretical breakthrough. Such problems can be found in abundance especially in number theory and discrete algebra.

Results of number theory and algebra, and the related algorithms, are presented in their own chapters, suitably divided into parts. Classifying problems of number theory and algebra into computationally ‘easy’ and ‘hard’ is essential here. The former are needed in encrypting and decrypting and also in setting up cryptosystems, the latter guarantee strength of encryption. The fledgling quantum cryptography is briefly introduced together with its backgrounds.