RSA-KEM

RSA-KEM ( RSA Key Encapsulation Method) on yksikertainen (tallennus-ja-välitys)-avaimen salausmekanismi lähetettäväksi julkisen avaimen salausjärjestelmissä . Yhdistää vääriä permutaatioita RSA :sta ja KDF:stä (Key Derivation Function). Sillä on yksinkertaisuus ja erinomaiset suojaominaisuudet verrattuna OAEP :iin tai OAEP+ :aan . Suurin haittapuoli on, että salateksti on hieman suurempi kuin pelkkä teksti.

Kuvaus

Johdanto

RSA-KEM kuuluu salausavainten kapselointimenetelmien luokkaan, joka on suunniteltu lähettämään turvallisesti symmetrisiä salausavaimia käyttämällä julkisen avaimen algoritmeja [1] . Käytännössä julkisen avaimen salausjärjestelmät ovat hankalat pitkien viestien välittämiseen, vaan niitä käytetään symmetristen avainten vaihtoon, jotka lopulta salaavat tekstin. Perinteinen lähestymistapa symmetrisen avaimen lähettämiseen julkisen avaimen järjestelmiä käyttäen on seuraava algoritmi:

  1. Satunnaislukujen sukupolvi.
  2. Numeron salaus valitulla julkisella avaimella. Tämä salattu viesti lähetetään vastaanottajalle.
  3. Vastaanottaja purkaa salauksen yksityisellä avaimella ja palauttaa symmetrisen avaimen.

Esitetyllä algoritmilla on useita haittoja [2] . Ensinnäkin, koska symmetrinen avain on pieni, sitä on pidennettävä, eikä avaimen pidentämisen turvallisuustodiste ole vahva. Toiseksi hyökkääjä voi lähettää numeronsa julkisella avaimella salattuna ja vaihtaa viestejä vastaanottajan kanssa. Kolmanneksi tietojen eheyttä ei valvota (toisen kohdan yleistys). Lisäksi samankaltaisten viestien salaukset voivat olla samanlaisia. Ilmeisesti esitetty järjestelmä ei ole tarpeeksi hyvä ja luotettava.

Avainten kapselointimenetelmä osoittaa erilaisen, edistyneemmän lähestymistavan, joka ratkaisee tunnistetut ongelmat.

Salausprosessi voidaan tiivistää seuraavasti:

  1. Syntyy satunnainen syöte w .
  2. Salattu w käyttäen RSA :ta lähetystä varten vastaanottajalle.
  3. Avainmateriaali y = KDF( w ) luodaan käytettäväksi myöhempään salaukseen.

Vastaanotin voi palauttaa w vastaanotetusta salatekstistä ja muodostaa sitten y :n , jotta sekä lähettäjä että vastaanottaja voivat sopia samasta symmetrisestä avaimesta.

Vaihtoehdot

Avaimen salausmekanismilla on seuraavat järjestelmäparametrit:

  1. RSAKeyGen: RSA-avainten luontialgoritmi.
  2. KDF: Avaimen johtamisfunktio.
  3. KeyLen: Positiivinen kokonaisluku.

Avaimen luominen

Julkinen avain koostuu RSA-kertoimesta , joka on kahden suuren alkuluvun tulo ja eksponentti , jossa (  on suurin yhteinen jakaja ) [3] . Se korostaa myös KDF:n avainjohtamistoimintoa. Olkoon nLen n: n pituus tavuina. Salainen avain koostuu salauksenpurkueksponentista d , jossa . Avaimen luontialgoritmi ei ota mitään syötteenä ja suoritetaan seuraavasti:

  1. Laskenta ( n , e , d ) = RSAKeyGen().
  2. Julkisen avaimen PK (julkinen avain) hankkiminen.
  3. Yksityisen avaimen pk (yksityinen avain) hankkiminen.

n , e , d  ovat positiivisia kokonaislukuja.

Salaus

Salausalgoritmin tavoitteena on tuottaa näennäissatunnainen avain K , jonka pituus on KeyLen, ja salateksti , joka salaa K :n . Salausalgoritmi hyväksyy seuraavat:

  1. julkinen avain, joka koostuu positiivisesta kokonaisluvusta n ja e .
  2. ei salausvaihtoehtoja.

Se tehdään seuraavasti [2] :

1) Luodaan satunnaisluku .

2) Salattu vastaanottajan julkisella avaimella

3) Numero muunnetaan salatuksi merkkijonoksi ja merkkijonoksi

4) Luodaan niin sanottu avainsalausavain (KEK), jonka pituus on , käyttämällä avainjohdannaisfunktiota (KDF):

5) Lähetetyt tiedot kääritään (englanninkielisessä kirjallisuudessa WRAP) KEK-avaimella käyttämällä avaimen käärintämenetelmää. Lähdössä saamme salatun tekstin

6) Yhdistä ja salaa teksti

on algoritmin tulos

Key Generation Function (KDF)

KDF ottaa syötteenä tavumerkkijonon ja kokonaisluvun . Esimerkiksi funktio KDF1. Se on parametroitu jollain hash-funktiolla ja se määritellään seuraavasti [2] : argumentit menevät tuloon , lähdössä saamme lausekkeen ensimmäiset tavut:

|| || ... || || missä

KDF1:n kaksoisosa on KDF2. Se eroaa KDF1:stä vain siinä, että laskuri käy kohdasta - , ei alkaen - . Näiden funktioiden on kuitenkin vaikea määrittää, kuinka "hyviä" pseudosatunnaislukugeneraattoreita ne ovat. Tämän mahdollisen haavoittuvuuden vuoksi on toivottavaa käyttää KDF3-toimintoa, esim. Se otetaan parametreina Hash ja Lausekkeen ensimmäiset tavut tulostetaan:

|| || · · · || , || missä .

Suositeltavat hash-funktiot SHA1 ja RIPMD-160. Suositeltava . KDF3:n luotettavuutta voidaan jo arvioida varsin luottavaisesti. IEEE P1363 -standardissa kuvattu funktio muuntaa luvun merkkijonoksi . Sen työ perustuu funktioon , joka päinvastoin saa numeron merkkijonosta.

Key Wrapping Schema

RFC 5990 -spesifikaatio edellyttää, että yhtä seuraavista käytetään käärekaaviona:

  1. AES-avaimen kääre
  2. Kolminkertainen DES-avainkotelo
  3. Camillia Avaimen kääre

Yleisin käärejärjestelmä on AES [4] . Se toimii 64-bittisissä lohkoissa ja vaatii syötteenä viestin, joka on pidempi kuin yksi tällainen lohko. Jos viestin pituus on 64 bittiä tai vähemmän, spesifikaation määrittämä vakio- ja avaintieto muodostavat yhden 128-bittisen lohkon, jonka rivitys on merkityksetön.

Salauksen purku

Salauksen purkualgoritmi ottaa syötteeksi seuraavan:

  1. yksityinen avain, joka koostuu positiivisesta kokonaisluvusta n ja d .
  2. salateksti .

Se suoritetaan seuraavasti:

  1. Salatun avaininformaation erottaminen tavupituiseksi salatekstiksi ja kääretyksi avaintiedoksi: Jos salatun avaininformaation pituus on eri kuin , salauksen purku epäonnistuu.



  2. Salatekstin muuntaminen kokonaisluvuksi ja sen salauksen purkaminen vastaanottajan yksityisellä avaimella: Jos ei sisällä , salauksen purku epäonnistuu.




  3. Muunna kokonaisluku pituiseksi tavumerkkijonoksi



  4. Pituustavujen luominen merkkijonosta KDF :n avulla:



  5. Avaintietojen purkaminen : Jos purkutoiminto epäonnistuu, koko algoritmi epäonnistuu.



  6. Algoritmin tulosteen saaminen .

Luotettavuusarvio

RSA-KEM:n turvallisuutta voidaan analysoida satunnaisessa oraakkelimallissa (Random Oracle Model, jäljempänä RO) [2] . Mallin olemus on seuraava. Oletetaan, että on olemassa jokin julkinen toiminto, jolla on seuraavat ominaisuudet:

  1. Funktio vastaa jokaiseen uuteen argumenttiin uudella arvolla ja kirjoittaa parin (argumentin, arvon) taulukkoon.
  2. Jos argumentti on jo täytetty, funktio siirtyy taulukkoonsa ja palauttaa tätä argumenttia vastaavan arvon.

Todistus perustuu oletukseen, että KDF on satunnainen oraakkeli ja että RSA:n käänteisongelman ratkaiseminen on mahdotonta (eli RSA:ta ei voi hakkeroida). Kaikille RSA:n avainten luontialgoritmille (eli algoritmille, joka palauttaa n, e ja d), n >= nBound on aina voimassa (eli nBound on pienin laillinen rajoitus n numerolle), ja jokaiselle hyökkääjälle A, seuraava on totta:

+

missä on suurin määrä pyyntöjä oraakkelille, jonka hyökkääjä voi tehdä yrittääkseen ratkaista salauksen , AdvantageRSA-KEM(A) = |Pr[b*-b] - 1/2| — Ennustava kyky A, AdvantageRSA(A') tarkoittaa todennäköisyyttä, että käänteinen RSA-ongelma ratkaistaan ​​onnistuneesti. On huomattava, että yllä oleva epäyhtälö ei ota huomioon sitä tosiasiaa, että todellisuudessa se palauttaa "huonoja" avaimia nollasta poikkeavalla todennäköisyydellä. Ottaaksesi sen huomioon, sinun tarvitsee vain lisätä tämä todennäköisyys epäyhtälön oikealle puolelle.

Annamme todisteen ottamalla huomioon pelien järjestyksen ja jokaisessa pelissä vastustaja A hyökkää. Jokainen näistä peleistä tapahtuu samassa todennäköisyysavaruudessa - vain satunnaismuuttujien laskentasäännöt muuttuvat. Jokaisessa pelissä on tapahtumaan liittyvä tapahtuma . Osoittakaamme, että ero on pieni, ja lisäksi se osoittaa, että viimeisessä pelissä . Olkoon - ensimmäinen peli, - tapahtuma, joka osoittaa, että pelin bitti on arvattu oikein . Olkoon satunnainen oraakkelin ennuste sijoittamalla elementtejä pituisiin bittijonoihin taulukossaan. Antaa olla hyökätty salateksti, ja . Seuraavaksi määrittelemmeseuraavan pelin , täsmälleen saman kuin pelin . Jos käy ilmi, että oraakkeli kutsuttiin purkamaan salaus argumentilla aiemmin ja puhelu onnistui, peli pysähtyy. Antaa olla tapahtumaa vastaava tapahtuma pelissä . Olkoon  tapahtuma, joka ilmaisee, että peli on pysäytetty. On selvää että

ja aikavälillä, jolloin pelit ja passit kulkevat samalla tavalla, eli ennen hetkeä, jolloin tapahtuu , seuraava lemma on totta:

Olkoon ja olla tapahtumia, jotka on määritelty satunnaisten tapahtumien avaruudessa siten, että

Sitten se suorittaa:

Meidän tapauksessamme Seuraavaksi määritämme pelin , joka on sama kuin , paitsi että hyökätty salateksti luodaan pelin alussa, ja jos vastustaja pyytää , peli pysähtyy. Olkoon &mdash tapahtumaa vastaava tapahtuma . Se on selvää

sen tosiasian perusteella, että avain on riippumaton kaikesta, mitä vastustajan käytettävissä on pelissä . Tässä pelissä v :tä kutsutaan vain salaustarkoituksessa.

Olkoon tapahtuma, joka ilmaisee, että edellinen peli keskeytettiin. On selvää, että pelit ja etenevät samalla tavalla kunnes , ja siksi lemmalla saamme:

Vaadimme sen algoritmille A', jonka ajoaikaa rajoittaa edellä kuvattu aika. Silloin epäyhtälö (*) täyttyy. Algoritmi A' alkaa seuraavasti. Se vastaanottaa tulona satunnaisen RSA-moduulin , RSA-eksponentin ja satunnaiselementin . A' luo julkisen avaimen käyttämällä ja ja sallii sitten vastustajan A aloittaa pelin. Kun A kutsuu oraakkelia salaamaan, A' vastaa A:lle parilla , jossa on satunnainen pituisen merkkijonon bitti , ja se annetaan syötteenä A:lle. Algoritmi A' simuloi satunnaista ennustetta , kuten salauksen purku RO, kuten seuraa. A' laskee jokaiselle satunnaisen ennustussyötteelle ja sijoittaa satunnaisarvon taulukkoon . Kuitenkin, jos A' sen sijaan tulostaa ja lopettaa. Kun vastustaja A tarjoaa salatekstin salauksenpurkuennusteelle, A' etsii arvon kuvatusta taulukosta määrittääkseen, onko satunnainen ennustearvo laskettu kohdassa . Jos kyllä, niin A' vastaa dekoodausennustetta taulukkoon tallennetulla arvolla . Muussa tapauksessa algoritmi luo uuden satunnaisavaimen ja sijoittaa parin toiseen taulukkoon. Lisäksi, jos tulevaisuudessa vastustaja A joutuu laskemaan satunnaisen ennusteen sillä perusteella , että yllä luotua avainta käytetään arvona . On selvää, että A' simuloi täydellisesti A:ta ja antaa ratkaisun tähän tapaukseen RSA todennäköisyydellä . Tämä todistaa algoritmin turvallisuuden. Kvantitatiivisesti voidaan varmistaa, että RSA-KEM tarjoaa paremman suojan kuin RSA-OAEP+ ja RSA-OAEP. Tämä etu ilmaistaan ​​mitä enemmän, sitä suurempi määrä viestejä on salattu yhdellä julkisella avaimella (mallittu BBM00:ssa). Tämä voidaan osoittaa hyödyntämällä sitä, että RSA-inversioongelman ratkaiseminen on erittäin työvoimavaltaista. Näin ollen RSA-KEM:n turvallisuus ei heikkene lainkaan salatekstien määrän kasvaessa. On huomattava, että tämä väite pitää paikkansa vain, jos Simple RSA:n salausalgoritmin luku r valitaan tasaisesti modulo n tai ainakin sen jakauman tulisi olla laskennan kannalta erotettavissa yhtenäisestä. Muun muassa RSA-KEM:ää, toisin kuin RSA-OAEP:tä tai RSA-OAEP+:aa, ei voida kutsua "hauraaksi" algoritmiksi, eli mahdollisuuksia hyökkäyksille sen toteutuksia vastaan ​​ei ole löydetty.

Muistiinpanot

  1. ↑ RSA-KEM-avaimen siirtoalgoritmin käyttö
  2. ↑ 1 2 3 4 V. Shoup. Ehdotus ISO-standardiksi julkisen avaimen salaukselle
  3. ↑ FCD 18033-2 -salausalgoritmit - Osa 2: Epäsymmetriset salaukset
  4. ↑ AES Key Wrap -määritykset

Linkit