VMPC

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30. huhtikuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

VMPC ( Variably  Modified Permutation Composition ) on tietovirtasalaus [1] , jota käytetään joissakin tietoturvajärjestelmissä tietokoneverkoissa. Salauksen kehitti kryptografi Bartosz Zultak ( puolaksi: Bartosz Żółtak , englanniksi:  Bartosz Zoltak ) parannellun versiona suositusta RC4 -salauksesta . VMPC-algoritmi on rakennettu kuten mikä tahansa virtasalaus, joka perustuu avainparametreihin pseudosatunnaisbittigeneraattoriin. Salauksen, kuten RC4:n, tärkeimmät edut ovat suuri nopeus, muuttuva avaimen ja alustusvektorin koko (128 - 512 bittiä mukaan lukien), toteutuksen helppous (kirjaimellisesti muutama tusina koodiriviä). [2]

Salauksen perusta on näennäissatunnaislukugeneraattori [3] , joka perustuu yksisuuntaiseen irreversiibeliin funktioon VMPC ( Variably Modified  Permutation Composition ):

Algoritmin toteutus

Avainaikataulu

Algoritmi avaimen [2] ja (valinnaisesti) alustusvektorin muuntamiseksi 256 elementin permutaatioksi P. Globaalimuuttujan s alustus.

C: Avaimen pituus tavuina

K: Avain

z : Alustusvektorin pituus tavuina

V: Alustusvektori

i: 8-bittinen muuttuja

j : 16-bittinen muuttuja

s : 8-bittinen globaali muuttuja

P: 256 tavun taulukko permutaatioiden tallentamiseen

1.s = 0 2. i = 0 - 255: P[i] = i 3. j = 0 - 767 // suorita vaiheet. 4-6: 4. i = j mod 256 5. s = P[(s + P[i] + K[j mod c]) mod 256] 6. Lämpötila = P[i] P[i] = P[s] P[s] = Temp 7. Jos käytetään alustusvektorimuunnosta j = 0 - 767 // suorita vaiheet. 8-10: 8. i = j mod 256 9. s = P[(s + P[i] + V[j mod z]) mod 256] 10. Lämpötila = P[i] P[i] = P[s] P[s] = Temp

Salausalgoritmi

Lähtönäppäinsarjan luominen [2] .
Luodaksesi L tavua tulosavainvirrasta, suoritetaan seuraavat toiminnot:

L: näppäinsarjan pituus tavuina

1. i = 0 2. Toista kappaleet. 3-6 L kertaa: 3. s = P[(s + P[i]) mod 256] 4. Lähtö = P[(P[P[s]] + 1) mod 256] 5. Lämpötila = P[i] P[i] = P[s] P[s] = Temp 6. i = (i + 1) mod 256

Pseudosatunnaislukugeneraattorin toteutus

Yksisuuntainen VMPC (Variably Modified Permutation Composition)

VMPC-funktio [2] , jonka aste on k < n n-alkiojoukossa x∈A, A = {0,1,…n-1}:

x = 0 - n-1: Q k (x) = VMPC k (P(x)) = P(P k (P k-1 (…(P 1 (P(x)))…)))

Missä P: A → A yksi yhteen n-elementin permutaatio
P i (x) n-elementin permutaatio,
P i = f i (P(x)), P i (x) ≠ P(x) ≠ P j (x) , i≠j i,j∈{1,2…k}
f i (x) = (x + i) mod n ,

Funktio VMPC 1 asteen Q 1 (x)= VMPC 1 (P(x) )=P(P(P(x))+1)

Funktio VMPC 2:n Q 2 potenssit (x)= VMPC 2 (P(x))=P(P(P(P(x))+1)+2)

Funktio VMPC 3:n Q 3 potenssit (x)= VMPC 3 (P(x))=P(P(P(P(P(x))+1)+2)+3)

Esimerkki 1. asteen VMPC-funktion laskemisesta

P(x) on yksi muunnelmista [2] permutaatiosta {0,1,2,3,4}

x 0 yksi 2 3 neljä
P(x) 3 0 neljä yksi 2
VMPC 1 (P(x)) neljä 2 yksi 0 3

VMPC 1 (P(x))=P(P(P(x)) + 1)

x=0

P(0) = 3

P(P(0)) = 1

P(P(0)) + 1 = 2

P(P(P(0) + 1)) = 4

VMPC 1 (P(0)) = 4

VMPC-funktion käänteisluvun etsiminen

VMPC-funktion käänteisluvun löytäminen on laskennallisesti vaikeaa [2] .
Esimerkiksi kun n = 256, VMPC 1 -funktion käänteisarvon laskemiseksi tarvitaan operaatioita , VMPC 2 - , VMPC 3 - .

Algoritmi

Arvoa Q(X)= VMPC k (P(X))  vastaavan n-elementin permutaatio P palautus .

X, Y ovat väliaikaisia ​​muuttujia 

Elementille P(x) = y otetaan käyttöön seuraava merkintä: 

X − argumentti: kanta tai parametri

Y − arvo: parametri tai kanta vastaavasti

Esimerkki: elementille P(0) = 3: jos argumentti 0 on parametri , niin arvo 3 on kanta . 

Algoritmi: 

  1. Hae mielivaltaiselle arvolle X ∈ {0,1,…n-1} ja Y ∈ {0,1,…n-1} yksi permutaatio P elementti oletuksesta P(X) = Y. 
    1. Valitaan satunnaisesti, onko X parametri , Y − kanta tai X kanta , Y − elementin parametri P(X) = Y. P(X) = Y on permutaation P nykyinen alkio. 
  2. Etsi kaikki permutaation P elementit hakualgoritmilla.
  3. Jos permutaation kaikki n elementtiä löytyy ilman ristiriitoja, lopeta algoritmi.
  4. Muuten
    1. Etsi uusi elementti permutaatiosta valintaalgoritmilla, P(X) = Y on permutaation nykyinen elementti.
    2. Tallenna nykyisen permutaatioelementin parametri .
    3. Siirry vaiheeseen 2.
  5. Jos kohtaa 2 suoritettaessa syntyy ristiriita:
    1. Poista kaikki vaiheessa 2 löydetyt permutaatio P elementit.
    2. Nykyiselle permutaatioelementille P: parametri = ( parametri + 1) mod n,
    3. Jos parametri ottaa arvon, joka on tallennettu suoritettaessa lauseketta 4.2, niin:
      1. poista nykyinen permutaatioelementti P.
      2. ota permutaation nykyiselle elementille arvo, joka on saatu suorittaessasi vaihetta 1.
      3. Siirry kohtaan 5.1.
  6. Siirry vaiheeseen 2.
Hakualgoritmi

Löytää kaikki mahdolliset permutaation P elementit, kun on annettu Q ja jo löydetyt permutaatiosta P elementit.

D, C ovat väliaikaisia ​​muuttujia

Nimitykset:

lause y on permutaatio P k + 2 elementin sekvenssi y , jota käytetään Q( y ) -arvon laskemiseen .

sekvenssin y sana x on sekvenssin y alkio numerolla x .

Algoritmi:

  1. C=0; D = 0;
  2. Jos elementti P tunnetaan:
    1. Jos elementti P(D) ja k muuta tunnettua elementtiä täyttävät minkä tahansa sekvenssilausekkeen k + 1 elementin yleisen mallin , etsi tämän sekvenssin jäljellä oleva sana
    2. Jos löydetty sana ei ole P:n tunnettu elementti
      1. Nimeä löydetty sana P:n elementiksi
      2. C = 1
    3. Jos löydetty sana on ristiriidassa jonkin aiemmin löydettyjen elementtien kanssa, ilmoita virheestä, lopeta hakualgoritmi.
  3. D=D+1
  4. Jos D < n  , siirry kohtaan 2
  5. Jos C = 1 , siirry kohtaan 1.
Valintaalgoritmi

Valitaan sellainen uusi permutaatioelementti P, jonka laskeminen mahdollistaa elementtien P maksimimäärän löytämisen funktion VMPC k käänteisarvon löytämiseksi algoritmin myöhemmissä vaiheissa. Valinta-algoritmin tuloksena uuden elementin kanta määritetään ja sen parametriarvo valitaan mielivaltaisesti . Tämä algoritmi sopii tapaukseen k<4.

B, R ovat väliaikaisia ​​muuttujia

T a , T v − väliaikaiset taulukot

W[j] − lukujono

Algoritmi:

  1. Muuttuva alustus
    1. Ta = 0, T v = 0
    2. B = 0
    3. R = 1
  2. Lasketaan permutaation tunnettujen elementtien lukumäärä m , jotka ovat sana sekvenssilauseessa , missä tuntematon elementti P on sana R argumentilla B. T a = T a + W[m]
  3. Lasketaan permutaation P tunnettujen elementtien lukumäärä m , jotka ovat sana sekvenssilauseessa , jossa P:n tuntematon elementti on sana R , jonka arvo on B. Tv = Tv + W [ m]
  4. R = R+1
  5. Jos R < n  , siirry kohtaan 2.
  6. B = B+1
  7. Jos B < n  , siirry kohtaan 1.c.
  8. Indeksiarvo valitaan - mikä tahansa taulukoiden Ta tai Tv indekseistä, jolla taulukon soluun tallennettu arvo on suurin.
  9. Jos taulukon T a indeksi on valittu lausekkeessa 8 , niin:
    1. X = indeksi
    2. Y ∈ {0,1,…n-1} valitaan satunnaisesti siten, että permutaatioelementtiä, jonka arvo on Y , ei ole vielä löydetty.
    3. Tulos: P(x) = YX - kanta, Y - parametri
  10. Jos kohdassa 8 valitaan taulukon T v indeksi , niin:
    1. Y = indeksi
    2. X ∈ {0,1,…n-1} valitaan satunnaisesti siten, että permutaatioelementtiä, jonka arvo on X , ei ole vielä löydetty.
    3. Tulos: P(x) = YX - parametri, Y - kanta

Ominaisuudet

Todennäköisyys saada kaksi peräkkäistä identtistä tulosta generoitaessa avainsekvenssiä VMPC-salauksella on  yhtä suuri kuin ideaalisen satunnaissekvenssigeneraattorin vastaava todennäköisyys [2] .  - näennäissatunnaisen sekvenssigeneraattorin sisäisen tilan bittien lukumäärä, yleensä yhtä suuri kuin . Vuonna 2005 A. Maksimov osoitti, että lähtöbittien perusteella on mahdollista erottaa VMPC-generaattorisekvenssi satunnaisesta virrasta [4]

 B. Zhultakin suorittamat kokeet osoittivat, että tulossekvenssin esiintymistodennäköisyydessä ei ole tilastollisesti merkitsevää poikkeamaa:

  • jokainen mahdollinen     arvo (   lähtösekvenssin    tavuille);
  • jokainen mahdollinen     peräkkäisten arvojen pari (   lähtösekvenssin    tavuille);
  • jokainen mahdollinen   peräkkäisten arvojen kolmoisosa (lähtösekvenssin   tavuille    )

Turvallisuus

Väitetään, että stream-salaus alkuperäisen RC4 :n merkittävän muutoksen vuoksi , ottaen huomioon sen haavoittuvuudet, kestää paremmin olemassa olevia tietovirtasalauksia ja RC4-salaukseen kohdistuvia hyökkäyksiä [2] . Samaan aikaan useimpien stream-salausten turvallisuus on käytännössä laskenut nollaan, kun samaa avainta käytetään eri selkeiden tekstien salaamiseen. Tällaisessa tapauksessa virtasalaus ei ole enää kertaluonteinen tyynygeneraattori (satunnaisten bittien virta selkeän tekstin salaamiseksi). Tämä ongelma on jossain määrin ratkaistu VMPC-salauksella käyttämällä ainutlaatuista alustusvektoria jokaiselle salatulle virralle.

Väitetään, että salaukseen kohdistuvan hyökkäyksen monimutkaisuus on operaatioita [2] . On kuitenkin olemassa menetelmä, joka suojaa algoritmia mahdollisilta haavoittuvuuksilta. Tämä lähestymistapa koostuu avaimesta riippuvan permutoinnin toistamisesta kahdesti: ennen alustusvektorista riippuvaa permutaatiota ja sen jälkeen. Tätä avainaikataulua kutsutaan KSA3:ksi.

Linkit

Katso myös

Kirjallisuus

  1. ↑ Gabidulin E.M., Kshevetsky A.S., Kolybelnikov A.I. Tietojen suojaus . - Moskova: MIPT, 2011. - s. 225.
  2. ↑ 1 2 3 4 5 6 7 8 9 Zoltak B. VMPC yksisuuntainen toiminto ja suorasalaus  // Bimal R., Meier W. Fast Software Encryption  . - Berliini: Springer Berlin Heidelberg, 2004. - S. 210-225. - ISBN 978-3-540-25937-4 . - doi : 10.1007/978-3-540-25937-4_14 .
  3. ↑ Schneier B. Käytännön kryptografia . - Moskova: 2. painos — M.: Williams, 2005. — s. 610.
  4. ↑ Goutam P., Subhamoy M. RC4 -virtasalaus ja sen muunnelmat  . - Boca Raton, FL: CRC Press, 2012. - ISBN 978-1-4398-3135-9 .
 Symmetriset salausjärjestelmät
Suoratoista salauksia
Feistelin verkko
SP verkko
Muut