Cryptography Lecture 3 - Part-2 hgh.pptx

cryptography

1. SIT281 Cryptography

2. Objectives In this lecture, we cover sections 3.6 and 3.7. The topics we study are: Theorem of Euler Primitive roots In the next lecture we will examine Section 3.9 on Finding square roots modulo n.

3. Euler’s Theorem Euler gave an analogue to Fermat’s Little Theorem for general n. Fermat’s congruence must be true for primes, but can be false for non-primes. Euler gives a congruence which must be true for all numbers n , both prime and composite. The result hinges on using only those numbers relatively prime to n .

4. The Euler φ -function Pronunciation of φ ( psaai or saai ) Working multiplication modulo n , we are interested in only those values between 1 and n – 1 which have a greatest common divisor of 1 with n . Note that if we include 0, gcd (0, n ) = n . Example 4.4. If n = 12, the set {1, 5, 7, 11} contains all numbers between 1 and 11 which are relatively prime to n . Notation. The size of this set is denoted φ (12) and φ is known as the Euler (phi) function ( Sagemath uses euler_phi ( n );). Note that if n is prime, φ ( n )= n – 1. If n is not prime, φ ( n ) < n – 1. HOMEWORK : Check this out with some numbers!

5. The Euler φ -function cont’d Some useful formulas for φ can be obtained by counting. These include: φ ( pq ) = ( p -1)( q -1) where p and q are distinct primes. where p is a prime and r a positive integer. for any positive integer n . Examples: φ (21) = φ (3*7) = 2*6 = 12; φ (105) = ???

6. Back to Euler’s Theorem THEOREM. If gcd ( a , n ) = 1, then a φ ( n ) ≡ 1 (mod n). We will not prove this , but the proof is identical to that of Fermat’s theorem except that we choose S to be the set of elements relatively prime to n . NOTE: The ‘relative primeness ’ is only needed in the proof at the point where we need to multiply by inverses. Example. Let n = 32 and a = 13. Then By Euler, 13 16 ≡ 1 (mod 32). HOMEWORK: Verify both parts of this.

7. Applications of Euler’s Theorem Example 4.7. Find the last three digits of 7 803 . To obtain the last three digits of any number, we can evaluate it modulo 1,000 (for the last four digits, modulo 10,000 and so on and so forth ). Since gcd (7,1000) = 1, we know by Euler’s Theorem that 7 φ ( 1000 ) ≡ 1 (mod 1000). This will cut our work down. Let’s compute So 7 400 ≡ 1 (mod 1000). It follows that Therefore, the last 3 digits of 7 803 are 343.

8. More applications Example. Compute 2 43210 (mod 101). We use Fermat’s theorem since 101 is a prime (verify!). By Fermat, 2 100 ≡ 1 (mod 101). So (2 100 ) 432 = 2 43200 ≡ 1 (mod 101). Thus 2 43210 ≡ 2 10 ≡ 14 (mod 101). Example. Compute 11 402 (mod 100). Since 100 is composite, we use Euler. Note that gcd (11, 100) = 1. We need φ ( 100 ) which is 40 . CHECK! So (11 40 ) 10 = 11 400 ≡ 1 (mod 100), and 11 402 = 11 2 ≡ 21 (mod 100).

9. Working in the exponent In each of the examples, we are working with φ ( n ) in the exponent. This is a critical observation that we will use many times. It is the basis of the RSA system for instance . BASIC PRINCIPLE If x ≡ y (mod φ ( n )) , then a x ≡ a y (mod n ) where a , x , y and n ≥ 1 are integers with gcd ( a , n ) =1. PROOF . Suppose x ≡ y (mod φ ( n )); then we can write For some integer k . Then by Euler:

10. Powers of values modulo a number In this part of the lecture, we continue to examine powers of numbers in congruences . We first look at a special property of some numbers which will be useful to us from time to time in the unit. Then we look at how to find square roots in congruence equations based on the above special property.

11. Primitive Roots In congruences, the numbers do not all operate in the same way in certain respects. Let’s look at how they might vary. Example 4.10. Choose p = 7. The powers of 2 are The powers of 3 are For powers of 2, we just get 1, 2, 4 repeatedly. For powers of 3, we get all values mod 7.

12. Primitive Roots We call 3 a primitive root (or multiplicative generator ) modulo 7. Definition. For p a prime, any number a between 2 and p – 1 whose powers generate all values 1 to p – 1 is called a one primitive root of p . We state some facts about primitive roots without giving proofs. In all of them, p is a prime. There are φ ( p -1 ) primitive roots modulo p . Let n be an integer and g a primitive root of p . Then g n ≡ 1 (mod p) if and only if n ≡ 0 (mod p -1). If j and k are integers and g a primitive root of p , then g j ≡ g k ( mod p) if and only if j ≡ k (mod p -1).

13. Primitive root properties cont’d Let p = 11. The number of primitive roots is φ (10) = 4. This does not tell us what the primitive roots are, but we might guess at 3 and 7 as these are relatively prime to 10. However, powers of 3 generate: 1, 3, 9, 5, 4, 1, 3 etc. (mod 11), and so 3 is not a primitive root for 11. Also, P roperty (2) above tells us that 3 n can be 1 (mod 11) only if 10 divides n . However, we obtained 3 5 ≡ 1 (mod 11) , so 3 is not a primitive root. Exercise : Determine all the primitive roots modulo 11.

14. The basic principle again Note that property 3 of primitive roots is a stronger statement of the basic principle. The basic principle tells us that if j ≡ k (mod p-1), then g j ≡ g k (mod p) where we only need g and p to be relatively prime. Property 3 tells us that if g is a primitive root, then we can go also in the o pposite direction.

15. Summary We have covered sections Sections 3.6 and 3.7 : Euler’s theorem; And primitive root (generator).

16. Exercises Let p = 561 and choose an a other than 1 and 2. Test to see if the FLT condition works for your value of a . Then factor 561. Complete all other remaining questions through this lecture.