VMPC

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. april 2015; checks kræver 4 redigeringer .

VMPC ( Variably  Modified Permutation Composition ) er en stream-chiffer [1] der bruges i nogle informationssikkerhedssystemer i computernetværk. Chifferen blev udviklet af kryptografen Bartosz Zultak ( polsk: Bartosz Żółtak , engelsk:  Bartosz Zoltak ) som en forbedret version af den populære RC4 -chiffer . VMPC-algoritmen er bygget som enhver stream-chiffer baseret på en nøgleparameteriseret pseudo-tilfældig bitgenerator. De vigtigste fordele ved chifferen, som RC4, er høj hastighed, variabel størrelse på nøglen og initialiseringsvektor (fra 128 til 512 bit inklusive), nem implementering (bogstaveligt talt et par dusin linjer kode). [2]

Grundlaget for chifferen er en pseudo-tilfældig talgenerator [3] , som er baseret på en envejs irreversibel funktion VMPC ( Variably Modified  Permutation Composition ):

Implementering af algoritmen

Nøgleplan

Algoritme til konvertering af nøglen [2] og (valgfrit) initialiseringsvektoren til en 256-elements permutation P. Initialisering af den globale variabel s.

C : Nøglenængde i bytes

K: Nøgle

z : Længde af initialiseringsvektoren i bytes

V : Initialiseringsvektor

i: 8-bit variabel

j : 16-bit variabel

s : 8-bit global variabel

P : tabel med 256 bytes til lagring af permutationer

1.s = 0 2. for i = 0 til 255: P[i] = i 3. for j = 0 til 767 // udfør trin. 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. Hvis initialiseringsvektortransformation anvendes for j = 0 til 767 // udfør trin. 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

Krypteringsalgoritme

Generering af outputtastsekvens [2] .
For at generere L bytes af outputnøglestrømmen udføres følgende operationer:

L : længden af ​​tastesekvensen i bytes

1. i = 0 2. Gentag afsnit. 3-6 L gange: 3. s = P[(s + P[i]) mod 256] 4. Output = P[(P[P[s]] + 1) mod 256] 5. Temp = P[i] P[i] = P[s] P[s] = Temp 6. i = (i + 1) mod 256

Implementering af en pseudo-tilfældig talgenerator

Envejs VMPC (Variably Modified Permutation Composition)

VMPC-funktion [2] af grad k < n over et n-elementsæt x∈A, A = {0,1,…n-1}:

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

Hvor P: A → En en-til-en n-element permutation
Pi (x) n-element permutation, Pi
= fi ( P(x)), Pi ( x) ≠ P(x) ≠ P j (x) , i≠j i,j∈{1,2…k} fi ( x) = (x + i) mod n ,

Funktion VMPC 1 af grad Q 1 (x)= VMPC 1 (P(x) )=P(P(P(x))+1)

Funktion VMPC 2 potenser af Q 2 (x)= VMPC 2 (P(x))=P(P(P(P(x))+1)+2)

Funktion VMPC 3 potenser af Q 3 (x)= VMPC 3 (P(x))=P(P(P(P(P(x))+1)+2)+3)

Et eksempel på beregning af VMPC-funktionen af ​​1. grad

P(x) er en af ​​varianterne [2] af permutationen {0,1,2,3,4}

x 0 en 2 3 fire
P(x) 3 0 fire en 2
VMPC 1 (P(x)) fire 2 en 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

Find det omvendte af VMPC-funktionen

At finde den gensidige af VMPC-funktionen er beregningsmæssigt vanskelig [2] .
For eksempel, for n = 256, for at beregne den inverse værdi af VMPC 1 -funktionen, kræves operationer , for VMPC 2 - , for VMPC 3 - .

Algoritme

Gendannelse af n - elementpermutationen P svarende til værdien Q(X)= VMPC k (P(X)). 

X, Y er midlertidige variable 

For elementet P(x) = y introduceres følgende notation: 

X − argument: base eller parameter

Y − værdi: henholdsvis parameter eller base

Eksempel: for element P(0) = 3: hvis argument 0 er parameter , så er værdi 3 base . 

Algoritme: 

  1. For en vilkårlig værdi X ∈ {0,1,…n-1} og Y ∈ {0,1,…n-1} , find ét element af permutationen P ud fra antagelsen P(X) = Y. 
    1. Det vælges tilfældigt om X er parameter , Y − base , eller X er base , Y − parameter for elementet P(X) = Y. P(X) = Y er det aktuelle element i permutationen P. 
  2. Find alle elementer i permutationen P ved hjælp af søgealgoritmen.
  3. Hvis alle n elementer af permutationen findes uden modsigelser, så afslut algoritmen.
  4. Ellers
    1. Find et nyt element i permutationen ved hjælp af udvælgelsesalgoritmen, P(X) = Y er det aktuelle element i permutationen.
    2. Gem parameteren for det aktuelle permutationselement.
    3. Gå til trin 2.
  5. Hvis der ved udførelse af punkt 2. opstår en modsigelse:
    1. Slet alle elementerne i permutationen P fundet under trin 2.
    2. For det aktuelle permutationselement P: parameter = ( parameter + 1) mod n,
    3. Hvis parameteren tager den værdi, der blev gemt ved udførelse af paragraf 4.2, så:
      1. fjern det aktuelle permutationselement P.
      2. for det aktuelle element af permutationen skal du tage den værdi, der opnås ved udførelse af trin 1.
      3. gå til punkt 5.1.
  6. Gå til trin 2.
Søgealgoritme

At finde alle mulige elementer af permutationen P givet Q og allerede fundne elementer af permutationen P.

D, C er midlertidige variable

Betegnelser:

sætning y er en sekvens y af k + 2 elementer af permutationen P, der bruges til at beregne Q( y ).

ord x i sekvens y er elementet i sekvens y med nummer x .

Algoritme:

  1. C=0; D=0;
  2. Hvis element P er kendt:
    1. Hvis et element P(D) og k andre kendte elementer opfylder det generelle mønster af k + 1 elementer i en hvilken som helst sekvenssætning , så find det resterende ord i denne sekvens
    2. Hvis det fundne ord ikke er et kendt element i P
      1. Angiv det fundne ord som et element af P
      2. C = 1
    3. Hvis det fundne ord modsiger nogen af ​​de tidligere fundne elementer, rapporter en fejl, afslut søgealgoritmen.
  3. D=D+1
  4. Hvis D < n  gå til punkt 2
  5. Hvis C = 1 , gå til punkt 1.
Valgalgoritme

Valget af et sådant nyt permutationselement P, hvis beregning vil gøre det muligt at finde det maksimale antal elementer P ved efterfølgende trin af algoritmen til at finde den inverse værdi af funktionen VMPC k. Som et resultat af udvælgelsesalgoritmen bestemmes bunden af ​​det nye element, og dets parameterværdi er vilkårligt valgt . Denne algoritme er egnet til tilfældet k<4.

B, R er midlertidige variable

T a , T v − midlertidige arrays

W[j] − række af tal

Algoritme:

  1. Variabel initialisering
    1. Ta = 0, Tv = 0
    2. B = 0
    3. R = 1
  2. Tæller antallet m af kendte elementer af permutationen, der er ord i sekvenssætningen, hvor det ukendte element P er ord R med argument B. Ta = Ta + W [ m]
  3. Tæller antallet m af kendte elementer af permutationen P, der er ord i sekvenssætningen , hvor det ukendte element i P er ord R med værdi B. Tv = Tv + W [ m]
  4. R=R+1
  5. Hvis R < n  gå til punkt 2.
  6. B=B+1
  7. Hvis B < n  gå til punkt 1.c.
  8. Indeksværdien er valgt - et hvilket som helst af indekserne for arrays Ta eller Tv , hvor værdien lagret i arraycellen er maksimal.
  9. Hvis indekset for arrayet Ta er valgt i klausul 8 , så:
    1. X = indeks
    2. Y ∈ {0,1,…n-1} er tilfældigt valgt , således at permutationselementet med værdien Y endnu ikke er fundet.
    3. Resultat: P(x) = YX - base, Y - parameter
  10. Hvis indekset for arrayet Tv i punkt 8 er valgt , så:
    1. Y = indeks
    2. Et X ∈ {0,1,…n-1} er tilfældigt valgt , således at permutationselementet med værdien X endnu ikke er fundet.
    3. Resultat: P(x) = YX - parameter, Y - base

Funktioner

Sandsynligheden for at opnå to på hinanden følgende identiske resultater ved generering af en nøglesekvens ved hjælp af VMPC-krypteringen er  lig med den tilsvarende sandsynlighed for en ideel tilfældig sekvensgenerator [2] .  - antallet af bits i den interne tilstand af pseudo-tilfældig sekvensgenerator, normalt lig med . I 2005 viste A. Maksimov, at det, baseret på output-bittene, er muligt at skelne VMPC-generatorsekvensen fra en tilfældig strøm [4]

 Eksperimenter udført af B. Zhultak viste, at der ikke er nogen statistisk signifikant afvigelse i sandsynligheden for forekomst i outputsekvensen:

  • hver af de mulige     værdier (   for    bytes af outputsekvensen);
  • hvert af de mulige     par af på hinanden følgende værdier (   for    bytes af outputsekvensen);
  • hver af de mulige   tripler af på hinanden følgende værdier (   for    bytes af outputsekvensen)

Sikkerhed

Det hævdes, at stream-chifferet, på grund af den betydelige modifikation af den originale RC4 , under hensyntagen til dens sårbarheder, er mere modstandsdygtig over for eksisterende angreb på stream-ciffer og angreb på RC4-ciffer [2] . Samtidig er sikkerheden for de fleste stream-cifre praktisk talt reduceret til nul, når du bruger den samme nøgle til at kryptere forskellige klartekster. I et sådant tilfælde er stream-chifferet ikke længere en engangs-pad-generator (en strøm af tilfældige bits til at kryptere klarteksten). Dette problem løses i nogen grad af VMPC-chifferet ved at bruge en unik initialiseringsvektor for hver krypteret strøm.

Det hævdes, at kompleksiteten af ​​angrebet på chifferen er operationer [2] . Der er dog en metode, der beskytter algoritmen mod mulige sårbarheder. Denne tilgang består i at gentage den nøgleafhængige permutation to gange: før og efter den initialiseringsvektorafhængige permutation. Denne nøgletidsplan omtales som KSA3.

Links

Se også

Litteratur

  1. ↑ Gabidulin E.M., Kshevetsky A.S., Kolybelnikov A.I. Informationsbeskyttelse . - Moskva: MIPT, 2011. - S. 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. - S. 210-225. - ISBN 978-3-540-25937-4 . - doi : 10.1007/978-3-540-25937-4_14 .
  3. ↑ Schneier B. Praktisk kryptografi . - Moskva: 2. udg. — M.: Williams, 2005. — S. 610.
  4. ↑ Goutam P., Subhamoy M. RC4 -strømchiffer og dens varianter  . - Boca Raton, FL: CRC Press, 2012. - ISBN 978-1-4398-3135-9 .
 Symmetriske kryptosystemer
Stream-cifre
Feistel netværk
SP netværk
Andet