01.02.2022

Расстояние единственности (в криптологии) — число символов шифртекста, при которых условная информационная энтропия ключа (а, следовательно, и открытого текста) равна нулю, а сам ключ определяется однозначно.

Достижение расстояния единственности ещё не означает, что ключ (или открытый текст) можно найти на практике, так как определение не учитывает практическую вычислимость ключа, но лишь постулирует, что его можно найти, например, с помощью полного перебора.

Определение

Определим функцию надёжности ключа через условную информационную энтропию ключа Z {displaystyle Z} и символов шифротекста y 1 , y 2 , … , y n {displaystyle y_{1},y_{2},dots ,y_{n}} , которые перехватывает криптоаналитик:

f 0 = H ( Z ) {displaystyle f_{0}=Hleft(Z ight)} f 1 = H ( Z | y 1 ) {displaystyle f_{1}=Hleft(Z|y_{1} ight)} f 2 = H ( Z | y 1 y 2 ) {displaystyle f_{2}=Hleft(Z|y_{1}y_{2} ight)} … {displaystyle dots } f n = H ( Z | y 1 y 2 … y n ) {displaystyle f_{n}=Hleft(Z|y_{1}y_{2}dots y_{n} ight)} f n ≤ f n − 1 ≤ ⋯ ≤ f 1 ≤ f 0 {displaystyle f_{n}leq f_{n-1}leq dots leq f_{1}leq f_{0}}

Такое число перехваченых символов u {displaystyle u} , при котором f u = 0 {displaystyle f_{u}=0} и называется расстоянием единственности.

Приблизительная формула

Выведение формулы расстояния единственности возможно для некоторой «хорошей» криптосистемы, у которой информационная энтропия шифротекста обладает определёнными свойствами «линейности»:

H ( Y ) = N log ⁡ L {displaystyle Hleft(Y ight)=Nlog L} где N {displaystyle N} — общее число символов шифротекста сообщения, L {displaystyle L} — алфавит шифротекста, для простоты принимаемый равным в том числе и для открытого текста, и для ключа шифрования H ( y 1 … y n ) ≈ n log ⁡ L {displaystyle Hleft(y_{1}dots y_{n} ight)approx nlog L} H ( y 1 … y n | Z ) ≈ n N H ( X ) {displaystyle Hleft(y_{1}dots y_{n}|Z ight)approx {n over N}Hleft(X ight)} последнее выражение является «линеаризацией» выражения H ( Y | Z ) = H ( X ) {displaystyle Hleft(Y|Z ight)=Hleft(X ight)}

Тогда из выражений для совместной информационной энтропии:

H ( y 1 … y n ; Z ) = H ( y 1 … y n ) + H ( Z | y 1 … y n ) ≈ n log ⁡ L + f n {displaystyle Hleft(y_{1}dots y_{n};Z ight)=Hleft(y_{1}dots y_{n} ight)+Hleft(Z|y_{1}dots y_{n} ight)approx nlog L+f_{n}} H ( y 1 … y n ; Z ) = H ( Z ) + H ( y 1 … y n | Z ) ≈ H ( Z ) + n N H ( X ) {displaystyle Hleft(y_{1}dots y_{n};Z ight)=Hleft(Z ight)+Hleft(y_{1}dots y_{n}|Z ight)approx Hleft(Z ight)+{n over N}Hleft(X ight)} n log ⁡ L + f n ≈ H ( Z ) + n N H ( X ) {displaystyle nlog L+f_{n}approx Hleft(Z ight)+{n over N}Hleft(X ight)} n ≈ H ( Z ) − f n log ⁡ L − H ( X ) / N = H ( Z ) − f n log ⁡ L ⋅ ( 1 − H ( X ) N log ⁡ L ) {displaystyle napprox {{Hleft(Z ight)-f_{n}} over {log L-Hleft(X ight)/N}}={{Hleft(Z ight)-f_{n}} over {log Lcdot left({1-{{Hleft(X ight)} over {Nlog L}}} ight)}}}

Тогда согласно определению расстояния единственности как u : f u = 0 {displaystyle u:f_{u}=0} :

u ≈ H ( Z ) log ⁡ L − H ( X ) / N = H ( Z ) log ⁡ L ⋅ ( 1 − H ( X ) N log ⁡ L ) {displaystyle uapprox {Hleft(Z ight) over {log L-Hleft(X ight)/N}}={Hleft(Z ight) over {log Lcdot left({1-{{Hleft(X ight)} over {Nlog L}}} ight)}}}

Выражение ρ = 1 − H ( X ) N log ⁡ L {displaystyle ho =1-{{Hleft(X ight)} over {Nlog L}}} называют избыточностью источника. Если избыточность источника равна нулю, то есть по открытому тексту невозможно определить, является ли корректным или нет (в нём нет контрольных проверочных сумм или сигнатур), тогда расстояние единственности становится равным бесконечности, а криптосистема — абсолютно надёжной.

Пример

Для русского языка избыточность равна 3,5 бита на символ. Если используется моноалфавитный шифр, то число возможных ключей в нём равно 33 ! ≈ 8 , 68 ⋅ 10 36 {displaystyle 33!approx 8,68cdot 10^{36}} , а энтропия ключа (при равновероятном выборе) H ( Z ) = log 2 ⁡ 33 ! ≈ 122 , 7 {displaystyle Hleft(Z ight)=log _{2}33!approx 122,7} бита.

Тогда расстояние единственности для русского текста, зашифрованного шифром простой замены, равно:

u = H ( Z ) ρ ≈ 35 , 1 {displaystyle u={{Hleft(Z ight)} over { ho }}approx 35,1}

То есть, если криптоаналитик перехватит более 35 символов шифротекста, это с большой степенью вероятности позволит (например, полным перебором) восстановить исходный открытый текст. Если же будет перехвачено меньшее количество символов, то восстановление текста будет неоднозначным (могут быть несколько разных вариантов открытого текста).


Имя:*
E-Mail:
Комментарий: