【正文】 ? intersection of {1,2,4,8} and {1,2,3,4,6,12} ? = {1,2,4} ? greatest mon divisor: gcd(x,y) is the number z such that ? z is a mon divisor of x and y ? no mon divisor of x and y is larger than z ? gcd(8,12) = 4 11/4/2020 Lecture 3: Pubic Key Cryptography 13 Euclidean Algorithm: gcd(r0,r1) 0 1 1 21 2 2 32 1 110 1 1 2 1...0gc d( , ) gc d( , ) ... gc d( , )m m m mm m mm m mr q r rr q r rr q r rr q rr r r r r r r? ? ???????????? ? ? ?Main idea: If y = ax + b then gcd(x,y) = gcd(x,b) 11/4/2020 Lecture 3: Pubic Key Cryptography 14 Example – gcd(15,37) ? 37 = 2 * 15 + 7 ? 15 = 2 * 7 + 1 ? 7 = 7 * 1 + 0 ? gcd(15,37) = 1 11/4/2020 Lecture 3: Pubic Key Cryptography 15 Relative primes ? x and y are relatively prime if they have no mon divisors, other than 1 ? Equivalently, x and y are relatively prime if gcd(x,y) = 1 ? 9 and 14 are relatively prime ? 9 and 15 are not relatively prime 11/4/2020 Lecture 3: Pubic Key Cryptography 16 Modular Arithmetic ? Definition: x is congruent to y mod m, if m divides (xy). Equivalently, x and y have the same remainder when divided by m. Notation: Example: ? We work in Zm = {0, 1, 2, …, m1}, the group of integers modulo m ? Example: Z9 ={0,1,2,3,4,5,6,7,8} ? We abuse notation and often write = instead of )( m o d myx ?1 4 5 ( m o d 9 )??11/4/2020 Lecture 3: Pubic Key Cryptography 17 Addition in Zm : ? Addition is welldefined: ? 3 + 4 = 7 mod 9. ? 3 + 8 = 2 mod 9. )( m o d39。39。)( m o d39。)( m o d39。myxyxt h e nmyymxxif?????11/4/2020 Lecture 3: Pubic Key Cryptography 18 Additive inverses in Zm ? 0 is the additive identity in Zm ? Additive inverse of a is a mod m = (ma) ? Every element has unique additive inverse. ? 4 + 5= 0 mod 9. ? 4 is additive inverse of 5. )( m o d0)( m o d0 mxmxx ????11/4/2020 Lecture 3: Pubic Key Cryptography 19 Multiplication in Zm : ? Multiplication is welldefined: ? 3 * 4 = 3 mod 9. ? 3 * 8 = 6 mod 9. ? 3 * 3 = 0 mod 9. )( m o d39。39。)( m o d39。)( m o d39。myxyxt h e nmyymxxif?????11/4/2020 Lecture 3: Pubic Key Cryptography 20 Multiplicative inverses in Zm ? 1 is the multiplicative identity in Zm ? Multiplicative inverse (x*x1=1 mod m) ? SOME, but not ALL elements have unique multiplicative inverse. ? In Z9 : 3*0=0, 3*1=3, 3*2=6, 3*3=0, 3*4=3, 3*5=6, …, so 3 does not have a multiplicative inverse (mod 9) ? On the other hand, 4*2=8, 4*3=3, 4*4=7, 4*5=2, 4*6=6, 4*7=1, so 41=7, (mod 9) )( m o d1)( m o d1 mxmxx ????11/4/2020 Lecture 3: Pubic Key Cryptography 21 Which numbers have inverses? ? In Zm, x has a multiplicative inverse if and only if x and m are relatively prime or gcd(x,m)=1 ? ., 4 in Z9 11/4/2020 Lecture 3: Pubic Key Cryptography 22 Extended Euclidian: a1 mod n ? Main Idea: Looking for inverse of a mod n means looking for x such that x*a – y*n = 1. ? To pute inverse of a mod n, do the following: ? Compute gcd(a, n) using Euclidean algorithm. ? Since a is relatively prime to m (else there will be no inverse) gcd(a, n) = 1. ? So you can obtain linear bination of rm and rm1 that yields 1. ? Work backwards getting linear bination of ri and ri1 that yields 1. ? When you get to linear bination of r0 and r1 you are done as r0=n and r1= a. 11/4/2020 Lecture 3: Pubic Key Cryptography 23 Example – 151 mod 37 ? 37 = 2 * 15 + 7 ? 15 = 2 * 7 + 1 ? 7 = 7 * 1 + 0 Now, ? 15 – 2 * 7 = 1 ? 15 – 2 (37 – 2 * 15) = 1 ? 5 * 15 – 2 * 37 = 1 So, 151 mod 37 is 5. 11/4/2020 Lecture 3: Pubic Key Cryptography 24 Modular Exponentiation: Square and Multiply method ? Usual