Section 1 Introduction
These lecture notes are based on class material offered at University of Debrecen, Hungary. The aim of the lecture note is to help the students to understand and to learn the course material. It provides detailed computations to see all the mathematical objects appearing. The Cryptography class has certain prerequirements that is assumed, Linear Algebra I-II, Algebra, Number Theory. In the computations the computer algebra software package SageMath is used, here also some basic knowledge is assumed. The nice tutorial provided by Michael O’Sullivan is a suggested source to start with: https://mosullivan.sdsu.edu/Teaching/sdsu-sage-tutorial/index.html. Especially the two sections Programming in SageMath and Mathematical Structures may be useful to be able to follow the implementations given in this lecture notes.
In Chapter 2 we deal with some simple classical cryptosystems like Caesar’s cipher and its generalized versions, Hill ciphers based on matrices and Vigenère ciphers.
In Chapter 3 the well-known RSA cryptosystem is introduced, a nice number theory based system. Since factorization provides an obvious attack against RSA we present a few algorithms in this direction.
In Chapter 4 other two factorization based cryptosystems are described, the Rabin cryptosystem and Paillier’s cryptosystem.
In Chapter 5 we deal with the applications of the discrete logarithm problem in cryptography. The Diffie-Hellman key exchange and ElGamal cryptosystem are studied here.
In Chapter 6 we consider some well-known techniques to handle the discrete logarithm problem such as the Baby-Step Giant-Step algorithm, Pollard’s \(\rho\) algorithm and index calculus in case of additive and multiplicative groups as well.
In Chapter 7 we show that difficult mathematical problems may yield cryptosystems that are not secure. As an example we study certain matrix groups and the discrete logarithm problem related to some special subgroups generated by two matrices. It turns out that there exists efficient algorithm to solve the discrete logarithm problem in these cases.
In Chapter 8 a newer cryptosystem is introduced, the NTRU that works on some special truncated polynomial rings. There are now many variants of the original system. Here we also consider the ITRU system and we show that it can be efficiently attacked by frequency analysis technique.
In Chapter 9 an interesting application in cryptography is discussed, namely secret sharing. We present the so-called Shamir’s secret sharing.
In Chapter 10 we consider a knapsack problem based cryptosystem the so-called Merkle-Hellman system. It uses certain superincreasing sequences to make decryption easy, however as we will see there is an efficient attack based on the famous LLL-algorithm.
In Chapter 11 we provide solutions of the exercises appearing in the lecture note, these are based on the software package SageMath.
Additional sources suggested to use related to the course:
-
CrypTool : https://www.cryptool.org/en/, very nice educational software in the area of cryptography and cryptoanalysis.
Figure 1.1. image -
Mysteri Twister C3 : https://www.mysterytwisterc3.org/en/, this is a cipher contest, here one can find all kind of crypto challenges. As an example we may try to solve one of the RSA Factoring Challenges, like RSA-210:
\begin{equation*} \begin{aligned} N=&& 2452466449002782119765176635730880184670267876783327\\ && 5974341445171506160083003858721695220839933207154910362\\ && 6827191679864079776723243005600592035631246561218465817\\ && 904100131859299619933817012149335034875870551067.\end{aligned} \end{equation*}