AoC day 25: Combo Breaker

advent of code aoc2020 haskell

Christmas is here! For today’s puzzle, modular arithmetic makes its comeback. A good opportunity to try out using a library to do it, for once. This post is a literate Haskell program, that starts with a few imports.

{-# LANGUAGE DataKinds #-}
import Data.List  (elemIndex)
import Data.Maybe (fromJust)
import Data.Modular

Today’s modulus is 20201227. Probably because -25 and -26 weren’t prime.

type N = Mod Int 20201227

Let’s implement the cryptographic protocol, to get the hang of it.

A device has a secret key called “loop size”. This loop size is the parameter to a transformation function, which in effect is a power function.

newtype LoopSize = LoopSize N
transform :: N -> LoopSize -> N
transform subject (LoopSize secret) = subject^(unMod secret)

This secret can be used to generate a public key, by applying the tranformation to number 7.

newtype PublicKey = PublicKey N
mkPubKey :: LoopSize -> PublicKey
mkPubKey = PublicKey . transform 7

The encryption key to use between card and door is then defined by transforming one device’s public key with the other’s loop size. By mathematical magic1, it happens to produce the same result. Assuming I’m the card, I’d compute it by using my secret loop size of 8 to transform the door’s public key of 17807724.

encryptionKey :: LoopSize -> PublicKey -> N
encryptionKey ls (PublicKey pk) = transform pk ls
λ> encryptionKey (LoopSize 8) (PublicKey 17807724)

Let’s verify the other party agrees.

λ> encryptionKey (LoopSize 11) (PublicKey 5764801)

All good.

Oh, but my input’s public keys aren’t the same. How do I extract the loop size from a public key?

All that needs to be done is invert the operation:
public key = 7loop size ⇔ loop size = log7(public key)

crackLoopSize :: PublicKey -> LoopSize
crackLoopSize (PublicKey pk) = LoopSize (logarithm 7 pk)

There are a few beautiful algorithms to perform this. Considering the small modulus we have here, I’ll use worthy old brute force.

logarithm :: N -> N -> N
logarithm base power =
  toMod $ fromJust $ elemIndex power $ iterate (* base) 1

Here’s my wrapper, that also verifies the results are consistent.

main :: IO ()
main = do
    <- map (PublicKey . read) . lines <$> readFile ""
  print $ encryptionKey (crackLoopSize cardPublicKey) doorPublicKey
  print $ encryptionKey (crackLoopSize doorPublicKey) cardPublicKey

This concludes today’s solution. See you soon!2

  1. The easter egg for this puzzle acknowledges Diffie-Hellman, which was transparent to me, and Merkle, that I don’t see just yet.↩︎

  2. No more advent of code if you’re reading this from the distant future. More out-of-sync advent of code if you’re from the present, as I catch up.↩︎