Day 25 was a foray into public key encryption, using Diffie-Hellman key exchange (or should that be Ellis-Cocks-Williamson key exchange?). The idea is one of raising numbers to a power (the power being the key) and exchanging the results.
The idea is that we agree a subject number (7 in the example) and both secretly choose a key. In the example, the card's key is 8 and the door's key is 11. The card calculates 78 = 5764801 and publishes the answer. The door calculates 711 = 1977326743 and publishes that answer. The card can then calculate the encryption key as 19773267438 = (711)8 = 711 + 8. Similarly, the door calculates the encryption key as 576480111 = (78)11 = 78 + 11. These are the same numbers.
That isn't too secure, as any eavesdropper can find the keys by taking logarithms of the published numbers: \( \log_7 5764801 = 8 \). The complication comes from the use of modular arithmetic, where the published numbers are taken modulus some large prime. That extra layer makes the logarithms very hard to find.
Luckily, this puzzle only uses small keys, so brute-force solutions are solvable.
I started by looking at the discrete logarithm function in the arithmoi library, but got scared off by the higher-level type signature. But I did get inspired by a Reddit post, of using a
newtype for numbers and defining a
Semigroup using modular multiplication based on that
import Data.Semigroup newtype MExp = MExp Integer deriving (Show, Eq) instance Semigroup MExp where (MExp a) <> (MExp b) = MExp $ (a * b) `mod` modularBase
Finding one of the keys was just counting up from 1, multiplying an accumulator until I found the target. I could have used a combination of
length $ takeWhile $ iterate to do that, or even an
unfold, but I decided to use
findRounds :: Integer -> Integer findRounds target = fst $ until (foundRounds t) countingExponential (0, seed) where t = MExp target seed = MExp 1 foundRounds :: MExp -> (Integer, MExp) -> Bool foundRounds target (_n, v) = v == target countingExponential :: (Integer, MExp) -> (Integer, MExp) countingExponential (n, v) = (n + 1, v <> subject)
All that's left is to find the encryption key, and
stimes does that efficiently.
part1 cardKey doorKey = publicKey where cardRounds = findRounds cardKey MExp publicKey = stimes cardRounds (MExp doorKey)
And that gives me 300 stars for the six events of Advent of Code.