Kryptering med RSA (demo)

Mål

Syftet med denna sida är att visa steg för steg hur ett krypteringssystem med offentlig nyckel fungerar. Vi använder RSA-algoritmen (uppkallad efter uppfinnarna Rivest, Shamir, Adleman) med mycket små primtal. De grundläggande funktionerna är implementerade i JavaScript (välj "Visa källa" i webbläsaren).
Obs! Den här sidan är endast till för att förklara mekanismen. I praktiken används mer avancerade algoritmer och mycket större primtal!

Idén och det mesta av koden kommer från en sida på University Honors College (Oregon State), som inte längre finns kvar. En mer realistisk demo finns här.) )

Översikt

Att arbeta med ett krypteringssystem med offentlig nyckel har huvudsakligen tre faser:

Nyckelgenerering: Den som vill ta emot hemliga meddelanden skapar en offentlig nyckel (som publiceras) och en privat nyckel (hemlig). Nycklarna genereras på ett sätt som döljer deras konstruktion och gör det svårt att hitta den privata nyckeln om man bara känner till den offentliga nyckeln.
Kryptering: Ett hemligt meddelande till vilken person som helst kan krypteras med dennes offentliga nyckel (som kan offentliggöras, som en mailadress).
Dekryptering: Endast personen som meddelandet är avsett för kan enkelt dekryptera det hemliga meddelandet med den privata nyckeln.

RSA: Generera nycklar

Från två valda primtal genererar datorn den offentliga (publika) nyckeln och den privata nyckeln.

Välj två (olika) primtal: p = q =

n = (n = p∙q)

φ = (φ = φ(n) = (p-1)∙(q-1); behövs för att beräkna e och d)

e = (godtycklig, men mindre än n och relatvit prim till φ)

d = (inversen av e modulo φ: e∙d mod φ = 1)

Från talen ovan konstrueras nycklarna:

den publika nyckeln är paret (e,n).
the privata nyckeln är paret (d,n).

Det är bara den publika nyckeln som publiceras; alla andra tal (p,q,φ,d) måste hållas privata! Huvudegenskapen hos denna konstruktion är att det är svårt att beräkna d bara från siffrorna e och n (svårt i den meningen att beräkningen är mer och mer tidskrävande ju större tal är inblandade). Mer exakt:

Det är svårt att beräkna d utan att veta φ.
Det är svårt att faktorisera n till p∙q (vilket behövs för beräkning av φ).

RSA: Krypteringen

Först behöver vi den publika nyckeln för den person som vi vill skicka meddelandet till:
(e,n) = ( , ) (Mata in lämpliga värden eller )

Sen behöver vi själva meddelandet. För enkelhets skull demonstrerar vi här med enbart en bokstav. (I säkra applikationer krypteras bokstäver aldrig individuellt utan i hela block.)
Välj en bokstav att chiffrera:
Innan vi kan kryptera bokstaven måste vi :
m = (här väljer vi bara index i alfabetet)

i sig är mycket enkel: m' = (m' = m^e mod n)

Värdet m' är det krypterade meddelandet som skickas till mottagaren.

RSA Dekrypteringen

Först behöver vi mottagarens privata nyckel
(d,n) = ( , ) (Mata in lämpliga värden eller )

Sen behöver vi det krypterade meddelandet:
m' = (Mata in lämpligt värde eller )

är också enkel: m = (m = m'^d mod n)

Det ska matcha den bokstav du valde ovan