// ------------------------------------------------------------ 57. Diffie-Hellman Revisited: Subgroup-Confinement Attacks This set is going to focus on elliptic curves. But before we get to that, we're going to kick things off with some classic Diffie-Hellman. Trust me, it's gonna make sense later. Let's get right into it. First, build your typical Diffie-Hellman key agreement: Alice and Bob exchange public keys and derive the same shared secret. Then Bob sends Alice some message with a MAC over it. Easy as pie. Use these parameters: p = 7199773997391911030609999317773941274322764333428698921736339643928346453700085358802973900485592910475480089726140708102474957429903531369589969318716771 g = 4565356397095740655436854503483826832136106141639563487732438195343690437606117828318042418238184896212352329118608100083187535033402010599512641674644143 The generator g has order q: q = 236234353446506858198510045061214171961 "Order" is a new word, but it just means g^q = 1 mod p. You might notice that q is a prime, just like p. This isn't mere chance: in fact, we chose q and p together such that q divides p-1 (the order or size of the group itself) evenly. This guarantees that an element g of order q will exist. (In fact, there will be q-1 such elements.) Back to the protocol. Alice and Bob should choose their secret keys as random integers mod q. There's no point in choosing them mod p; since g has order q, the numbers will just start repeating after that. You can prove this to yourself by verifying g^x mod p = g^(x + k*q) mod p for any x and k. The rest is the same as before. How can we attack this protocol? Remember what we said before about order: the fact that q divides p-1 guarantees the existence of elements of order q. What if there are smaller divisors of p-1? Spoiler alert: there are. I chose j = (p-1) / q to have many small factors because I want you to be happy. Find them by factoring j, which is: j = 30477252323177606811760882179058908038824640750610513771646768011063128035873508507547741559514324673960576895059570 You don't need to factor it all the way. Just find a bunch of factors smaller than, say, 2^16. There should be plenty. (Friendly tip: maybe avoid any repeated factors. They only complicate things.) Got 'em? Good. Now, we can use these to recover Bob's secret key using the Pohlig-Hellman algorithm for discrete logarithms. Here's how: 1. Take one of the small factors j. Call it r. We want to find an element h of order r. To find it, do: h := rand(1, p)^((p-1)/r) mod p If h = 1, try again. 2. You're Eve. Send Bob h as your public key. Note that h is not a valid public key! There is no x such that h = g^x mod p. But Bob doesn't know that. 3. Bob will compute: K := h^x mod p Where x is his secret key and K is the output shared secret. Bob then sends back (m, t), with: m := "crazy flamboyant for the rap enjoyment" t := MAC(K, m) 4. We (Eve) can't compute K, because h isn't actually a valid public key. But we're not licked yet. Remember how we saw that g^x starts repeating when x > q? h has the same property with r. This means there are only r possible values of K that Bob could have generated. We can recover K by doing a brute-force search over these values until t = MAC(K, m). Now we know Bob's secret key x mod r. 5. Repeat steps 1 through 4 many times. Eventually you will know: x = b1 mod r1 x = b2 mod r2 x = b3 mod r3 ... Once (r1*r2*...*rn) > q, you'll have enough information to reassemble Bob's secret key using the Chinese Remainder Theorem.