Unicity avstånd

I kryptografi är unicity distans längden på en original chiffertext som behövs för att bryta chiffer genom att reducera antalet möjliga falska nycklar till noll i en brute force attack . Det vill säga, efter att ha provat alla möjliga nyckel bör det bara finnas en dechiffrering som är vettig, dvs förväntad mängd chiffertext som behövs för att bestämma nyckeln fullständigt, förutsatt att det underliggande meddelandet har redundans.

Claude Shannon definierade enhetsavståndet i sin artikel från 1949 " Communication Theory of Secrecy Systems " .

Överväg en attack på chiffertextsträngen "WNAIW" krypterad med ett Vigenère-chiffer med en fembokstavsnyckel. Tänkbart skulle denna sträng kunna dechiffreras till vilken annan sträng som helst – RIVER och WATER är båda möjligheter för vissa tangenter. Detta är en allmän regel för kryptoanalys : utan ytterligare information är det omöjligt att avkoda detta meddelande.

Naturligtvis, även i det här fallet, kommer endast ett visst antal av fembokstavsnycklar att resultera i engelska ord. Genom att prova alla möjliga nycklar får vi inte bara RIVER och WATER, utan även SXOOS och KHDOP. Antalet "fungerande" nycklar kommer sannolikt att vara mycket mindre än uppsättningen av alla möjliga nycklar. Problemet är att veta vilken av dessa "fungerande" nycklar som är den rätta; resten är falska.

Relation till nyckelstorlek och eventuell klartext

I allmänhet, givet speciella antaganden om storleken på nyckeln och antalet möjliga meddelanden, finns det en genomsnittlig chiffertextlängd där det bara finns en nyckel (i genomsnitt) som kommer att generera ett läsbart meddelande. I exemplet ovan ser vi bara versaler , så om vi antar att klartexten har denna form, så finns det 26 möjliga bokstäver för varje position i strängen. Likaså om vi antar fem tecken stora nycklar, finns det K=26 ⁵ möjliga nycklar, av vilka majoriteten inte kommer att "fungera".

Ett enormt antal möjliga meddelanden, N, kan genereras med även denna begränsade uppsättning tecken: N = 26 ^L , där L är meddelandets längd. Men bara en mindre uppsättning av dem är läsbar klartext på grund av språkets regler, kanske M av dem, där M sannolikt är mycket mindre än N. Dessutom har M en en-till-en-relation med talet av nycklar som fungerar, så givet K möjliga nycklar, kommer endast K × (M/N) av dem att "fungera". En av dessa är den korrekta nyckeln, resten är falska.

Eftersom M/N blir godtyckligt litet när längden L på meddelandet ökar, finns det så småningom något L som är tillräckligt stort för att göra antalet falska nycklar lika med noll. Grovt sett är detta L som gör KM/N=1. Detta L är enhetsavståndet.

Relation med nyckelentropi och klartextredundans

Enhetsavståndet kan på motsvarande sätt definieras som den minsta mängd chiffertext som krävs för att tillåta en beräkningsmässigt obegränsad motståndare att återställa den unika krypteringsnyckeln.

Det förväntade enhetsavståndet kan då visas vara:

U=H(k)/D

där U är enhetsavståndet, H ( k ) är entropin för nyckelutrymmet (t.ex. 128 för 2 ¹²⁸ lika sannolika nycklar, något mindre om nyckeln är en memorerad lösenordsfras). D definieras som redundansen i klartext i bitar per tecken.

Nu kan ett alfabet på 32 tecken bära 5 bitar information per tecken (som 32 = 2 ⁵ ). I allmänhet är antalet informationsbitar per tecken $log 2 (N)$ , där N är antalet tecken i alfabetet och $log 2$ är den binära logaritmen . Så för engelska kan varje tecken förmedla $log 2 (26) = 4,7$ bitar av information.

Den genomsnittliga mängden faktisk information per tecken i meningsfull engelsk text är dock bara cirka 1,5 bitar per tecken. Så den klartextredundansen är D = 4,7 − 1,5 = 3,2.

I princip ju större enhetsavstånd desto bättre. För en engångsplatta av obegränsad storlek, givet den obegränsade entropin i nyckelutrymmet, har vi ${\displaystyle U=\infty } ,$ vilket är förenligt med att engångsplattan är okrossbar.

Unicity avstånd för substitutionschiffer

För ett enkelt ersättnings-chiffer är antalet möjliga nycklar $26! = 4,0329 \times 10 26 = 2 88,4$ , antalet sätt som alfabetet kan permuteras på. Om man antar att alla nycklar är lika sannolika, $H (k) = log 2 (26!) = 88,4$ bitar. För engelsk text $D = 3,2$ , alltså $U = 88,4/3,2 = 28$ .

Så givet 28 tecken chiffertext borde det vara teoretiskt möjligt att utarbeta en engelsk klartext och därav nyckeln.

Praktisk applikation

Enhetsavstånd är ett användbart teoretiskt mått, men det säger inte mycket om säkerheten för ett blockchiffer när det attackeras av en motståndare med verkliga (begränsade) resurser. Betrakta ett blockchiffer med ett enhetsavstånd på tre chiffertextblock. Även om det helt klart finns tillräckligt med information för att en beräkningsmässigt obegränsad motståndare ska hitta rätt nyckel (enkel uttömmande sökning), kan detta vara beräkningsmässigt omöjligt i praktiken.

Enhetsavståndet kan ökas genom att reducera redundansen i klartext. Ett sätt att göra detta är att implementera datakomprimeringstekniker före kryptering, till exempel genom att ta bort överflödiga vokaler med bibehållen läsbarhet. Detta är hur som helst en bra idé, eftersom det minskar mängden data som ska krypteras.

Chiffertexter som är större än enhetsavståndet kan antas ha endast en meningsfull dekryptering. Chiffertexter som är kortare än enhetsavståndet kan ha flera rimliga dekrypteringar. Enhetsavstånd är inte ett mått på hur mycket chiffertext som krävs för kryptoanalys, ^{[ varför? ]} men hur mycket chiffertext krävs för att det bara ska finnas en rimlig lösning för kryptoanalys.

externa länkar

Bruce Schneier : How to Recognize Plaintext (Crypto-Gram Newsletter 15 december 1998)
Unicity Distance beräknat för vanliga chiffer