Cryptography

3 Mathematical Basics and Computation Algorithms for Cryptography

Cryptography is a discipline that requires a background in mathematics. All encryption, decryption, and signature algorithms are based on notions and theorems known in number theory, modular arithmetic, and abstract algebra. Before we start the presentation and analysis of cryptographic algorithms, we need to review basics from number theory and abstract algebra. This chapter aims to review and present, with examples and exercises, the mathematical background to address cryptography algorithms. Seminal theorems are given with the names of their authors. Proofs of theorems are not included in this chapter and can be found in many books and papers on the topics [1–6].

To make attacks against cryptosystems computationally infeasible, numbers used in cryptographic algorithms are very large (in magnitude of , etc.). Therefore, optimized (in term of execution time) computation methods are needed. In addition to mathematical basics, algorithms commonly used to do fast computations in cryptographic algorithms are addressed in this chapter. Finally, the birthday paradox is presented; it is useful for the analysis of attack complexity.

According to the mathematics and computation algorithms skills of the reader, he/she may:

• Skip this chapter and address directly cryptographic algorithms.
• Learn basics, move to cryptographic ...