Expand description
§Combo Breaker
The puzzle description for today describes the [Diffie-Hellman-Merkle] handshake, which your browser uses every day for encrypted traffic. It relies on the fact that if you use the product of two prime numbers as your encryption key, where each of the two parties in the transaction only knows one of the two prime numbers, then modular arithmetic allows both sides to efficiently compute the same results, while an eavesdropper would have exponentially more work to do to first factor the product into the original components. Here, we are playing the role of the eavesdropper, so we are doing exponential work. But since 2²⁵ is small, brute force is tolerable, when compared to more typical Diffie-Hellman parameters of 2⁵¹² or larger (these days, anything less than 2048 bits is insecure).
The common encryption key is then calculated efficiently by [modular exponentiation] using [exponentiation by squaring].
That said, we can still perform much faster than the potential of 20201227 steps needed for brute force, by using the [Baby-step giant-step algorithm]. This takes only √20201227 = 4495 steps, similar to how listing all divisors of a number can stop after reaching the square root of that number, since all the larger divisors will pair with a smaller one.
See also this alternative patch
that can further speed things up to less than one-tenth of the work by using the [Pohlig-Hellman]
algorithm (yes, the same Hellman that described secure key exchange also described how to speed
up the factoring of that key). However, the complexity required to exploit properties from
[Fermat’s Little Theorem] and the [Chinese Remainder Theorem] to reduce the work to √116099 = 341
table entries (as one of the factors of 20201227-1) is harder to maintain, when this
solution is already fast enough.
Diffie-Hellman-Merkle modular exponentiation exponentiation by squaring Baby-step giant-step algorithm Pohlig-Hellman Fermat’s Little Theorem Chinese Remainder Theorem
Constants§
- MOD 🔒
Functions§
- discrete_
logarithm 🔒 - Baby-step giant-step algorithm to compute discrete logarithm. Constants are hardcoded to this specific problem.
- parse
- part1
- part2