GGH-salausjärjestelmä

GGH-salausjärjestelmä ( eng. Goldreich–Goldwasser–Halevi ) on epäsymmetrinen salausjärjestelmä, joka perustuu hilaan . On myös GGH - allekirjoitusjärjestelmä .

Salausjärjestelmä perustuu ratkaisuihin lyhimmän vektorin löytämiseen ja lähimmän vektorin löytämiseen . Tiedemiesten Oded Goldreichin , Shafi Goldwasserin ja Shai Halevin vuonna 1997 julkaisema GGH-salausjärjestelmä käyttää yksisuuntaista salaista syöttötoimintoa , koska minkä tahansa hilapohjan perusteella on helppo luoda vektori lähellä hilapistettä. Esimerkiksi ottamalla hilapiste ja lisäämällä pieni virhevektori. Virhevektorista palaamiseksi hilan alkupisteeseen tarvitaan erityinen perusta. Vuonna 1999 Phong Q. Nguyen [1] paransi alkuperäistä GGH-salausjärjestelmää, mikä mahdollisti neljän viidestä GGH-ongelmasta ratkaisemisen ja osittaisen tiedon hankkimisen jälkimmäisestä. Vaikka GGH voi olla turvallinen tietyillä parametrivalinnoilla, sen tehokkuus perinteisiin julkisen avaimen salausjärjestelmiin verrattuna on edelleen kiistanalainen [2] . Usein salaus vaatii korkean hilamitan, kun taas avaimen koko kasvaa suunnilleen neliöllisesti hilan kokoon nähden [2] .

Ainoa suuria mittoja käsittelevä hilakaavio on NTRU [3] .

Algoritmi

GGH sisältää julkisen avaimen ja yksityisen avaimen [4] . Yksityinen avain on hilan pohja, jossa on unimodulaarinen matriisi . $B$ $L$ $U$

Julkinen avain on toinen kanta lomakkeen hilassa . $L$ $B'=UB$

Olkoon sanoma-avaruus M koostuva väliin kuuluvista vektoreista . ${\näyttötyyli (m_{1},...,m_{n})}$ $-M<m_{i}<M$

Salaus

Annettu viesti , virhe ja julkinen avain : $m=(m_{1},...,m_{n})$ $e$ $B'$

v=\sum m_{i}b_{i}'

Matriisimerkinnällä:

v=m\cdot B'

On muistettava, että se koostuu kokonaislukuarvoista, on hilapiste ja on siksi myös hilapiste. Sitten salateksti on: $m$ $b'$ $v$

c=v+e=m\cpiste B'+e

Transkriptio

Salatekstin purkamiseksi lasketaan:

c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B ^{-1}=m\cdot U+e\cdot B^{-1}

Jos se on tarpeeksi pieni, poistamiseen käytetään Babain pyöristysmenetelmää [ 5] . $e\cdot B^{-1}$

Sitten saadaksesi tekstin:

m=m\cdot U\cdot U^{-1}

Turvallisuusanalyysi

Tässä osiossa käsitellään useita tapoja hyökätä kryptojärjestelmää vastaan [6] .

Hyökkäys pyöristämällä

Pyöristyshyökkäys on tämän salausjärjestelmän ilmeisin hyökkäys, lukuun ottamatta raa'an voiman hyökkäystä - virhevektorin etsimistä . Sen ydin on käyttää julkista avainta B kääntämään funktio samalla tavalla kuin käytettäessä yksityistä avainta R Nimittäin tietäen , voit laskea . Siten voit löytää vektorin . Alle 80 LLL :n mitoissa algoritmi pystyy määrittämään perusteen oikein, mutta alkaen mitat 100 ja suuremmista, tämä hyökkäys on huonompi kuin triviaali virhevektorin luettelointi. $e.$ $c=B\cdot v+e$ $B^{-1}\cdot c=v+B^{-1}\cdot e$ $d=B^{-1}\cdot e$

Myrskyhyökkäys

Tämä algoritmi on ilmeinen jalostus pyöristyshyökkäyksestä. Tässä käytetään parasta approksimaatioalgoritmia lyhimmälle vektoriongelmalle . Erityisesti lähimmän tason algoritmia käytetään Babain pyöristysalgoritmin sijaan. Se toimii näin. Annettu piste ja pelkistetty kanta c = { } LLL :lle . Kaikki affine välilyönnit = { + } : } otetaan huomioon. Kaikesta huolimatta on lähimpänä pistettä oleva hypertaso . Lisäksi piste heijastetaan (n - 1)-ulotteiseen avaruuteen, jonka = { } peittää . Tämä antaa uuden pisteen ja uuden kantakohdan = { }. Algoritmi etenee nyt rekursiivisesti löytääkseen pisteen tässä (n - 1)-ulotteisessa hilassa lähellä . Lopuksi algoritmi asettaa . Tämä menetelmä toimii paljon nopeammin kuin edellinen. Kuitenkin myös sen työmäärä kasvaa eksponentiaalisesti hilaulottuvuuden myötä. Kokeet osoittavat, että käytettäessä LLL :ää hilavähennysalgoritmina, tarvitaan jonkin verran hakuaikaa, alkaen koosta 110-120. Hyökkäys muuttuu mahdottomaksi koosta 140-150 alkaen. $c$ $B$ ${b_{1}},\dots {b_{n}}$ ${\näyttötyyli {H_{k))}$ $k\cdot {b_{n))$ $\sum _{i=0}^{n-1}{a_{i}}\cdot {b_{i}}$ ${a_{i}}\in {\mathcal {R}}$ $k\in {\mathcal {Z))$ ${\näyttötyyli {H_{k))}$ $c$ $B$ ${b_{1}},\dots {b_{n}}$ $ck\cdot {b_{n))$ $c'$ $B'$ ${b_{1}},\dots {b_{n}}$ $p'$ $c'$ $p=p'+k\cdot {b_{n))$

Injektiohyökkäys

Toinen tapa, jota käytetään usein approksimoimaan lähimmän vektorin löytämisongelmaa, on upottaa n kantavektoria ja piste , jolle on tarpeen löytää läheinen hilapiste (n + 1)-ulotteisessa hilassa. $c$

$B'={\begin{pmatrix}\vdots &\vdots &\vdots &\cdots &\vdots \\c&b_{1}&b_{2}&\cdots &b_{n}\\\vdots &\vdots &\vpisteet &\ddots &\vdots \\1&0&0&\cdots &0\end{pmatrix}}$

Hilavähennys-algoritmia käytetään sitten etsimään lyhyin nollasta poikkeava vektori kohdasta , siinä toivossa, että tämän vektorin ensimmäiset n elementtiä ovat lähimpänä pistettä . Tälle hyökkäykselle tehdyt kokeet (käyttäen LLL :ää työkaluna lyhimpien vektorien löytämiseen) osoittavat, että se toimii noin 110-120 ulottuvuuksiin asti, mikä on parempi kuin pyöristyshyökkäys, josta tulee huonompi kuin triviaali haku dimension 100 jälkeen. $L(B')$ $c$

Hyökkäysten tehokkuuden arviointi [7]

Arvioitu hyökkäys pyöristämällä

Luodaan viisi suljettua kantaa jokaiseen ulottuvuuteen. Jokainen kanta valitaan muodossa = + rand , jossa I on identiteettimatriisi ja rand on neliömatriisi , jonka jäsenet valitaan tasaisesti alueelta . Jokaiselle kannalle lasketaan arvo = , jossa on suurimman rivin euklidinen normi ja . Jokaiselle suljetulle pohjalle luodaan viisi avointa kantaa $n$ ${\näyttötyyli {R_{i))}$ $4\left|{\sqrt {n}}\right|\cdot I$ $(\pm 4)$ $(\pm 4)$ ${-4,...,4}$ ${\näyttötyyli {R_{i))}$ ${\sigma _{i))$ ${\displaystyle ({\gamma _{i)){\sqrt {8\ln({2n}/{\varepsilon }))))^{-1))$ ${\näyttötyyli {\gamma _{i))}$ ${R_{i}}^{-1}$ $\varepsilon =10^{-5}$ ${\näyttötyyli {R_{i))}$ ${\näyttötyyli {B_{ij))}$

${työkuorma_{ij))$ = , missä on kaksoisortogonaalisuusvirhe: missä tarkoittaa matriisin riviä . ${\displaystyle ({\pi }e)^{n/2))$ $\cdot {\sigma _{i}^{n))$ $\cdot {\frac {orth-defect^{*}({B_{ij)))}{det|{B_{ij}}|}}$ $orth-defect^{*}$ $orth-defect^{*}(B)=|det(B)|\cdot \prod _{i}\|{\hat {b_{i))}\|,$ ${\näyttötyyli {\hattu {b_{i))))$ $B^{{-1}}$

Assault score

Hyökkäyksen arvioimiseksi käytettiin samoja avoimia ja suljettuja tukikohtia kuin hyökkäyksessä pyöristämällä.

Injektiohyökkäyksen arviointi

Koska injektiohyökkäyksen "työkuormasta" ei voi puhua, mitattiin maksimiarvo (virhevektoriin liittyen), jolla tämä hyökkäys toimii. Näissä kokeissa käytettiin samoja suljettuja tukikohtia ja avoimia tukikohtia kuin kahdessa edellisessä hyökkäyksessä. Sitten jokaisella avoimella pohjalla arvioitiin toiminto useissa kohdissa useilla eri arvoilla ja tarkistettiin, palauttaako injektiohyökkäys salatun viestin. ${\sigma}$ ${R}$ ${\näyttötyyli {B_{ij))}$ $\sigma$

Esimerkki

Olkoon hila kantaneen ja sen käänteisluvun kanssa : $L\subset \mathbb {R} ^{2}$ $B$ $B^{{-1}}$

B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}

B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}

Unimodulaarisella matriisilla:

U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}

U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}

Saamme:

B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}

Olkoon viesti ja virhevektori Sitten salateksti: $m=(3,-7)$ $e=(1,-1).$

c=mB'+e=(-104,-79)

Salauksen purkamiseen tarvitset:

cB^{-1}=\vasen({\frac {-104}{7)),{\frac {-79}{3}}\oikea)

Tämä pyöristyy $(-15,-26).$

Ja viesti palautetaan seuraavasti:

m=(-15,-26)U^{-1}=(3,-7).\,

Lähteet ja lisätietoa

Oded Goldreich, Shafi Goldwasser ja Shai Halevi. Julkisen avaimen salausjärjestelmät hilan pelkistysongelmista. Julkaisussa CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, sivut 112-131, Lontoo, UK, 1997. Springer-Verlag.
Phong Q. Nguyen. Goldreich-Goldwasser-Halevi kryptosysteemin kryptoanalyysi Cryptosta '97. Julkaisussa CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, sivut 288-304, Lontoo, UK, 1999. Springer-Verlag.

Muistiinpanot

↑ Phong Q. Nguyen. Goldreich-Goldwasser-Halevi kryptosysteemin kryptoanalyysi Cryptosta '97. . - S. 1-17 . Arkistoitu alkuperäisestä 16. heinäkuuta 2018.
↑ 1 2 Phong Q. Nguyen. Goldreich-Goldwasser-Halevi kryptosysteemin kryptoanalyysi Cryptosta '97. S. - 1-2. . Arkistoitu alkuperäisestä 16. heinäkuuta 2018. (määrätön)
↑ Phong Q. Nguyen. Goldreich-Goldwasser-Halevi kryptosysteemin kryptoanalyysi Cryptosta '97. S. - 1. . Arkistoitu alkuperäisestä 16. heinäkuuta 2018. (määrätön)
↑ Oded Goldreich, Shafi Goldwasser ja Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Julkisen avaimen salausjärjestelmät hilavähennysongelmista]. - S. 112-114 . Arkistoitu 4. toukokuuta 2019.
↑ Phong Q. Nguyen. Goldreich-Goldwasser-Halevi kryptosysteemin kryptoanalyysi Cryptosta '97. . - S. 4 . Arkistoitu alkuperäisestä 16. heinäkuuta 2018.
↑ Oded Goldreich, Shafi Goldwasser ja Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Julkisen avaimen salausjärjestelmät hilavähennysongelmista]. - S. 122-124 . Arkistoitu 4. toukokuuta 2019.
↑ Oded Goldreich, Shafi Goldwasser ja Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Julkisen avaimen salausjärjestelmät hilavähennysongelmista]. - S. 127-130 . Arkistoitu 4. toukokuuta 2019.