Mathematical Foundations of Cryptography

This presentation contains the contents pertaining to the undergraduate course on Cryptography and Network Security (UITC203) at Sri Ramakrishna Institute of Technology. This covers the basic concepts of mathematics that are essential to work with cryptography.

1. Mathematical Foundations Adri Jovin J J , M.Tech ., Ph.D. UITC203 CRYPTOGRAPHY AND NETWORK SECURITY

2. Overview Divisibility Division Algorithm Modular Arithmetic Euclidean Algorithm Extended Euclidean Algorithm Groups, Rings and Fields UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 2 Prime Numbers Relative Primality Fermat’s Theorem Euler Totient Function Euler’s Theorem Chinese Remainder Theorem

3. Divisibility If , then to say that divides , denoted by , means that for a unique , denoted by . The existence and uniqueness of implies that cannot be This can be stated as is divisible by . If does not divide , then we write and say that is not divisible by . Division by zero is undefined .   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 3

4. Division Algorithm If and , then there exist unique integers with , and . Proof: Two parts Existence Uniqueness   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 4

5. Modular Arithmetic Let and suppose that for any , denotes the congruence class of modulo .   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 5 Congruence: If , then we say that a is congruent to modulo if , denoted by . On the other hand, if , then we write and say that and are incongruent modulo , or that is not congruent to modulo . The integer is the modulus of the congruence. The set of all integers that are congruent to a given integer modulo , denoted by , is called the congruence class or residue class of modulo .   Sometimes termed “clock arithmetic”

6. Euclidean Algorithm Let , and set . By repeatedly applying the Division Algorithm, we get with for all , where is the least non-negative number such that , in which case . An equivalent definition: A simpler form: Let with . Then,   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 6 The Euclidean algorithm GCD Input: Integers with Output: The greatest common divisor of and if return else return  

7. Extended Euclidean Algorithm Let , and let for be the quotients obtained from the application of the Euclidean Algorithm to find , where is the least non-negative integer such that . If , , and , for , then .   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 7 The extended Euclidean algorithm eGCD Input: Integers with Output: with and if return else Compute integers with and /* note that */ return  

8. Groups, Rings and Fields UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 8 Image Source: Cryptography and Network Security: Principles and Practices, 6 th Ed.

9. Prime Numbers Why Prime numbers are prominently used in Cryptography? Difficulty in determining the prime factors of a large number … UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 9 The Factoring Problem is the determination of the prime factorization of a given guaranteed by The Fundamental Theorem of Arithmetic. This theorem says that the primes in the factorization of a given natural number are unique to up to order of the factors. Thus, the prime numbers are the fundamental building blocks of number theory .  

10. Relative Primality If , and , then and are said to be relatively prime or coprime. Sometimes the phrase is prime to is also used.   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 10

11. Fermat’s Theorem If is prime and is a positive integer not divisible by , then   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 11

12. Euler Totient Function The Euler’s totient function, usually represented as is defined as the number of positive integers less than and relatively prime to . By convention, . In general,   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 12

13. Euler’s Theorem For every and that are relatively prime:   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 13

14. Chinese Remainder Theorem Discovered by the Chinese mathematician Sun Tse Let ∈ for natural numbers be pairwise relatively prime, set and let for . Then the system of simultaneous linear congruences given by , has a unique solution modulo . In simpler terms, if the prime factorization of is , then the system of equations has a unique solution, , where is less than .   UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 14

15. References Schneier , B. (2007). Applied cryptography: protocols, algorithms, and source code in C. John Wiley & Sons. Rosen, K. H. (2007). An Introduction to Cryptography. ISBN-10, 1-58488. Stallings, W. (2014). Cryptography and network security, 6/E. Pearson Education India. Katz, J., & Lindell, Y. (2014). Introduction to modern cryptography. CRC press. UITC203 CRYPTOGRAPHY AND NETWORK SECURITY 15