Kan DES brytas av differentiell kryptoanalys?
Differentiell kryptoanalys är en form av kryptoanalys som främst är tillämplig på blockchiffer, vilket innebär att man analyserar effekten av särskilda skillnader i ingångspar på skillnaderna vid utgången. Denna metod introducerades av Eli Biham och Adi Shamir i slutet av 1980-talet och har sedan dess blivit ett grundläggande verktyg i kryptoanalytikerns verktygslåda. Data Encryption Standard (DES), en symmetrisk nyckelalgoritm för kryptering av digital data, har varit ett av de primära ämnena för differentiell kryptoanalys.
DES-algoritmen, designad av IBM i början av 1970-talet och antagen som en federal standard 1977 av National Institute of Standards and Technology (NIST), fungerar på 64-bitars datablock med hjälp av en 56-bitars nyckel. DES använder 16 omgångar av ett Feistel-nätverk, där varje omgång består av en serie ersättningar och permutationer som bestäms av nyckelschemat.
För att förstå om DES kan brytas av differentiell kryptoanalys är det viktigt att överväga detaljerna i både DES-strukturen och principerna för differentiell kryptoanalys.
DES-struktur och nyckelschema
DES bygger på en kombination av substitutions- och permutationsoperationer. Varje omgång av DES innefattar följande steg:
1. Expansion (E-box): 32-bitars halvblocket expanderas till 48 bitar med hjälp av en expansionspermutation.
2. Nyckelblandning: Det utökade halvblocket XORed med en rund nyckel härledd från huvudnyckeln med hjälp av ett nyckelschema.
3. Byte (S-box): 48-bitarsresultatet är uppdelat i åtta 6-bitars segment, som vart och ett leds genom en motsvarande S-box för att producera en 4-bitars utdata. De åtta 4-bitars utgångarna är sammanlänkade för att bilda ett 32-bitars block.
4. Permutation (P-box): 32-bitarsblocket permuteras med hjälp av en fast permutationstabell.
5. XOR och Swap: Det permuterade blocket XORed med den andra halvan av datablocket, och halvorna byts ut.
Nyckelschemat genererar en serie av 16 runda nycklar, var och en med en längd på 48 bitar, från den ursprungliga 56-bitarsnyckeln. Denna process involverar permuterade valoperationer och vänstercirkulära skift.
Principer för differentiell kryptoanalys
Differentiell kryptoanalys innebär att studera hur skillnader i klartextpar fortplantar sig genom chifferet för att producera skillnader i chiffertexten. Grundidén är att välja par av klartexter som har en specifik skillnad, kryptera dem och analysera de resulterande chiffertextskillnaderna. Genom att observera hur dessa skillnader utvecklas genom chiffrets rundor kan en angripare sluta sig till information om nyckeln.
Nyckelbegrepp i differentiell kryptoanalys inkluderar:
- Differentiell: XOR-skillnaden mellan två värden. Till exempel om 
och 
är två klartexter, deras skillnad är 
.
- Karaktär: En sekvens av skillnader som beskriver hur en ingångsdifferential fortplantar sig genom chifferets rundor.
- Sannolikhet: Sannolikheten att en given ingångsskillnad kommer att producera en specifik utgångsskillnad efter ett visst antal omgångar.
Ansökan till DES
DES designades specifikt för att motstå differentiell kryptoanalys, som inte var allmänt känd vid tidpunkten för dess design men som IBM och NSA förstod. S-boxarna i DES valdes noggrant ut för att minimera sannolikheten för differentialegenskaper, vilket försvårade differentiell kryptoanalys.
Biham och Shamir visade dock att DES inte är immun mot differentiell kryptoanalys. De visade att även om den fullständiga 16-runda DES är resistent mot praktiska differentialattacker, är versioner av chiffer med reducerade rundor sårbara. Specifikt utvecklade de attacker på DES med färre än 16 omgångar.
Till exempel kan en attack på en 8-runds DES utföras med en komplexitet på ca 
utvalda klartexter, vilket är betydligt effektivare än en brute-force attack på hela nyckelutrymmet. För hela 16-runda DES är komplexiteten för differentiell kryptoanalys mycket högre, vilket gör det opraktiskt med de beräkningsresurser som finns tillgängliga vid tidpunkten för deras forskning.
Exempel på differentiell krypteringsanalys på DES
För att illustrera hur differentiell kryptoanalys fungerar, överväg ett förenklat exempel med en reducerad rund DES:
1. Välj en differential: Välj en specifik ingångsdifferential 
. För enkelhetens skull, anta påverkar bara några få bitar.
2. Generera klartextpar: Generera ett stort antal klartextpar 
Så att 
.
3. Kryptera klartextpar: Kryptera varje par för att få chiffertexter 
.
4. Analysera utdataskillnader: Beräkna utgångsdifferensen 
för varje par.
5. Identifiera egenskaper: Identifiera mönster i utdataskillnaderna som antyder specifika egenskaper hos chifferets interna struktur.
6. Härleda nyckelinformation: Använd de identifierade egenskaperna för att härleda information om de runda tangenterna, och i slutändan huvudnyckeln.
Praktiska överväganden
Även om differentiell kryptoanalys är ett kraftfullt verktyg, kräver dess praktiska tillämpning på DES betydande beräkningsresurser och ett stort antal utvalda klartexter. Moderna kryptografiska metoder har utvecklats för att använda mer komplexa och säkra algoritmer, såsom Advanced Encryption Standard (AES), som är designade för att motstå inte bara differentiell kryptoanalys utan också ett brett utbud av andra kryptoanalytiska attacker.
Differentiell kryptoanalys är en väletablerad teknik inom kryptografi som kan användas för att analysera och i vissa fall bryta blockchiffer som DES. Medan hela 16-runda DES är resistent mot praktiska differentialattacker, är versioner av DES med reducerade rundor sårbara. Designen av DES, särskilt dess S-boxar, speglar en medvetenhet om differentiella kryptoanalysprinciper, vilket visar vikten av noggrann kryptografisk design för att säkerställa säkerhet.
Andra senaste frågor och svar ang Data Encryption Standard (DES) - Nyckelschema och dekryptering:
- Vilket är effektivt för att bryta DES mellan linjär och differentiell kryptoanalys?
- Hur kan linjär cyrptanalys bryta ett DES-kryptosystem?
- Kan två olika ingångar x1, x2 producera samma utdata y i Data Encryption Standard (DES)?
- Är differentiell kryptoanalys mer effektiv än linjär kryptoanalys för att bryta DES-kryptosystem?
- Hur fungerade DES som en grund för moderna krypteringsalgoritmer?
- Varför anses nyckellängden i DES vara relativt kort med dagens standarder?
- Vad är Feistel-nätverkets struktur och hur relaterar den till DES?
- Hur skiljer sig dekrypteringsprocessen i DES från krypteringsprocessen?
- Vad är syftet med nyckelschemat i DES-algoritmen?
- Hur bidrar förståelsen av nyckelschemat och dekrypteringsprocessen för DES till studiet av klassisk kryptografi och utvecklingen av krypteringsalgoritmer?
Se fler frågor och svar i Data Encryption Standard (DES) - Nyckelschema och dekryptering