Eindelijk bereik je de incheckbalie. Helaas is hun registratiesysteem momenteel offline en kunnen ze je niet inchecken. Ze merken de blik op je gezicht en voegen er snel aan toe dat de technische dienst al onderweg is! Ze hebben vanmorgen zelfs al alle kamersleutels gemaakt. Je kan jouw sleutel nu al meenemen aan de waarborg voor je kamer betalen van zodra het registratiesysteem weer werkt.

De kamersleutel is een kleine RFID¹-kaart. Je kamer bevindt zich op de 25e verdieping en de liften zijn ook tijdelijk buiten gebruik, dus zit er niets anders op dan de weinige energie die je nog in je hebt te gebruiken om de trap te nemen en door de gangen te navigeren. Uiteindelijk bereik je de deur van je kamer, scan je de kaart en — piep — het licht wordt rood.

Als je de kaart nader bekijkt, ontdekt je een telefoonnummmer van de technische dienst.

“Hallo! Waar kunnen we je vandaag mee van dienst zijn?” Je legt de situatie uit.

“Wel, dat klinkt alsof de kaart niet het juiste commando verstuurt om de deur te ontgrendelen. Als je teruggaat naar de incheckbalie, dan kan iemand daar vast wel je kaart resetten.” Nog steeds op adem komend, beschrijf je de toestand van de lift en het exacte aantal trappen dat je net hebt moeten beklimmen.

“Ik begrijp het! Wel, je enige andere optie is om de cryptografische handdruk tussen de kaart en de deur te reverse-engineeren en dan je eigen commando’s in de datastroom te injecteren, maar dat is absoluut onmogelijk.” Je bedankt ze voor hun tijd.

Helaas voor de deur weet je het een en ander over cryptografische handdrukken.

De handdruk die door de kaart en de deur gebruikt wordt, gebruikt een bewerking die een basisgetal transformeert. Om een basisgetal te transformeren, begin je met de waarde 1. Daarna voer je een aantal keren (dit wordt de lusgrootte genoemd) de volgende stappen uit:

Stel de waarde in op zichzelf vermenigvuldigd met het basisgetal.
Stel de waarde in op de rest na deling van de waarde door 20201227.

De kaart gebruikt altjd een specifieke, geheime lusgrootte als het een basisgetal transformeert. De deur gebruikt altijd een andere, geheime lusgrootte.

De cryptografische handdruk werkt als volgt:

De kaart transformeert het basisgetal 7 volgens de geheime lusgrootte van de kaart. Het resultaat wordt de publieke sleutel van de kaart genoemd.
De deur transformeert het basisgetal 7 volgens de geheime lusgrootte van de deur. Het resultaat wordt de publieke sleutel van de deur genoemd.
De kaart en de deur gebruiken draadloze RFID-signalen om de twee publieke sleutels naar het andere apparaat te sturen. Nu heeft de kaart de publieke sleutel van de deur en heeft de deur de publieke sleutel van de kaart. Omdat je het signaal kunt onderscheppen, heb je beide publiek sleutels, maar niet de lusgrootte van een van beide apparaten.
De kaart transformeert de publieke sleutel van de deur als basisgetal volgens de lusgrootte van de kaart. Het resultaat is de encryptiesleutel.
De deur transformeert de publieke sleutel van de kaart als basisgetal volgens de lusgrootte van de deur. Het resultaat is dezelfde encryptiesleutel als de kaart berekend heeft.

Als je de publieke sleutel kunt gebruiken om de lusgrootte van één van beide apparaten te bepalen, dan heb je voldoende om de geheime encryptiesleutel te berekenen die de kaart en de sleutel gebruiken om met elkaar te communiceren. Hierdoor kun je het ontgrendelingscommando rechtstreeks naar de deur sturen!

Stel bijvoorbeeld dat je weet dat de publieke sleutel van de kaart 5764801 is. Met een beetje trial and error kun je erachter komen dat de lusgrootte van de kaart 8 moet zijn, omdat het transformeren van het basisgetal 7 met een lusgrootte van 8 de waarde 5764801 oplevert.

Stel dat je dan ook weet dat de publieke sleutel van de deur 17807724 is. Op dezelfde manier kun je bepalen dat de lusgrootte van de deur 11 is, omdat het transformeren van het basisgetal 7 met een lusgrootte van 11 de waarde 17807724 oplevert.

Op dit punt kan je de lusgrootte van beide apparaten gebruiken in combinatie met de publieke sleutel van het andere apparaat om de encryptesleutel te berekenen. Het basisgetal 17807724 (de publieke sleutel van de deur) transformeren met een lusgrootte van 8 (de lusgrootte van de kaart) levert de encryptiesleutel 14897079 op. (Het basisgetal 5764801 (de publieke sleutel van de kaart) transformeren met een lusgrootte van 11 (de lusgrootte van de deur) levert dezelfde encryptiesleutel op: 14897079.)

Opgave

Wat is de encryptiesleutel waarmee de handdruk tot stand gebracht kan worden? Hiervoor ga je als volgt te werk:

Schrijf een functie loop_size waaraan een publieke sleutel (int) en een basisgetal (int) moeten doorgegeven worden. De functie moet de lusgrootte (int) voor de gegeven publieke sleutel en het gegeven basisgetal teruggeven.
Schrijf een functie transform waaraan een basisgetal (int) en een lusgrootte (int) moeten doorgegeven worden. De functie moet het resultaat (int) teruggeven dat bekomen wordt door het gegeven basisgetal om te zetten met de gegeven lusgrootte.
Schrijf een functie encryption_key waaraan twee publieke sleutels (int) en een basisgetal (int) moeten doorgegeven worden. De functie moet de corresponderende encryptiesleutel (int) teruggeven waarmee de handdruk tot stand gebracht kan worden.

Voorbeeld

> loop_size(5764801, 7)
8
> loop_size(17807724, 7)
11

> transform(17807724, 8)
14897079
> transform(5764801, 11)
14897079

> encryption_key(5764801, 17807724, 7)
14897079