RSA-krypto

Antag att ett kommunikationssystem (t.ex. www) har ett stort antal användare som vill kunna kommunicera med varandra på ett säkert sätt. Ett säkert sätt betyder:

1.

om B kommunicerar med A ska A vara säker på att det är just B som kommunicerar,

2.

att en annan användare C som avlyssnar kommunikationen inte ska kunna förstå den.

Vi ska anta att kommunikationen försiggår genom att man sänder icke-negativa heltaltal m mindre än ett fixt heltal N.

Varje användare A väljer två extremt stora primtal p och q större än N och sätter n_A=pq.

Hon väljer också (slumpmässigt) ett heltal s_A relativt prima med $\phi(pq)=(p-1)(q-1).$

Hon tillkänna ger (n_A,s_A)(=(n,s)) för alla användare genom att göra paret allmänt tillgängligt i sitt bibliotek.

Om B vill sända meddelandeenheten m till A gör han på följande vis:

1. han tittar i A:s bibliotek och finner (n,s),

2. han beräknar $k\equiv m^{s}\mbox{ mod }n$

(beräkning av potenser modulo n går att göra snabbt (med en dator))

2. han skickar k till A.

För att förstå vad B vill gör A på följande vis:

1.hon beräknar (en gång för alla) en invers t_A till s_A modulo $\phi(n)=(p-1)(q-1)$ med hjälp av Euklides algoritm (går blixt snabbt med en dator),

2. hon beräknar k^t modulo n

Eftersom m är mindre än såväl p som q är m och n=pq relativt prima. Enligt Eulers sats gäller att

$$m^{\phi(n)}\equiv 1\mbox{ mod }n$$

Eftersom

$$st\equiv 1\mbox{ mod }\phi(n)\mbox{ dvs }st=l\phi(n)+1$$

för något heltal l, har vi

$$k^{t}\equiv (m^{s})^{t}\equiv (m^{\phi(n)})^{l}m\equiv m\mbox{ mod }n.$$

A kan alltså förstå vad B kommunicerar.

Varför kan en annan användare C inte förstå kommunikationen från B till A? För att få tillbaka m från k är ju det enda som behövs kännedom om inversen t_A till s_A modulo $\phi(n_{A})$.

Men det enda kända sättet att bestämma t_A är att bestämma den med Euklides algoritm för största gemensamma delaren till s_A och $\phi(n_{A})$. För att göra detta krävs kännedom om $\phi(n_{A})$. För att beräkna $\phi(n_{A})$ krävs i sin tur kännedom om faktoriseringen av n som produkt av primtal. Och detta är extremt tidskrävande även för de bästa datorerna. I praktiken är det alltså omöjligt att bestämma t_A. Men för A är detta en enkel match eftersom hon känner till primtalsfaktoriseringen n_A=pq; det är ju hon själv som valt den.

Hur kan nu A vara säker på att det är B som kommunicerar med henne? Det kan ju lika gärna vara C som hon har på tråden.

För att klara detta kan man modifiera proceduren ovan på följande sätt:

1.

B beräknar inversen t_B till s_B modulo $\phi(n_{B})$(en gång för alla),

2.

han beräknar $m'\equiv m^{t_{B}}\mbox{ mod } n_{B}$

3.

han beräknar sedan $k\equiv (m')^{s_{A}}\mbox{ mod }n_{A}$

4.

han skickar k till A.

Mottagaren A gör å andra sidan följande:

1.

hon beräknar $m'\equiv k^{t_{A}}\mbox{ mod }n_{A}$

2.

hon tittar i B:s bibliotek och finner (n_B,s_B)

3.

hon beräknar $(m')^{s_{B}}\equiv (m^{t_{B}})^{s_{B}}\equiv m\mbox{ mod }n_{B}$

Om meddelandet går att förstå, kan hon känna sig säker på att det är just B som sänt det. Bara han kan beräkna inversen t_B till s_B modulo n_B