Distanța de unicitate

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 martie 2018; verificarea necesită 1 editare .

Distanța de unicitate (în criptologie) este numărul de caractere de text cifrat la care entropia informațională condiționată a cheii (și, în consecință, a textului simplu ) este egală cu zero, iar cheia în sine este determinată în mod unic.

Atingerea distanței de unicitate nu înseamnă încă că cheia (sau textul simplu) poate fi găsită în practică, deoarece definiția nu ține cont de calculabilitatea practică a cheii, ci doar postulează că aceasta poate fi găsită, de exemplu, folosind exhaustiv . cauta .

Definiție

Să definim funcția de fiabilitate a cheii prin entropia informațională condiționată a simbolurilor cheii și textului cifrat care sunt interceptate de criptoanalist : $Z$ $y_{1},y_{2},\dots,y_{n)$

f_{0}=H\stânga(Z\dreapta)

f_{1}=H\stânga(Z|y_{1}\dreapta)

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

\dots

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

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

Un astfel de număr de caractere interceptate , la care și se numește distanța de unicitate. $u$ $f_{u}=0$

Formula aproximativă

Derivarea formulei distanței unicității este posibilă pentru un criptosistem „bun”, în care entropia informațională a textului cifrat are anumite proprietăți de „liniaritate”:

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

unde este numărul total de caractere din textul cifrat al mesajului, este alfabetul textului cifrat, pentru simplitate, luat egal atât cu textul simplu, cât și cu cheia de criptare

N

L

H\stanga(y_{1}\dots y_{n}\dreapta)\aprox n\log L

H\left(y_{1}\dots y_{n}|Z\dreapta)\aproximativ {n\peste N}H\left(X\right)

ultima expresie este o „liniarizare” a expresiei

H\left(Y|Z\right)=H\stanga(X\dreapta)

Apoi, din expresiile pentru entropia informațională comună:

H\left(y_{1}\dots y_{n};Z\right)=H\left(y_{1}\dots y_{n}\right)+H\left(Z|y_{1) }\puncte y_{n}\dreapta)\aproximativ 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) )\aproximativ H\stanga(Z\dreapta)+{n \peste N}H\stanga(X\dreapta)

n\log L+f_{n}\aproximativ H\stanga(Z\dreapta)+{n\peste N}H\stanga(X\dreapta)

n\aprox {{H\left(Z\right)-f_{n}} \over {\log LH\left(X\right)/N}}={{H\stânga(Z\dreapta) -f_{n}} \over {\log L\cdot \left({1-{{H\left(X\right)} \over {N\log L}}}\right)))

Apoi, conform definiției distanței unicității ca : $u:f_{u}=0$

u\aprox {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)} \peste {N\log L}}}\right)}}

Expresia se numește redundanță sursă . Dacă redundanța sursei este zero, adică este imposibil să se determine din textul clar dacă este corectă sau nu (nu există sume de control sau semnături în ea), atunci distanța de unicitate devine egală cu infinit, iar criptosistemul devine absolut sigur. $\rho =1-{{H\left(X\right)} \over {N\log L}}$

Exemplu

Pentru limba rusă, redundanța este de 3,5 biți pe caracter. Dacă se folosește un cifru monoalfabetic , atunci numărul de chei posibile din acesta este egal cu , iar entropia cheii (cu o alegere equiprobabilă) de un bit . $33!\aproximativ 8,68\cdot 10^{36)$ $H\left(Z\right)=\log _{2}33!\aproximativ 122,7$

Apoi, distanța de unicitate pentru un text rusesc criptat cu un simplu cifr de substituție este:

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

Adică, dacă un criptoanalist interceptează mai mult de 35 de caractere ale textului cifrat, acest lucru va permite cel mai probabil (de exemplu, prin căutare exhaustivă) să restabilească textul simplu original. Dacă sunt interceptate mai puține caractere, atunci recuperarea textului va fi ambiguă (pot exista mai multe versiuni diferite ale textului simplu).

Literatură

Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Unicitatea distanță // Securitatea informației : manual - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
G. V. Basalova Unicitatea Distanța // Fundamentele Criptografiei (rusă)

Link -uri

Bruce Schneier : Cum să recunoașteți textul simplu (Buletin informativ Crypto-Gram 15 decembrie 1998 )
Unicity Distanța calculată pentru cifrurile comune