AoC 2020, 25. päev

Ülesanne

Siin: https://adventofcode.com/2020/day/25

Hüppab Whitfield, valmistub Martin

Esimese jõulupüha hommikuks pakuti murdmiseks lahjat Diffie-Hellmani võtmekehtestust¹. Õige ka, eilse vorsti peale peabki midagi lahjat olema.

Kuigi lahendus on toore jõuründe teema, siis neile, kes asjaga kokku pole puutunud: Diffie-Hellmani võtmekehtestus on selline põhimõtteliselt iidne kuid geniaalne tükk krüptograafilist aparatuuri, millele kas otse või oma derivaatide kaudu toetub sisuliselt kogu tänane internetiliikluse turvamine. Praktikas kasutatakse seda muidugi märksa suuremate ja märksa hoolikamalt valitud parameetritega kui siin ülesandes.

Tähtis on tähele panna, et tsüklis mingi arvuga läbi korrutamine ning seejärel jäägi leidmine ei ole mitte midagi muud kui modulo astendamine.

Antud juhul tekib meil kaks võrrandit: $$subjectNr^{cLoops} \pmod 202012227 \equiv cPK$$ ja $$subjectN^{dLoops} \pmod 202012227 \equiv dPK$$

(DH standardterminoloogias on $subjectNr$ hoopis base ehk alus ning $cLoops$ ja $dLoops$ vastava osapoole privaatvõtmed.)

Diffie-Hellmani võtmevahetus toetub järgmisele ekvivalentsusele:

$$sharedSecret \equiv cPK^{dLoops} \equiv dPK^{cLoops} \equiv subjectNr^{dLoops*cLoops}$$

Kõige kiirem tee lahendamiseks (võib-olla küll mitte kõige kiirem CPU operatsioonide mõttes) on leida jõuründega emb kumb privaatvõtmetest (ülesande terminoloogias „loop size“) ning arvutada seejärel lahendus vastava valemi järgi.

Matemaatiliselt taandub ülesanne diskreetse logaritmi leidmisele.

Ma ei tea, kas sellel ülesandel on jõuründest efektiivsemaid lahendusi ka: minumeelest ei, sest 7 ja 202012227 on mõlemad algarvud. Kui oleks vaja selliseid diskreetseid logartime palju arvutada, saaks tabelipõhise algoritmiga tööd kiirendada, aga ühe logaritmi puhul mitte: https://core.ac.uk/download/pdf/206024005.pdf.

EDIT: mõnevõrra efektiivsem algoritm on siiski olemas, nagu tähelepanu juhiti, aga selle kasutegur oleks siinkohal olematu või lausa negatiivne, kui valmis realisatsiooni võtta ei ole: https://en.wikipedia.org/wiki/Pollard's_rho_algorithm_for_logarithms.

Lahendus

Lahendus: https://github.com/fazz/aoc/blob/master/aoc2020/day25.py