Ainutlaatuinen etäisyys

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30. maaliskuuta 2018 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Ainutlaatuisuusetäisyys (salakirjoituksessa) on salatekstin merkkien määrä, jolla avaimen (ja siten myös tavallisen tekstin ) ehdollisen informaation entropia on nolla ja itse avain on yksilöllisesti määritetty.

Ainutlaatuisuusetäisyyden saavuttaminen ei vielä tarkoita, että avain (tai pelkkä teksti) löytyisi käytännössä, koska määritelmä ei ota huomioon avaimen käytännön laskettavuutta, vaan vain olettaa, että se voidaan löytää esimerkiksi tyhjentävällä etsi .

Määritelmä

Määritetään avaimen luotettavuusfunktio salausanalyytikon sieppaamien avain- ja salatekstisymbolien ehdollisen tiedon entropian kautta : $Z$ ${\displaystyle y_{1},y_{2},\dots ,y_{n))$

f_{0}=H\left(Z\oikea)

f_{1}=H\left(Z|y_{1}\right)

f_{2}=H\left(Z|y_{1}y_{2}\right)

\pisteet

f_{n}=H\left(Z|y_{1}y_{2}\dots y_{n}\right)

{\displaystyle f_{n}\leq f_{n-1}\leq \dots \leq f_{1}\leq f_{0))

Tällainen määrä siepattuja merkkejä , joissa ja kutsutaan ainutlaatuisuusetäisyydeksi. $u$ $f_{u}=0$

Likimääräinen kaava

Yksilöllisyysetäisyyskaavan johtaminen on mahdollista jollekin "hyvälle" kryptosysteemille, jossa salatekstin informaatioentropialla on tiettyjä "lineaarisuuden" ominaisuuksia:

H\left(Y\right)=N\log L

missä on viestin salatekstin merkkien kokonaismäärä, on salatekstin aakkoset yksinkertaisuuden vuoksi yhtä suureksi kuin selväteksti ja salausavain

N

L

H\left(y_{1}\dots y_{n}\right)\approx n\log L

H\left(y_{1}\dots y_{n}|Z\right)\approx {n \over N}H\left(X\right)

viimeinen lauseke on lausekkeen "linearisointi".

H\vasen(Y|Z\oikea)=H\vasen(X\oikea)

Sitten yhteisen informaatioentropian lausekkeista:

H\left(y_{1}\dots y_{n};Z\right)=H\left(y_{1}\dots y_{n}\right)+H\left(Z|y_{1 }\pisteet y_{n}\oikea)\noin n\log L+f_{n}

H\left(y_{1}\dots y_{n};Z\right)=H\left(Z\right)+H\left(y_{1}\dots y_{n}|Z\right )\noin H\vasen(Z\oikea)+{n \yli N}H\vasen(X\oikea)

n\log L+f_{n}\approx H\left(Z\right)+{n \over N}H\left(X\right)

n\noin {{H\left(Z\right)-f_{n}} \over {\log LH\left(X\right)/N}}={{H\left(Z\right) -f_{n}} \ylä {\log L\cdot \left({1-{{H\left(X\right)} \over {N\log L}}}\right)))

Sitten ainutlaatuisuusetäisyyden määritelmän mukaan : $u:f_{u}=0$

u\approx {H\left(Z\right) \over {\log LH\left(X\right)/N))={H\left(Z\right) \over {\log L\cdot \left({1-{{H\left(X\right)} \over {N\log L}}}\right)}}

Lauseketta kutsutaan lähderedundanssiksi . Jos lähteen redundanssi on nolla, eli selkeästä tekstistä on mahdotonta määrittää, onko se oikein vai ei (sissä ei ole tarkistussummia tai allekirjoituksia), niin yksilöllisyysetäisyydestä tulee yhtä suuri kuin ääretön ja kryptosysteemistä tulee ehdottoman turvallinen. $\rho =1-{{H\left(X\right)} \over {N\log L))$

Esimerkki

Venäjän kielellä redundanssi on 3,5 bittiä per merkki. Jos käytetään yksiaakkosista salausta , siinä olevien mahdollisten avainten määrä on yhtä suuri kuin , ja avaimen entropia (yhdentodennäköisellä valinnalla) on bitti . ${\displaystyle 33!\noin 8,68\cdot 10^{36))$ $H\left(Z\right)=\log _{2}33!\noin 122,7$

Sitten yksinkertaisella korvaussalauksella salatun venäjän tekstin ainutlaatuisuusetäisyys on:

u={{H\left(Z\right)} \over {\rho }}\noin 35,1

Eli jos kryptanalyytikko sieppaa yli 35 merkkiä salatekstistä, tämä todennäköisesti mahdollistaa (esimerkiksi tyhjentävällä haulla) palauttaa alkuperäisen selkeän tekstin. Jos kaapataan vähemmän merkkejä, tekstin palautus on epäselvää (selkotekstistä voi olla useita eri versioita).

Kirjallisuus

Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Ainutlaatuisuusetäisyys // Tietoturva : oppikirja - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
G. V. Basalova Uniqueness Distance // Kryptografian perusteet (venäjä)

Linkit

Bruce Schneier : Kuinka tunnistaa selkeä teksti (Crypto-Gram-uutiskirje, 15. joulukuuta 1998 )
Unicity Distance laskettu tavallisille salakirjoille