English summary at the end.
Hej!
Jag är kryptomatematikern Mikko-Peter Tyramant, brylling till den store organisten Stig-Aron En och geografen Georg af En. Jag tänkte lära er lite om vad som är hett inom kryptoforskningen just nu: PQC, dvs. Postkvantkryptografi (Post Quantum Cryptography).
Bakgrunden är att flera av de vanligaste asymmetriska kryptoalgoritmerna har visat sig vara sårbara för attacker från kvantdatorer. Algoritmerna RSA, Diffie-Hellman, Diffie-Hellman över elliptiska kurvor m.fl., som du och jag använder dagligen utan att tänka på det när vi är ute på Internet, kan attackeras med en kvantdator och Shors algoritm. Till skillnad från vanliga klassiska datorer som arbetar med ettor och nollor, arbetar kvantdatorer med kvantbitar (qubits) som (lite förenklat) är både ett och noll på samma gång genom att vara i s.k. superposition, vilket reducerar komplexiteten dramatiskt för en viss klass av problem.
I dag, 2020, är man inte i närheten av att bygga en tillräckligt stor kvantdator för att kunna attackera dagens kryptografi, och det råder delade meningar om det någonsin kommer att bli möjligt. Det är en gigantisk utmaning att kunna hålla ett system av många kvantbitar i superposition utan att det kollapsar. Man måste bland annat hålla kvantdatorn nedkyld under lång tid till några milliKelvin, dvs. bara en bråkdel av temperaturen i yttre rymden. Ingen kan dock garantera att ingen klarar av utmaningen, och skulle det byggas en tillräckligt stor kvantdator inom säg 10–20 år hotar det krypterade hemligheter som kanske har 50 års sekretess eller mer.
Just nu forskas det alltså intensivt om kvantsäkra algoritmer, som både ska vara säkra mot en attack från kvantdatorer och mot klassisk kryptoanalys. Att algoritmerna ska kunna motstå klassisk kryptoanalys är ofta svårare att bevisa än att de motstår attacker från kvantdatorer. Lika fullt är det bråttom. Just nu genomför den amerikanska standardiseringsorganisationen NIST (National Institute of Standards and Technology) en utvärdering i syfte att någon gång mellan 2022 och 2024 ha ett antal färdiga standardalgoritmer som förhoppningsvis är tillräckligt starka.
Det finns flera olika principer för PQC, och olika principer passar olika bra för olika tillämpningar. I den här mysten ska vi titta lite närmare på en av principerna, s.k. multivariat kryptografi som bygger på icke-linjära ekvationssystem i många variabler. Denna princip har hittills visat sig vara olämplig för att skydda sekretess, t.ex. nyckelutbyte. Däremot bedöms den fortfarande vara lämplig för att skapa signaturer. En kryptografisk signatur kan ses som en digital underskrift, dvs. ett bevis för dels att avsändaren av ett meddelande verkligen är den som påstår sig har skickat meddelandet, dels att meddelandet inte har förändrats längs vägen.
I vårt exempel ska Alice skicka ett meddelande till Bob om var hon har gömt något intressant till honom. Det har tidigare visat sig att den elaka Eve ibland skickar felaktiga koordinater, där hon kanske har gömt en gillrad råttfälla, en burk dyvelsträck eller något annat otrevligt. För att Bob ska vara säker på att det verkligen är Alice och inte Eve som har skickat koordinaterna har Alice skapat ett signaturschema. Tillsammans med koordinaterna Nord AB° CD.EFG Öst HI° JK.LMN skickar hon också signaturen a-b-c-d-e-f-g-h-i-j-k-l-m-n. Koordinaterna och signaturen ska uppfylla nedanstående ekvationer:
\(A = 3a+7b+6c+2d+e+2f+3g+6h+3i+9j+2k+l+7m+8n+ae+4af+ak+5am+3be+2bg+6bl+3bn+4cf+7cg+6cl+7cn+7eh+2ei+3fh+9fi+6gj+4hk+2hm+10ik+2im+2jl+jn+7 \\ B = 5a+5b+6c+9d+4e+7f+9g+5j+8k+10l+8m+7n+ae+8af+6ak+4am+8be+4bg+5bl+8bn+4cf+2cg+2cl+5cn+eh+9ei+4fh+2fi+10gj+9hk+4hm+ik+9im+8jl+9jn+2 \\ C = 4b+d+8e+5f+5g+10h+6i+j+10l+7m+2n+af+10am+6be+9bg+8bl+4cf+8cn+9eh+ei+10fh+10fi+10gj+5hk+3hm+5ik+im+3jl+6jn \\ D = 9a+3b+5c+4e+8f+10h+9i+j+4k+l+6m+6ae+af+10ak+6be+2bg+bl+9bn+5cf+3cg+8cl+6cn+eh+4fh+4gj+6hk+3hm+jl+jn+10 \\ E = 8a+4b+2c+7d+6e+f+4g+9h+2i+5j+10k+9l+10m+n+6ae+3af+2ak+4am+8be+4bg+2bl+4bn+10cf+4cg+6cl+6cn+eh+7ei+fh+4fi+9gj+hk+10hm+2ik+7im+6jl+8jn+8 \\ F = 2a+3b+9c+6d+10e+8f+3h+3i+5j+l+2n+2ae+6af+3be+10bg+4bl+2cf+6cg+cl+3cn+8eh+6ei+5fh+5fi+6gj+8hk+hm+8ik+6im+jl+8 \\ G = 5a+2b+2c+3d+6e+7f+4g+5h+8i+7j+9k+l+4m+8n+ae+8af+6ak+5am+6be+6bg+10bl+4bn+4cf+3cg+10cn+5eh+3ei+6fh+8fi+6gj+hk+9hm+4ik+3im+4jl+7jn+7 \\ H = 9a+5b+6c+4d+6e+9f+7g+8h+9i+2j+2k+9l+5m+2n+8ae+3af+9ak+9am+3be+7bg+7bn+3cf+3cg+4cl+9cn+4ei+6fh+7fi+gj+10hk+7hm+9ik+4im+6jl+7jn+10 \\ I = 8a+5b+10c+3d+8f+2g+3i+9j+3k+2m+7n+4ae+8af+9ak+7am+bg+4bl+6bn+cf+4cg+3cl+cn+10eh+3ei+3fh+8fi+7gj+5hk+9hm+4ik+3im+3jl+7jn+8 \\ J = 10b+10c+9d+2e+5f+8h+9i+10m+10n+2ae+3af+5ak+10am+3be+6bg+4bl+6bn+7cf+2cn+9ei+fh+2fi+3gj+4hk+9hm+ik+9im+8jl+jn+1 \\ K = 2a+2b+8c+7d+9e+5f+9g+9h+5i+j+6k+2l+7m+2n+5ae+8af+9ak+4am+be+3bg+2bl+10bn+cf+9cg+5cn+3eh+7ei+9fh+4fi+3hk+2ik+7im+7jn+3 \\ L = 3a+3b+4c+8d+e+8f+2g+8h+4i+8j+4k+9l+7m+4n+4ae+10af+8am+7be+9bg+5bl+10bn+7cf+5cg+2cl+10cn+7eh+8ei+9fh+3fi+gj+7hk+6hm+7ik+8im+2jl+9jn+5 \\ M = 9a+4b+10c+8d+7e+7f+7g+6h+2i+3j+9k+2l+3m+n+ae+6af+10ak+10am+6be+4bg+3bl+3bn+3cf+8cg+cl+3cn+9eh+8ei+9fh+3fi+8gj+2hk+4hm+7ik+8im+3jl+7jn+7 \\ N = 9b+10c+9d+3e+5f+g+4h+4i+3k+8l+m+4n+6ae+2af+8ak+5am+4be+8bg+10bl+2bn+9cg+5cl+4cn+2eh+9ei+6fh+2fi+4gj+8hk+5hm+ik+9im+10jl+7jn+9 \)
Alla ekvationer är modulo 11, dvs. efter genomförd beräkning behåller man enbart resten vid division med 11.
Dessa ekvationer kan vi kalla den öppna nyckeln, med vilken det är möjligt att verifiera att en signatur är korrekt. Det är dock mycket svårt att skapa en signatur från den öppna nyckeln eftersom det kräver att man löser ett icke-linjärt ekvationssystem. Detta är i allmänhet ett s.k. NP-fullständigt problem, vilket betyder att problemet är matematiskt komplext och tar lång tid att lösa. Den som vill fördjupa sig i lösning av allmänna icke-linjära ekvationssystem kan studera Gröbnerbaser och Buchbergers algoritm. Det är dock inget som behövs för att lösa denna myst.
Alice har dessutom en hemlig nyckel, där hon har skapat ett specialfall med ett icke-linjärt ekvationssystem som är lätt att lösa och som hon genom ett basbyte har omvandlat till den öppna nyckeln. Med denna hemliga nyckel kan hon enkelt skapa signaturer. Så länge hon inte avslöjar basbytet är systemet mycket säkert.
Som exempel kan vi ta de publicerade koordinaterna N 59° 16.789 E 17° 45.123 (där det inte finns något av intresse) med tillhörande signatur (kontrollera gärna att ekvationerna är uppfyllda): 8-7-2-6-4-6-2-9-3-9-4-8-6-5
En dag skickade Alice en koordinat med dess signatur. Till Bobs förvåning var koordinaterna och signaturen identiska, dvs. A=a, B=b och så vidare. Vilka koordinater var det? Bege dig dit så hittar du kanske något intressant där.
Med vänliga hälsningar
Mikko-Peter Tyramant
English Summary
This puzzle cache is about Post-Quantum Cryptography, more specifically Multivariate Cryptography. The task is to solve the non-linear system of equations above with the condition A=a, B=b, etc. The cache is located at North AB° CD.EFG East HI° JK.LMN. All equations are modulo 11, i.e. after calculations and division by 11 only the remainder is kept.
Please contact CO if you wish a translation of the entire text.
