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.
Kinesiska restsatsen¶
Vad händer om du måste uppfylla flera kongruenser samtidigt, med olika moduler? Säg \(x \equiv 2 \pmod 3\) och \(x \equiv 3 \pmod 5\). Så länge modulerna saknar gemensam faktor finns det alltid en lösning, och den är entydig modulo produkten.
Kinesiska restsatsen (CRT)
Om \(m_1, m_2, \dots, m_r\) är parvis relativt prima (två godtyckliga saknar gemensam faktor), så har systemet
en lösning, och den är entydig modulo \(M = m_1 m_2 \cdots m_r\).
Varför entydig modulo \(M\). Om \(x\) och \(x'\) båda löser systemet är deras differens delbar med varje \(m_i\); eftersom \(m_i\) är parvis relativt prima är den delbar med produkten \(M\). Så två lösningar överensstämmer mod \(M\) — det finns precis en lösning i \(\{0, 1, \dots, M-1\}\).
Receptet¶
Den pålitliga handmetoden är successiv substitution — lös en kongruens, mata in den i nästa, upprepa. Ingen formel att minnas fel.
Löst i lugn takt: \(x \equiv 2 \pmod 3\), \(x \equiv 3 \pmod 5\), \(x \equiv 2 \pmod 7\)
Ta de två första. Från \(x \equiv 2 \pmod 3\), skriv \(x = 2 + 3t\). Sätt in i den andra:
Nu är \(3^{-1} \equiv 2 \pmod 5\) (eftersom \(3\cdot 2 = 6 \equiv 1\)), så \(t \equiv 2 \pmod 5\), dvs. \(t = 2 + 5s\). Substituera tillbaka:
Väv in den tredje. Sätt in \(x = 8 + 15s\) i \(x \equiv 2 \pmod 7\):
där \(15 \equiv 1\) och \(8 \equiv 1 \pmod 7\). Så \(s = 1 + 7u\), och
Kontroll: \(23 = 3\cdot7+2\), \(23 = 4\cdot5+3\), \(23 = 3\cdot7+2\) — alla tre gäller. ✓ Och \(105 = 3\cdot5\cdot7 = M\), precis den utlovade modulen.
Parvis relativt prima är hypotesen — kontrollera den först
Om två moduler delar en faktor kan systemet sakna all lösning (t.ex. \(x \equiv 0 \pmod 2\) och \(x \equiv 1 \pmod 4\) är omöjligt) eller ha en mindre lösningsmängd. CRT som formulerad kräver att modulerna är parvis relativt prima; verifiera det innan du veva. Detta är också varför RSA tar \(n = pq\) med \(p \neq q\) distinkta primtal — det är CRT med två relativt prima moduler under ytan.
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.)
Eulers sats och totienten¶
Fermats sats kräver en prim modul. Eulers sats är versionen för vilken modul som helst, och den är vad som faktiskt underbygger RSA (där modulen \(n = pq\) är sammansatt). Priset för att släppa "prim" är att \(p - 1\) ersätts av en räkning:
Eulers totientfunktion
\(\varphi(n)\) är antalet heltal i \(\{1, \dots, n\}\) som är relativt prima till \(n\) — precis storleken på enhetsgruppen \(\mathbb{Z}_n^{\times}\). Två fakta beräknar den:
- För ett primtal \(p\): \(\varphi(p) = p - 1\) (allt under \(p\) är relativt primt till det).
- \(\varphi\) är multiplikativ för relativt prima argument: \(\varphi(mn) = \varphi(m)\varphi(n)\) när \(\gcd(m,n) = 1\).
Så för \(n = pq\) med \(p, q\) distinkta primtal är \(\varphi(n) = (p-1)(q-1)\) — vilket är precis talet \(m\) från RSA-nyckelgenereringen.
Eulers sats
Om \(\gcd(a, n) = 1\), så är
Fermats lilla sats är specialfallet \(n = p\) primt, där \(\varphi(p) = p-1\).
Vad den ger dig. Precis vad Fermat gjorde, men för vilken modul som helst: för att beräkna \(a^k \bmod n\) med \(\gcd(a,n)=1\), reducera först exponenten \(k\) modulo \(\varphi(n)\). Och den förklarar RSA på en rad — dekryptering upphöjer till potensen \(ed\), där \(ed \equiv 1 \pmod{\varphi(n)}\), så \(a^{ed} = a^{1 + t\varphi(n)} \equiv a \pmod n\) enligt Euler.
Löst: sista två siffrorna i \(7^{803}\)
"Sista två siffrorna" betyder mod \(100\). Eftersom \(\gcd(7, 100) = 1\) gäller Euler. Beräkna totienten: \(100 = 2^2 \cdot 5^2\), så
Reducera exponenten mod \(40\): \(803 = 20\cdot 40 + 3\), så \(803 \equiv 3 \pmod{40}\), alltså
De sista två siffrorna är 43 — ingen gigantisk potens beräknades någonsin. (För en primtalspotens som \(\varphi(25)\) är formeln \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)\), vilket ger \(25 - 5 = 20\).)
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.