Klartext attack

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 3 januari 2020; verifiering kräver 1 redigering .

Känd klartextattack är en typ av kryptoanalys där standardpassager finns i chiffertexten , vars innebörd är känd för analytikern i förväg. Under andra världskriget kallade engelska kryptoanalytiker sådana passager "tips" ( Engelsk krubba - tips, fuskblad) [Anm. 1] .

Chiffer från olika länder innehöll ofta specifika uttryck: Heil Hitler! , Banzai! , Proletärer i alla länder, förena er! etc.

Ett annat exempel på att använda metoden är en kryptografisk attack på den enkla gammaalgoritmen . Om minst en klartext är känd och längden på chiffertexten som motsvarar den är större än eller lika med längden på gamma (nyckel), så hittas den senare unikt.

Beskrivning

Enligt Kerckhoffs princip har kryptoanalytikern all information om kryptosystemet förutom en viss uppsättning parametrar som kallas nyckeln . Kryptanalytikerns uppgift är att hitta en gemensam krypteringsnyckel eller dekrypteringsalgoritm för att dekryptera andra chiffertexter med samma nyckel.

Given:

P 1 , P 2 , …, P i — klartexter
C 1 =E k (P 1 ), C 2 =E k (P 2 ), …, C i =E k (P i ) — deras motsvarande chiffertexter

Behöver hitta:

k är krypteringsnyckeln, eller
D(C) - dekrypteringsfunktion (inte som en funktion av nyckeln, utan endast av chiffertexten)

Skillnader från andra metoder för kryptoanalys

Enbart chiffertext attack

En attack med endast chiffertext är en primär kryptoanalysteknik där endast chiffertexter är kända för kryptoanalytikern. Klartextattacken är en förbättring av den, eftersom vi också känner till källtexterna. Till exempel öppnar den frekvenskrypteringsmetod som ofta används för chiffertextbaserad kryptoanalys i fallet med klartextbaserad kryptoanalys upp fler möjligheter, eftersom frekvenssvaret för det chiffrerade meddelandet inte måste jämföras med språkets frekvensrespons, utan med frekvenssvar för det ursprungliga meddelandet (i särskilda fall frekvenssvaret för den öppna texten), text och frekvenssvar för språket kan variera mycket).

Vald klartextattack

Vald klartextattack - Denna typ av attack är en förbättring av den klartextbaserade metoden. Här har kryptoanalytikern också ett antal klartext/chiffertext-par som är kända i förväg. Men han kan också få chiffertexter som motsvarar texter han har valt i förväg. Sättet att få tag på sådana chiffertexter är till exempel att skriva ett brev med vanlig text, samtidigt som man utger sig för att vara en person från vilken ett krypterat meddelande förväntas, och under vissa förutsättningar kan man få ett svar med ett citat från denna text, men redan i krypterad form. Skillnaden mellan denna metod och klartextattacken är att i denna metod kan kryptoanalytikern välja vilken text han vill kryptera. Och i klartextmetoden är alla klartext/chiffertextpar kända i förväg.

Adaptiv klartextattack

Den adaptivt valda klartextattacken är en förlängning av den valda klartextattacken. Skillnaden ligger i det faktum att, efter att ha fått en chiffertext som motsvarar en given klartext, bestämmer kryptoanalytikern själv vilken text han vill kryptera vidare, vilket så att säga ger feedback till hackningsmetoden. Denna metod kräver direkt åtkomst till krypteringsenheten.

Ett exempel på tillämpning i historien

I fallet Enigma var det tyska överkommandot mycket noggrant med att säkra systemet, eftersom de var medvetna om det möjliga problemet med sprickbildning baserat på klartexter. Teamet som arbetade med hacket kunde gissa innehållet i texterna utifrån när meddelandena skickades. Till exempel sändes väderprognosen varje dag vid samma tidpunkt. Enligt reglerna för militära meddelanden innehöll varje meddelande ordet "Väder" (Vättare) på samma plats, och kunskap om vädret i ett visst område var till stor hjälp för att gissa om innehållet i resten av meddelandet. Också mycket hjälpsamma var meddelanden från officeren som skickade "Inget att rapportera" varje gång, vilket gav material för kryptoanalys. Andra befälhavare skickade också standardsvar, eller så innehöll deras svar standarddelar.

Efter att en tillfångatagen tyska under förhör erkänt att operatörerna beordrades att kryptera siffror genom att skriva varje siffra med bokstäver, granskade Alan Turing meddelandena och fastställde att ordet "eins" förekommer i 90 % av meddelandena. Baserat på detta skapades en katalog av Eins, som innehöll alla möjliga positioner för rotorerna, initiala positioner och uppsättningar av Enigma-nycklar.

Nu

Moderna chiffer är dåligt mottagliga för denna metod för kryptoanalys. Till exempel kräver att knäcka DES ungefär klartext/chiffertext-par. $2^{{47}}$

Samtidigt är olika krypterade arkiv som ZIP sårbara för denna form av attack. I det här fallet behöver en angripare som vill öppna en grupp krypterade ZIP-filer bara känna till en okrypterad fil från arkivet eller en del av det, som i det här fallet kommer att fungera som klartext. Vidare, med hjälp av program som är fritt tillgängliga, hittas snabbt nyckeln som behövs för att dekryptera hela arkivet. Krackert kan försöka hitta den okrypterade filen på Internet eller i andra arkiv, eller kan försöka återställa klartexten genom att känna till namnet från det krypterade arkivet.

Grundläggande metoder

Linjär metod för kryptoanalys

I den öppna pressen föreslogs den linjära metoden för kryptoanalys först av den japanske matematikern Matsui. Metoden förutsätter att kryptoanalytikern känner till klartexten och motsvarande chiffertexter. Oftast, vid kryptering, används modulo 2-tillägg av text med en nyckel, blandnings- och spridningsoperationer. Kryptanalytikerns uppgift är att hitta en sådan linjär approximation

$x_{i_{1}}+\ldots +x_{i_{r}}+y_{j_{1}}+y_{j_{s}}=z_{k_{1}}+\ldots +z_ {k_{t}}$ , (ett)

vilket blir bäst. Låt vara sannolikheten att (1) är uppfylld. Det är klart att vi behöver , och även att värdet är maximalt. Om detta värde är tillräckligt stort och kryptoanalytikern känner till tillräckligt många par av klartexten och motsvarande chiffertext, så är modulo 2 summan av nyckelns bitar i motsvarande position på den högra sidan av likheten (1) lika med den mest sannolika värdet av modulo 2 summan av motsvarande bitar i den öppna texten och chiffertexten på vänster sida. I det fall där , summan på höger sida av (1) är noll när summan av bitarna på vänster sida är noll i mer än hälften av paren av chiffertexter. Summan av bitarna på höger sida är lika med en om summan av bitarna på vänster sida är lika med en i mer än hälften av fallen med texter. Om , då vice versa: summan av bitarna på höger sida är lika med en, om summan av bitarna på vänster sida är lika med noll för mer än hälften av texterna. Och summan av bitarna på höger sida är noll om summan av bitarna på vänster sida är en mer än halva tiden. För att hitta varje bit av nyckeln är det nu nödvändigt att lösa ett system av linjära ekvationer för motsvarande kända kombinationer av dessa bitar. Detta är inte svårt, eftersom komplexiteten i detta system uttrycks av ett polynom på högst en tredje grad av nyckellängden. Antalet obligatoriska klartext/chiffertextpar för att bryta chifferen uppskattas med formeln . För att bryta ett DES-chiffer på detta sätt visar det sig att det behövs cirka 247 öppna/krypterade blockpar. $sid$ $p\approx 0,5$ $|p-0.5|$ $p>0,5$ $p<0,5$ $N=|p-1/2|2^{{-2}}$

Differentiell metod för kryptoanalys.

Den differentiella metoden för kryptoanalys (DCA) föreslogs 1990 av E. Biham och A. Shamir. Differentiell kryptoanalys är ett försök att bryta den hemliga nyckeln till blockchiffer, som är baserade på den upprepade tillämpningen av kryptografiskt svaga krypteringsoperationer r gånger. Cryptanalysis antar att varje krypteringscykel använder sin egen krypteringsundernyckel. DFA kan använda både vald och känd klartext. Huvudvillkoret för framgången med försök att öppna ett r-cykliskt chiffer är förekomsten av differentialer i (r-1) -:e cykeln, som har en hög sannolikhet. Differentialen för den i:te cykeln definieras som ett par av tal så att ett par olika klartexter x och x* med en skillnad kan, efter den i:te cykeln, ge ett par av y och y* med en skillnad . Sannolikheten för i-cykeldifferentialen är den villkorade sannolikheten att skillnaden mellan y och y* efter den i:te cykeln är lika , förutsatt att det initialt fanns x och x* med en skillnad på . Klartext x och undernycklar till 1 , till 2 , …, till i anses vara oberoende och slumpmässiga. DFA-proceduren för ett r-cykliskt chiffer med vald klartext kan vara som följer: $(\alpha ,\beta )_{i},$ $\alfa$ $\beta$ $P(\Delta y(i)=\beta |\Delta x=\alpha )$ $\beta$ $\alfa$

Detta skede är stadiet för förberäkningar. På den letar vi efter en uppsättning (r-1)-cykeldifferentialer . Vi ordnar den givna mängden efter värdet av deras sannolikheter. $(\alpha _{1},\beta _{1})_{r-1},(\alpha _{2},\beta _{2})_{r-1},... .(\alpha _{s},\beta _{s})_{r-1}$
Detta steg kräver att vi väljer x och x* så att deras skillnad är lika med , för dem har vi ett par chiffertexter y(r), y*(r). Vi tror att vid utgången av den näst sista cykeln är skillnaden lika med den mest sannolika . För en trippel hittar vi alla möjliga värden på undernyckeln k (r) . Vi ökar räknaren för förekomsten av varje sådant värde som är kopplat till (r) . $\alpha_{1}$ $\Delta y(r-1)=\beta _{1}$ $(\Delta y(r-1),y(r),y^{*}(r))$
I detta skede upprepar vi föregående stycke tills en eller flera undernycklar börjar visas oftare än andra. Vi tar den givna nyckeln (eller uppsättningen nycklar) som en lösning på (r) .
I detta skede upprepar vi steg 1-3 för den (r-1):e cykeln, medan värdena för y(r-1) beräknas genom att dekryptera y(r) med nyckeln till (r) som finns i föregående steg. Och vi upprepar dessa åtgärder tills vi hittar nycklarna till alla cykler.

Denna metod föreslogs ursprungligen för att lösa ett enda chiffer, men sedan visade den framgång i kryptoanalys av många Markov-chiffer. Ett chiffer kallas Markovian om dess ekvation på en cykel uppfyller villkoret att sannolikheten för differentialen inte beror på valet av klartext. Om cyklernas nycklar är oberoende, bildar sekvensen av skillnader för varje cykel en Markov-kedja där varje efterföljande element endast beror på det föregående. Exempel på Markov-chiffer är DES och FEAL. Låt oss visa att ett Markov r-cykliskt chiffer med oberoende undernycklar är sårbart för DFA om och bara om, under en cykel, nyckeln lätt kan beräknas från den kända trippeln . Det finns också en (r-1) differential , och dess sannolikhet uppfyller uttrycket där n är antalet bitar i chiffertextblocket. Komplexiteten i att hitta nyckeln till ett r-cykliskt chiffer Q(r) definieras som antalet använda krypteringar, följt av att hitta nyckeln: där i synnerhet, om , då kommer en sådan attack inte att lyckas. Eftersom operationen att hitta en undernyckel är mer mödosam än operationen av kryptering, är komplexitetsenheten komplexiteten i att hitta möjliga undernycklar för en cykel över kända trippel. Ett utmärkande drag för differentiell kryptoanalys är att den nästan inte använder de algebraiska egenskaperna av chifferet (såsom linjäritet, andra.) Det är endast baserat på olikformigheten i sannolikhetsfördelningen av differentialerna. $(y,y^{*},\Delta x)$ ${\displaystyle (\alpha ,\beta )_{r-1))$ $P(\Delta y(r-1)=\beta |\Delta x=\alpha )\gg 2^{-n},$ $Q(r)\geqslant 2/(P_{\mathrm {max} }-1/(2^{n}-1)),$ $P_{\mathrm {max} }=\operatörsnamn {max} (\alpha )\operatörsnamn {max} (\beta )(P(\Delta y(r-1)=\beta |\Delta x=\ alfa ))$ $P_{\mathrm {max} }\approx 1/(2^{n}-1)$ $(\Delta y(r-1),y(r),y^{*}(r)).$

Anteckningar

↑ Ordet crib (både ett substantiv och ett verb) har dussintals betydelser på engelska, inklusive slang . I synnerhet i skolslang betyder spjälsäng en ledtråd, ett fuskblad, etc. olagliga metoder för att klara prov

Litteratur

Bruce Schneier. Tillämpad kryptografi . Arkiverad 28 februari 2014 på Wayback Machine }
David Kahn. Kodbrytare.

Welchman, Gordon (1982), The Hut Six Story: Breaking the Enigma Codes , Harmondsworth: Allen Lane, ISBN 0713912944