VMPC

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2015. április 30-án áttekintett verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A VMPC ( Variably  Modified Permutation Composition ) egy adatfolyam titkosító [1] , amelyet számítógépes hálózatok egyes információbiztonsági rendszereiben használnak. A titkosítást Bartosz Zultak kriptográfus ( lengyelül: Bartosz Żółtak , angolul:  Bartosz Zoltak ) fejlesztette ki a népszerű RC4 titkosítás továbbfejlesztett változataként . A VMPC algoritmus, mint bármely adatfolyam titkosítás, kulcsparaméteres pszeudo-véletlen bitgenerátorra épül. Az RC4-hez hasonlóan a titkosítás fő előnyei a nagy sebesség, a kulcs és az inicializálási vektor változó mérete (128-tól 512 bitig), a könnyű implementáció (szó szerint néhány tucat sornyi kód). [2]

A titkosítás alapja egy pszeudo-véletlen számgenerátor [3] , amely egy egyirányú irreverzibilis VMPC (Variably Modified  Permutation Composition ) függvényen alapul:

Az algoritmus megvalósítása

Kulcsütemezés

Algoritmus a kulcs [2] és (opcionálisan) az inicializálási vektor átalakítására 256 elemű P permutációvá. Az s globális változó inicializálása.

C: Kulcshossz bájtokban

K: Kulcs

z : Az inicializálási vektor hossza bájtokban

V : Inicializálási vektor

i: 8 bites változó

j : 16 bites változó

s : 8 bites globális változó

P: 256 bájtos táblázat a permutációk tárolására

1.s = 0 2. i = 0 és 255 között: P[i] = i 3. j = 0-tól 767-ig // lépések végrehajtása. 4-6: 4. i = j mod 256 5. s = P[(s + P[i] + K[j mod c]) mod 256] 6. Hőmérséklet = P[i] P[i] = P[s] P[s] = Temp 7. Ha inicializálási vektor transzformációt használunk j = 0 és 767 között // lépések végrehajtása. 8-10: 8. i = j mod 256 9. s = P[(s + P[i] + V[j mod z]) mod 256] 10. Hőmérséklet = P[i] P[i] = P[s] P[s] = Temp

Titkosító algoritmus

Kimeneti kulcssorozat generálása [2] .
A kimeneti kulcsfolyam L bájtjának generálásához a következő műveleteket kell végrehajtani:

L : a kulcssorozat hossza bájtban

1. i = 0 2. Ismételje meg a bekezdéseket. 3-6 liter: 3. s = P[(s + P[i]) mod 256] 4. Kimenet = P[(P[P[s]] + 1) mod 256] 5. Hőmérséklet = P[i] P[i] = P[s] P[s] = Temp 6. i = (i + 1) mod 256

Pszeudo-véletlenszám-generátor megvalósítása

Egyirányú VMPC (Variably Modified Permutation Composition)

K < n fokú VMPC függvény [2] egy n-elemű x∈A halmazon, A = {0,1,…n-1}:

x = 0 és n-1 között: Q k (x) = VMPC k (P(x)) = P(P k (P k-1 (…(P 1 (P(x)))…)))

Ahol P: A → A egy az egyhez n-elem permutáció
P i (x) n-elem permutáció,
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 ,

A Q 1 (x) fokú VMPC 1 függvény = VMPC 1 (P(x) )=P(P(P(x))+1)

VMPC 2 függvény Q 2 (x)= VMPC 2 (P(x))=P(P(P(P(x))+1)+2)

VMPC 3 függvény Q 3 (x)= VMPC 3 (P(x))=P(P(P(P(P(x))+1)+2)+3)

Példa az I. fokú VMPC függvény kiszámítására

P(x) a {0,1,2,3,4} permutáció egyik változata [2]

x 0 egy 2 3 négy
P(x) 3 0 négy egy 2
VMPC 1 (P(x)) négy 2 egy 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

A VMPC függvény inverzének megkeresése

A VMPC függvény reciprokának megtalálása számításilag nehéz [2] .
Például n = 256 esetén a VMPC 1 függvény inverz értékének kiszámításához műveletekre van szükség , VMPC 2 esetén - , VMPC 3 esetén - .

Algoritmus

A Q(X)= VMPC k (P(X)) értéknek megfelelő P n - elemű permutáció helyreállítása. 

X, Y átmeneti változók 

A P(x) = y elemre a következő jelölést vezetjük be: 

X − argumentum: bázis vagy paraméter

Y − érték: paraméter vagy bázis rendre

Példa: P(0) = 3 elem esetén: ha a 0 argumentum paraméter , akkor a 3 érték bázis . 

Algoritmus: 

  1. Egy tetszőleges X ∈ {0,1,…n-1} és Y ∈ {0,1,…n-1} értékhez keressük meg a P permutáció egyik elemét a P(X) = Y feltevésből. 
    1. Véletlenszerűen választjuk ki, hogy X paraméter , Y − bázis , vagy X bázis , Y − P(X) = Y elem paramétere . P(X) = Y a P permutáció aktuális eleme. 
  2. Keresse meg a P permutáció összes elemét a keresési algoritmussal.
  3. Ha a permutáció mind az n eleme ellentmondások nélkül megtalálható, akkor fejezzük be az algoritmust.
  4. Másképp
    1. Keresse meg a permutáció új elemét a kiválasztási algoritmussal, P(X) = Y a permutáció aktuális eleme.
    2. Tárolja az aktuális permutációs elem paraméterét .
    3. Folytassák a 2. lépéssel.
  5. Ha a 2. tétel végrehajtása során ellentmondás merül fel:
    1. Törölje a 2. lépésben talált P permutáció összes elemét.
    2. Az aktuális P permutációs elemhez: paraméter = ( paraméter + 1) mod n,
    3. Ha a paraméter a 4.2. szakasz végrehajtásakor elmentett értéket veszi fel, akkor:
      1. távolítsa el az aktuális P permutációs elemet.
      2. a permutáció aktuális eleméhez vegyük az 1. lépés végrehajtásakor kapott értéket.
      3. ugorjon az 5.1 pontra.
  6. Folytassák a 2. lépéssel.
Keresési algoritmus

A P permutáció összes lehetséges elemének megkeresése adott Q és a P permutáció már megtalált elemeinek megkeresése.

D, C ideiglenes változók

Megnevezések:

Az y állítás a Q( y ) kiszámításához használt P permutáció k + 2 elemének y sorozata .

az y sorozat x szava az y sorozat x számú eleme .

Algoritmus:

  1. C=0; D=0;
  2. Ha a P elem ismert:
    1. Ha egy P(D) elem és k másik ismert elem kielégíti bármely szekvencia utasítás k + 1 elemének általános mintáját , akkor keresse meg a sorozat fennmaradó szavát
    2. Ha a talált szó nem P ismert eleme
      1. Jelölje ki a talált szót a P elemeként
      2. C = 1
    3. Ha a talált szó ellentmond a korábban talált elemek valamelyikének, jelezzen hibát, szakítsa meg a keresési algoritmust.
  3. D=D+1
  4. Ha D < n  , folytassa a 2. lépéssel
  5. Ha C = 1 , menjen az 1. tételre.
Kiválasztási algoritmus

Egy ilyen új P permutációs elem kiválasztása, amelynek kiszámítása lehetővé teszi a P elemek maximális számának megtalálását a VMPC k függvény inverz értékének meghatározására szolgáló algoritmus következő lépéseiben . A kiválasztási algoritmus eredményeként meghatározásra kerül az új elem alapja , és tetszőlegesen megválasztható paraméterértéke . Ez az algoritmus k<4 esetre alkalmas.

B, R átmeneti változók

T a , T v − ideiglenes tömbök

W[j] − számtömb

Algoritmus:

  1. Változó inicializálás
    1. Ta = 0, T v = 0
    2. B =0
    3. R = 1
  2. Megszámoljuk a permutáció azon ismert elemeinek m számát, amelyek a szekvencia utasításban szó , ahol az ismeretlen P elem az R szó B argumentummal . T a = T a + W[m]
  3. Megszámoljuk a P permutáció ismert elemeinek m számát, amelyek szó a szekvencia utasításban , amelyben P ismeretlen eleme a B értékű R szó . Tv = Tv + W [ m]
  4. R=R+1
  5. Ha R < n  , lépjen a 2. pontra.
  6. B=B+1
  7. Ha B < n  , lépjen az 1.c pontra.
  8. Az index értéke kiválasztásra kerül - a T a vagy a T v tömb bármely indexe , amelynél a tömbcellában tárolt érték maximális.
  9. Ha a T a tömb indexe a 8. pontban van kiválasztva , akkor:
    1. X = index
    2. Y ∈ {0,1,…n-1} véletlenszerűen van kiválasztva úgy, hogy az Y értékű permutációs elemet még nem találtuk meg.
    3. Eredmény: P(x) = YX - alap, Y - paraméter
  10. Ha a 8. pontban a T v tömb indexét választjuk , akkor:
    1. Y = index
    2. Egy X ∈ {0,1,…n-1} véletlenszerűen van kiválasztva úgy, hogy az X értékű permutációs elemet még nem találtuk meg.
    3. Eredmény: P(x) = YX - paraméter, Y - alap

Jellemzők

Annak a valószínűsége, hogy két egymást követő azonos eredményt kapunk egy kulcssorozat VMPC titkosítással történő generálásakor,  megegyezik egy ideális véletlensorozat-generátor megfelelő valószínűségével [2] .  - a pszeudo-véletlen sorrendgenerátor belső állapotának bitjeinek száma, általában egyenlő . 2005-ben A. Maksimov megmutatta, hogy a kimeneti bitek alapján meg lehet különböztetni a VMPC generátor szekvenciát egy véletlen adatfolyamtól [4]

 B. Zhultak kísérletei azt mutatták, hogy nincs statisztikailag szignifikáns eltérés a kimeneti szekvencia előfordulási valószínűségében:

  • a lehetséges     értékek mindegyike (   a    kimeneti sorozat bájtjaihoz);
  •    az egymást követő értékek minden lehetséges  párja (   a    kimeneti sorozat bájtjaihoz);
  •   az egymást követő értékek lehetséges háromszorosai (   a    kimeneti sorozat bájtjaihoz)

Biztonság

Azt állítják, hogy a stream titkosítás az eredeti RC4 jelentős módosítása miatt , figyelembe véve annak sebezhetőségeit, jobban ellenáll a stream titkosítások és az RC4 titkosítás elleni támadásoknak [2] . Ugyanakkor a legtöbb adatfolyam-rejtjel biztonsága gyakorlatilag nullára csökken, ha ugyanazt a kulcsot használják különböző nyílt szövegek titkosításához. Ilyen esetben az adatfolyam-rejtjel többé nem egyszeri pad-generátor (véletlenszerű bitek folyama a nyílt szöveg titkosításához). Ezt a problémát valamelyest megoldja a VMPC-rejtjel, minden egyes titkosított adatfolyamhoz egyedi inicializálási vektort használva.

Azt állítják, hogy a titkosítás elleni támadás összetettsége műveletek [2] . Van azonban egy módszer, amely megvédi az algoritmust az esetleges sebezhetőségektől. Ez a megközelítés abból áll, hogy a kulcsfüggő permutációt kétszer megismételjük: az inicializálás-vektor-függő permutáció előtt és után. Ezt a kulcsfontosságú ütemezést KSA3-nak nevezik.

Linkek

Lásd még

Irodalom

  1. ↑ Gabidulin E.M., Kshevetsky A.S., Kolybelnikov A.I. Információvédelem . - Moszkva: MIPT, 2011. - 225. o.
  2. ↑ 1 2 3 4 5 6 7 8 9 Zoltak B. VMPC egyirányú funkció és adatfolyam titkosítás  // 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. Gyakorlati kriptográfia . - Moszkva: 2. kiadás. — M.: Williams, 2005. — 610. o.
  4. ↑ Goutam P., Subhamoy M. RC4 adatfolyam titkosítás és változatai  . - Boca Raton, FL: CRC Press, 2012. - ISBN 978-1-4398-3135-9 .
 Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam
Feistel hálózat
SP hálózat
Egyéb