Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Slide 87Slide 88Slide 89Slide 909.1Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 9Mathematics of CryptographyPart III: Primes and Related Congruence Equations9.2Objectives ❏ To introduce prime numbers and their applications in cryptography. ❏ To discuss some primality test algorithms and their efficiencies. ❏ To discuss factorization algorithms and their applications in cryptography. ❏ To describe the Chinese remainder theorem and its application. ❏ To introduce quadratic congruence. ❏ To introduce modular exponentiation and logarithm.Chapter 99.39-1 PRIMES9-1 PRIMESAsymmetric-key cryptography uses primes extensively. Asymmetric-key cryptography uses primes extensively. The topic of primes is a large part of any book on The topic of primes is a large part of any book on number theory. This section discusses only a few number theory. This section discusses only a few concepts and facts to pave the way for Chapter 10.concepts and facts to pave the way for Chapter 10.9.1.1 Definition9.1.2 Cardinality of Primes9.1.3 Checking for Primeness9.1.4 Euler’s Phi-Function9.1.5 Fermat’s Little Theorem9.1.6 Euler’s Theorem9.1.7 Generating PrimesTopics discussed in this section:Topics discussed in this section:9.49.1.1 DefinitionFigure 9.1 Three groups of positive integersA prime is divisible only by itself and 1.Note9.59.1.1 ContinuedWhat is the smallest prime?Example 9.1SolutionThe smallest prime is 2, which is divisible by 2 (itself) and 1. List the primes smaller than 10.Example 9.2SolutionThere are four primes less than 10: 2, 3, 5, and 7. It is interesting to note that the percentage of primes in the range 1 to 10 is 40%. The percentage decreases as the range increases.9.69.1.2 Cardinality of PrimesInfinite Number of PrimesThere is an infinite number of primes.NoteNumber of Primes9.79.1.2 ContinuedAs a trivial example, assume that the only primes are in the set {2, 3, 5, 7, 11, 13, 17}. Here P = 510510 and P + 1 = 510511. However, 510511 = 19 × 97 × 277; none of these primes were in theoriginal list. Therefore, there are three primes greater than 17.Example 9.3Find the number of primes less than 1,000,000.Example 9.4SolutionThe approximation gives the range 72,383 to 78,543. The actual number of primes is 78,498.9.8Given a number n, how can we determine if n is a prime? The answer is that we need to see if the number is divisible by all primes less than9.1.3 Checking for PrimenessWe know that this method is inefficient, but it is a good start.9.99.1.3 ContinuedIs 97 a prime?Example 9.5SolutionThe floor of 97 = 9. The primes less than 9 are 2, 3, 5, and 7. We need to see if 97 is divisible by any of these numbers. It is not, so 97 is a prime.Is 301 a prime?Example 9.6SolutionThe floor of 301 = 17. We need to check 2, 3, 5, 7, 11, 13, and 17. The numbers 2, 3, and 5 do not divide 301, but 7 does. Therefore 301 is not a prime.9.10Sieve of Eratosthenes9.1.3 Continued9.11Euler’s phi-function, (n), which is sometimes called theEuler’s totient function plays a very important role in cryptography. 9.1.4 Euler’s Phi-Function9.12We can combine the above four rules to find the value of (n). For example, if n can be factored as n = p1e1 × p2e2 × … × pkek then we combine the third and the fourth rule to find9.1.4 ContinuedThe difficulty of finding (n) depends on the difficulty of finding the factorization of n.Note9.139.1.4 ContinuedWhat is the value of (13)?Example 9.7SolutionBecause 13 is a prime, (13) = (13 −1) = 12.What is the value of (10)?Example 9.8SolutionWe can use the third rule: (10) = (2) × (5) = 1 × 4 = 4, because 2 and 5 are primes.9.149.1.4 ContinuedWhat is the value of (240)?Example 9.9SolutionWe can write 240 = 24 × 31 × 51. Then (240) = (24 −23) × (31 − 30) × (51 − 50) = 64Can we say that (49) = (7) × (7) = 6 × 6 = 36?Example 9.10SolutionNo. The third rule applies when m and n are relatively prime. Here 49 = 72. We need to use the fourth rule: (49) = 72 − 71 = 42.9.159.1.4 ContinuedWhat is the number of elements in Z14*?Example 9.11SolutionThe answer is (14) = (7) × (2) = 6 × 1 = 6. The members are 1, 3, 5, 9, 11, and 13.Interesting point: If n > 2, the value of (n) is even.Note9.169.1.5 Fermat’s Little TheoremFirst Versionap ≡ a mod pap − 1 ≡ 1 mod pSecond Version9.179.1.5 ContinuedFind the result of 610 mod 11.Example 9.12SolutionWe have 610 mod 11 = 1. This is the first version of Fermat’s little theorem where p = 11.Find the result of 312 mod 11.Example 9.13SolutionHere the exponent (12) and the modulus (11) are not the same. With substitution this can be solved using Fermat’s little theorem.9.18Multiplicative Inverses 9.1.5 Continueda−1 mod p = a p − 2 mod pThe answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean algorithm:Example 9.149.199.1.6 Euler’s TheoremFirst Versiona(n) ≡ 1 (mod n)Second Versiona k × (n) + 1 ≡ a (mod n)The second version of Euler’s theorem is used in the RSA cryptosystem in Chapter 10.Note9.209.1.5 ContinuedFind the result of 624 mod 35.Example 9.15SolutionWe have 624 mod 35 = 6(35) mod 35 = 1.Find the result of 2062 mod 77.Example 9.16SolutionIf we let k = 1 on the second version, we have 2062 mod 77 = (20 mod 77) (20(77) + 1 mod 77) mod 77 = (20)(20) mod 77 = 15.9.21Multiplicative Inverses Euler’s theorem can be used to find multiplicative inverses modulo a composite. 9.1.6 Continueda−1 mod n = a(n)−1 mod


View Full Document

UND CSCI 389 - Mathematics of Cryptography

Download Mathematics of Cryptography
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Mathematics of Cryptography and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Mathematics of Cryptography 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?