网络安全：数论初步.ppt

* The actual RSA encryption and decryption computations are each simply a single exponentiation mod (n). Note that the message must be smaller than the modulus. The “magic” is in the choice of the exponents which makes the system work. * Can show that RSA works as a direct consequence of Euler’s Theorem, so that raising a number to power e then d (or vica versa) results in the original number! * Here walk through example RSA key generation using “trivial” sized numbers. Selecting primes requires the use of a primality test. Finding d as inverse of e mod ?(n) requires use of Euclid’s Inverse algorithm (see Ch4) * Then show that the encryption and decryption operations are simple exponentiations mod 187. Rather than having to laborious repeatedly multiply, can use the square and multiply algorithm with modulo reductions to implement all exponentiations quickly and efficiently (see next). * To perform the modular exponentiations, you can use the “Square and Multiply Algorithm”, a fast, efficient algorithm for doing exponentiation. The idea is to repeatedly square the base, and multiply in the ones that are needed to compute the result, as found by examining the binary representation of the exponent. * State here one version of the “Square and Multiply Algorithm”, from Stallings Figure 9.7. * * To speed up the operation of the RSA algorithm using the public key, can choose to use a small value of e (but not too small, since its then vulnerable to attack). Must then ensure any p or q chosen are relatively prime to the fixed e (and reject and find another if not), for system to work. * To speed up the operation of the RSA algorithm using the private key, can use the Chinese Remainder Theorem (CRT) to compute mod p q separately, and then combine results to get the desired answer. This is approx 4 times faster than calculating “C^d mod n” directly. Note that only the owner of the private key details (who knows the values of p q) can do this, but of course that’s exactly w