part1 (4583B)
1--- Day 25: Combo Breaker --- 2 3You finally reach the check-in desk. Unfortunately, their registration systems are currently 4offline, and they cannot check you in. Noticing the look on your face, they quickly add that tech 5support is already on the way! They even created all the room keys this morning; you can take yours 6now and give them your room deposit once the registration system comes back online. 7 8The room key is a small RFID card. Your room is on the 25th floor and the elevators are also 9temporarily out of service, so it takes what little energy you have left to even climb the stairs 10and navigate the halls. You finally reach the door to your room, swipe your card, and - 11[1m[37mbeep[0m - the light turns red. 12 13Examining the card more closely, you discover a phone number for tech support. 14 15"Hello! How can we help you today?" You explain the situation. 16 17"Well, it sounds like the card isn't sending the right command to unlock the door. If you go back to 18the check-in desk, surely someone there can reset it for you." Still catching your breath, you 19describe the status of the elevator and the exact number of stairs you just had to climb. 20 21"I see! Well, your only other option would be to reverse-engineer the cryptographic handshake the 22card does with the door and then inject your own commands into the data stream, but that's 23definitely impossible." You thank them for their time. 24 25Unfortunately for the door, you know a thing or two about cryptographic handshakes. 26 27The handshake used by the card and the door involves an operation that [1m[37mtransforms[0m a 28[1m[37msubject number[0m. To transform a subject number, start with the value 1. Then, a number 29of times called the [1m[37mloop size[0m, perform the following steps: 30 31 32 - Set the value to itself multiplied by the [1m[37msubject number[0m. 33 - Set the value to the remainder after dividing the value by [1m[37m20201227[0m. 34 35 36The card always uses a specific, secret [1m[37mloop size[0m when it transforms a subject number. 37The door always uses a different, secret loop size. 38 39The cryptographic handshake works like this: 40 41 42 - The [1m[37mcard[0m transforms the subject number of [1m[37m7[0m according to the 43[1m[37mcard's[0m secret loop size. The result is called the [1m[37mcard's public key[0m. 44 - The [1m[37mdoor[0m transforms the subject number of [1m[37m7[0m according to the 45[1m[37mdoor's[0m secret loop size. The result is called the [1m[37mdoor's public key[0m. 46 - The card and door use the wireless RFID signal to transmit the two public keys (your puzzle 47input) to the other device. Now, the [1m[37mcard[0m has the [1m[37mdoor's[0m public key, and 48the [1m[37mdoor[0m has the [1m[37mcard's[0m public key. Because you can eavesdrop on the 49signal, you have both public keys, but neither device's loop size. 50 - The [1m[37mcard[0m transforms the subject number of [1m[37mthe door's public key[0m 51according to the [1m[37mcard's[0m loop size. The result is the [1m[37mencryption key[0m. 52 - The [1m[37mdoor[0m transforms the subject number of [1m[37mthe card's public key[0m 53according to the [1m[37mdoor's[0m loop size. The result is the same [1m[37mencryption key[0m 54as the [1m[37mcard[0m calculated. 55 56 57If you can use the two public keys to determine each device's loop size, you will have enough 58information to calculate the secret [1m[37mencryption key[0m that the card and door use to 59communicate; this would let you send the unlock command directly to the door! 60 61For example, suppose you know that the card's public key is 5764801. With a little trial and error, 62you can work out that the card's loop size must be [1m[37m8[0m, because transforming the initial 63subject number of 7 with a loop size of 8 produces 5764801. 64 65Then, suppose you know that the door's public key is 17807724. By the same process, you can 66determine that the door's loop size is [1m[37m11[0m, because transforming the initial subject 67number of 7 with a loop size of 11 produces 17807724. 68 69At this point, you can use either device's loop size with the other device's public key to calculate 70the [1m[37mencryption key[0m. Transforming the subject number of 17807724 (the door's public key) 71with a loop size of 8 (the card's loop size) produces the encryption key, [1m[37m14897079[0m. 72(Transforming the subject number of 5764801 (the card's public key) with a loop size of 11 (the 73door's loop size) produces the same encryption key: [1m[37m14897079[0m.) 74 75[1m[37mWhat encryption key is the handshake trying to establish?[0m 76 77