RSA-algoritmen | algoritm som används för att kryptera och dekryptera meddelanden

Begrepp som används

RSA använder ett antal begrepp från kryptografin:

• En enkelriktad funktion som är lätt att beräkna; det är mycket svårt att hitta en funktion som vänder den, eller att beräkna denna funktion.
• RSA använder ett koncept som kallas diskret logaritm. Det fungerar ungefär som den vanliga logaritmen: Skillnaden är att endast hela tal används, och i allmänhet är det en modulusoperation som används. Som exempel kan nämnas a^x =b, modulo n. Den diskreta logaritmen handlar om att hitta det minsta x som uppfyller ekvationen när a b och n anges.
• Den kan eventuellt motverkas av Shors algoritm.

 

Generering av nycklar

Nycklarna för RSA-algoritmen genereras på följande sätt:

1. Välj två olika stora slumpmässiga primtal p {\displaystyle p} och q {\displaystyle q} . Detta bör hållas hemligt.
2. Beräkna n = p q {\displaystyle n=pq} .
• n {\displaystyle n} är modulen för den offentliga nyckeln och de privata nycklarna.
3. Beräkna totiten: ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
4. Välj ett heltal e {\displaystyle e} så att 1 < e < ϕ ( n ) {\displaystyle 1<e<\phi (n)} , och e {\displaystyle e} är lika med ϕ ( n ) {\displaystyle \phi (n)} .
   Det vill säga: e {\displaystyle e} och ϕ ( n ) {\displaystyle \phi (n)} delar inga andra faktorer än 1 {\displaystyle 1} : gcd ( e , ϕ ( n ) ) = 1 {\displaystyle \gcd(e,\phi (n))=1} ; Se största gemensamma divisorn.
• e {\displaystyle e} släpps som exponent för den offentliga nyckeln.
5. Beräkna d {\displaystyle d} för att uppfylla kongruensförhållandet d e ≡ 1 ( mod ϕ ( n ) ) {\displaystyle de\equiv 1\!\!\!\!\!{\pmod {\phi (n)}}} .
   Dvs. d e = 1 + x ⋅ ϕ ( n ) {\displaystyle de=1+x\cdot \phi (n)} för något heltal x {\displaystyle x} . (Enkelt uttryckt: Beräkna d = ( 1 + x ⋅ ϕ ( n ) ) / e {\displaystyle d=(1+x\cdot \phi (n))/e} för att vara ett heltal).
• d {\displaystyle d} behålls som exponent för den privata nyckeln.

Anteckningar om ovanstående steg:

• Steg 1: Tal kan testas på sannolikhetsmässiga grunder för primalitet.
• Steg 3: Ändrat i PKCS#1 v2.0 till λ ( n ) = l c m ( p - 1 , q - 1 ) {\displaystyle \lambda (n)={\rm {lcm}}(p-1,q-1)} i stället för ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
• Steg 4: Ett populärt val för de offentliga exponenterna är e = 2 16 + 1 = 65537 {\displaystyle e=2^{16}+1=65537} . Vissa tillämpningar väljer mindre värden som e = 3 {\displaystyle e=3} , 5 {\displaystyle 5} eller 35 {\displaystyle 35} i stället. Detta görs för att göra kryptering och signaturverifiering snabbare på små enheter som smartkort, men små offentliga exponenter kan leda till större säkerhetsrisker.
• Steg 4 och 5 kan utföras med den utvidgade euklidiska algoritmen [en]; se modulär aritmetik.

 Den offentliga nyckeln består av modulus n {\displaystyle n\,} och den offentliga (eller krypterings) exponenten e {\displaystyle e\,} .
Den personliga nyckeln består av p,q och den privata (eller dekrypterings) exponenten d {\displaystyle d\,} som måste hållas hemlig.

• Av effektivitetsskäl kan en annan form av den privata nyckeln lagras:
• p {\displaystyle p} och q {\displaystyle q} : primtalen från nyckelgenereringen;
• d mod ( p - 1 ) {\displaystyle d{\bmod {(}}p-1)} och d mod ( q - 1 ) {\displaystyle d{\bmod {(}}q-1)} : ofta kallade dmp1 och dmq1;
• q - 1 mod p {\displaystyle q^{-1}{\bmod {p}}}} : kallas ofta iqmp.
• Alla delar av den privata nyckeln måste hållas hemliga i denna form. p {\displaystyle p\,} och q {\displaystyle q\,} är känsliga eftersom de är faktorerna till n {\displaystyle n\,} , och gör det möjligt att beräkna d {\displaystyle d\,} givet e {\displaystyle e\,} . Om p {\displaystyle p\,} och q {\displaystyle q\,} inte lagras i denna form av den privata nyckeln raderas de på ett säkert sätt tillsammans med andra mellanliggande värden från nyckelgenereringen.
• Även om denna form möjliggör snabbare dekryptering och signering med hjälp av det kinesiska restsatsen (CRT) är den betydligt mindre säker eftersom den möjliggör sidokanalattacker [en]. Detta är ett särskilt problem om det genomförs på smarta kort, som gynnas mest av den förbättrade effektiviteten. 
  (Börja med y ≡ x e ( mod n ) {\displaystyle y\equiv x^{e}\!\!\!\!\!{\pmod {n}}}} och låt kortet dekryptera det. Så det beräknar ( y d mod p ) {\displaystyle (y^{d}{\bmod {p}})} eller ( y d mod q ) {\displaystyle (y^{d}{\bmod {q}})} vars resultat ger ett visst värde z {\displaystyle z} . Gör nu ett fel i en av beräkningarna. Då kommer gcd ( z - x , n ) {\displaystyle \gcd(z-x,n)} att avslöja p {\displaystyle p} eller q {\displaystyle q} .)

 

Kryptering av meddelandet

Alice ger sin offentliga nyckel ( n , e ) {\displaystyle (n,e)} till Bob och håller sin privata nyckel hemlig. Bob vill skicka meddelandet M {\displaystyle M} till Alice.

Först förvandlar han M {\displaystyle M} till ett antal m {\displaystyle m} som är mindre än n {\displaystyle n} med hjälp av ett överenskommet reversibelt protokoll, ett så kallat paddingschema. Han beräknar sedan den chiffertext c {\displaystyle c\,} som motsvarar:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

Detta kan göras snabbt med hjälp av exponentiering genom kvadrering. Bob skickar sedan c {\displaystyle c\,} till Alice.

 

Dekryptering av meddelandet

Alice kan återskapa m {\displaystyle m\,} från c {\displaystyle c\,} genom att använda sin privata nyckel d {\displaystyle d\,} enligt följande förfarande:

Givet m {\displaystyle m\,} , kan hon återfå de ursprungliga primtalen genom att tillämpa den kinesiska restsatsen på dessa två kongruenser.

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Således,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Därför:

m = c d m o d n {\displaystyle m=c^{d}\ mod\ n}

Ett fungerande exempel

Här är ett exempel på RSA-kryptering och dekryptering. Primtalen som används här är för små för att vi ska kunna kryptera något på ett säkert sätt. Du kan använda OpenSSL för att generera och undersöka ett riktigt nyckelpar.

1. Välj två slumpmässiga primtal p {\displaystyle p} och q {\displaystyle q\,} :

p = 61 {\displaystyle p=61} och q = 53 {\displaystyle q=53\,} ;

2. Beräkna n = p q {\displaystyle n=pq\,} :

n = 61 × 53 = 3233 {\displaystyle n=61\times 53=3233\!} ;

3. Beräkna totiten ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} :

ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120\!} ;

4. Välj e > 1 {\displaystyle e>1} som är lika med 3120 {\displaystyle 3120\,} :

e = 17 {\displaystyle e=17\,} ;

5. Välj d {\displaystyle d\,} så att e d ≡ 1 mod ϕ ( n ) {\displaystyle ed\equiv 1{\bmod {\phi (n)}}} :

d = 2753 {\displaystyle d=2753\,} , med 17 × 2753 = 46801 = 1 + 15 × 3120 {\displaystyle 17\times 2753=46801=1+15\times 3120} .

 Den offentliga nyckeln är ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). För ett uppstoppat meddelande m {\displaystyle m\,} blir krypteringsfunktionen c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} :

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}}233\,}

Den privata nyckeln är ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Dekrypteringsfunktionen m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} blir:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}}233\,}

 Till exempel, för att kryptera m = 123 {\displaystyle m=123} beräknar vi

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}

För att dekryptera c = 855 {\displaystyle c=855} Vi beräknar

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Båda dessa beräkningar kan beräknas snabbt och enkelt med hjälp av algoritmen för modulär exponentiering genom att kvadrera och multiplicera.

 

Avledning av RSA-ekvationen från Eulers sats

RSA kan enkelt härledas med hjälp av Eulers sats och Eulers totientfunktion.

Vi börjar med Eulers sats,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

Vi måste visa att om vi dekrypterar ett krypterat meddelande med rätt nyckel får vi fram det ursprungliga meddelandet. Givet ett uppstoppat meddelande m, beräknas chiffertexten c genom att

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}

Genom att ersätta dekrypteringsalgoritmen får vi följande

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}

Vi vill visa att detta värde också är kongruent med m. Värdena för e och d har valts så att de uppfyller kraven,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

Det vill säga, det finns ett heltal k som gör att

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Nu ersätter vi det krypterade och sedan det dekrypterade meddelandet,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}

Vi tillämpar Eulers sats och får resultatet.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

 

System för utfyllnad

När RSA används i praktiken måste det kombineras med någon form av utfyllnadssystem, så att inga värden på M leder till osäkra chiffertexter. RSA kan ha vissa problem om det används utan padding:

• Värdena m = 0 eller m = 1 ger alltid chiffertexter som är lika med 0 respektive 1, på grund av exponentieringens egenskaper.
• Vid kryptering med små krypteringsexponenter (t.ex. e = 3) och små värden på m kan det (icke-modulära) resultatet av m e {\displaystyle m^{e}}} vara strikt mindre än modulus n. I detta fall kan chiffertexter lätt dekrypteras genom att man tar den etiska roten av chiffertexten utan hänsyn till modulus.
• RSA-kryptering är en deterministisk krypteringsalgoritm. Den har ingen slumpmässig komponent. Därför kan en angripare framgångsrikt genomföra en attack mot kryptosystemet genom att välja en klartext. De kan skapa en ordbok genom att kryptera sannolika klartexter med den offentliga nyckeln och lagra de resulterande chiffertexterna. Angriparen kan sedan observera kommunikationskanalen. Så snart de ser chiffertexter som matchar de som finns i deras ordbok kan angriparna använda denna ordbok för att få reda på innehållet i meddelandet.

I praktiken kan de två första problemen uppstå när korta ASCII-meddelanden skickas. I sådana meddelanden kan m vara en sammanfogning av ett eller flera ASCII-kodade tecken. Ett meddelande som består av ett enda ASCII NUL-tecken (vars numeriska värde är 0) skulle kodas som m = 0, vilket ger en chiffertext på 0 oavsett vilka värden på e och N som används. På samma sätt skulle ett enda ASCII SOH (vars numeriska värde är 1) alltid ge en chiffertext på 1. För system som konventionellt använder små värden på e, t.ex. 3, skulle alla ASCII-meddelanden med ett enda tecken som kodas med detta system vara osäkra, eftersom det största m skulle ha värdet 255, och 255³ är mindre än någon rimlig modul. Sådana klartexter skulle kunna återskapas genom att helt enkelt ta kubikroten av chiffertexten.

För att undvika dessa problem bäddar praktiska RSA-implementationer vanligtvis in någon form av strukturerad, slumpmässig utfyllnad i värdet m innan det krypteras. Denna fyllning säkerställer att m inte faller inom intervallet för osäkra klartexter och att ett givet meddelande, när det väl är fyllt, kommer att krypteras till ett av ett stort antal olika möjliga chiffertexter. Den sistnämnda egenskapen kan öka kostnaden för en ordboksattack så att en rimlig angripare inte har möjlighet att genomföra den.

Standarder som PKCS har noggrant utformats för att säkert fylla på meddelanden före RSA-kryptering. Eftersom dessa system fyller på den rena texten m med ett visst antal extra bitar måste storleken på det ofyllda meddelandet M vara något mindre. RSA-paddingsystem måste vara noggrant utformade för att förhindra sofistikerade attacker. Detta kan underlättas av en förutsägbar meddelandestruktur. I tidiga versioner av PKCS-standarden användes ad hoc-konstruktioner, som senare visade sig vara sårbara för en praktisk adaptiv attack med utvald chiffertext. Moderna konstruktioner använder säkra tekniker som optimal asymmetrisk krypteringspadding (OAEP) för att skydda meddelanden samtidigt som dessa attacker förhindras. PKCS-standarden har också bearbetningsscheman som är utformade för att ge ytterligare säkerhet för RSA-signaturer, t.ex. det probabilistiska signaturschemat för RSA (RSA-PSS).

 

Signering av meddelanden

Antag att Alice använder Bobs offentliga nyckel för att skicka ett krypterat meddelande till honom. I meddelandet kan hon hävda att hon är Alice, men Bob har inget sätt att kontrollera att meddelandet verkligen kommer från Alice eftersom vem som helst kan använda Bobs offentliga nyckel för att skicka krypterade meddelanden till honom. För att verifiera ett meddelandes ursprung kan RSA alltså också användas för att signera ett meddelande.

Anta att Alice vill skicka ett signerat meddelande till Bob. Hon tar fram ett hashvärde av meddelandet, höjer det till potensen d mod n (precis som när hon dekrypterar ett meddelande) och bifogar det som en "signatur" till meddelandet. När Bob tar emot det signerade meddelandet höjer han signaturen till potensen e mod n (precis som vid kryptering av ett meddelande) och jämför det resulterande hashvärdet med meddelandets faktiska hashvärde. Om de två stämmer överens vet han att upphovsmannen till meddelandet hade Alice hemliga nyckel och att meddelandet inte har manipulerats sedan dess.

Observera att säkra utfyllnadssystem som RSA-PSS är lika viktiga för säkerheten vid signering av meddelanden som för kryptering av meddelanden, och att samma nyckel aldrig bör användas för både kryptering och signering.