Når man krypterer en tekst med RSA-krypteringsmetoden, så krypterer man teksten ved brug af en nøgle. Den krypterede tekst sendes så til modtageren. Modtageren dekrypterer det vedkommende har modtaget, og står tilbage med den oprindelige tekst.
I RSA-kryptering har en person en privat nøgle og en offentlig nøgle. Den private nøgle holder personen for sig selv. Den offentlige nøgle kan offentliggøres.
Hvis man f.eks. skal sende en besked til banken, så henter man bankens offentlige nøgle. Man krypterer så beskeden ved brug af den offentlige nøgle. Så sender man den krypterede besked til banken. Når banken har modtaget den krypterede besked, så dekrypterer de den med deres private nøgle, og de kan så læse beskeden. Man så at sig ‘låser beskeden’ med den offentlige nøgle, og man ‘låser beskeden op’ med den private nøgle.
Principperne bag RSA-kryptering
Man finder først to store primtal \(p\) og \(q\).
Man ganger de to primtal med hinanden, resultatet kalder man \(n\) :
\( n = p \cdot q \)Beregn så størrelsen \(\varphi(n)\)
\(\varphi(n) = (p-1) \cdot (q-1)\)Find et tal \(e\) som er primisk med \(\varphi(n)\).
Da \(e\) og \(\varphi(n)\) er primiske, så vil man, med Euklids ‘omvendte algoritme’, kunne bestemme to tal \(d\) og \(k\), således at
\(e \cdot d + k \cdot \varphi(n) = 1 \)Den private nøgle er så talparret \((d,n)\).
Den offentlige nøgle er talparret \((e,n)\).
Du tager nu din meddelelse \(m\). Beregn størrelsen
\(c = m^e \mod n\)Dette er den krypterede meddelelse.
Du sender den krypterede meddelelse til modtageren. Modtageren beregner så værdien
\(c^d \mod n\)Dette giver den oprindelige meddelelse \(m\).
For at gøre rede for hvorfor vi ender med den oprindelige meddelelse, så skal vi bruge Euler-Fermats sætning som siger, at er \(m\) og \(n\) indbyrdes primiske, så er
\(m^{\varphi(n)} = 1 \mod n\)Dermed har vi at
\((m^e)^d = m^{ed} = m^{1-k \cdot \varphi(n)} = m \cdot m^{-k \cdot \varphi(n)} \newline \qquad \quad = m \cdot (m^{\varphi(n)})^{-k} = m \cdot 1^{-k} = m \mod n \)