Talteori och kryptografi¶
Här är den goda nyheten om hela detta område: nästan allt följer av en enda algoritm. Euklides algoritm beräknar den största gemensamma delaren av två tal, och — baklänges — skriver den den delaren som en kombination av dem. Det enda knepet löser diofantiska ekvationer, ger modulära inverser och genererar RSA-nycklar. Lär dig den utantill och det mesta av detta kapitel faller ut.
Euklides algoritm¶
Målet. Hitta \(\gcd(n, m)\), det största heltal som delar både \(n\) och \(m\).
Metoden. Ersätt upprepade gånger det större talet med dess rest vid division med det mindre. Fortsätt tills resten blir \(0\); den sista nollskilda resten är den gemensamma delaren.
Varför den fungerar (enradsskälet). Varje gemensam delare till \(n\) och \(m\) delar också deras rest \(n \bmod m\) — så vid varje steg är mängden gemensamma delare oförändrad. Talen krymper men deras gemensamma delare gör det inte, och när ett når \(0\) är delaren helt enkelt det andra talet.
Att skriva delaren som en kombination¶
Det är den här delen som gör allt det nedströms arbetet.
Bézouts identitet
Den gemensamma delaren kan alltid skrivas som en heltalskombination av de två talen:
Du hittar \(x\) och \(y\) genom att köra algoritmen framåt, och sedan substituera baklänges genom divisionsstegen för att veckla ut delaren i termer av originalen. Detta är den utvidgade Euklides algoritmen. Den är mekanisk när du gjort den några gånger — öva tills den sitter.
Långsamt genomräknat: \(\gcd(15, 17)\) som en kombination
Framåt (dividera, notera resten, upprepa):
Den sista nollskilda resten är \(1\), så \(\gcd(15, 17) = 1\).
Baklänges — börja i raden vars rest är delaren, och substituera in varje tidigare rest i tur och ordning. Börja vid \(15 = 7 \cdot 2 + 1\), dvs. isolera \(1\):an:
Nu säger föregående rad att \(2 = 17 - 15\). Substituera in det, samla sedan \(15\):orna och \(17\):orna:
Så \(x = 8\), \(y = -7\). Kontroll: \(15 \cdot 8 + 17 \cdot(-7) = 120 - 119 = 1\). ✓
Rytmen är alltid densamma: isolera delaren, och ersätt sedan upprepade gånger den senaste resten med raden ovanför, och håll allt i termer av de två ursprungliga talen.
Linjära diofantiska ekvationer¶
En diofantisk ekvation är en där lösningarna måste vara heltal — inga bråk tillåtna. Den linjära sorten ser ut som \(ax + by = c\).
Första frågan: har den överhuvudtaget en lösning? Notera att vänsterledet \(ax + by\) alltid är en multipel av \(\gcd(a,b)\) (eftersom delaren delar både \(a\) och \(b\)). Så om \(\gcd(a,b)\) inte delar \(c\) finns inget hopp. Anmärkningsvärt nog är det det enda hindret:
Lösbarhetskriterium
\(ax + by = c\) har heltalslösningar om och endast om \(\gcd(a, b) \mid c\).
Receptet¶
- Beräkna \(d = \gcd(a, b)\) med Euklides algoritm. Om \(d \nmid c\), sluta — det finns inga lösningar.
- Använd den utvidgade algoritmen för att skriva \(d = ax_0' + by_0'\).
- Skala upp med \(c/d\) för att få en faktisk lösning \((x_0, y_0)\) till \(ax + by = c\).
- Få alla lösningar genom att lägga till "gör-ingenting"-dragen — de ändringar av \(x\) och \(y\) som håller \(ax + by\) oförändrat:
Varför det sista steget är precis så. Om du höjer \(x\) med \(b/d\) och sänker \(y\) med \(a/d\) blir ändringen i \(ax + by\) lika med \(a \cdot \frac{b}{d} - b \cdot \frac{a}{d} = 0\) — den tar ut sig perfekt, så du landar på en annan lösning. Och \(b/d\) är den minsta höjning i \(x\) som kan uppvägas av en heltalsändring i \(y\), så att stega med \(k\) kopior av den sveper ut varje lösning.
Det klassiska felet: att glömma dividera med \(d\)
Att använda steglängd \(b\) i stället för \(b/d\) ger fortfarande giltiga lösningar — men det hoppar över några av dem, så din "allmänna lösning" blir ofullständig. Dividera alltid med den gemensamma delaren.
Tentamen (maj 2024, uppgift 1): \(15x + 17y = 20\)
Lösbar? \(\gcd(15, 17) = 1\), och \(1 \mid 20\), så ja.
En lösning. Från det genomräknade exemplet ovan är \(1 = 15 \cdot 8 + 17 \cdot (-7)\). Multiplicera igenom med \(20\) för att träffa högerledet:
så \((x_0, y_0) = (160, -140)\).
Alla lösningar. Här är \(d = 1\), så stegen är \(b/d = 17\) och \(a/d = 15\):
(Samma mängd, bara skriven med det oskalade \(8\) och \(-7\) och faktorn \(20\) synlig.)
Tentamen (maj 2023, uppgift 2): icke-negativa lösningar till \(23x + 31y = 1000\)
När en uppgift specifikt ber om icke-negativa lösningar, gör det vanliga för att få hela familjen, och begränsa sedan \(k\). Kräv \(x \geq 0\) och \(y \geq 0\) på den allmänna lösningen; var och en ger en olikhet på \(k\), och deras överlapp är ett ändligt intervall av \(k\)-värden. Räkna upp det intervallet — slutsvaret är en kort explicit lista av par, inte en oändlig familj. (Uppställningen är samma recept; den enda nya färdigheten är att göra två olikheter till ett intervall och lista det.)
Modulär aritmetik¶
Modulär aritmetik är "klockaritmetik": vi bryr oss bara om rester. Vi skriver \(a \equiv b \pmod n\) ("\(a\) är kongruent med \(b\) mod \(n\)") för att mena \(n \mid (a - b)\) — att \(a\) och \(b\) lämnar samma rest vid division med \(n\).
Detta är en av de ekvivalensrelationer från föregående kapitel: den sorterar heltalen i \(n\) hinkar efter rest, och de hinkarna är elementen i \(\mathbb{Z}_n\). Allt du gör "mod \(n\)" är egentligen aritmetik på hinkarna.
Inverser¶
I vanlig aritmetik betyder att dividera med \(a\) att multiplicera med \(1/a\). Mod \(n\) finns inga bråk, så att "dividera med \(a\)" betyder att multiplicera med en invers — ett tal \(a^{-1}\) med \(a \cdot a^{-1} \equiv 1 \pmod n\). Inte varje \(a\) har en:
När finns en invers?
\(a\) har en invers mod \(n\) om och endast om \(\gcd(a, n) = 1\) (de saknar gemensam faktor).
Hur man hittar den. Lös \(ax + ny = 1\) med utvidgade Euklides algoritmen (möjligt just för att \(\gcd(a,n) = 1\)). Då är \(ax = 1 - ny \equiv 1 \pmod n\), så \(x\) är inversen. Elementen som har inverser bildar en grupp under multiplikation, skriven \(\mathbb{Z}_n^{\times}\).
En genväg värd att se: \((n-1)^{-1} \bmod n\)
Notera \(n - 1 \equiv -1 \pmod n\). Så \((n-1)^2 \equiv (-1)^2 = 1\). Ett element vars kvadrat är \(1\) är sin egen invers, så \((n-1)^{-1} = n - 1\) utan att någon algoritm behövs. Till exempel \(89^{-1} \equiv 89 \pmod{90}\).
Håll ögonen öppna för "kvadrerar till \(1\)" — det kollapsar en inversberäkning till ingenting, och det dyker upp i RSA-uppgifter hela tiden.
Att lösa linjära kongruenser¶
\(ax \equiv b \pmod n\) är den modulära kusinen till \(ax = b\). Hur den beter sig beror helt på \(d = \gcd(a, n)\):
| Fall | Vad som händer | Varför |
|---|---|---|
| \(d \nmid b\) | Inga lösningar | \(ax\) är alltid en multipel av \(d\); om \(b\) inte är det kan du inte matcha det |
| \(d = 1\) | Exakt en lösning: \(x \equiv a^{-1} b\) | \(a\) är inverterbart, så multiplicera bara båda led med \(a^{-1}\) |
| \(d \mid b\), \(d > 1\) | \(d\) lösningar mod \(n\) | dividera hela kongruensen med \(d\) och lös mod \(n/d\) |
Trippeldrillen \(6x \equiv 4 \pmod 7\), \(3x \equiv 4 \pmod 8\), \(6x \equiv 4 \pmod 9\) är byggd för att marschera dig genom alla tre fallen i rad — räkna ut vilket fall var och en är innan du löser.
Fermats lilla sats¶
Fermats lilla sats
Om \(p\) är ett primtal och \(p \nmid a\), så är
Vad den är till för. Den tämjer enorma exponenter. Eftersom \(a^{p-1} \equiv 1\) cyklar potenser av \(a\) med en period som delar \(p - 1\) — så för att beräkna \(a^{k} \bmod p\) kan du först reducera exponenten \(k\) modulo \(p - 1\). En gigantisk exponent blir en liten. (Detta är också motorn som får RSA-dekryptering att fungera, nedan.)
Snabb modulär exponentiering¶
För att beräkna något som \(a^k \bmod n\) för hand utan att talen exploderar, använd upprepad kvadrering och reducera vid varje steg:
- Skriv exponenten \(k\) i binär form (som en summa av tvåpotenser).
- Bygg upp \(a^{2}, a^{4}, a^{8}, \dots\) genom att kvadrera den föregående, med reduktion mod \(n\) varje gång så att talen hålls små.
- Multiplicera ihop de bitar du behöver.
Långsamt genomräknat: \(2^{11} \bmod 35\)
Steg 1 — exponenten i binär form. \(11 = 8 + 2 + 1\), så \(2^{11} = 2^{8} \cdot 2^{2} \cdot 2^{1}\).
Steg 2 — bygg potenserna, med reduktion allteftersom:
Steg 3 — multiplicera de bitar som behövs (\(2^8 \equiv 11\), \(2^2 = 4\), \(2^1 = 2\)):
Gyllene regeln: reducera mod \(n\) innan du multiplicerar vidare, aldrig efter — det är det som håller varje mellanresultat under \(n^2\) och aritmetiken görbar för hand. (Sanitetstest: \(2^{10} = 1024 \equiv 9 \pmod{35}\), och \(9 \cdot 2 = 18\). ✓)
RSA-kryptosystemet¶
Skala bort säkerhetsberättelsen och RSA är bara Fermats lilla sats förvandlad till ett protokoll. Varje tentamen ställer i grunden samma fyrdelade fråga, så lär dig dragen en gång.
Uppställningen i ett andetag: två personer vill skicka hemliga meddelanden. Mottagaren publicerar ett "lås" som alla kan använda (\(n\) och \(e\)) men håller "nyckeln" hemlig (\(d\)). Vem som helst kan kryptera; bara den som har \(d\) kan dekryptera.
Nyckelgenerering¶
- Välj två distinkta primtal \(p\) och \(q\).
- Beräkna \(n = pq\) och \(m = (p-1)(q-1)\).
- Välj en krypteringsnyckel \(e\) med \(\gcd(e, m) = 1\) (så att \(e\) har en invers mod \(m\)).
- Beräkna dekrypteringsnyckeln \(d\) som den inversen: \(ed \equiv 1 \pmod m\).
Den publika nyckeln är paret \((n, e)\) — tryggt att ropa ut från taken. Den privata nyckeln är \(d\). Avgörande: \(p\), \(q\) och \(m\) måste hållas hemliga: den som får reda på \(m\) kan beräkna \(d\) direkt och läsa allt.
Kryptering och dekryptering¶
Modulerna är olika — detta är misstag nummer 1
Meddelanden upphöjs till potenser mod \(n\), men nycklarna \(e, d\) är inverser mod \(m\). Två olika moduler i ett problem. När du beräknar \(d\) arbetar du mod \(m\); när du krypterar eller dekrypterar arbetar du mod \(n\). Håll dem åtskilda.
Tentamen (maj 2024, uppgift 3): RSA med \(p = 5\), \(q = 7\)
Först parametrarna: \(n = 5 \cdot 7 = 35\) och \(m = (5-1)(7-1) = 4 \cdot 6 = 24\).
(a) Vilket villkor måste \(e\) uppfylla, och vad är minsta giltiga \(e\) i \(10 \le e \le 15\)? Villkoret är \(\gcd(e, m) = \gcd(e, 24) = 1\). Testa intervallet: \(10, 12, 14\) är jämna (delar faktorn \(2\) med \(24\)); \(15\) delar faktorn \(3\). Den som blir kvar är \(e = 11\). ✓
(b) Hitta dekrypteringsnyckeln \(d\). Vi behöver \(11d \equiv 1 \pmod{24}\). Pröva kvadrerar-till-\(1\)-genvägen: \(11^2 = 121 = 5 \cdot 24 + 1 \equiv 1 \pmod{24}\). Så \(11\) är sin egen invers och \(d = 11\).
(c) Kryptera \(a = 2\). Beräkna \(2^{e} = 2^{11} \bmod 35\). Med \(2^8 \equiv 11\) från exponentieringsexemplet:
Det krypterade meddelandet är \(18\).
(d) Hur dekrypterar man? Återvinn meddelandet som \(x \equiv y^{d} \bmod 35\) — du ombeds ange formeln, inte mala igenom den.
Den publicerade lösningen har ett skrivfel här
Den officiella lösningen skriver detta som \(2^{13} = 2^8 \cdot 2^4 \cdot 2 \equiv 11 \cdot 4 \cdot 2 \equiv 18\). Två saker är feletiketterade: exponenten ska vara \(11\) (det \(e\) från (a)), inte \(13\), och \(2^4 = 16\), inte \(4\). Faktorerna \(11 \cdot 4 \cdot 2\) är egentligen \(2^8 \cdot 2^2 \cdot 2^1 = 2^{11}\), så slutsvaret \(18\) är korrekt — bara etiketterna är fel. (För protokollet: \(2^{13} \equiv 2 \pmod{35}\).)
Lärdomen: lösningsförslag är inte evangelium. Om din uträkning inte stämmer med ett, kontrollera den igen innan du antar att det är du som har fel.
Varför dekryptering faktiskt återvinner meddelandet
Dekryptering beräknar \(y^d \equiv (x^e)^d = x^{ed} \pmod n\). Eftersom \(ed \equiv 1 \pmod m\) har vi \(ed = 1 + km\) för något \(k\), så \(x^{ed} = x \cdot (x^{m})^{k}\). Fermats lilla sats (tillämpad på primtalen \(p\) och \(q\) var för sig) ger \(x^{m} \equiv 1\), vilket kollapsar svansen och lämnar bara \(x\). Kan du rekonstruera den kedjan glömmer du aldrig vilken modul som är vilken — för det är Fermats sats som tvingar \(m = (p-1)(q-1)\) att vara exponentens modul.