Blokcodeerstandaarden. Lineaire cryptanalyse voor dummies

Algoritme DES

De belangrijkste voordelen van het DES-algoritme:

· er wordt slechts één sleutel met een lengte van 56 bits gebruikt;

· nadat u een bericht met één pakket hebt gecodeerd, kunt u elk ander pakket gebruiken om het te decoderen;

· de relatieve eenvoud van het algoritme zorgt ervoor hoge snelheid informatieverwerking;

· voldoende hoge stabiliteit van het algoritme.

DES codeert 64-bits gegevensblokken met behulp van een 56-bits sleutel. Decodering in DES is de omgekeerde bewerking van codering en wordt uitgevoerd door de coderingsbewerkingen te herhalen negatieve reeks(ondanks de schijnbare voor de hand liggende, wordt dit niet altijd gedaan. Later zullen we kijken naar cijfers waarin encryptie en decryptie worden uitgevoerd met behulp van verschillende algoritmen).

Het versleutelingsproces bestaat uit een initiële permutatie van de bits van een blok van 64 bits, zestien versleutelingscycli en tenslotte een omgekeerde permutatie van de bits (Fig. 1).

Er moet onmiddellijk worden opgemerkt dat ALLE tabellen in dit artikel STANDAARD zijn en daarom ongewijzigd in uw implementatie van het algoritme moeten worden opgenomen. Alle permutaties en codes in de tabellen worden door de ontwikkelaars zo geselecteerd dat het decoderingsproces zo moeilijk mogelijk wordt gemaakt door het selecteren van een sleutel. De structuur van het DES-algoritme wordt getoond in figuur 2.

Afb.2. Structuur van het DES-coderingsalgoritme

Laat het volgende blok T van 8 bytes als volgt uit het bestand worden gelezen, dat als volgt wordt getransformeerd met behulp van de initiële permutatiematrix IP (Tabel 1): bit 58 van blok T wordt bit 1, bit 50 wordt bit 2, enz., waardoor geef het resultaat: T(0) = IP(T).

De resulterende bitreeks T(0) wordt verdeeld in twee reeksen van elk 32 bits: L(0) - linker- of hoge-orde bits, R(0) - rechter- of lage-orde bits.

Tabel 1: IP-initiële permutatiematrix

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Vervolgens wordt encryptie uitgevoerd, bestaande uit 16 iteraties. Resultaat i iteratie wordt beschreven door de volgende formules:

R(i) = L(i-1) xof f(R(i-1), K(i)) ,

waarbij xor de EXCLUSIEVE OF-bewerking is.

De functie f wordt de encryptiefunctie genoemd. De argumenten zijn de 32-bits reeks R(i-1), verkregen bij de (i-1)th iteratie, en de 48-bits sleutel K(i), die het resultaat is van het converteren van de 64-bits sleutel K. In detail worden hieronder de encryptiefunctie en het algoritme voor het verkrijgen van sleutels K(i) beschreven.

Bij de 16e iteratie worden de reeksen R(16) en L(16) (zonder permutatie) verkregen, die worden samengevoegd tot een 64-bits reeks R(16)L(16).

Vervolgens worden de posities van de bits van deze reeks opnieuw gerangschikt in overeenstemming met de matrix IP-1 (Tabel 2).

Tabel 2: Inverse permutatiematrix IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

De IP -1- en IP-matrices zijn als volgt gerelateerd: de waarde van het 1e element van de IP -1-matrix is 40, en de waarde van het 40e element van de IP-matrix is 1, de waarde van de 2e element van de IP -1-matrix is 8, en de waarde van het 8e IP-matrixelement is gelijk aan 2, enz.

Het proces van gegevensdecodering is omgekeerd aan het coderingsproces. Alle acties moeten worden uitgevoerd in omgekeerde volgorde. Dit betekent dat de gedecodeerde gegevens eerst opnieuw worden gerangschikt volgens de IP-1-matrix, en vervolgens dezelfde acties worden uitgevoerd op de reeks bits R(16)L(16) als bij het coderingsproces, maar in omgekeerde volgorde.

Het iteratieve decoderingsproces kan worden beschreven met de volgende formules:

R(i-1) = L(i), ik = 1, 2, ..., 16;

L(i-1) = R(i) xof f(L(i), K(i)), i = 1, 2, ..., 16 .

Bij de 16e iteratie worden de reeksen L(0) en R(0) verkregen, die worden samengevoegd tot een 64-bits reeks L(0)R(0).

De bitposities van deze reeks worden vervolgens opnieuw gerangschikt volgens de IP-matrix. Het resultaat van een dergelijke permutatie is de oorspronkelijke 64-bits reeks.

Beschouw nu de encryptiefunctie f(R(i-1),K(i)). Het is schematisch weergegeven in Fig. 3.

Afb.3. Berekening van functie f(R(i-1), K(i))

Om de waarde van de functie f te berekenen, worden de volgende matrixfuncties gebruikt:

E - uitbreiding van een reeks van 32 bits naar 48 bits,

S1, S2, ..., S8 - conversie van een 6-bits blok naar een 4-bits blok,

P - permutatie van bits in een reeks van 32 bits.

De expansiefunctie E is gedefinieerd in Tabel 3. Volgens deze tabel zijn de eerste 3 bits van E(R(i-1)) bits 32, 1 en 2, en de laatste 31, 32 en 1.

Tabel 3: Uitbreidingsfunctie E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Het resultaat van de functie E(R(i-1)) is een reeks van 48 bits die modulo 2 (xor-bewerking) wordt opgeteld met de 48-bits sleutel K(i). De resulterende reeks van 48 bits wordt verdeeld in acht blokken van 6 bits B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). Dat is:

E(R(i-1)) xof K(i) = B(1)B(2)...B(8) .

De functies S1, S2, ..., S8 zijn gedefinieerd in Tabel 4.

Tabel 4

Naar tabel 4. verdere verduidelijking is vereist. Stel dat de invoer van de matrixfunctie Sj een 6-bits blok B(j) = b1b2b3b4b5b6 is, dan geeft het twee-bits getal b1b6 het rijnummer van de matrix aan, en b2b3b4b5 het kolomnummer. Het resultaat van Sj(B(j)) zal een 4-bits element zijn dat zich op het snijpunt bevindt gespecificeerde lijnen en kolom.

Bijvoorbeeld B(1)=011011. Dan bevindt S1(B(1)) zich op het snijpunt van rij 1 en kolom 13. In kolom 13 van rij 1 is de waarde 5. Dit betekent S1(011011)=0101.

Door de selectiebewerking toe te passen op elk van de 6-bits blokken B(1), B(2), ..., B(8), verkrijgen we de 32-bits reeks S1(B(1))S2(B(2) ))S3(B(3))...S8(B(8)).

Ten slotte moeten, om het resultaat van de encryptiefunctie te verkrijgen, de bits van deze reeks opnieuw worden gerangschikt. Voor dit doel wordt de permutatiefunctie P gebruikt (Tabel 5). In de invoerreeks worden de bits opnieuw gerangschikt, zodat bit 16 bit 1 wordt, bit 7 bit 2, enzovoort.

Tabel 5: Permutatiefunctie P

Dus,

f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))

Om de beschrijving van het gegevenscoderingsalgoritme te voltooien, moet nog het algoritme worden gepresenteerd voor het verkrijgen van 48-bits sleutels K(i), i=1...16. Bij elke iteratie wordt een nieuwe sleutelwaarde K(i) gebruikt, waaruit wordt berekend initiële sleutel K. K is een 64-bits blok met acht pariteitsbits op posities 8,16,24,32,40,48,56,64.

Om controlebits te verwijderen en de rest opnieuw te rangschikken, wordt functie G van de initiële toetsvoorbereiding gebruikt (Tabel 6).

Tabel 6

Matrix G van initiële toetsvoorbereiding

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Het resultaat van de transformatie G(K) wordt verdeeld in twee 28-bits blokken C(0) en D(0), en C(0) zal bestaan uit de bits 57, 49, ..., 44, 36 van de sleutel K, en D(0 ) zullen bestaan uit bits 63, 55, ..., 12, 4 van sleutel K. Na het definiëren van C(0) en D(0), C(i) en D(i), i= 1...16, worden recursief bepaald. Om dit te doen, past u een cyclische verschuiving naar links toe met één of twee bits, afhankelijk van het iteratienummer, zoals weergegeven in Tabel 7.

Tabel 7

Shift-tabel voor sleutelberekening

Iteratienummer	Verschuiving (bits)
01	1
02	1
03	2
04	2
05	2
06	2
07	2
08	2
09	1
10	2
11	2
12	2
13	2
14	2
15	2
16	1

De resulterende waarde wordt opnieuw “gemengd” volgens de matrix H (Tabel 8).

Tabel 8: Sleutelinvulmatrix H

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

De sleutel K(i) zal bestaan uit de bits 14, 17, ..., 29, 32 van de reeks C(i)D(i). Dus:

K(i) = H(C(i)D(i))

Het blokdiagram van het sleutelberekeningsalgoritme wordt getoond in figuur 4.

Afb.4. Blokdiagram van het algoritme voor het berekenen van de sleutel K(i)

Het herstellen van de originele tekst wordt uitgevoerd met behulp van dit algoritme, maar eerst gebruikt u de sleutel

K(15), dan K(14) enzovoort. Nu zou je moeten begrijpen waarom de auteur met klem aanbeveelt om de gegeven matrices te gebruiken. Als je roekeloos gaat, kun je eindigen met een zeer geheime code, maar je kunt deze niet zelf kraken!

Bedrijfsmodi van het DES-algoritme

Om zo volledig mogelijk aan alle vereisten te voldoen commerciële systemen encryptie, zijn verschillende werkingsmodi van het DES-algoritme geïmplementeerd. De meest gebruikte modi zijn:

· elektronisch codeboek (Electronic Codebook) - ECB;

· keten van digitale blokken (Cipher Block Chaining) - CBC;

· digitaal feedback(Cijferfeedback) - CFB;

· externe feedback (uitgangsfeedback) - OFB.

In deze modus bronbestand M is verdeeld in blokken van 64 bits (elk 8 bytes): M = M(1)M(2)...M(n). Elk van deze blokken wordt onafhankelijk gecodeerd met dezelfde coderingssleutel (Fig. 5). Het belangrijkste voordeel van dit algoritme is het gemak van implementatie. Het nadeel is dat het relatief zwak is tegen ervaren cryptanalisten.

De DES-standaard is ontworpen om te beschermen tegen ongeoorloofde toegang tot gevoelige maar niet-geclassificeerde informatie bij Amerikaanse overheids- en commerciële organisaties. Het algoritme dat ten grondslag ligt aan de standaard verspreidde zich vrij snel en werd al in 1980 goedgekeurd door het Amerikaanse National Institute of Standards and Technology. Vanaf dit moment wordt DES niet alleen qua naam, maar ook feitelijk een standaard. Verschijnen software en gespecialiseerde microcomputers die zijn ontworpen om informatie in datatransmissienetwerken te coderen en te decoderen.

Tot op heden is DES het meest gebruikte algoritme in beveiligingssystemen commerciële informatie. Bovendien wordt de implementatie van het DES-algoritme in dergelijke systemen een teken van goede vorm.

De belangrijkste voordelen van het DES-algoritme:

· er wordt slechts één sleutel met een lengte van 56 bits gebruikt;

· nadat u een bericht met één pakket hebt gecodeerd, kunt u elk ander pakket gebruiken om het te decoderen;

· de relatieve eenvoud van het algoritme zorgt voor een hoge snelheid van informatieverwerking;

· voldoende hoge stabiliteit van het algoritme.

DES codeert 64-bits gegevensblokken met behulp van een 56-bits sleutel. Decodering in DES is de omgekeerde bewerking van codering en wordt uitgevoerd door de coderingsbewerkingen in omgekeerde volgorde te herhalen (ondanks de schijnbare voor de hand liggende wordt dit niet altijd gedaan. Later zullen we kijken naar cijfers waarin codering en decodering worden uitgevoerd met behulp van verschillende algoritmen).

Het versleutelingsproces bestaat uit een initiële permutatie van de bits van een 64-bits blok, zestien versleutelingscycli en ten slotte een omgekeerde bitpermutatie (Figuur 1).

Rijst. 2.

Laat het volgende blok T van 8 bytes als volgt uit het bestand worden gelezen, dat wordt getransformeerd met behulp van de initiële permutatiematrix IP (Tabel 1): bit 58 van blok T wordt bit 1, bit 50 wordt bit 2, enz., waardoor resultaat: T(0) = IP(T).

De resulterende bitreeks T(0) wordt verdeeld in twee reeksen van elk 32 bits: L(0) - linker- of hoge-orde bits, R(0) - rechter- of lage-orde bits.

Tabel 1: IP-initiële permutatiematrix

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Vervolgens wordt encryptie uitgevoerd, bestaande uit 16 iteraties. Resultaat i-de iteratie wordt beschreven door de volgende formules:

R(i) = L (i-1) xof f (R(i-1), K(i)),

waarbij xor de EXCLUSIEVE OF-bewerking is.

Bij de 16e iteratie worden de reeksen R(16) en L(16) (zonder permutatie) verkregen, die worden samengevoegd tot een 64-bits reeks R(16) L(16).

Vervolgens worden de bitposities van deze reeks opnieuw gerangschikt in overeenstemming met de IP-1-matrix (Tabel 2).

Tabel 2: Inverse permutatiematrix IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

Het proces van gegevensdecodering is omgekeerd aan het coderingsproces. Alle stappen moeten in omgekeerde volgorde worden uitgevoerd. Dit betekent dat de gedecodeerde gegevens eerst opnieuw worden gerangschikt volgens de IP-1-matrix, en vervolgens dezelfde acties worden uitgevoerd op de reeks bits R(16) L(16) als bij het coderingsproces, maar in omgekeerde volgorde.

Het iteratieve decoderingsproces kan worden beschreven met de volgende formules:

R (i-1) = L(i), ik = 1, 2,…, 16;

L (i-1) = R(i) xof f (L(i), K(i)), i = 1, 2,…, 16.

Bij de 16e iteratie worden de reeksen L(0) en R(0) verkregen, die worden samengevoegd tot een 64-bits reeks L(0) R(0).

De bitposities van deze reeks worden vervolgens opnieuw gerangschikt volgens de IP-matrix. Het resultaat van een dergelijke permutatie is de oorspronkelijke 64-bits reeks.

Beschouw nu de encryptiefunctie f (R(i-1), K(i)). Het is schematisch weergegeven in Fig. 3.

Rijst. 3.

Om de waarde van de functie f te berekenen, worden de volgende matrixfuncties gebruikt:

E - uitbreiding van een reeks van 32 bits naar 48 bits,

S1, S2,…, S8 - conversie van een 6-bits blok naar een 4-bits blok,

P - permutatie van bits in een reeks van 32 bits.

De uitbreidingsfunctie E wordt bepaald door tabel. 3. Volgens deze tabel zijn de eerste 3 bits van E (R(i-1)) bits 32, 1 en 2, en de laatste 31, 32 en 1.

Tabel 3: Uitbreidingsfunctie E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Het resultaat van functie E (R(i-1)) is een 48-bits reeks die modulo 2 (xor-bewerking) wordt opgeteld met de 48-bits sleutel K(i). De resulterende reeks van 48 bits wordt verdeeld in acht blokken van 6 bits B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). Dat is:

E (R(i-1)) xof K(i) = B(1) B(2)… B(8).

Functies S1, S2,…, S8 zijn gedefinieerd in de tabel. 4.

Tabel 4

Aan tafel 4. Er is aanvullende verduidelijking nodig. Stel dat de invoer van de matrixfunctie Sj een 6-bits blok B(j) = b1b2b3b4b5b6 is, dan geeft het twee-bits getal b1b6 het rijnummer van de matrix aan, en b2b3b4b5 het kolomnummer. Het resultaat van Sj (B(j)) zal een 4-bits element zijn dat zich op het snijpunt van de gespecificeerde rij en kolom bevindt.

Bijvoorbeeld B(1)=011011. Dan bevindt S1 (B(1)) zich op het snijpunt van rij 1 en kolom 13. In kolom 13 van rij 1 is de waarde 5. Dit betekent S1 (011011)=0101.

Door de selectiebewerking toe te passen op elk van de 6-bits blokken B(1), B(2),…, B(8), verkrijgen we een 32-bits reeks S1 (B(1)) S2 (B(2)) S3 (B(3))... S8 (B(8)).

Tabel 5: Permutatiefunctie P

Dus,

f (R(i-1), K(i)) = P (S1 (B(1)),… S8 (B(8)))

Om de beschrijving van het gegevenscoderingsalgoritme te voltooien, moet nog het algoritme worden gepresenteerd voor het verkrijgen van 48-bits sleutels K(i), i=1...16. Bij elke iteratie wordt een nieuwe sleutelwaarde K(i) gebruikt, die wordt berekend op basis van de initiële sleutel K. K is een 64-bits blok met acht pariteitsbits op posities 8,16,24,32,40,48, 56. 64.

Om controlebits te verwijderen en de rest opnieuw te rangschikken, wordt functie G van de initiële toetsvoorbereiding gebruikt (Tabel 6).

Tabel 6

Matrix G van initiële toetsvoorbereiding

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Het resultaat van de transformatie G(K) wordt verdeeld in twee 28-bits blokken C(0) en D(0), en C(0) zal bestaan uit de bits 57, 49, ..., 44, 36 van de sleutel K, en D(0) zullen bestaan uit bits 63, 55,…, 12, 4 sleutels K. Na het bepalen van C(0) en D(0), C(i) en D(i), i=1… 16, worden recursief bepaald. Om dit te doen, past u een cyclische verschuiving naar links toe met één of twee bits, afhankelijk van het iteratienummer, zoals weergegeven in de tabel. 7.

Tabel 7. Shift-tabel voor sleutelberekening

Iteratienummer	Verschuiving (bits)

De resulterende waarde wordt opnieuw “gemengd” volgens de matrix H (Tabel 8).

Tabel 8: Sleutelinvulmatrix H

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

De sleutel K(i) zal bestaan uit de bits 14, 17,…, 29, 32 van de reeks C(i) D(i). Dus:

K(i) = H (C(i) D(i))

Het blokdiagram van het sleutelberekeningsalgoritme wordt getoond in Fig. 4.

Rijst. 4.

Het herstellen van de originele tekst wordt uitgevoerd met behulp van dit algoritme, maar eerst gebruik je de sleutel K(15), dan K(14) enzovoort. Nu zou je moeten begrijpen waarom de auteur met klem aanbeveelt om de gegeven matrices te gebruiken. Als je roekeloos gaat, kun je eindigen met een zeer geheime code, maar je kunt deze niet zelf kraken!

Handleiding

Hallo %gebruikersnaam%!
Veel mensen weten dat dit de standaardstandaard is op het gebied van symmetrische encryptie voor een lange tijd werd overwogen DES-algoritme. De eerste succesvolle aanval op dit niet te doden algoritme werd gepubliceerd in 1993, 16 jaar nadat het als standaard werd aangenomen. De methode, die de auteur lineaire cryptanalyse noemde, in de aanwezigheid van 2 47 paren platte/cijferteksten, maakt het mogelijk om de geheime sleutel te onthullen DES-cijfer voor 2 43 operaties.
Onder de snede zal ik proberen de belangrijkste punten van deze aanval kort te schetsen.

Lineaire cryptanalyse

Lineaire cryptanalyse is een speciaal soort aanval op symmetrische cijfers, gericht op het herstellen van een onbekende coderingssleutel van bekende geopende berichten en de bijbehorende cijferteksten.

IN algemeen geval aanval gebaseerd lineaire cryptanalyse komt neer op de volgende voorwaarden. De aanvaller heeft een groot aantal paren platte tekst/cijfertekst verkregen met dezelfde coderingssleutel K. Het doel van de aanvaller is om de sleutel K geheel of gedeeltelijk te herstellen.

Allereerst onderzoekt de aanvaller het cijfer en vindt het zogenaamde statistische analoog, d.w.z. een vergelijking met de volgende vorm, die geldt met waarschijnlijkheid P ≠ 1/2 voor een willekeurig publiek/privaat tekstpaar en een vaste sleutel:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
waarbij Pn, Cn, Kn de n-de bits van de tekst, cijfertekst en sleutel zijn.
Zodra een dergelijke vergelijking is gevonden, kan de aanvaller 1 bit aan sleutelinformatie herstellen met behulp van het volgende algoritme

Algoritme 1
Laat T het aantal teksten zijn waarvoor linkerkant vergelijking (1) is dan gelijk aan 0
Als T>N/2, waarbij N het aantal bekende leesbare teksten is.
Neem aan dat K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (als P>1/2) of 1 (als P<1/2).
Anders
Neem aan dat K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (als P>1/2) of 0 (als P<1/2).
Het is duidelijk dat het succes van het algoritme rechtstreeks afhangt van de waarde van |P-1/2| en op het aantal beschikbare open/gesloten tekstparen N. Hoe meer de waarschijnlijkheid P van gelijkheid (1) verschilt van 1/2, hoe minder aantal open teksten N nodig is voor de aanval.

Er zijn twee problemen die moeten worden opgelost om de aanval te laten slagen:

Hoe een effectieve vergelijking van de vorm (1) te vinden.
Hoe deze vergelijking te gebruiken om meer dan één stukje informatie over de sleutel te krijgen.

Laten we de oplossing voor deze problemen bekijken met behulp van de DES-codering als voorbeeld.

Beschrijving van DES

Maar laten we eerst kort beschrijven hoe het algoritme werkt. Er is al genoeg gezegd over DES. Een volledige beschrijving van het cijfer is te vinden op Wikipedia. Om de aanval verder uit te leggen hebben we echter een aantal definities nodig die het beste vooraf kunnen worden geïntroduceerd.

DES is dus een blokcijfer gebaseerd op het Feistel-netwerk. Het cijfer heeft een blokgrootte van 64 bits en een sleutelgrootte van 56 bits. Laten we eens kijken naar het versleutelingsschema van het DES-algoritme.

Zoals uit de afbeelding blijkt, worden bij het coderen van tekst de volgende bewerkingen uitgevoerd:

Initiële bitpermutatie. In dit stadium worden de bits van het invoerblok in een bepaalde volgorde geschud.
Hierna worden de gemengde bits in twee helften gesplitst, die naar de ingang van de Feistel-functie worden gevoerd. Voor standaard DES omvat het Feistel-netwerk 16 ronden, maar er bestaan ook andere varianten van het algoritme.
De twee blokken die in de laatste transformatieronde zijn verkregen, worden gecombineerd en er wordt een nieuwe permutatie uitgevoerd op het resulterende blok.

In elke ronde van het Feistel-netwerk worden de minst significante 32 bits van het bericht via de functie f doorgegeven:

Laten we eens kijken naar de bewerkingen die in dit stadium zijn uitgevoerd:

Het invoerblok wordt doorgegeven via de uitbreidingsfunctie E, die een blok van 32 bits omzet in een blok van 48 bits.
Het resulterende blok wordt toegevoegd aan de ronde sleutel Ki.
Het resultaat van de vorige stap wordt verdeeld in 8 blokken van elk 6 bits.
Elk van de ontvangen blokken Bi wordt door de substitutiefunctie S-Boxi gevoerd, die de reeks van 6 bits vervangt door een blok van 4 bits.
Het resulterende 32-bits blok wordt door de permutatie P geleid en geretourneerd als resultaat van functie f.

Van het grootste belang voor ons vanuit het oogpunt van cijfercryptanalyse zijn S-blokken, ontworpen om de verbinding tussen de invoer- en uitvoergegevens van de functie f te verbergen. Om DES succesvol aan te vallen, zullen we eerst statistische analogen construeren voor elk van de S-boxen, en deze vervolgens uitbreiden naar het gehele cijfer.

S-blokanalyse

Elke S-box neemt een reeks van 6 bits als invoer, en voor elke reeks wordt een vaste waarde van 4 bits geretourneerd. Die. Er zijn in totaal 64 invoer- en uitvoeropties. Onze taak is om de relatie tussen de invoer- en uitvoergegevens van S-blokken te tonen. Voor de derde S-box van het DES-cijfer is het derde bit van de invoerreeks bijvoorbeeld in 38 van de 64 gevallen gelijk aan het derde bit van de uitvoerreeks. Daarom hebben we de volgende statistische analoog gevonden voor de derde S -doos:
S 3 (x) = x, waaraan wordt voldaan met waarschijnlijkheid P=38/64.
Beide zijden van de vergelijking vertegenwoordigen 1 bit informatie. Als de linker- en rechterkant onafhankelijk van elkaar zouden zijn, zou de vergelijking dus tevreden moeten zijn met een waarschijnlijkheid van 1/2. We hebben dus zojuist de relatie aangetoond tussen de invoer en uitvoer van de derde S-box van het DES-algoritme.

Laten we eens kijken hoe we in het algemene geval een statistische analoog van de S-box kunnen vinden.

Voor een S-box Sa, 1 ≤ α ≤ 63 en 1 ≤ β ≤ 15, beschrijft de waarde NS a (α, β) hoe vaak van de 64 mogelijke XOR-invoerbits Sa gesuperponeerd op de α-bits gelijk zijn aan de XOR-uitvoerbits gesuperponeerd op de α-bits β, dat wil zeggen:
waarbij het symbool logisch AND is.
De waarden van α en β waarvoor NS a (α, β) het meest verschilt van 32 beschrijven de meest efficiënte statistische analoog van de S-box Sa.

De meest effectieve analoog werd gevonden in de 5e S-box van het DES-cijfer voor α = 16 en β = 15 NS 5 (16, 15) = 12. Dit betekent dat de volgende vergelijking geldt: Z=Y ⊕ Y ⊕ Y ⊕ Y, waarbij Z de invoerreeks van de S-box is en Y de uitvoerreeks.
Of rekening houdend met het feit dat in het DES-algoritme de gegevens, voordat ze de S-box binnenkomen, modulo 2 worden opgeteld met een ronde sleutel, d.w.z. Z = X ⊕ K krijgen we
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, waarbij X en Y de invoer- en uitvoergegevens zijn van de functie f zonder rekening te houden met permutaties.
De resulterende vergelijking wordt uitgevoerd in alle ronden van het DES-algoritme met dezelfde waarschijnlijkheid P = 12/64.
De volgende tabel toont een lijst met effectieve, d.w.z. met de grootste afwijking van P=1/2, statistische analogen voor elk s-blok van het DES-algoritme.

Statistische analogen construeren voor meerdere DES-rondes

Laten we nu laten zien hoe we de statistische analogen van verschillende DES-rondes kunnen combineren en uiteindelijk een statistische analoog voor het hele cijfer kunnen verkrijgen.
Om dit te doen, overweeg een drierondeversie van het algoritme:

Laten we een efficiënte statistische analoog van de 5e s-box gebruiken om bepaalde bits van de X(2)-waarde te berekenen.
We weten dat met waarschijnlijkheid 12/64 de gelijkheid geldt in de f-functie X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, waar X het tweede invoerbit van de 5e S-box is, is dit in wezen het 26e bit van de reeks die wordt verkregen na het uitbreiden van de invoerbits. Door de uitbreidingsfunctie te analyseren, kunnen we vaststellen dat het 26e bit wordt vervangen door het 17e bit van de X(1)-reeks.
Op dezelfde manier zijn Y,..., Y in wezen de 17e, 18e, 19e en 20e bits van de reeks verkregen vóór de permutatie P. Als we de permutatie P onderzoeken, ontdekken we dat de bits Y,..., Y feitelijk bits Y zijn (1), Y(1), Y(1), Y(1).
Het sleutelbit K dat bij de vergelijkingen betrokken is, is het 26e bit van de subsleutel K1 van de eerste ronde, waarna de statistische analoog de volgende vorm aanneemt:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Vandaar, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) met waarschijnlijkheid P=12/64.
Als je 3, 8, 14, 25 bits van de reeks Y(1) kent, kun je 3, 8, 14, 25 bits van de reeks X(2) vinden:
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) of rekening houdend met vergelijking (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) met een waarschijnlijkheid van 12/64.

Laten we een soortgelijke uitdrukking vinden met behulp van de laatste ronde. Deze keer hebben we de vergelijking
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Omdat
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
wij snappen dat
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) met een waarschijnlijkheid van 12/64.

Door de rechterkant van de vergelijkingen (3) en (4) gelijk te stellen, verkrijgen we
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 met waarschijnlijkheid (12/64) 2 +(1-12/64) 2.
Rekening houdend met het feit dat X(1) = PR en X(3) = CR verkrijgen we een statistische analoog
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
die wordt uitgevoerd met waarschijnlijkheid (12/64) 2 + (1-12/64) 2 =0,7.
De hierboven beschreven statistische analoog kan als volgt grafisch worden weergegeven (bits in de figuur zijn genummerd van rechts naar links en beginnend bij nul):

Alle bits aan de linkerkant van de vergelijking zijn bekend bij de aanvaller, dus hij kan algoritme 1 toepassen en de waarde van K1 ⊕ K3 achterhalen. Laten we laten zien hoe u met behulp van deze statistische analoog niet 1, maar 12 bits van de coderingssleutel K kunt openen.

Aanval op DES met bekende platte tekst

Laten we een methode presenteren waarmee u de aanval kunt uitbreiden en onmiddellijk 6 bits van de eerste ronde connect kunt verkrijgen.
Bij het opstellen van vergelijking (5) hebben we rekening gehouden met het feit dat we de waarde van F1(PR, K1) niet kennen. Daarom hebben we de statistische analoog K1 ⊕ PR gebruikt.
Laten we de waarde F1(PR, K1) retourneren in plaats van de uitdrukking K1 ⊕ PR en de volgende vergelijking verkrijgen:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , die zal worden uitgevoerd met waarschijnlijkheid 12/64. De waarschijnlijkheid is veranderd sinds we alleen de statistische analoog uit de derde ronde hebben achtergelaten, alle andere waarden staan vast.

We hebben hierboven al vastgesteld dat de waarde van F1(PR, K1) wordt beïnvloed door de ingangsbits van de 5e S-box, namelijk de sleutelbits K1 en de bits van het PR-blok. Laten we laten zien hoe u, met slechts een set open/gesloten teksten, de waarde van K1 kunt herstellen. Om dit te doen, zullen we algoritme 2 gebruiken.

Algoritme 2
Laat N het aantal open/gesloten tekstparen zijn dat bekend was vóór de aanval. Om vervolgens de sleutel te openen, moet u de volgende stappen uitvoeren.
Voor (i=0; ik<64; i++) do
{
Voor(j=0; j {
als(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) dan
T ik =T ik +1
}
}
Als een waarschijnlijke reeks K1 wordt een waarde van i genomen zodat de uitdrukking |T i -N/2| heeft de maximale waarde.

Gegeven een voldoende aantal bekende leesbare teksten, zal het algoritme een grote waarschijnlijkheid hebben om de juiste waarde van de zes bits van de eerste ronde subsleutel K1 terug te geven. Dit wordt verklaard door het feit dat als de variabele i niet gelijk is aan K1, de waarde van de functie F1(PR j, K) willekeurig zal zijn en het aantal vergelijkingen voor een dergelijke waarde van i waarvoor de linkerkant gelijk is gelijk aan nul zal neigen naar N/2. Als de subsleutel correct wordt geraden, is de linkerkant gelijk aan het vaste bit K3 met een waarschijnlijkheid van 12/64. Die. er zal een significante afwijking zijn van N/2.

Nadat u 6 bits van subsleutel K1 heeft ontvangen, kunt u op dezelfde manier 6 bits van subsleutel K3 openen. Het enige wat u hoeft te doen is C vervangen door P en K1 door K3 in vergelijking (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algoritme 2 retourneert de juiste K3-waarde omdat het decoderingsproces van het DES-algoritme identiek is aan het coderingsproces, alleen de sleutelreeks is omgekeerd. Dus in de eerste decoderingsronde wordt de sleutel K3 gebruikt, en in de laatste ronde wordt de sleutel K1 gebruikt.

Nadat de aanvaller 6 bits van de subsleutels K1 en K3 heeft ontvangen, herstelt hij 12 bits van de gemeenschappelijke sleutel van het cijfer K, omdat ronde sleutels zijn de gebruikelijke permutatie van de sleutel K. Het aantal leesbare teksten dat nodig is voor een succesvolle aanval hangt af van de waarschijnlijkheid van de statistische analoog. Om een 12-bits DES-sleutel met drie rondes te kraken, zijn 100 openbare/private tekstparen voldoende. Om 12 bits van een 16-ronde DES-sleutel te kraken, zijn ongeveer 244 tekstparen nodig. De resterende 44 bits van de sleutel worden geopend met normaal brute kracht.

Het DES-algoritme is zeer geschikt voor zowel encryptie als authenticatie van gegevens. Hiermee kan 64-bits leesbare tekstinvoer rechtstreeks worden omgezet naar 64-bits cijfertekstuitvoer, maar de gegevens zijn zelden beperkt tot 64 bits.

Om het DES-algoritme te gebruiken om een verscheidenheid aan cryptografische problemen op te lossen, zijn er vier werkingsmodi ontwikkeld:

· elektronisch codeboek ECB (Elektronisch Codeboek);

· aaneenschakeling van CBC-coderingsblokken (Cipher Block Chaining);

· CFB (Cipher Feed Back) cijfertekstfeedback;

· feedback op de uitgang OFB (Output Feed Back).

Modus "Elektronisch codeboek".

Een lang bestand is verdeeld in 64-bits segmenten (blokken) van 8 bytes. Elk van deze blokken wordt onafhankelijk gecodeerd met dezelfde coderingssleutel (Fig. 3.6).

Het belangrijkste voordeel is het gemak van implementatie. Nadeel: relatief zwakke weerstand tegen ervaren cryptanalisten. Vanwege het vaste karakter van encryptie, met een beperkte bloklengte van 64 bits, is cryptoanalyse in het woordenboek mogelijk. Een blok van deze omvang kan in een bericht worden herhaald vanwege de hoge redundantie in tekst in natuurlijke taal.

Figuur 3.6 – Schema van het DES-algoritme in elektronische codeboekmodus

Dit zorgt ervoor dat identieke blokken leesbare tekst in een bericht worden weergegeven door identieke blokken cijfertekst, waardoor de cryptanalyticus enige informatie krijgt over de inhoud van het bericht.

Modus "Cijferblokken aan elkaar koppelen".

In deze modus wordt het bronbestand M verdeeld in blokken van 64 bits: M = M 1 M 2 ...M n. Het eerste blok M1 wordt modulo 2 toegevoegd met een 64-bits initiële vector IV, die dagelijks verandert en geheim wordt gehouden (Fig. 3.7). Het ontvangen bedrag wordt vervolgens gecodeerd met behulp van een DES-sleutel die bekend is bij zowel de afzender als de ontvanger van de informatie. Het resulterende 64-bits cijfer C 1 wordt modulo 2 opgeteld bij het tweede tekstblok, het resultaat wordt gecodeerd en een tweede 64-bits cijfer C 2 wordt verkregen, enz. De procedure wordt herhaald totdat alle tekstblokken zijn verwerkt.

Dus voor alle i = 1…n (n is het aantal blokken) wordt het encryptieresultaat Ci als volgt bepaald: C i =

DES (М i  C i –1), waarbij С 0 = IV de initiële waarde van het cijfer is, gelijk aan de initiële vector (initialisatievector).

Het is duidelijk dat het laatste 64-bits cijfertekstblok een functie is van de geheime sleutel, de startvector en elke bit

Figuur 3.7 – Schema van het DES-algoritme in cipher block chaining-modus

platte tekst, ongeacht de lengte. Dit blok cijfertekst wordt een berichtauthenticatiecode (MAC) genoemd.

De CAS-code kan eenvoudig worden geverifieerd door de ontvanger, die over de geheime sleutel en de zaadvector beschikt, door de procedure van de afzender te herhalen. Een buitenstaander kan echter geen UAS genereren die door de ontvanger als echt wordt ervaren om aan een vals bericht toe te voegen, of de UAS van een echt bericht scheiden voor gebruik met een aangepast of vals bericht.

Het voordeel van deze modus is dat fouten zich tijdens de verzending niet kunnen ophopen.

Blok Mi is alleen een functie van Ci –1 en Ci. Daarom zal een transmissiefout resulteren in het verlies van slechts twee blokken brontekst.

"Cypher-feedback"-modus

In deze modus kan de blokgrootte afwijken van 64 bits (Fig. 3.8). Het te coderen (decoderen) bestand wordt gelezen in opeenvolgende blokken met een lengte van k bits (k=1...64).

Het invoerblok (64-bits schuifregister) bevat eerst een rechts uitgelijnde initialisatievector.

Stel dat we als gevolg van het opdelen in blokken n blokken met een lengte van k bits elk hebben ontvangen (aan de rest zijn nullen of spaties toegevoegd). Dan voor elk i=1…n cijfertekstblok

С ik = M ik  P ik –1 ,

waarbij P i–1 de k meest significante bits van het vorige gecodeerde blok aangeeft.

Het schuifregister wordt bijgewerkt door de hoogste k bits ervan te verwijderen en Ci naar het register te schrijven. Het herstellen van versleutelde gegevens is ook relatief eenvoudig: P i –1 en C i worden op een vergelijkbare manier berekend

М ik = С ik  Р ik –1 .

Figuur 3.8 – Schema van het DES-algoritme in cijfertekstfeedbackmodus

Uitgangsfeedback-modus

Deze modus maakt ook gebruik van een variabele blokgrootte en een schuifregister dat op dezelfde manier wordt geïnitialiseerd als in de CFB-modus, namelijk dat het invoerblok eerst een initialisatievector IV bevat, uitgelijnd naar rechts (Fig. 3.9). In dit geval is het voor elke data-encryptiesessie noodzakelijk om een nieuwe initiële status van het register te gebruiken, die in duidelijke tekst over het kanaal moet worden verzonden.

M = M 1 M 2 ... M n.

Voor alle i = 1…n

C ik = M ik  P ik ,

waarbij Р i de hoogste k bits van de DES-bewerking zijn (С i –1).

Het verschil met de cijfertekstfeedbackmodus is de methode voor het bijwerken van het schuifregister.

Dit wordt gedaan door de hoogste k bits weg te gooien en Pi aan de rechterkant toe te voegen.

Figuur 3.9 – Schema van het DES-algoritme in uitvoerfeedbackmodus

3.3. Toepassingsgebieden van het DES-algoritme

Elk van de beschouwde modi (ECB, CBC, CFB, OFB) heeft zijn eigen voor- en nadelen, die de toepassingsgebieden bepalen.

De ECB-modus is zeer geschikt voor sleutelversleuteling: de CFB-modus is meestal bedoeld voor het versleutelen van individuele tekens, en de OFB-modus wordt vaak gebruikt voor versleuteling in satellietcommunicatiesystemen.

De CBC- en CFB-modi zijn geschikt voor gegevensauthenticatie. Met deze modi kunt u het DES-algoritme gebruiken om:

· interactieve encryptie bij het uitwisselen van gegevens tussen de terminal en de hostcomputer;

· encryptie van een cryptografische sleutel in de praktijk van geautomatiseerde sleuteldistributie;

· encryptie van bestanden, mail, satellietgegevens en andere praktische taken.

Aanvankelijk was de DES-standaard bedoeld voor het versleutelen en ontsleutelen van computergegevens. De toepassing ervan is echter gegeneraliseerd naar authenticatie.

Bij automatische gegevensverwerkingssystemen kan een mens de gegevens niet beoordelen om te bepalen of er wijzigingen in zijn aangebracht. Met de enorme hoeveelheden gegevens die door moderne verwerkingssystemen stromen, zou browsen te veel tijd kosten. Bovendien is gegevensredundantie mogelijk niet voldoende om fouten te detecteren. Zelfs in gevallen waarin menselijke beoordeling mogelijk is, kunnen de gegevens zodanig worden gewijzigd dat het voor mensen erg moeilijk wordt om de veranderingen te detecteren. Zo kan “do” worden vervangen door “do not”, “$1900” door “$9100”. Zonder aanvullende informatie kan een persoon die deze bekijkt, de gewijzigde gegevens gemakkelijk voor echte gegevens verwarren. Dergelijke gevaren kunnen zelfs bestaan als gegevensversleuteling wordt gebruikt. Daarom is het wenselijk om over automatische middelen te beschikken voor het detecteren van opzettelijke en onopzettelijke gegevenswijzigingen.

Gewone foutdetectiecodes zijn ongeschikt omdat als het algoritme voor het genereren van de code bekend is, de tegenstander na het aanbrengen van wijzigingen in de gegevens de juiste code kan genereren. Met behulp van het DES-algoritme is het echter mogelijk om een cryptografische controlesom te genereren die bescherming biedt tegen zowel onbedoelde als opzettelijke maar ongeoorloofde wijzigingen in gegevens.

Dit proces beschrijft de standaard voor computergegevensauthenticatie (FIPS 113). De essentie van de standaard is dat gegevens worden gecodeerd in de cijfertekstfeedbackmodus (CFB-modus) of in de aaneenschakelingsmodus van coderingsblokken (CBC-modus), wat resulteert in een uiteindelijk coderingsblok dat een functie is van alle leesbare tekstbits. Het bericht, dat de leesbare tekst bevat, kan vervolgens worden verzonden met behulp van het berekende definitieve cijferblok, dat als cryptografische controlesom dient.

Dezelfde gegevens kunnen worden beschermd met behulp van zowel codering als authenticatie. Gegevens worden beschermd tegen toegang door middel van encryptie en wijzigingen worden gedetecteerd via authenticatie. Het authenticatiealgoritme kan worden toegepast op zowel leesbare als gecodeerde tekst. Bij financiële transacties, waarbij in de meeste gevallen zowel encryptie als authenticatie zijn geïmplementeerd, geldt dit laatste ook voor open

mu tekst.

Encryptie en authenticatie worden gebruikt om gegevens die op een computer zijn opgeslagen te beschermen. Op veel computers worden wachtwoorden onomkeerbaar gecodeerd en opgeslagen in het geheugen van de machine. Wanneer een gebruiker toegang krijgt tot de computer en een wachtwoord invoert, wordt dit wachtwoord gecodeerd en vergeleken met de opgeslagen waarde. Als beide gecodeerde waarden hetzelfde zijn, krijgt de gebruiker toegang tot de machine, anders wordt deze geweigerd.

Vaak wordt een gecodeerd wachtwoord gegenereerd met behulp van het DES-algoritme, waarbij de sleutel gelijk is aan het wachtwoord en de platte tekst gelijk aan de gebruikersidentificatiecode.

Met behulp van het DES-algoritme kunt u ook computerbestanden coderen voor opslag.

Een van belangrijkste toepassingen algoritme DES is bescherming van elektronische betalingssysteem (EPS)-berichten tijdens transacties met een brede klantenkring en tussen banken.

Het DES-algoritme wordt geïmplementeerd in geldautomaten, verkoopterminals, werkstations en mainframecomputers. Het scala aan gegevens dat het beschermt is zeer breed: van betalingen van $ 50 tot overdrachten van vele miljoenen dollars. Dankzij de flexibiliteit van het kern-DES-algoritme kan het worden gebruikt in een breed scala aan toepassingen voor elektronische betalingssystemen.

Handleiding

Hallo %gebruikersnaam%!
Veel mensen weten dat het DES-algoritme lange tijd werd beschouwd als de standaardstandaard op het gebied van symmetrische encryptie. De eerste succesvolle aanval op dit niet te doden algoritme werd gepubliceerd in 1993, 16 jaar nadat het als standaard werd aangenomen. De methode, die de auteur lineaire cryptanalyse noemde, stelt je in de aanwezigheid van 2 47 gewone / gecodeerde tekstparen in staat de geheime sleutel van het DES-codering in 2 43 bewerkingen te openen.
Onder de snede zal ik proberen de belangrijkste punten van deze aanval kort te schetsen.

Lineaire cryptanalyse

Lineaire cryptanalyse is een speciaal soort aanval op symmetrische cijfers, gericht op het achterhalen van een onbekende coderingssleutel uit bekende gewone berichten en de bijbehorende cijferteksten.

Over het algemeen komt een aanval op basis van lineaire cryptanalyse neer op de volgende voorwaarden. De aanvaller beschikt over een groot aantal paren platte tekst/cijfertekst die zijn verkregen met dezelfde coderingssleutel K. Het doel van de aanvaller is om de sleutel K geheel of gedeeltelijk te herstellen.

Algoritme 1
Laat T dan het aantal teksten zijn waarvoor de linkerkant van vergelijking (1) gelijk is aan 0
Als T>N/2, waarbij N het aantal bekende leesbare teksten is.
Neem aan dat K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (als P>1/2) of 1 (als P<1/2).
Anders
Neem aan dat K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (als P>1/2) of 0 (als P<1/2).
Het is duidelijk dat het succes van het algoritme rechtstreeks afhangt van de waarde van |P-1/2| en op het aantal beschikbare open/gesloten tekstparen N. Hoe meer de waarschijnlijkheid P van gelijkheid (1) verschilt van 1/2, hoe minder aantal open teksten N nodig is voor de aanval.

Er zijn twee problemen die moeten worden opgelost om de aanval te laten slagen:

Hoe een effectieve vergelijking van de vorm (1) te vinden.
Hoe deze vergelijking te gebruiken om meer dan één stukje informatie over de sleutel te krijgen.

Laten we de oplossing voor deze problemen bekijken met behulp van de DES-codering als voorbeeld.

Beschrijving van DES

Initiële bitpermutatie. In dit stadium worden de bits van het invoerblok in een bepaalde volgorde geschud.
Hierna worden de gemengde bits in twee helften gesplitst, die naar de ingang van de Feistel-functie worden gevoerd. Voor standaard DES omvat het Feistel-netwerk 16 ronden, maar er bestaan ook andere varianten van het algoritme.
De twee blokken die in de laatste transformatieronde zijn verkregen, worden gecombineerd en er wordt een nieuwe permutatie uitgevoerd op het resulterende blok.

In elke ronde van het Feistel-netwerk worden de minst significante 32 bits van het bericht via de functie f doorgegeven:

Laten we eens kijken naar de bewerkingen die in dit stadium zijn uitgevoerd:

Het invoerblok wordt doorgegeven via de uitbreidingsfunctie E, die een blok van 32 bits omzet in een blok van 48 bits.
Het resulterende blok wordt toegevoegd aan de ronde sleutel Ki.
Het resultaat van de vorige stap wordt verdeeld in 8 blokken van elk 6 bits.
Elk van de ontvangen blokken Bi wordt door de substitutiefunctie S-Boxi gevoerd, die de reeks van 6 bits vervangt door een blok van 4 bits.
Het resulterende 32-bits blok wordt door de permutatie P geleid en geretourneerd als resultaat van functie f.

S-blokanalyse

Laten we eens kijken hoe we in het algemene geval een statistische analoog van de S-box kunnen vinden.

Statistische analogen construeren voor meerdere DES-rondes