RSA-KEM

RSA-KEM ( RSA Key Encapsulation Method) är en enkelpassage (lagra och vidarebefordra) nyckelkrypteringsmekanism för överföring i kryptosystem med offentliga nyckel . Kombinerar falska permutationer av RSA och KDF (Key Derivation Function). Den har enkelhet och överlägsna skyddsegenskaper jämfört med OAEP eller OAEP+ . Den största nackdelen är att chiffertexten är något större än klartexten.

Beskrivning

Introduktion

RSA-KEM tillhör en klass av metoder för inkapsling av kryptografiska nyckel utformade för att säkert skicka symmetriska krypteringsnycklar med hjälp av algoritmer för offentliga nyckel [1] . I praktiken är krypteringssystem för offentliga nyckel obekväma för överföring av långa meddelanden, istället används de för utbyte av symmetriska nycklar, som i slutändan krypterar texten. Den traditionella metoden för att skicka en symmetrisk nyckel med offentliga nyckelsystem är följande algoritm:

  1. Generering av slumptal.
  2. Kryptering av ett nummer med den valda publika nyckeln. Detta krypterade meddelande skickas till mottagaren.
  3. Mottagaren dekrypterar den med den privata nyckeln och återställer den symmetriska nyckeln.

Den presenterade algoritmen har flera nackdelar [2] . För det första, eftersom den symmetriska nyckeln är liten, måste den förlängas och säkerhetsbeviset för nyckelförlängning är inte starkt. För det andra kan angriparen skicka sitt nummer krypterat med den offentliga nyckeln och utbyta meddelanden med mottagaren. För det tredje övervakas inte dataintegriteten (en generalisering av den andra punkten). Dessutom kan chifferna för liknande meddelanden vara liknande. Uppenbarligen är det presenterade schemat inte tillräckligt bra och tillförlitligt.

Nyckelinkapslingsmetoden visar en annan, mer avancerad metod som löser de identifierade problemen.

Krypteringsprocessen kan sammanfattas enligt följande:

  1. En slumpmässig ingång w genereras .
  2. Krypterad w med RSA för överföring till mottagaren.
  3. Nyckelmaterial y = KDF( w ) genereras för användning i efterföljande kryptering.

Mottagaren kan återhämta w från den mottagna chiffertexten och sedan generera y så att både sändare och mottagare kan komma överens om samma symmetriska nyckel.

Alternativ

Nyckelkrypteringsmekanismen har följande systemparametrar:

  1. RSAKeyGen: RSA-nyckelgenereringsalgoritm.
  2. KDF: En nyckelhärledningsfunktion.
  3. KeyLen: Ett positivt heltal.

Nyckelgenerering

Den publika nyckeln består av RSA-koefficienten , som är produkten av två stora primtal och exponenten , där (  är den största gemensamma delaren ) [3] . Den belyser också nyckelhärledningsfunktionen i KDF. Låt nLen beteckna längden av n i byte. Den hemliga nyckeln består av dekrypteringsexponenten d , där . Nyckelgenereringsalgoritmen tar inget som indata och exekveras enligt följande:

  1. Beräkning ( n , e , d ) = RSAKeyGen().
  2. Skaffa en publik nyckel PK (public key).
  3. Skaffa en privat nyckel pk (privat nyckel).

n , e , d  är positiva heltal.

Kryptering

Målet med krypteringsalgoritmen är att producera en pseudo-slumpmässig nyckel K med längden KeyLen och en chiffertext som krypterar K . Krypteringsalgoritmen accepterar följande:

  1. en publik nyckel som består av ett positivt heltal n och e .
  2. inga krypteringsalternativ.

Det görs på följande sätt [2] :

1) Ett slumptal genereras .

2) Krypterad med mottagarens publika nyckel

3) Numret konverteras till en krypterad sträng och till en sträng

4) En så kallad nyckelkrypterande nyckel (KEK) skapas, med längden , med hjälp av Key Derivation Function (KDF):

5) Den överförda informationen lindas in (i den engelska litteraturen WRAP) med en KEK-nyckel, med hjälp av ett nyckelomslagsschema. Vid utgången får vi den krypterade texten

6) Kombinera och chiffertext

är utdata från algoritmen

Key Generation Function (KDF)

KDF tar en bytesträng och ett heltal som indata . Till exempel funktionen KDF1. Den parametriseras av någon hashfunktion och definieras enligt följande [2] : argument går till ingången , vid utgången får vi de första byten av uttrycket:

|| || ... || || var

Tvillingen till KDF1 är KDF2. Den skiljer sig från KDF1 endast genom att räknaren går från till , inte från till . Det är dock svårt för dessa funktioner att fastställa hur "bra" pseudo-slumptalsgeneratorer de är. På grund av denna potentiella sårbarhet är det önskvärt att använda KDF3-funktionen, t.ex. Det tar som parametrar Hash och De första byten av uttrycket matas ut:

|| || · · · || , || var .

Rekommenderade hashfunktioner SHA1 och RIPMD-160. Rekommenderas . Tillförlitligheten hos KDF3 kan redan bedömas ganska säkert. Funktionen , som beskrivs i IEEE P1363-standarden, konverterar ett tal till en sträng. Dess arbete är baserat på funktionen , som tvärtom tar emot ett nummer från en sträng.

Key Wrapping Schema

RFC 5990- specifikationen kräver att något av följande används som omslagsschema:

  1. AES nyckelomslag
  2. Trippel-DES nyckelomslag
  3. Camillia nyckelomslag

Det vanligaste omslagsschemat är AES [4] . Den fungerar i block om 64 bitar och kräver ett meddelande som är längre än ett sådant block som indata. Om meddelandelängden är 64 bitar eller mindre bildar den specifikationsdefinierade konstanten och nyckelinformationen ett enda 128-bitars block, vilket är meningslöst.

Dekryptering

Dekrypteringsalgoritmen tar följande som indata:

  1. en privat nyckel som består av ett positivt heltal n och d .
  2. chiffertext .

Det utförs enligt följande:

  1. Separering av krypterad nyckelinformation i byte- längd chiffertext och omslagen nyckelinformation: Om längden på krypterad nyckelinformation skiljer sig från , misslyckas dekrypteringen.



  2. Konvertera chiffertexten till ett heltal och dekryptera den med mottagarens privata nyckel: Om inte inom , misslyckas dekrypteringen.




  3. Konvertera heltal till längdbytesträng



  4. Generera längdbytes från en sträng med KDF:



  5. Packa upp nyckelinformation med : Om uppackningen misslyckas, misslyckas hela algoritmen.



  6. Få utdata från algoritmen.

Tillförlitlighetsbedömning

Säkerheten för RSA-KEM kan analyseras i en slumpmässig orakelmodell (Random Oracle Model, nedan kallad RO) [2] . Kärnan i modellen är som följer. Anta att det finns någon offentlig funktion som har följande egenskaper:

  1. Funktionen svarar på varje nytt argument med ett nytt värde och skriver paret (argument, värde) till tabellen.
  2. Om argumentet redan har uppfyllts, kommer funktionen att vända sig till sin tabell och returnera värdet som motsvarar detta argument.

Beviset är baserat på antagandet att KDF är ett slumpmässigt orakel och att det är omöjligt att lösa det omvända RSA-problemet (med andra ord, RSA kan inte hackas). För alla nyckelgenereringsalgoritmer för RSA (det vill säga en algoritm som returnerar n, e och d), gäller alltid n >= nBound (det vill säga nBound är den minsta lagliga gränsen för n tal), och för varje angripare A, följande är sant:

+

var är det maximala antalet förfrågningar till oraklet som en angripare kan göra för att försöka lösa chiffret , AdvantageRSA-KEM(A) = |Pr[b*-b] - 1/2| — prediktiv förmåga A, AdvantageRSA(A') anger sannolikheten för att framgångsrikt lösa det omvända RSA-problemet. Det bör noteras att ovanstående ojämlikhet inte tar hänsyn till det faktum att den i verkligheten returnerar "dåliga" nycklar med en sannolikhet som inte är noll. För att ta hänsyn till det behöver du bara lägga till denna sannolikhet till höger sida av ojämlikheten.

Vi ger beviset genom att överväga spelsekvensen , och i varje spel gör motståndare A en attack. Vart och ett av dessa spel utspelar sig i samma sannolikhetsutrymme – bara reglerna för hur slumpvariabler beräknas ändras. Varje spel kommer att ha en händelse kopplad till en händelse . Låt oss bevisa att skillnaden är liten, och dessutom kommer det att indikera att i det senaste spelet . Låt - det första spelet, - en händelse som anger att biten i spelet är korrekt gissad . Låt beteckna en slumpmässig orakelförutsägelse som placerar element i längdbitsträngar i sin tabell. Låt vara den attackerade chiffertexten, och . Därefter kommer vi att definiera följande spel , exakt samma som spelet . Om det visar sig att oraklet kallades för att dekryptera med ett argument tidigare, och samtalet lyckades, så stannar spelet. Låt vara en händelse i spelet som motsvarar händelsen . Låt vara  en händelse som signalerar att spelet har stoppats. Det är tydligt att

och i tidsintervallet när spelen och passerar på samma sätt, nämligen innan ögonblicket då händer , är följande lemma sant:

Låta och vara händelser definierade på utrymmet av slumpmässiga händelser på ett sådant sätt att

Sedan körs:

I vårt fall Next definierar vi ett spel , samma som , förutom att den attackerade chiffertexten genereras i början av spelet, och om motståndaren begär , stoppar spelet. Låt &mdash vara händelsen som motsvarar händelsen . Det är uppenbart

på grund av det faktum att nyckeln är oberoende av allt tillgängligt för motståndaren i spelet . I det här spelet anropas v endast i krypteringssyfte.

Låt vara en händelse som signalerar att det föregående spelet avbröts. Det är tydligt att spelen fortsätter på samma sätt tills , och därför får vi genom lemma:

Vi kräver det för algoritmen A', vars körtid är begränsad av den tid som beskrivs ovan. Då kommer ojämlikheten (*) att vara uppfylld. Algoritm A' börjar enligt följande. Den får en slumpmässig RSA-modul , en RSA-exponent och ett slumpmässigt element som indata . A' genererar en offentlig nyckel med hjälp av och , och låter sedan motståndare A starta spelet. När A anropar oraklet för att kryptera, svarar A' på A med ett par av , där är en slumpmässig bit av en längdsträng , och ges som indata till A. Algoritm A' simulerar en slumpmässig förutsägelse , som dekryptering RO, som följer. För varje slumpmässig förutsägelseinmatning beräknar A' , och placerar , och ett slumpmässigt värde i tabellen. Men om A' istället skrivs ut och avslutas. När motståndare A tillhandahåller chiffertexten till dekrypteringsförutsägelsen, slår A' upp värdet i den beskrivna tabellen för att bestämma om det slumpmässiga förutsägelsevärdet har beräknats till . Om ja, så motsvarar A' avkodningsförutsägelsen med värdet lagrat i tabellen. Annars skapar algoritmen en ny slumpmässig nyckel och placerar paret i den andra tabellen. Dessutom, om motståndare A i framtiden måste beräkna en slumpmässig förutsägelse givet att , då kommer nyckeln som genereras ovan att användas som värdet på . Det är tydligt att A' perfekt simulerar A och ger lösningen för detta fall RSA med sannolikhet . Detta bevisar algoritmens säkerhet. Kvantitativt kan det verifieras att RSA-KEM ger bättre skydd än RSA-OAEP+ och RSA-OAEP. Denna fördel uttrycks ju fler desto fler meddelanden krypterade med en publik nyckel (modellerad i BBM00). Detta kan visas genom att dra fördel av det faktum att det är mycket arbetsintensivt att lösa RSA-inversionsproblemet. Säkerheten för RSA-KEM minskar alltså inte alls när antalet chiffertexter ökar. Det bör noteras att detta uttalande är sant endast om talet r i krypteringsalgoritmen för Simple RSA väljs enhetligt modulo n, eller åtminstone dess fördelning bör vara omöjlig att skilja från enhetlig ur beräkningssynpunkt. Bland annat kan RSA-KEM, till skillnad från RSA-OAEP eller RSA-OAEP +, inte kallas en "bräcklig" algoritm, det vill säga inga möjligheter till attacker på dess implementeringar har hittats.

Anteckningar

  1. ↑ Användning av RSA-KEM Key Transport Algorithm
  2. ↑ 1 2 3 4 V. Shopp. Ett förslag till ISO-standard för kryptering av offentlig nyckel
  3. ↑ FCD 18033-2 Krypteringsalgoritmer - Del 2: Asymmetriska chiffer
  4. ↑ AES Key Wrap Specifikation

Länkar