Hoppa till huvudinnehållet
Logga inSkapa konto
4. Kongruenser och RSA

Kongruenser och RSA

Räkna med rester, modulära inverser och stora potenser.

Översikt

Kongruens handlar om skillnadens delbarhet

Två heltal är kongruenta ett positivt heltal när deras differens är delbar med detta tal. Addition, subtraktion och multiplikation respekterar . Division kräver däremot en inverterbar faktor. En invers finns precis när faktorn och modulen är . Den hittas med Euklides algoritm baklänges.

au≡1(modm)  ⟺  au+mv=1 fo¨r na˚got v∈Zau\equiv1\pmod m\iff au+mv=1\text{ för något }v\in\mathbb Z

Exempel

Exempel: reducera en stor potens

Beräkna resten när sju upphöjt till hundra delas med tretton. Tretton är primtal och delar inte sju, så Fermats lilla sats ger perioden tolv som en möjlig exponentreduktion. Hundra ger resten fyra vid division med tolv. Två kvadreringar räcker sedan för att finna resten nio.

7100≡74≡492≡102≡9(mod13)7^{100}\equiv7^4\equiv49^2\equiv10^2\equiv9\pmod{13}

Fördjupning

RSA och villkoren bakom exponenterna

I kursens RSA-modell väljs två olika primtal och deras produkt blir modulen. Krypteringsexponenten måste vara med produkten av vartdera primtalet minskat med ett. Dekrypteringsexponenten är dess modulära invers. Vid beräkning används upprepad kvadrering och reduktion efter varje steg. Fermats lilla sats kräver en primtalsmodul och ett tal som inte är delbart med primtalet; den får inte användas mekaniskt en sammansatt RSA-modul.

n=pq,m=(p−1)(q−1),ed≡1(modm),c≡ae(modn)n=pq,\quad m=(p-1)(q-1),\quad ed\equiv1\pmod m,\quad c\equiv a^e\pmod n

Formler i området

a−1(modm) finns  ⟺  gcd⁡(a,m)=1a^{-1}\pmod m\text{ finns}\iff\gcd(a,m)=1
Vad gör formeln?
Tillåter division med en faktor i en .
När får den användas?
Modulen är ett heltal större än ett.

Fermats lilla sats

p∤a⇒ap−1≡1(modp)p\nmid a\quad\Rightarrow\quad a^{p-1}\equiv1\pmod p
Vad gör formeln?
Reducerar stora exponenter primtal.
När får den användas?
Modulen är ett primtal som inte delar basen.

Kinesiska restsatsen

gcd⁡(m,n)=1 ⇒ {x≡a(modm)x≡b(modn) har en unik lo¨sning modulo mn\gcd(m,n)=1\ \Rightarrow\ \begin{cases}x\equiv a\pmod m\\ x\equiv b\pmod n\end{cases}\text{ har en unik lösning modulo }mn
Vad gör formeln?
Sätter samman restvillkor för olika moduler.
När får den användas?
Modulerna är positiva och .

RSA: nycklar och kryptering

n=pq,m=(p−1)(q−1),gcd⁡(e,m)=1,ed≡1(modm),c≡ae(modn)n=pq,\quad m=(p-1)(q-1),\quad\gcd(e,m)=1,\quad ed\equiv1\pmod m,\quad c\equiv a^e\pmod n
Vad gör formeln?
Kopplar kryptering och dekryptering genom inversa exponenter.
När får den användas?
Två olika primtal används. Dekrypteringsexponenten väljs positiv.

Hänger ihop med

Kan du använda kongruenser och rsa?

Lös en riktig tentauppgift från SF1662 med ledtrådar och lösningsförslag. Inget konto behövs.

Prova en uppgift