Homework #4 SolutionsQuestion 1aSlide 3Question 1b - Rebalanced RSAQuestion 1bSlide 6Slide 7Question 2 – IPSEC costQuestion 2aQuestion 2a - SolutionSlide 11Question 2bQuestion 2b - SolutionQuestion 3 – KDC EavesdroppingQuestion 3aSlide 16Slide 17Slide 18Slide 19Question 3bSlide 21Man-in-the-MiddleQuestion 3c (Extra Credit)Slide 24Question 3cHomework #4Homework #4SolutionsSolutionsBrian A. LaMacchiaBrian A. [email protected]@[email protected]@microsoft.comPortions © 2002-2006, Brian A. LaMacchia. This material is provided without warranty of any kind including, without limitation, warranty of non-infringement or suitability for any purpose. This material is not guaranteed to be error free and is intended for instructional use only.January 31, 2006January 31, 2006Practical Aspects of Modern CryptographyPractical Aspects of Modern Cryptography22Question 1aQuestion 1aQuestion 1(a): Compute the relative Question 1(a): Compute the relative cost of RSA encryption to RSA cost of RSA encryption to RSA decryption in SSL in terms of decryption in SSL in terms of modular multiplications mod n. modular multiplications mod n. The server’s public key is (n, e), where n The server’s public key is (n, e), where n is a 1024-bit composite, n = p*q (p, q is a 1024-bit composite, n = p*q (p, q 512-bit primes), and e = 2512-bit primes), and e = 21616+1. +1. The server’s private decryption The server’s private decryption exponent is d where ed exponent is d where ed 1 mod (p-1)(q- 1 mod (p-1)(q-1). Assume for this problem that half 1). Assume for this problem that half the bits in d are 1’s and |d| = 1024.the bits in d are 1’s and |d| = 1024.January 31, 2006January 31, 2006Practical Aspects of Modern CryptographyPractical Aspects of Modern Cryptography33Question 1aQuestion 1aRecall Josh's description of how to multiply Recall Josh's description of how to multiply fastfastFollow the bits in the exponent (high to low, Follow the bits in the exponent (high to low, ignoring the high bit since it's always 1), a 0 is a ignoring the high bit since it's always 1), a 0 is a square and a 1 is a square followed by a side square and a 1 is a square followed by a side multiply.multiply.So the cost of exponentiating is determined by So the cost of exponentiating is determined by the size of the exponent and the number of 1 the size of the exponent and the number of 1 bits it has.bits it has.The cost of encrypting (exponentiating to The cost of encrypting (exponentiating to e) is thus going to involve 16 squares and e) is thus going to involve 16 squares and 1 side multiply, since |e| = 17 and has only 1 side multiply, since |e| = 17 and has only the high & low bit set. the high & low bit set. The cost of decrypting (exponentiating to The cost of decrypting (exponentiating to d) is going to involve 1023 squares and d) is going to involve 1023 squares and 511 side multiplies (because |d| = 1024 511 side multiplies (because |d| = 1024 and half the bits in d are 1s).and half the bits in d are 1s).January 31, 2006January 31, 2006Practical Aspects of Modern CryptographyPractical Aspects of Modern Cryptography44Question 1b - Question 1b - Rebalanced RSARebalanced RSAn = pq, |p| = |q| = 512, p, q primen = pq, |p| = |q| = 512, p, q primeServer chooses the decryption Server chooses the decryption exponent d first such thatexponent d first such thatd d r1 mod p-1, d r1 mod p-1, d r2 mod q-1, |r1| = | r2 mod q-1, |r1| = |r2| = 160r2| = 160Assume half the bits in r1 & r2 are 1sAssume half the bits in r1 & r2 are 1sThe server then computes e such The server then computes e such that ed that ed 1 mod (p-1)(q-1). 1 mod (p-1)(q-1).|e| = 1024, assume half the bits in e are |e| = 1024, assume half the bits in e are 1s1sEncryption E(X) = XEncryption E(X) = Xee mod n mod nDecryption D(X) is now done by Decryption D(X) is now done by computing Xcomputing Xr1 r1 mod p, Xmod p, Xr2r2 mod q, and mod q, and using CRT to construct Xusing CRT to construct Xdd mod n. mod n.January 31, 2006January 31, 2006Practical Aspects of Modern CryptographyPractical Aspects of Modern Cryptography55Question 1bQuestion 1bQuestion 1(b): Compute the Question 1(b): Compute the relative cost of RSA encryption relative cost of RSA encryption to RSA decryption in the to RSA decryption in the Rebalanced RSA case for |n| = Rebalanced RSA case for |n| = 1024, |r1| = |r2| = 160, again in 1024, |r1| = |r2| = 160, again in terms of modular terms of modular multiplications in the multiplications in the exponentiations. exponentiations. What’s the speedup for a server What’s the speedup for a server compared to the “regular” RSA compared to the “regular” RSA in Question 1(a)? in Question 1(a)?January 31, 2006January 31, 2006Practical Aspects of Modern CryptographyPractical Aspects of Modern Cryptography66Question 1bQuestion 1bWe proceed as in 1(a), looking at the We proceed as in 1(a), looking at the sizes and number of 1 bits in the sizes and number of 1 bits in the various exponents.various exponents.Encrypting: e is now "full size“, so |Encrypting: e is now "full size“, so |e| = 1024 and half the bits in e are e| = 1024 and half the bits in e are 1s1sComputing XComputing Xee mod n will involve 1023 mod n will involve 1023 squares and 511 side multipliessquares and 511 side multipliesDecrypting: we need to compute XDecrypting: we need to compute Xr1r1 mod p and Xmod p and Xr2r2 mod q. mod q.|r|r11| = |r| = |r22| = 160 (by definition), and each | = 160 (by definition), and each has 80 1 bits.has 80 1 bits.Each exponentiation will involve 159 Each exponentiation will involve 159 squares and 79 side multiplies. So squares and 79 side multiplies. So together, the server has to perform 318 together, the server has to perform 318 squares and 158 side multiplies.squares and 158 side multiplies.January 31, 2006January 31, 2006Practical Aspects of Modern CryptographyPractical Aspects of Modern Cryptography77Question 1bQuestion 1bJust comparing the number of Just comparing the number of exponentiations, we've reduced the exponentiations, we've reduced the server's workload from 1023 squares server's workload from 1023 squares & 511 side multiplies to 318 squares & 511 side multiplies to 318 squares and 158 side multiplies, which is and 158 side multiplies, which is about a 3.2X speedup for
View Full Document
Unlocking...