1. Eulers φ-funksjon via primtallsfaktorisering

Eulers φ-funksjon \(\varphi(n)\) teller hvor mange av tallene \(1,2,\dots,n\) som er relativt primiske til \(n\). Den er fundamentet for RSA fordi den styrer eksponentaritmetikken modulo \(N\).

Regneregler for φ:

For primtall: \(\varphi(p)=p-1\).

For primtallspotens: \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\).

Multiplikativ (kun for \(\gcd(m,n)=1\)): \(\varphi(mn)=\varphi(m)\varphi(n)\).

Generell produktformel: hvis \(n=p_1^{a_1}\cdots p_r^{a_r}\), så \(\varphi(n)=n\prod_i\left(1-\dfrac{1}{p_i}\right)\).

Eksempel: Beregn \(\varphi(360)\).

Faktoriser: \(360=2^3\cdot3^2\cdot5\)

\(\varphi(360)=360\left(1-\tfrac12\right)\left(1-\tfrac13\right)\left(1-\tfrac15\right)\)

\(=360\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45\)

\(=360\cdot\tfrac{8}{30}=96\)

2. RSA nøkkelgenerering: N=pq, φ(N), valg av e

RSA er et asymmetrisk kryptosystem: alle kan kryptere med den offentlige nøkkelen \((N,e)\), men bare innehaveren av \(d\) kan dekryptere.

Nøkkelgenerering (fire steg):

1. Velg to ulike primtall \(p,q\); sett \(N=pq\).

2. Beregn \(\varphi(N)=(p-1)(q-1)\).

3. Velg \(e\) med \(1

4. Beregn \(d\equiv e^{-1}\pmod{\varphi(N)}\).

Offentlig nøkkel: \((N,e)\). Privat: \(d\). Hemmelig: \(p,q,\varphi(N),d\).

Korrektheten følger av Eulers teorem: når \(\gcd(m,N)=1\) er \(m^{\varphi(N)}\equiv1\pmod N\). Siden \(ed\equiv1\pmod{\varphi(N)}\) er \(ed=1+k\varphi(N)\), og dermed \(c^d=m^{ed}=m\cdot(m^{\varphi(N)})^k\equiv m\pmod N\).

3. Finne dekrypteringseksponent d med modulær invers

Steg 4 over løses med utvidet Euklids algoritme, som gir heltall \(x,y\) slik at \(ex+\varphi(N)y=\gcd(e,\varphi(N))=1\). Da er \(d\equiv x\pmod{\varphi(N)}\).

Eksempel: For \(p=11,q=13\) er \(N=143,\ \varphi(N)=120\). Med \(e=7\), finn \(d\).

Vi løser \(7d\equiv1\pmod{120}\)

Utvidet Euklid: \(120=17\cdot7+1\)

Altså \(1=120-17\cdot7\)

Da \(d\equiv-17\equiv103\pmod{120}\)

Sjekk: \(7\cdot103=721=6\cdot120+1\;\checkmark\)

4. Kryptering/dekryptering med gjentatt kvadrering

Kryptering er \(c\equiv m^e\pmod N\) og dekryptering \(m\equiv c^d\pmod N\). Disse store potensene beregnes effektivt med gjentatt kvadrering (binær eksponentiering), som bruker \(O(\log k)\) modulære multiplikasjoner.

Gjentatt kvadrering:

1. Skriv eksponenten binært.

2. Beregn suksessive kvadrater \(a,a^2,a^4,a^8,\dots\bmod n\).

3. Multipliser sammen kvadratene som svarer til 1-bitene i eksponenten, og reduser \(\bmod n\) underveis.

Eksempel: Beregn \(7^{11}\bmod 13\).

\(11=1011_2=8+2+1\)

\(7^1\equiv7,\quad 7^2\equiv49\equiv10\)

\(7^4\equiv10^2=100\equiv9\)

\(7^8\equiv9^2=81\equiv3\)

\(7^{11}\equiv7^8\cdot7^2\cdot7^1\equiv3\cdot10\cdot7=210\equiv2\pmod{13}\)

5. Faktorisering ved p≈q (Fermat) og Håstads kringkastingsangrep

RSA er bare sikkert ved gode parametervalg. To klassiske angrep illustrerer fallgruvene.

Fermats faktorisering: Skriv \(N=a^2-b^2=(a-b)(a+b)\). Start med \(a=\lceil\sqrt N\rceil\) og øk \(a\) til \(a^2-N\) er et perfekt kvadrat \(b^2\). Effektiv når \(p\approx q\).

Håstads angrep: Samme \(m\) (uten polstring) kryptert med lik lav \(e\) (typisk 3) til \(e\) ulike moduli. CRT gir \(m^e\) over heltallene; ta \(e\)-te rot for å finne \(m\).

Eksempel (Fermat): Faktoriser \(N=8051\).

\(\lceil\sqrt{8051}\rceil=90\)

\(90^2-8051=8100-8051=49=7^2\)

Perfekt kvadrat med en gang: \(b=7\)

\(N=(90-7)(90+7)=83\cdot97\)

Eksempel (Håstad, e=3): Tre mottakere med moduli \(N_1,N_2,N_3\) får samme \(m\).

Chiffertekster: \(c_i\equiv m^3\pmod{N_i}\)

CRT gir \(x\equiv m^3\pmod{N_1N_2N_3}\)

Siden \(m

Finn \(m=\sqrt[3]{x}\) (heltallskubikkrot)

Forsvar: Velg \(p,q\) godt adskilt (mot Fermat) og bruk tilfeldig polstring (mot Håstad/kubikkrot-angrep).

Studieguide: RSA og kryptografi

Studieguide: RSA og kryptografi