VMPC

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 aprilie 2015; verificările necesită 4 modificări .

VMPC ( Variably  Modified Permutation Composition ) este un stream cipher [1] utilizat în unele sisteme de securitate a informațiilor din rețelele de calculatoare. Cifrul a fost dezvoltat de criptograful Bartosz Zultak ( poloneză: Bartosz Żółtak , engleză:  Bartosz Zoltak ) ca o versiune îmbunătățită a popularului cifr RC4 . Algoritmul VMPC este construit ca orice cifru de flux bazat pe un generator de biți pseudo-aleatoriu parametrizați cu cheie. Principalele avantaje ale cifrului, precum RC4, sunt viteza mare, dimensiunea variabilă a cheii și vectorul de inițializare (de la 128 la 512 biți inclusiv), ușurința de implementare (literal câteva zeci de linii de cod). [2]

Baza cifrului este un generator de numere pseudo-aleatoare [3] , care se bazează pe o funcție ireversibilă unidirecțională VMPC ( Variably  Modified Permutation Composition ):

Implementarea algoritmului

Program cheie

Algoritm de conversie a cheii [2] și (opțional) a vectorului de inițializare într-o permutare de 256 de elemente P. Inițializarea variabilei globale s.

C: lungimea cheii în octeți

K: Cheie

z : Lungimea vectorului de inițializare în octeți

V : Vector de inițializare

i : variabilă pe 8 biți

j : variabilă pe 16 biți

s : variabilă globală de 8 biți

P : tabel de 256 de octeți pentru stocarea permutărilor

1.s = 0 2. pentru i = 0 până la 255: P[i] = i 3. pentru j = 0 până la 767 // executați pași. 4-6: 4. i = j mod 256 5. s = P[(s + P[i] + K[j mod c]) mod 256] 6. Temp = P[i] P[i] = P[s] P[s] = Temp 7. Dacă se utilizează transformarea vectorului de inițializare pentru j = 0 până la 767 // executați pași. 8-10: 8. i = j mod 256 9. s = P[(s + P[i] + V[j mod z]) mod 256] 10. Temp = P[i] P[i] = P[s] P[s] = Temp

Algoritm de criptare

Generarea secvenței de taste de ieșire [2] .
Pentru a genera L octeți ai fluxului de chei de ieșire, sunt efectuate următoarele operații:

L : lungimea secvenței de taste în octeți

1. i = 0 2. Repetați paragrafele. 3-6 L ori: 3. s = P[(s + P[i]) mod 256] 4. Ieșire = P[(P[P[s]] + 1) mod 256] 5. Temp = P[i] P[i] = P[s] P[s] = Temp 6. i = (i + 1) mod 256

Implementarea unui generator de numere pseudo-aleatoare

VMPC unidirecțional (Compoziție de permutare modificată variabil)

Funcția VMPC [2] de gradul k < n peste o mulțime de n elemente x∈A, A = {0,1,…n-1}:

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

Unde P: A → O permutare unu-la-unu cu n elemente
Pi (x) permutare cu n elemente, 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 ,

Funcția VMPC 1 de gradul Q 1 (x)= VMPC 1 (P(x) )=P(P(P(x))+1)

Funcția VMPC 2 puteri ale lui Q 2 (x)= VMPC 2 (P(x))=P(P(P(P(x))+1)+2)

Funcția VMPC 3 puteri ale lui Q 3 (x)= VMPC 3 (P(x))=P(P(P(P(P(x))+1)+2)+3)

Un exemplu de calcul al funcției VMPC de gradul I

P(x) este una dintre variantele [2] ale permutației {0,1,2,3,4}

X 0 unu 2 3 patru
P(x) 3 0 patru unu 2
VMPC 1 (P(x)) patru 2 unu 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

Găsirea inversului funcției VMPC

Găsirea reciprocă a funcției VMPC este dificilă din punct de vedere computațional [2] .
De exemplu, pentru n = 256, pentru a calcula valoarea inversă a funcției VMPC 1 , sunt necesare operații , pentru VMPC 2 - , pentru VMPC 3 - .

Algoritm

Recuperarea permutării n - elementului P corespunzătoare valorii Q(X)= VMPC k (P(X)). 

X, Y sunt variabile temporare 

Pentru elementul P(x) = y se introduce următoarea notație: 

X − argument: bază sau parametru

Y − valoare: parametru sau respectiv bază

Exemplu: pentru elementul P(0) = 3: dacă argumentul 0 este parametrul , atunci valoarea 3 este baza . 

Algoritm: 

  1. Pentru o valoare arbitrară X ∈ {0,1,…n-1} și Y ∈ {0,1,…n-1} , găsiți un element al permutației P din ipoteza P(X) = Y. 
    1. Se alege aleatoriu dacă X este parametrul , Y − baza sau X este baza , Y − parametrul elementului P(X) = Y. P(X) = Y este elementul curent al permutației P. 
  2. Găsiți toate elementele permutației P prin algoritmul de căutare.
  3. Dacă toate cele n elemente ale permutației sunt găsite fără contradicții, atunci terminați algoritmul.
  4. In caz contrar
    1. Găsiți un nou element al permutării prin algoritmul de selecție, P(X) = Y este elementul curent al permutației.
    2. Stocați parametrul elementului de permutare curent.
    3. Treceți la pasul 2.
  5. Dacă, la efectuarea punctului 2., apare o contradicție:
    1. Ștergeți toate elementele permutației P găsite la pasul 2.
    2. Pentru elementul de permutare curent P: parametru = ( parametru + 1) mod n,
    3. Dacă parametrul ia valoarea salvată la executarea clauzei 4.2, atunci:
      1. eliminați elementul de permutare curent P.
      2. pentru elementul curent al permutării, luați valoarea obținută la efectuarea pasului 1.
      3. mergeți la punctul 5.1.
  6. Treceți la pasul 2.
Algoritm de căutare

Găsirea tuturor elementelor posibile ale permutației P dat Q și elementele deja găsite ale permutației P.

D, C sunt variabile temporare

Denumiri:

afirmația y este o secvență y de k + 2 elemente ale permutației P utilizate pentru a calcula Q( y ).

cuvântul x al secvenței y este elementul secvenței y cu număr x .

Algoritm:

  1. C=0; D=0;
  2. Dacă elementul P este cunoscut:
    1. Dacă un element P(D) și alte k elemente cunoscute satisfac modelul general de k + 1 elemente ale oricărei instrucțiuni de secvență, atunci găsiți cuvântul rămas din această secvență
    2. Dacă cuvântul găsit nu este un element cunoscut al lui P
      1. Desemnați cuvântul găsit ca element al lui P
      2. C = 1
    3. Dacă cuvântul găsit contrazice oricare dintre elementele găsite anterior, raportați o eroare, opriți algoritmul de căutare.
  3. D=D+1
  4. Dacă D < n  mergeți la pasul 2
  5. Dacă C = 1 , treceți la articolul 1.
Algoritm de selecție

Alegerea unui astfel de nou element de permutare P, al cărui calcul va permite găsirea numărului maxim de elemente P la etapele ulterioare ale algoritmului pentru găsirea valorii inverse a funcției VMPC k. Ca rezultat al algoritmului de selecție, baza noului element este determinată și valoarea parametrului acestuia este aleasă în mod arbitrar . Acest algoritm este potrivit pentru cazul k<4.

B, R sunt variabile temporare

T a , T v − tablouri temporare

W[j] − matrice de numere

Algoritm:

  1. Inițializare variabilă
    1. Ta = 0 , Tv = 0
    2. B =0
    3. R = 1
  2. Numărarea numărului m de elemente cunoscute ale permutației care sunt cuvânt în instrucțiunea secvenței , unde elementul necunoscut P este cuvântul R cu argumentul B. Ta = Ta + W [ m]
  3. Numărarea numărului m de elemente cunoscute ale permutației P care sunt cuvânt în enunțul de succesiune , în care elementul necunoscut al lui P este cuvântul R cu valoarea B. Tv = Tv + W [ m]
  4. R=R+1
  5. Dacă R < n  mergeți la punctul 2.
  6. B=B+1
  7. Dacă B < n  treceți la punctul 1.c.
  8. Se selectează valoarea indexului - oricare dintre indecșii tablourilor T a sau T v , la care valoarea stocată în celula matricei este maximă.
  9. Dacă indexul matricei T a este selectat în clauza 8 , atunci:
    1. X = indice
    2. Y ∈ {0,1,…n-1} este ales aleatoriu astfel încât elementul de permutare cu valoarea Y nu a fost încă găsit.
    3. Rezultat: P(x) = YX - baza, Y - parametru
  10. Dacă la punctul 8 se alege indicele tabloului T v , atunci:
    1. Y = indice
    2. Un X ∈ {0,1,…n-1} este ales aleatoriu astfel încât elementul de permutare cu valoarea X nu a fost încă găsit.
    3. Rezultat: P(x) = YX - parametru, Y - baza

Caracteristici

Probabilitatea de a obține două rezultate identice consecutive atunci când se generează o secvență de cheie folosind cifrul VMPC este  egală cu probabilitatea corespunzătoare a unui generator de secvență aleatoare ideală [2] .  - numărul de biți ai stării interne a generatorului de secvențe pseudoaleatoare, de obicei egal cu . În 2005, A. Maksimov a arătat că, pe baza biților de ieșire, este posibil să se distingă secvența generatorului VMPC de un flux aleator [4]

 Experimentele efectuate de B. Zhultak au arătat că nu există o abatere semnificativă statistic în probabilitatea de apariție în secvența de ieșire:

  • fiecare dintre     valorile posibile (   pentru    octeți ai secvenței de ieșire);
  • fiecare dintre     perechile posibile de valori consecutive (   pentru    octeți ai secvenței de ieșire);
  • fiecare dintre   triplele posibile ale valorilor consecutive (   pentru    octeți ai secvenței de ieșire)

Securitate

Se susține că cifrul stream, datorită modificării semnificative a RC4 original , ținând cont de vulnerabilitățile sale, este mai rezistent la atacurile existente asupra cifrurilor stream și la atacurile asupra cifrului RC4 [2] . În același timp, securitatea majorității criptelor de flux este practic redusă la zero atunci când se folosește aceeași cheie pentru a cripta diferite texte clare. Într-un astfel de caz, cifrul de flux nu mai este un generator de tampon unic (un flux de biți aleatori pentru a cripta textul simplu). Această problemă este oarecum rezolvată de cifrul VMPC prin utilizarea unui vector de inițializare unic pentru fiecare flux criptat.

Se susține că complexitatea atacului asupra cifrului este operațiunile [2] . Cu toate acestea, există o metodă care protejează algoritmul de posibile vulnerabilități. Această abordare constă în repetarea de două ori a permutației dependente de cheie: înainte și după permutarea dependentă de vector de inițializare. Acest program cheie este denumit KSA3.

Link -uri

Vezi și

Literatură

  1. ↑ Gabidulin E.M., Kshevetsky A.S., Kolybelnikov A.I. Protecția informațiilor . - Moscova: MIPT, 2011. - P. 225.
  2. ↑ 1 2 3 4 5 6 7 8 9 Zoltak B. VMPC One-Way Function and Stream Cipher  // Bimal R., Meier W. Fast Software Encryption  . - Berlin: Springer Berlin Heidelberg, 2004. - P. 210-225. - ISBN 978-3-540-25937-4 . - doi : 10.1007/978-3-540-25937-4_14 .
  3. ↑ Schneier B. Criptografie practică . - Moscova: ed. a II-a. — M.: Williams, 2005. — P. 610.
  4. ↑ Goutam P., Subhamoy M. Cifrarea fluxului RC4 și variantele sale  . - Boca Raton, FL: CRC Press, 2012. - ISBN 978-1-4398-3135-9 .
 Criptosisteme simetrice
Cifruri în flux
Rețeaua Feistel
Rețeaua SP
Alte