Ei-kommutatiivinen kryptografia

Ei-kommutatiivinen kryptografia  on kryptologian ala , jossa salausprimitiivit , menetelmät ja järjestelmät perustuvat ei- kommutatiivisiin algebrallisiin rakenteisiin.

Ei- kommutatiivinen kryptografia perustuu operaatioihin ei-kommutatiivisessa ryhmässä 𝐺 alkaen (𝐺, ∗), joka koostuu ryhmistä , puoliryhmistä tai renkaista , joissa on vähintään kaksi elementtiä ryhmästä 𝑎 ja 𝑏 alkaen 𝐺, joille epäyhtälö 𝑎∗𝑏 ≠ 𝑏∗𝑎 [1] . Tätä rakennetta käyttäviä protokollia on kehitetty erilaisten salausongelmien ratkaisemiseen, esimerkiksi autentikointi , salaus -salauksen purku ja avaimenvaihtoistunnon perustaminen [1] .

Relevanssi

Yksi varhaisimmista ei-kommutatiivisen algebrallisen rakenteen käyttötavoista salaustarkoituksiin oli punosryhmän käyttö , jota seurasi salausprotokollan kehittäminen. Myöhemmin useita muita ei-kommutatiivisia rakenteita, kuten Thompson-ryhmät , polysykliset ryhmät , Grigorchuk- ryhmät ja matriisiryhmät, tunnistettiin mahdollisiksi ehdokkaiksi salaussovelluksiin. Toisin kuin ei-kommutatiivinen kryptografia, tällä hetkellä laajasti käytetyt julkisen avaimen salausjärjestelmät, kuten RSA , Diffie-Hellman-protokolla ja elliptinen kryptografia , perustuvat lukuteoriaan ja ovat siksi riippuvaisia ​​kommutatiivisista algebrallisista rakenteista [1] . Lähitulevaisuudessa mahdollisesti ilmenevä kvanttitietokoneen käyttö kryptografiassa nopeuttaa kuitenkin merkittävästi tekijöiden jakamisen ja diskreettien logaritmiongelmien ratkaisemista syklisessä ryhmässä (nämä ongelmat ratkaistaan ​​polynomiajassa ) [2] . Jälkimmäinen tarkoittaa sitä, että kaikista yleisimmin käytetyistä salausjärjestelmistä tulee epävarmoja, koska niiden turvallisuus perustuu näiden kahden ongelman superpolynomiseen monimutkaisuuteen, kun ne ratkaistaan ​​tällä hetkellä saatavilla olevilla tietokoneilla.Tässä tapauksessa turvallisuus voidaan saavuttaa rakentamalla salausjärjestelmiä, jotka perustuvat ei-kommutatiivinen ryhmä.

Perusryhmä

Ei-kommutatiivista ryhmää, jota käytetään salausprotokollan ytimessä, kutsutaan kyseisen protokollan perusryhmäksi. Vain ryhmiä, joilla on tietyt ominaisuudet, voidaan käyttää perusryhminä toteutettaessa ei-kommutatiivisia kryptojärjestelmiä. Olkoon G ryhmä, jota ehdotetaan perusryhmäksi ei-kommutatiivisen kryptojärjestelmän rakentamiseen. Alla on luettelo ominaisuuksista, jotka G:n on täytettävä.

  1. Ryhmän G on oltava tunnettu. Toisin sanoen konjugassin löytämisen ongelmaa on joko tutkittu pitkään ja tuloksetta, tai se voidaan pelkistää toiseksi tunnetuksi ongelmaksi.
  2. Ryhmän G sana tasa-arvoongelma on ratkaistava nopeasti deterministisellä algoritmilla. G:n elementeillä täytyy olla tehokkaasti laskettava "normaalimuoto".
  3. G:n on oltava superpolynomin kasvuryhmä, eli G:n pituisten n alkioiden lukumäärä kasvaa nopeammin kuin mikään polynomi n:ssä. (Suojaa yksinkertaiselta numeraatiolta)
  4. Alkioiden x ja y palauttaminen G:n xy:n tulosta ei pitäisi olla mahdollista.

Esimerkkejä perusryhmistä

Punosryhmä

Olkoon n positiivinen kokonaisluku. Punosryhmä B n voidaan määritellä ( n − 1) generaattoreilla ja suhteilla [3] :

Erityisesti mikä tahansa B 4 :n elementti voidaan kirjoittaa seuraavien kolmen elementin (ja niiden käänteisten) koostumukseksi:

        
  σ 1   σ2 _   σ 3

Thompson Group

Thompson-ryhmä on ääretön ryhmä F, jolla on seuraava ääretön esitys [4] :

Grigorchukin ryhmä

Olkoon T ääretön juurtunut binääripuu . Piikkien joukko V on kaikkien äärellisten binäärijonojen joukko. Olkoon A(T) T:n kaikkien automorfismien joukko . (Automorfismi T permutoi kärjet säilyttäen yhteyden.) Grigorchukin ryhmä Γ on A(T):n aliryhmä, jonka muodostavat automorfismit a, b, c, d määritellään seuraavasti:

Artinin ryhmä

Artin-ryhmä A(Γ) on ryhmä, jolla on seuraava esitys [5] :

missä

For , tarkoittaa sanan ja pitkän tuloa, alkaen . Esimerkiksi,

ja

Jos , niin (sopimuksen mukaan) ja välillä ei ole suhdetta .

Matriisiryhmät

Olkoon F äärellinen kenttä. F:n yläpuolella olevia matriisiryhmiä on käytetty perusryhminä joissakin ei-kommutatiivisissa kryptografisissa protokollissa.

Jotkut ei-kommutatiiviset kryptografiset protokollat

Nämä protokollat ​​olettavat, että G on ei-abelin ryhmä . Jos w ja a ovat ryhmän G elementtejä, niin merkintä w a merkitsee elementtiä a −1 wa .

Avaimenvaihtoprotokollat

Protocol, Ko, Lee ym.

Seuraava protokolla on samanlainen kuin Diffie-Hellman-protokolla. Se perustaa jaetun salaisen avaimen K Alicelle ja Bobille .

  1. Elementti w G : stä on kaikkien tiedossa.
  2. Kaksi alaryhmää A ja B G :stä siten, että ab = ba kaikille a : lle A: sta ja b :stä B :stä julkaistaan.
  3. Alice valitsee elementin a A: sta ja antaa w a :n Bobille. Alice pitää salaisuuden .
  4. Bob valitsee elementin b B :stä ja välittää w b :n Alicelle. Bob pitää salaisuuden .
  5. Alice laskee K = ( w b ) a = w ba .
  6. Bob laskee K' = ( w a ) b = w a .
  7. Kun ab = ba ja K = K' , niin Alice ja Bob jakavat yhteisen salaisen avaimen K.
Anshel-Anshel-Goldfeld-protokolla

Tämä on avaimenvaihtoprotokolla, joka käyttää ei-Abelin ryhmää G. Tämä on tärkeää, koska se ei vaadi kahta G:n kytkentäaliryhmää A ja B, kuten edellisen protokollan tapauksessa.

  1. Elementit a 1 , a 2 , . . . , a k , b 1 , b 2 , . . . , b m G :stä valitaan ja julkaistaan.
  2. Alice valitsee salaisen x :n G : stä sanaksi , joka koostuu luvusta 1 , a 2 , . . . , a k ; siis x = x ( a 1 , a 2 , . . . , a k ).
  3. Alice lähettää b 1 x , b 2 x , . . . , p m x Bob.
  4. Bob valitsee salaisen y :n G :stä sanaksi, joka koostuu b 1 , b 2 , . . . , bm ; _ tästä syystä y = y ( b 1 , b 2 , . . . , b m ).
  5. Bob lähettää 1 v , 2 v , . . . , a k y Alice.
  6. Alice ja Bob jakavat salaisen avaimen K = x −1 y −1 xy .
  7. Alice laskee x ( a 1 y , a 2 y , . . . , a k y ) = y −1 xy . Kun se kerrotaan x −1 :llä , Alice saa K .
  8. Bob laskee y ( b 1 x , b 2 x , . . . , b m x ) = x −1 yx . Kun se kerrotaan y −1 :llä ja otetaan käänteisalkio, Bob saa K .
Stickel Key Exchange Protocol

Tämän protokollan alkuperäinen muotoilu käytti käännettävien matriisien ryhmää äärellisen kentän yli.

  1. Olkoon G tunnettu ei-Abelin äärellinen ryhmä .
  2. Olkoon a , b G : stä tunnettu alkiopari siten, että: ab ≠ ba . Vastaa a:n ja b :n järjestystä N ja M .
  3. Alice valitsee kaksi satunnaislukua n < N ja m < M ja lähettää u = a m b n Bobille.
  4. Bob ottaa kaksi satunnaislukua r < N ja s < M ja lähettää v = a r b s Alicelle.
  5. Liisa ja Bob yhteinen avain on K = a m + r b n + s .
  6. Alice laskee avaimen kaavalla: K = a m vb n .
  7. Bob laskee avaimen kaavalla: K = a r ub s .

Salaus- ja salauksenpurkuprotokollat

Tämä protokolla kuvaa salaisen viestin salaamisen ja sen salauksen purkamisen käyttämällä ei-kommutatiivista ryhmää. Anna Alice lähettää Bobille salaisen viestin m.

  1. Olkoon G ei-kommutatiivinen ryhmä. Olkoot A ja B myös G :n julkisia aliryhmiä, joille ab = ba kaikille a :sta A: sta ja b :stä B .
  2. Elementti x G :stä valitaan ja julkaistaan.
  3. Bob valitsee salaisen avaimen b A: sta ja julkaisee julkisena avaimekseen z = x b .
  4. Alice valitsee satunnaisen r :n joukosta B ja laskee t = z r .
  5. Salattu viesti on C = ( x r , H ( t ) m ), jossa H on jokin hash-funktio ja tarkoittaa XOR -toimintoa . Alice lähettää C :n Bobille.
  6. C :n salauksen purkamiseksi Bob rekonstruoi t :n kautta: ( x r ) b = x rb = x br = ( x b ) r = z r = t . Alicen lähettämä tekstiviesti lasketaan kaavalla P = ( H ( t ) m ) H ( t ) = m .

Todennusprotokollat

Bob haluaa tarkistaa, onko viestin lähettäjä Alice.

  1. Olkoon G ei-kommutatiivinen ryhmä. Olkoot A ja B myös G :n aliryhmiä, joille ab = ba kaikille a :sta A: sta ja b :stä B .
  2. G : n elementti w valitaan ja julkaistaan.
  3. Alice valitsee salaisen s : n A: sta ja julkaisee parin ( w , t ) , jossa t = ws .
  4. Bob valitsee r :n B :stä ja lähettää viestin w ' = w r Alicelle.
  5. Alice lähettää vastauksen w ' ' = ( w ') s Bobille.
  6. Bob tarkistaa yhtäläisyyden w ' ' = t r . Jos tasa-arvo pätee, Alicen henkilöllisyys vahvistetaan.

Protokollasuojauksen perusteet

Edellä esitettyjen eri protokollien turvallisuuden ja vahvuuden perusta on seuraavan kahden ongelman ratkaisemisen vaikeus:

  • Konjugaation olemassaoloongelma  : Annettu kaksi alkiotaujavryhmästäG. Määritä, onkoG:stäx, ettäv=u x , eli sellainen, ettäv=x−1ux.
  • Konjugaatioongelma : Annettu kaksi elementtiä u ja v ryhmästä G. Etsi elementti x G :stä siten, että v = u x , eli sellainen, että v = x −1 ux

Jos konjugaatioongelman ratkaisun algoritmia ei tunneta, funktiota x → u x voidaan pitää yksisuuntaisena funktiona .

Muistiinpanot

  1. ↑ 1 2 3 Kumar, Saini. Uusi ei-kommutatiivinen kryptografiajärjestelmä Extra Special  Groupin avulla . - 2017 - tammikuu. - s. 1-3 . Arkistoitu alkuperäisestä 26. joulukuuta 2018.
  2. ↑ D.N. Moldovyan. Julkisen avaimen kryptosysteemien primitiivit: Neliulotteisten vektorien rajalliset ei-kommutatiiviset ryhmät  (venäjä) . — 2010. Arkistoitu 26. maaliskuuta 2020.
  3. ↑ David Garber. BRAID GROUP KRYPTOGRAFIA ALUSTAVA  LUONNOS . - 2007 - joulukuu. Arkistoitu alkuperäisestä 26. joulukuuta 2018.
  4. ↑ Vladimir Shpilrain, Aleksanteri Ushakov. Thompson's Group ja Public Key  Cryptography . - 2007 - joulukuu. Arkistoitu alkuperäisestä 9. huhtikuuta 2019.
  5. ↑ K.I.Appel, PESchupp. Artin-ryhmät ja äärettömät Coxeter-ryhmät  . - 1983. - kesäkuuta. Arkistoitu alkuperäisestä 26. joulukuuta 2018.

Kirjallisuus

  1. Aleksei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Ei-kommutatiivinen kryptografia ja ryhmäteoreettisten ongelmien monimutkaisuus. — ISBN 9780821853603 .
  2. Aleksei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Ryhmäpohjainen kryptografia.
  3. Benjamin Fine, et. al. Nonabelin ryhmäpohjaisen kryptografian näkökohdat: Tutkimus ja avoimet ongelmat .

Linkit

  1. Aleksei Myasnikov; Vladimir Shpilrain; Aleksanteri Ushakov. Ryhmäpohjainen kryptografia  (uuspr.) . Berliini: Birkhauser Verlag, 2008.
  2. Zhenfu Cao. Modernin kryptografian uudet suunnat  (uuspr.) . - Boca Raton: CRC Press, Taylor & Francis Group, 2012. - ISBN 978-1-4665-0140-9 .
  3. Benjamin Fine, et. al., Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems, arΧiv : 1103.4093 . 
  4. Aleksei G. Myasnikov; Vladimir Shpilrain; Aleksanteri Ushakov. Ei-kommutatiivinen kryptografia ja ryhmäteoreettisten ongelmien monimutkaisuus  (englanti) . - American Mathematical Society, 2011. - ISBN 9780821853603 .
 Symmetriset salausjärjestelmät
Suoratoista salauksia
Feistelin verkko
SP verkko
Muut
 Julkisen avaimen salausjärjestelmät
Algoritmit
Kokonaislukujen faktorointi
Diskreetti logaritmi
Kryptografia ristikoilla
Muut
Teoria
Standardit
Aiheet
 Hash-funktiot
yleinen tarkoitus
Kryptografinen
Avainten luontitoiminnot
Tarkista numero ( vertailu )
Hashes