RSA

**RSA** er en krypteringsalgoritme basert på offentlig nøkkel (en.: *public key*).

## Drift
For å bruke RSA-algoritmen må den gjennom tre steg; generering av nøkkeltall, kryptering og dekryptering.

### Generering av nøkkeltall
* Mottaker finner fram to primtall som **<math>p</math>** og **<math>q</math>** og regner ut n=p\cdot q og b=(p-1)\cdot (q-1). For at dette skal bli tilstrekkelig sikkert må man velge to store primtall (over noen 100 siffer i hver).
* Nå velger mottaker et tall **<math>e</math>** slik at '''<math>sfd(e,b)=1</math>'''
* Tallene **<math>n</math>** og **<math>e</math>** kan nå offentliggjøres for at sender kan begynne kryptering. Dette er den offentlige nøkkelen (en.: public key).
* Kongruensen ed\equiv 1 \pmod{b} regnes nå ut, og det minste positive tallet velges til det hemmelige tallet **<math>d</math>**. (**<math>d</math>**= hemmelig dekrypteringsnøkkel).

### Kryptering
* Meldingen som skal sendes gjøres om til tall. La **<math>M</math>** være ett av tallene.
* Vi finner nå det minste positive tallet for **<math>N</math>**, slik at N \equiv M^e \pmod{n}. Resten ved divisjonen **<math>M^e:n</math>** er altså den hemmelige meldingen.
* Nå kan avsender sende **<math>N</math>** til mottaker.

### Dekryptering
* I dekrypteringsprosessen er **<math>M</math>** det minste positive tallet i M\equiv N^d \pmod{n}. Ved å finne resten av **<math>N^d:n</math>** kan man finne meldingen, **<math>M</math>**.

### Eksempel
#### Generering av nøkkeltall
Vi velger to primtall som **<math>p</math>** og **<math>q</math>**. 
 **<math>p=5</math>** og **<math>q=7</math>**

Vi finner *n* og *b*.
 n=p\cdot q=5\cdot 7=35
 b=(p-1)(q-1)=(5-1)(7-1)=4\cdot 6=24

Nå må vi finne en verdi for **<math>e 
</math>** slik at **[[Største felles divisor|<math>sfd(e,b)=1</math>]]**.
 Vi faktoriserer **<math>b</math>**.
 24=2\cdot 2\cdot 2\cdot 3 
 Nå velger vi et tall for **<math>e</math>**. Vi kan velge **<math>e=11</math>** siden **<math>11</math>** ikke finnes i **<math>24</math>**
 Vi ser at **<math>sfd(11,24)=1</math>**

Vi offentliggjør nøklene *n* og *e*, (e = encryption key)
 **<math>n=35</math>** og **<math>e=11</math>**

Nå må vi lage det hemmelige tallet **<math>d</math>**.
 ed\equiv 1 \pmod{b}
 11d\equiv 1 \pmod{24}
 11d\equiv 1+5\cdot 24 \pmod{24}
 11d\equiv 121 \pmod{24}
 11d\equiv 11\cdot 11 \pmod{24}
 d\equiv 11 \pmod{24}

 Det hemmelige tallet er dermed **<math>d=11 </math> (**d=decryption key)

**OBS:** **<math>e</math>** og **<math>d</math>** er ikke alltid like. Det er bare en tilfeldighet at de er like i dette eksemplet.

#### Kryptering
Vi mottar de offentlige nøklene **<math>e</math>** og **<math>n</math>**
 **<math>e=11</math>** og **<math>n=35</math>**

Meldingen **<math>M=8</math>** ønskes å bli sendt, men den må krypteres først.
For å finne **<math>N</math>**, den krypterte meldingen, gjør vi slik:
 N\equiv M^e \pmod{n}
 N\equiv 8^{11} \pmod{35}
 N\equiv 8589934592 \pmod{35}
 N\equiv 8589934592 - 245426702\cdot 35 \pmod{35}
 N\equiv 22 \pmod{35}

 Den hemmelige meldingen er **<math>N=22</math>**

#### Dekryptering
Vi mottar den krypterte meldingen **<math>N</math>**.
 **<math>N=22</math>**

Fra tidligere kjenner vi den hemmelige nøkkelen **<math>d</math>** og den offentlige nøkkelen **<math>n</math>**
 **<math>d=11</math>** og **<math>n=35</math>**

Vi ser at det er en sammenheng mellom **<math>N</math>**, **<math>d</math>** og **<math>n</math>** slik at vi kan finne **<math>M</math>**.
 M\equiv N^d \pmod{n}
 M\equiv 22^{11} \pmod{35}

For å få lettere tall å regne med så bruker vi litt kreativ regning. Vi ser på eksponenter av 22 som er lavere enn 11.
 22^1 = 22\equiv 22 \pmod{35}
 22^2 = 484\equiv 29 \pmod{35}
 22^4 = (22^2)^2\equiv 29^2\equiv 841\equiv 1 \pmod{35}
 22^8 = (22^4)^2\equiv 1^2\equiv 1 \pmod{35}

Vi ser at **<math>11=1+2+8</math>**
 22^1\cdot 22^2\cdot 22^8\equiv 22\cdot 29\cdot 1 \pmod{35}
 22^{1+2+8} \equiv 638 \pmod{35}
 22^{11} \equiv 638-18\cdot 35 \pmod{35}
 22^{11} \equiv 8 \pmod{35}

Vi har nå funnet den krypterte meldingen
 **<math>M=8</math>**

## Historie
Algoritmen ble først beskrevet i 1977 av Ron Rivest, Adi Shamir og Leonard Adleman ved MIT; de tre bokstavene **RSA** er initialene i etternavnene deres i samme rekkefølge som de fremkommer på artikkelen deres.

Den Britiske matematikeren Clifford Cocks beskrev et lignende system i et internt dokument for den britiske etterretningstjenesten GCHQ. Hans oppdagelse ble ikke offentliggjort før i 1997, grunnet top-secret klassifisering av arbeidet.

MIT fikk et patent på "Cryptographic communications system and method" som benyttet algoritmen i 1983. Patentet ville vært gyldig til 2003, men ble offentliggjort av RSA 21. september 2000.

## Referanser