I am sharing 'ICS_Unit -2_Mathematical foundation and Public key cryptography (1)' with you.pptx

Summarizes cybersecurity concepts regarding public key cryptography along with appropriate mathematical background

1. SY BTech Semester-IV (AY 2024-25) Computer Science and Engineering Disclaimer: Information included in these slides came from multiple sources. We have tried our best to cite the sources. Please refer to the references to learn about the sources, when applicable. The slides should be used only for preparing notes, academic purposes (e.g. in teaching a class), and should not be used for commercial purposes.

2. Information Security: Unit - II Unit-II ‹#› Information Security [Mathematical Foundation and Public Key Cryptography] Cryptography and Network Security, William Stallings, Pearson Education 5th Edition, ISBN 13: 978-0-13-609704-4

3. Syllabus

4. Modular Arithmetic Modular arithmetic is a kind of integer arithmetic that reduces all numbers to one of a fixed set for some number . Any integer outside this range is reduced to one in this range by taking the remainder after division by n .

5. Modular Arithmetic define modulo operator “ a mod n” to be remainder when a is divided by n where integer n is called the modulus b is called a residue of a mod n since with integers can always write: a = qn + b usually chose smallest positive remainder as residue ie. 0 <= b <= n-1 process is known as modulo reduction eg. -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7 a & b are congruent if: a mod n = b mod n when divided by n, a & b have same remainder eg. 100 mod 11 = 34 mod 11

6. Modular Arithmetic Operations can perform arithmetic with residues uses a finite number of values, and loops back from either end Z n = {0, 1, . . . , ( n – 1)} modular arithmetic is when do addition & multiplication and modulo reduce answer can do reduction at any point, ie a+b mod n = [a mod n + b mod n] mod n

7. Modular Arithmetic Operations [(a mod n) + (b mod n)] mod n = (a + b) mod n [(a mod n) – (b mod n)] mod n = (a – b) mod n [(a mod n) x (b mod n)] mod n = (a x b) mod n e.g. [(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 (11 + 15) mod 8 = 26 mod 8 = 2 [(11 mod 8) – (15 mod 8)] mod 8 = –4 mod 8 = 4 (11 – 15) mod 8 = –4 mod 8 = 4 [(11 mod 8) x (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 x 15) mod 8 = 165 mod 8 = 5

8. Modular Arithmetic Properties

9. Euclidean Algorithm an efficient way to find the GCD(a,b) uses theorem that: GCD(a,b) = GCD(b, a mod b) Euclidean Algorithm to compute GCD(a,b) is: Euclid(a,b) if (b=0) then return a; else return Euclid(b, a mod b);

10. Number Theory 07-Dec-20 Information Security: Unit - II ‹#› Prime Numbers Relative Prime Numbers Two numbers are called relatively prime if the greatest common divisor (GCD) of those numbers is 1 . 8 and 15 are relatively prime number. The factors of 8 are 1, 2, 4, 8 and the factors of 15 are 1, 3, 5, 15. Examples of relatively prime numbers are: (10, 21), (14, 15), (45, 91), .... for more info https://edurev.in/studytube/Prime-Numbers-PPT-PowerPoint-Presentation---Mathem/719baed3-6ca0-42f7-a262-6a882cb16cb6_p

11. Information Security: Unit - I ‹#› Find the value of 5^117 mod 19.

12. Information Security: Unit - I ‹#› 5^1 mod 19 = 5 5^2 mod 19 = ( 5^1 * 5^1 ) mod 19 = ( 5^1 mod 19 * 5^1 mod 19 ) mod 19 5^2 mod 19 = ( 5 * 5 ) mod 19 = 25 mod 19 5^2 mod 19 = 6 5^4 mod 19 = ( 5^2 * 5^2 ) mod 19 = ( 5^2 mod 19 * 5^2 mod 19 ) mod 19 5^4 mod 19 = ( 6 * 6 ) mod 19 = 36 mod 19 5^4 mod 19 = 17 5^8 mod 19 = ( 5^4 * 5^4 ) mod 19 = ( 5^4 mod 19 * 5^4 mod 19 ) mod 19 5^8 mod 19 = ( 17 * 17 ) mod 19 = 289 mod 19 5^8 mod 19 = 4 5^16 mod 19 = ( 5^8 * 5^8 ) mod 19 = ( 5^8 mod 19 * 5^8 mod 19 ) mod 19 5^16 mod 19 = ( 4 * 4 ) mod 19 = 16 mod 19 5^16 mod 19 = 16

13. Information Security: Unit - I ‹#› 5^32 mod 19 = ( 5^16 * 5^16 ) mod 19 = ( 5^16 mod 19 * 5^16 mod 19 ) mod 19 5^32 mod 19 = ( 16 * 16 ) mod 19 = 256 mod 19 5^32 mod 19 = 9 5^64 mod 19 = ( 5^32 * 5^32 ) mod 19 = ( 5^32 mod 19 * 5^32 mod 19 ) mod 19 5^64 mod 19 = ( 9 * 9 ) mod 19 = 81 mod 19 5^64 mod 19 = 5 5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64 ) mod 19 5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19 ) mod 19 5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19 5^117 mod 19 = 61200 mod 19 = 1

14. Extended Euclidean Algorithm calculates not only GCD but x & y: ax + by = d = gcd(a, b) useful for later crypto computations follow sequence of divisions for GCD but assume at each step i, can find x &y: r = ax + by at end find GCD value and also x & y if GCD(a,b)=1 these values are inverses

15. Euler Totient Function ø(n) when doing arithmetic modulo n complete set of residues is: 0..n-1 reduced set of residues is those numbers (residues) which are relatively prime to n eg for n=10, complete set of residues is {1,2,3,4,5,6,7,8,9} reduced set of residues is {1,3,7,9} number of elements in reduced set of residues is called the Euler Totient Function ø(n)

16. Euler Totient Function ø(n) to compute ø(n) need to count number of residues to be excluded in general need prime factorization, but for p (p prime) ø(p)=p-1 for p.q (p,q prime) ø(p.q)=(p-1)x(q-1) eg. ø(37) = 36 ø(21) = (3–1)x(7–1) = 2x6 = 12

17. Fermat's Theorem where p is prime and gcd(a,p)=1 also known as Fermat’s Little Theorem also have: a p = a (mod p) useful in public key and primality testing Suppose a = 7 and p = 19 then prove Fermat’s Little theorem Ex. 2 16 mod 17 2 50 mod 17

18. Chinese Remainder Theorem used to speed up modulo computations if working modulo a product of numbers eg. mod M = m 1 m 2 ..m k Chinese Remainder theorem lets us work in each moduli m i separately since computational cost is proportional to size, this is faster than working in the full modulus M

19. Chinese Remainder Theorem can implement CRT in several ways to compute A(mod M) first compute all a i = A mod m i separately determine constants c i below, where M i = M/m i then combine results to get answer using:

20. Chinese Remainder Theorem-Example 5 March 2025 School of Computer Engineering & Technology ‹#›

21. 5 March 2025 School of Computer Engineering & Technology ‹#›

22. 5 March 2025 School of Computer Engineering & Technology ‹#›

23. 5 March 2025 School of Computer Engineering & Technology ‹#›

24. 5 March 2025 School of Computer Engineering & Technology ‹#›

25. Discrete Logarithms the inverse problem to exponentiation is to find the discrete logarithm of a number modulo p This exponent i is referred to as the discrete logarithm of the number b for the base a(mod p). that is to find i such that b ≡ a i (mod p) where, 0≤i≤(p-1) This exponent i is referred to as the discrete logarithm of the number b for the base a(mod p). this is written as i = dlog a b (mod p) Consider, b=9,a=2 and p=11

26. Public-Key Applications can classify uses into 3 categories: encryption/decryption (provide secrecy) digital signatures (provide authentication) key exchange (of session keys) some algorithms are suitable for all uses, others are specific to one ‹#›

27. RSA En/decryption ‹#› by R on Rivest, Adi S hamir and Leonard A dleman of MIT in 1977 best known & widely used public-key scheme based on exponentiation in a finite (Galois) field over integers modulo a prime uses large integers (eg. 1024 bits)

28. each user generates a public/private key pair by: selecting two large primes at random: p, q computing their system modulus n = (p * q) Compute: ø(n) = (p -1)(q -1) ‹#› where 1< e < ø(n), gcd(e,ø(n)) = 1 selecting at random the encryption key (public) e, solve following equation to find decryption key d d * e = 1 mod ø(n) and 0 ≤ d ≤ n publish their public encryption key: PU = {e, n} keep secret private decryption key: PR = {d, n} RSA Key Setup

29. to encrypt a message M the sender: obtains public key of recipient PU = {e, n} computes Ciphertext : C = M e mod n , where 0 ≤ M < n to decrypt the ciphertext C the owner: uses their private key PR = {d, n} computes: M = C d mod n note that the message M must be smaller than the modulus n (block if needed) ‹#›

30. ‹#› d * e mod ø( n ) =1 d = (1 + k * ø( n ))/e, k<e

31. RSA Example 1 - Key Setup ‹#› Select primes: p = 3 & q = 11 Calculate n = pq = 3 x 11 = 33 Calculate ø( n ) = ( p - 1)( q - 1) = 2 x 10 = 20 Select e: 1 < e < ø( n ) gcd(ø( n ),e) = 1; choose e = 3 Determine d: Value is d = 7 Publish public key PU = {3,33} Keep secret private key PR = {7, 33 } M=15

32. Advantages of RSA Can be used for both encryption as well as for digital signature. Trapdoor in RSA is in knowing value of n but not knowing the primes of that are factors of n Disadvantages of RSA If any one value of p, q, Φ(n) and e is known then the other values can be calculated. ‹#›

33. Symmetric Encryption Asymmetric Encryption Symmetric encryption is fast in execution Asymmetric Encryption is slow in execution due to the high computational burden Symmetric encryption uses a single key for both encryption and decryption Asymmetric encryption uses a different key for encryption and decryption Size of resulting encrypted text usually same or less than original Size of resulting encrypted text more than original Problem of Key Exchange No Problem of Key Exchange Easier to implement Practically more difficult Exemple: DES, 3DES, AES, and RC4 Exemple: Diffie-Hellman, RSA. ‹#›

34. Hash Functions condenses arbitrary message to fixed size h = H(M) usually assume hash function is public hash used to detect changes to message want a cryptographic hash function computationally infeasible to find data mapping to specific hash (one-way property) computationally infeasible to find two data to same hash (collision-free property)

35. hash function A hash function H accepts a variable-length block of data as input and produces a fixed-size hash value h = H(M) The kind of hash function needed for security applications is referred to as a cryptographic hash function. APPLICATIONS OF CRYPTOGRAPHIC HASH FUNCTIONS Message Authentication Digital Signatures

36. APPLICATIONS OF CRYPTOGRAPHIC HASH FUNCTIONS Message Authentication Message authentication is a mechanism or service used to verify the integrity of a message. i.e. Integrity Checking: Virus and Malware Scanning Message authentication assures that data received are exactly as sent (i.e., contain no modification, insertion, deletion, or replay). In many cases, there is a requirement that the authentication mechanism assures that maintained identity of the sender is valid. When a hash function is used to provide message authentication, the hash function value is often referred to as a message digest.

37. Cryptographic Hash Function

38. Message Digest 5 March 2025 School of Computer Engineering & Technology ‹#›

39. Example 7391743 Operation Result Multiply 7 by 3 21 Discard first digit 1 Multiply 1 by 9 9 . . Message Digest= 5 March 2025 School of Computer Engineering & Technology ‹#›

40. 5 March 2025 School of Computer Engineering & Technology ‹#›

41. APPLICATIONS OF CRYPTOGRAPHIC HASH FUNCTIONS Simplified Examples of the Use of a Hash Function for Message Authentication

42. Secure Hash Algorithm (SHA) Input :- It works with any input message that is less than bits in length. Output:- is MD of 160 bits in length. 5 March 2025 School of Computer Engineering & Technology ‹#›

43. Working of SHA Step 1: Padding Step 2: Append length Step 3: Divide the input into 512-bit blocks Step 4: Initialize chaining variables Step 5: Process Blocks Has 4 sub steps. 5 March 2025 School of Computer Engineering & Technology ‹#›

44. Step 1: Padding Add padding to the end of original message. Because, To make the length of the original message equal to a value which is 64 bits less than an exact multiple of 512. 5 March 2025 School of Computer Engineering & Technology ‹#›

45. Step 1: Padding 5 March 2025 School of Computer Engineering & Technology ‹#›

46. Step 2: Append the length Now the length of the message is a multiple of 512 bits 5 March 2025 School of Computer Engineering & Technology ‹#›

47. Step 3: Divide the input into 512-bit blocks School of Computer Engineering & Technology ‹#›

48. Step 4: Initialize chaining variables 5 March 2025 School of Computer Engineering & Technology ‹#›

49. Step 5: Process Blocks 5 March 2025 School of Computer Engineering & Technology ‹#›

50. 5 March 2025 School of Computer Engineering & Technology ‹#›

51. 5 March 2025 School of Computer Engineering & Technology ‹#› / Stage

52. Single iteration on SHA School of Computer Engineering & Technology ‹#›

53. comparison SHA-1 MD5 Developed by NIST Developed by Ron Rivest Input message size is < 2 64 Input message is of arbitrary length Output – 160 bit Message Digest Output – 128 bit Message Digest 80 operations(steps) [4 rounds of 20 steps] 64 operations(steps) [4 rounds of 16 operations] Collision resistant Not collision resistant Stronger than MD5 Weaker than SHA1 Slower than MD5 Faster than SHA1