第三章 Public Key－Mac 电子商务信息安全与管理教学课件.pptVIP

* This key setup is done once (rarely) when a user establishes (or replaces) their public key. The exponent e is usually fairly small, just must be relatively prime to ?(N). Need to compute its inverse to find d. It is critically important that the private key KR={d,p,q} is kept secret, since if any part becomes known, the system can be broken. Note that different users will have different moduli N. * Here walk through example using “trivial” sized numbers. Selecting primes requires the use of primality tests. Finding d as inverse of e mod ?(n) requires use of Inverse algorithm (see Ch4) * Can show that RSA works as a direct consequence of Euler’s Theorem. For n ? 1, let ?(n) denote the number of integers in the interval [1, n] which are relatively prime to n. The function ? is called the Euler phi function (or the Euler totient function). Fact 1. The Euler phi function is multiplicative. I.e. if gcd(m, n) = 1, then ?(mn) = ?(m) x ?(n). E.g. 91=7×13 ?(7) =6 ?(13)=12 ?(91) = ?(7) × ?(13) =6×12＝72 The Euler phi Function Euler’s Theorem Let n be a composite. Then b?(n) ＝1 (mod n) for any integer b which is relatively prime to n. E.g. b=3; n=10;  ?(10)=4 ? 34 ＝ 81 ＝ 1 (mod 10) E.g. b=2; n=11;  ?(11)=10 ? 210 ＝ 1024 ＝ 1 (mod 11) Eulers Theorem RSA Key Generation each user generates a public/private key pair by: selecting two large primes at random p, q computing their system modulus N=p.q note φ(N)=(p-1)(q-1) selecting at random the encryption key e where 1eφ(N), gcd(e,φ(N))=1 solve following equation to find decryption key d e.d=1 mod φ(N) and 0≤d≤N publish their public encryption key: KU={e,N} keep secret private decryption key: KR={d,N} Example of RSA Algorithm RSA Example Select primes: p=17 q=11 Compute n = pq= 187 Compute φ(n)=(p–1)(q-1)=16×10=160 Select e : gcd(e,160)=1; choose e=7 Determine d: de=1 mod 160 and d 160 Value is d=23 since 23×7=161= 10×160+1 public key KU=(7,187)