《m = c d mod n：m = c d mod n》由会员分享，可在线阅读，更多相关《m = c d mod n：m = c d mod n（32页珍藏版）》请在金锄头文库上搜索。
1、Cryptography & Network Security,RSA Algorithm Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977 Used for both public key encryption and digital signaturesPlain text is encrypted in blocks, each block having a binary value less than some number n. Block size = log2(n); ,the block size i
2、s i bits, where 2i n= 2i+1 C = Me mod n M = Cd mod n = (Me)d mod n = Med mod n public key of KU = e, n private key of KR = d, n Requirements It is possible to find values of e, d, n such that Med = M mod n for all M n. It is relatively easy to calculate mod Me and Cd for all values of M n. It is inf
3、easible to determine d given e and n.,Med = M mod nAccording to Eulers theorem Given two prime numbers p & q and two integers n and m such that n = pq and 0 m nArbitrary integer kmk(n)+1=mk(p-1)(q-1)+1=m mod n p,q prime (pq) = (p-1)(q-1),The preceding relationship holds if e and d are multiplicative
4、 inverses modulo (n), where (n) is the Euler totient function.,ed = k (n) + 1 This is equivalent to saying ed =1 mod (n) d =e-1 mod (n) That is, e and d are multiplicative inverses mod (n). Equivalently, gcd(n),d) = 1. Ingredients of RSAp,q, two prime numbers (private, chosen) n = pq (public, calcul
5、ated) e, with gcd(n),e) = 1;1 e (n) (public, chosen) d =e-1(mod (n) (private, calculated),The private key consists of d, n and the public key consists of e, n.Suppose that user A has published its public key and that user B wishes to send the message M to A. Then B calculates C = Me mod n and transm
6、its C. On receipt of this ciphertext, user A decrypts by calculating M = Cd mod n.,Select two prime numbers, p = 17 and q = 11. Calculate n = pq = 17 x 11 = 187. Calculate (n) = (p - 1)(q - 1) = 16 x 10 = 160. Select e such that e is relatively prime to (n) = 160 and less than (n) we choose e = 7. D
7、etermine d such that de = 1 (mod 160) and d 160. The correct value is d = 23, because 23 x 7 = 161 = 160 + 1; d can be calculated using the extended Euclids algorithm,RSA is usch slower than DES & Other Symmetric Cryptosystems,The Security of RSA Four possible approaches to attacking the RSA algorit
8、hm:Brute force: This involves trying all possible private keys.Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of two primes.Timing attacks: These depend on the running time of the decryption algorithm.Chosen ciphertext attacks: This type of atta
9、ck exploits properties of the RSA algorithm.The defense against the brute-force approach is the same for RSA as for other cryptosystems, use a large key space. Thus, the larger the number of bits in d, the better.,The Factoring ProblemThree approaches to attacking RSA mathematically Factor n into it
10、s two prime factors. Enables calculation of f(n) = (p - 1) x (q - 1), which, in turn, enables determination of d e1 (mod f(n). Determine f(n) directly, enables determination of d e1 (mod f(n). Determine d directly, without first determining f(n).,Example IllustrationThe resulting keys are public key
11、 PU = 7,187 and private key PR = 23,187. Plain text input of M = 88. For encryption, calculate C = 887 mod 187.,887 mod 187 = (884 mod 187) x (882 mod 187) x (881 mod 187) mod 187 881 mod 187 = 88 882 mod 187 = 7744 mod 187 = 77 884 mod 187 = 59,969,536 mod 187 = 132 887 mod 187 = (88 x 77 x 132) mo
12、d 187 = 894,432 mod 187 = 11 For decryption, we calculate M = 1123 mod 187: 1123 mod 187 = (111 mod 187) x (112 mod 187) x (114 mod 187) x (118 mod 187) x (118 mod 187) mod 187 111 mod 187 = 11 112 mod 187 = 121 114 mod 187 = 14,641 mod 187 = 55 118 mod 187 = 214,358,881 mod 187 = 33 1123 mod 187 =
13、(11 x 121 x 55 x 33 x 33) mod 187 = 79,720,245 mod 187 = 88,Key Management Distribution of Public KeysPublic announcement - Publicly available directory,3. PUBLIC KEY AUTHORITY,4. PUBLIC CERTIFICATE,Digital SignaturesMessage authentication protects two parties who exchange messages from any third pa
14、rty. Scenario An electronic funds transfer takes place, and the receiver increases the amount of funds transferred and claims that the larger amount had arrived from the sender.Not complete trust between sender and receiverDS have the following properties: It must verify the author and the date and
15、time of the signature.It must to authenticate the contents at the time of the signature.It must be verifiable by third parties, to resolve disputes.,On the basis of these properties, we can formulate the following requirements for a digital signature:The signature must be a bit pattern that depends
16、on the message being signed.The signature must use some information unique to the sender, to prevent both forgery and denial.It must be relatively easy to produce the digital signature.It must be relatively easy to recognize and verify the digital signature.It must be computationally infeasible to forge a digital signature, either by constructing a new message for an existing digital signature or by constructing a fraudulent digital signature for a given message.It must be practical to retain a copy of the digital signature in storage.,
