3. Оценка криптостойкости метода генерации ключа. Вероятностный анализ.

3.1. Вариант обмена ключами без использования квантового эффекта.

Рассмотрим сначала вариант алгоритма, когда абоненты отбирают элементарный ключ по уравнениям шифрования всех сообщений, т. е. когда длина серии T=Nc. Ключ K шифрует эталонный открытый текст X(t) по уравнению шифрования (2.2) и передается по каналу связи шифротекстом Y(t). Нас интересует условная вероятность угадывания этого ключа при известных открытом тексте {Х(t)}₁^Tи шифротексте{Y(t)}₁^T.

Введем следующие обозначения:

• Pg – безусловная (априорная) вероятность угадывания ключа без знания шифротекста (без учета уравнения шифрования),
• Pg|c – условная вероятность угадывания ключа при известных открытом и шифрованном текстах, т. е. с учетом уравнения шифрования,
• Pc – вероятность, что данное значение ключа удовлетворяет уравнению шифрования,
• Pc|g – условная вероятность того же события при условии, что ключ истинный, т. е. угадан правильно,
• Pc|f – то же, при условии, что ключ ложный, т. е. не угадан.

Интересующая нас условная вероятность угадывания Pg|c может быть вычислена по формуле апостериорной вероятности через априорную вероятность Pg и вероятность рассматриваемого условия Pc:

(3.1)…..Pg|c=Pc|g*Pg/Pc

Вероятность Pc события «данный ключ удовлетворяет системе уравнений шифрования» можно разложить по полной системе из двух событий: «ключ истинный, т. е. угадан правильно» и «ключ ложный, т. е. не угадан» с соответствующими вероятностями Pg и 1-Pg:

(3.2)…..Pc= Pc|g*Pg+Pc|f*(1-Pg) .

В силу определения истинного ключа первое из этих событий достоверно, т. е. Pc|g=1. Априорная вероятность угадывания Pg, очевидно, равна 1/Mk. С учетом этих соотношений из (3.1) и (3.2) получаем:

(3.3)….. Pg|c=1/(1+(Mk-1)*Pc|f) .

Найденная вероятность имеет простую связь с числом ложных ключей F, определяемым формулой (2.4). Что бы подчеркнуть эту связь, формулу (3.3) целесообразно переписать в виде:

(3.4)….. Pg|c=1/(1+F) , F=(Mk-1)*Pc|f .

Но условная вероятность Pc|f - есть вероятность ложного ключа для системы из 2*Nc уравнений шифрования и равна q^^2*Nc. Поэтому формула (3.4) принимает вид:

(3.5)…..Pg|c=1/(1+F) , F=(Mk-1)*q^^2*Nc.

Рассмотрим теперь процедуру криптоанализа перехваченных шифротекстов. Отличие этой процедуры от протокола абонентов состоит в том, что абонент на каждом шаге наугад выбирает один ключ из множества Mk и проверяет его по системе уравнений шифрования, а криптоаналитик перебирает все ключи из Mk и каждый из них проверяет по этой же системе уравнений. Таким образом, вероятностная схема для абонентов оперирует с одним событием «угадывание ключа», исходы которого представляют временную последовательность. Для криптоаналитика вероятностная схема оперирует с множеством идентичных событий, исход которых единовременный. (Это аналогично бросанию монеты много раз последовательно или бросанию один раз множества монет.) Из аксиоматики теории вероятности известно, что частота положительных исходов в обоих случаях стремится к одной и той же теоретической вероятности данного события. А так как абоненты и криптоаналитик располагают и оперируют одной и той же системой уравнений шифрования, то механизм случайности рассматриваемого события для них одинаков. Следовательно, условная вероятность угадывания ключа для криптоаналитика та же, что и для абонентов и определяется так же формулой (3.5). Такой результат имеет место, когда абоненты не используют квантовый эффект случайных событий.

3.2. Вариант обмена ключами с использованием квантового эффекта.

В этом варианте длина серии сообщений T существенно больше длины интервала сохранения ключа до его отбора Nc. Рассмотрим сначала вероятность угадывания для абонентов. Абонент отбирает элементарный ключ, только когда он удовлетворит уравнениям шифрования партнера Nc раз подряд. При этом формула (3.3) остается справедливой, но смысл вероятности ложного ключа Pc|f изменяется, так как изменяется условие угадывания абонентом ключа партнера. Угадывание ключа теперь происходит при условии, что он удовлетворяет уравнениям шифрования, причем не обязательно для совпадающих по номеру сообщений абонентов. При этом указанная вероятность ложного ключа зависит от величины взаимного смещения интервалов сохранения ключа абонентами Dt, как показано на схеме рис. 3.1.

Рис. 3.1. Взаимное расположение интервалов сохранения ключей абонентов А и В.

Рассмотрим сначала крайние случаи. Если интервалы сохранения ключей абонентов совпадают (Dt=0), то ложным ключом является ключ, удовлетворяющий системе из 2*Nc уравнений шифрования и не совпадающий с истинным ключом этой системы. В соответствии с п.3.1, вероятность такого ложного ключа равна q^^2*Nc. Если же интервалы сохранения ключей вообще не перекрываются (Dt≥Nc), то, как следует из общих соображений, сохраненные и отобранные абонентами ключи могут совпасть лишь случайно и, следовательно, в этом случае вероятность угадывания абонентов (вероятность совпадения отобранных ключей) равна априорной вероятности угадывания Pg=1/Mk. Тогда из общей формулы (3.3) следует для этого случая Pc|f=1, т. е. любой ключ, удовлетворяющий Nc уравнениям шифрования, в этом случае является ложным. Это можно трактовать так, что системы уравнений шифрования каждого из абонентов не связаны в единую систему и не имеют общего истинного ключа. Таким образом, в крайних случаях Pc|f=q^^2*Nc для Dt=0 и Pc|f=1 для Dt≥Nc. В промежуточном случае, когда сообщения, для которых абоненты сохраняют ключи, смещены на Dt шагов (Dt<Nc), т. е. перекрываются на интервале Nc-Dt, на этом интервале их перекрытия истинный ключ существует. Тогда вероятность ложного ключа – это вероятность того, что этот ключ удовлетворяет одновременно 2*(Nc-Dt) уравнениям шифрования и эта вероятность равна q^^2*(Nc-Dt). Итак, можем записать:

q^^2*(Nc-Dt) для 0≤ Dt<Nc ,

(3.6)…..Pc|f(Dt)=

1 для Dt≥Nc .

Величина взаимного смещения интервалов сохранения ключа Dt – есть случайная величина, характеризующаяся распределением вероятностей P(Dt). Следовательно, вероятность Pc|f определяется по формуле полной вероятности:

(3.7)…..Pc|f=∑_Dt[Pc|f (Dt)*P(Dt)]₀^T-Nc ,

где T-Nc – максимально возможное смещение на интервале [1,T].

Остается найти распределение P(Dt) на интервале [0, T-Nc]. По определению Dt относится к интервалу сообщений, на котором один из абонентов не сохраняет свой ключ. Это происходит, когда его ключ не удовлетворяет уравнениям шифрования этих сообщений, т. е. не является для них ни истинным, ни ложным ключом. Вероятность того, что ключ удовлетворяет уравнению шифрования Pc была найдена в п. 3.1 – формула (3.2). Поэтому вероятность P(Dt) равна (1-Pc)^^Dt. Но такое распределение еще не учитывает условие успешности серии, т. е. условие, что в данной серии оба абонента отобрали ключи. Это дополнительное условие равносильно нормировке распределения P(Dt) на интервале [0, T-Nc], т. е. условию ∑_Dt[P(Dt)]₀^T-Nc=1. Таким образом, имеем:

(3.8)…..P(Dt)=(1-Pc)^^Dt/∑_Dt[(1-Pc)^^Dt]₀^T-Nc=(1-Pc)^^Dt*Pc/(1-(1-Pc)^^(T-Nc+1)) .

Это – геометрическое распределение вероятностей [3].

Теперь подставим найденные вероятности (3.6) и (3.8) в формулу (3.7). При вычислении суммы в этой формуле следует различать два случая в зависимости от выбора длины серии T. Если серия относительно короткая: T<2*Nc, то верхний предел суммирования T-Nc<Nc (интервалы отбора ключей абонентов всегда перекрываются) и все величины Pc|f(Dt) в сумме берутся по верхней строке в (3.6). Если же длина серии T выбрана больше, т. е. T≥2*Nc и значит T-Nc≥Nc, то сумма разбивается на две части: от 0 до Nc-1 (c Pc|f(Dt) по верхней строке) и от Nc до T-Nc (c Pc|f(Dt) по нижней строке). В результате, используя формулу суммы геометрической прогрессии, находим:

-для T<2*Nc

(3.9a)…..Pc|f=q^^(2*Nc)*(((1-Pc)/q^²)^^(T-Nc+1)-1)/((1-Pc)/q^²-1)*Pc/(1-(1-Pc)^^(T-Nc+1)),

-для T≥2*Nc

(3.9b)….. Pc|f=q^^(2*Nc)*(((1-Pc)/q^²)^^(T-Nc+1)-1)/((1-Pc)/q^²-1)*Pc/(1-(1-Pc)^^(T-Nc+1))+

(1-Pc)^^Nc*(1-(1-Pc)^^(T-2*Nc+1))/(1-(1-Pc)^^(T-Nc+1)) .

Итак, для рассматриваемого в данном пункте варианта алгоритма вероятность ложного элементарного ключа для абонентов определяется формулой (3.9), а их вероятность угадывания - формулой (3.5).

Перейдем теперь к вычислению вероятности угадывания ключа криптоаналитиком. Криптоаналитик не знает расположения интервалов сохранения ключей в серии сообщений, т. е. не знает момента t на оси времени, показанной на рис. 3.1. Заметим, что у абонентов конкретное расположение этих интервалов возникает автоматически в силу протокола обмена ключами, и их знание не потребовалось для вычисления вероятностных характеристик. Криптоаналитик же для выявления всей совокупности ложных ключей должен перепробовать все возможные расположения указанных интервалов, т. е. проанализировать все возможные системы из 2*Nc уравнений шифрования абонентов.

Формулу для вероятности ложного ключа криптоаналитика можно вывести двумя способами. Первый из них непосредственно следует алгоритму криптоанализа. Криптоаналитик выявляет путем перебора все ключи, удовлетворяющие возможным системам из 2*Nc уравнений шифрования, которые можно составить из всех T пар уравнений серии сообщений. Полученное таким образом множество ключей – это множество всех допустимых ключей, из которых один истинный, а остальные – ложные. Второй способ базируется на следующем факте, доказанном в п. 3.1. Если бы криптоаналитику было известно конкретное расположение интервалов сохранения ключей абонентов в серии сообщений (момент t на оси рис. 3.1), то его вероятность ложного ключа равнялась бы таковой для абонентов. Воспользуемся вторым способом, так как он позволяет легче получить сравнительную оценку вероятностных характеристик абонентов и криптоаналитика.

Обозначим все вероятности и числа ложных ключей, относящиеся к криптоаналитику с верхним индексом «ca», а относящиеся к абонентам – с индексом «ab». Каждому отобранному ключу поставим в соответствие момент времени t, как показано на рис. 3.1. Очевидно, вероятность ложного ключа криптоаналитика совпадает с таковой для абонентов Pc|f^ab при фиксированном t. Множество всех возможных значений t в успешной серии есть T-Nc+1. Тогда вероятность того, что на интервале всей серии нет ни одного ложного ключа, равна (1-Pc|f^ab)^^(T-Nc+1). Нас интересует противоположное событие «ложный ключ есть хотя бы в одном месте данного интервала». Вероятность этого события и есть искомая вероятность ложного ключа криптоаналитика Pc|f^ca и она равна:

(3.10)…..Pc|f^ca=1-(1-Pc|f^ab)^^(T-Nc+1) .

Соответственно, для среднего числа ложных ключей F^ca , в силу его определения (3.4), имеем:

(3.11)…..F^ca=(Mk-1)*Pc|f^ca=(Mk-1)*(1-(1-Pc|f^ab)^ ^(T-Nc+1)) .

Далее, так как угадывания элементарных ключей – взаимно независимые события, то вероятность угадывания всего составного общего ключа comPg|c равна произведению вероятностей угадывания элементарных ключей comPg|c=Pg|c^^NK=1/(1+F)^^NK. Здесь и далее предикативный индекс com означает принадлежность ко всему общему ключу. С другой стороны, по аналогии с (3.5) comPg|c=1/(1+comF). Поэтому для вероятности comPg|c можем записать:

(3.12)…..comPg|c=1/(1+comF) , comF=(1+F)^^NK –1 .

Эта формула справедлива как для абонентов, так и для криптоаналитика.

Понятие среднего числа ложных ключей связано с понятием условной энтропии ключа и полезно при оценке стойкости ключа, как альтернатива оценке в виде вероятности угадывания ключа. По определению энтропии информации, безусловная (полная) энтропия H(comK) всего составного общего ключа без знания исходного и шифрованного текстов равна его длине: H(comK)=log₂(1/comPg)=L. Для лица, знающего эти тексты, полная энтропия сокращается до условной энтропии Hc(comK)=log₂(1/comPg|c) и в силу (3.12) равна log₂(1+comF). Итак, среднее число ложных ключей при угадывании ключа служит оценкой его условной энтропии. Из формулы (3.10) видно, что всегда Pc|f^ca>Pc|f^ab. Тогда, в силу определения среднего числа ложных ключей абонентов (3.4), следует, что всегда F^ca>F^ab. Следовательно, и для всего общего ключа всегда comF^ca>comF^ab и H(comF^ca)>H(comF^ab). В этом и заключается действие квантового эффекта угадывания ключа.

Криптографическая эффективность процедуры генерации общего секретного ключа определяется соотношением вероятности отбора абонентами одинаковых ключей (вероятности совпадения их составных ключей) и вероятности определения этого ключа криптоаналитиком. Удобнее измерять эффективность в терминах энтропии информации. Процедура будет криптографически эффективной, если условная энтропия общего ключа для абонентов исчезающе мала, а для криптоаналитика составляет существенную часть длины ключа L.

Отметим следующий важный факт. При любой вероятности угадывания абонентами элементарных ключей, вероятность угадывания составного общего ключа, уменьшается с увеличением его длины, так как равна произведению указанных вероятностей. Поэтому приведенный протокол не позволяет сгенерировать достаточно длинный общий секретный ключ со сколь угодно высокой достоверностью. Одного только квантового эффекта случайных событий для этого недостаточно. Необходим какой-то прием, позволяющий повышать вероятность угадывания по мере наращивания числа элементарных ключей. В качестве такого приема можно применить метод сверки контрольного функционала от полученных ключей. В качестве контрольного функционала можно применить любой однородный многочлен от элементарных ключей, например, их сумму. Более эффективным оказывается применение набора функционалов, построенного по иерархическому принципу. Для этого общий составной ключ разбивается на связные группы элементарных ключей. Для каждой группы отобранных элементарных ключей вычисляется свой контрольный функционал. Назовем эти функционалы групповыми, а ключ, составленный из элементарных ключей данной группы – групповым ключом. Общий ключ составляется из групповых ключей.

Группировка элементарных ключей производится по иерархическому принципу. Так, несколько последовательных групповых ключей могут быть объединены в группой ключ следующего, более высокого уровня. Для этой группы также вычисляется групповой функционал следующего уровня. Здесь важно учесть, что для групповых функционалов разных уровней должно выполняться условие их взаимной независимости. А именно, функционал более высокого уровня не должен выражаться через функционалы предыдущих уровней. Если функционал каждого уровня определить, как сумму всех элементарных ключей этого уровня, то данное условие не выполняется: функционал следующего уровня всегда будет равен сумме групповых функционалов предыдущего уровня. Чтобы этого избежать следует применить нелинейное преобразование ключей при переходе к следующему уровню. Простейшим таким преобразованием является перевод составных ключей каждого уровня в десятичную систему счисления. Эти десятичные ключи и рассматриваются как элементарные ключи следующего уровня. Например, если элементарные ключи каждого отдельного сообщения – однобитовые, то групповой функционал первого уровня определяется, как сумма всех бит данной группы. Затем, вычисляется десятичный ключ этой группы. Групповой функционал второго уровня определяется, как сумма десятичных ключей входящих в него групп первого уровня и так для каждого следующего уровня.

Описанный метод генерации общего секретного ключа, основанный на комбинации генерации элементов ключа с использованием квантового эффекта и сверки контрольных функционалов разных уровней иллюстрируется схемой на рис. 3.2.

Рис. 3.2. Схема метода генерации общего секретного ключа.

Ясно, что сверка абонентами своих групповых контрольных функционалов повышает их вероятность угадывания общего ключа. Но она, очевидно, повышает и вероятность угадывания криптоаналитика.

1. 3. Вероятностная модель процедуры генерации общего секретного ключа с контрольными функционалами.

Рассмотрим общий случай, когда составной ключ разбит на группы нескольких иерархических уровней. Группа каждого следующего уровня состоит из десятичных групповых ключей предыдущего уровня. В соответствии с протоколом на каждом уровне производится два последовательных преобразования: вычисляется контрольный функционал от ключей предыдущего уровня и затем эти ключи группируются в десятичный составной ключ данного уровня. Вероятностная модель многоуровневого процесса генерации составного общего ключа имеет блочную структуру, представленную на рис. 3.3. На схеме обозначено: i- номер уровня группы, i=1,2,…,I; N_i и M_i – число элементов и мощность группового ключа i–ой группы; F_i и Fe_i - числа ложных ключей без учета и с учетом сверки функционала. Нулевой уровень соответствует процедуре отбора абонентами первичных элементарных ключей.

Рис. 3.3. Вероятностная схема генерации составного общего ключа.

Для любого i-го уровня имеем:

(3.13)…..M_i=M_i-1^^Ni ,

и в соответствии с формулой (3.12), справедливой для составного ключа любого уровня:

(3.14)…..F_i=(1+ Fe_i-1)^^Ni –1 .

Для замыкания этой модели необходимо найти связь между Fe_i и F_i, т. е. модель блока «сверка функционалов». Для этого рассмотрим вероятности угадывания группового ключа без учета функционала Pg|c_i и с учетом функционала Pg|e_i. Используя формулу апостериорной вероятности аналогично (3.1), (3.2) и (3.5) можем записать:

(3.15)…..Pg|e_i=Pe|g_i*Pg|c_i/(Pe|g_i*Pg|c_i+Pe|f_i*(1-Pg|c_i))=1/(1+Fe_i), Fe_i=(1-Pg|c_i)/Pg|c_i*Pe|f_i ,

где Pe|f_i - вероятность ложного ключа функционала, а Pe|g_i=1 по определению.

Выражая вероятность угадывания Pg|c_i через число ложных ключей F_i в соответствии с (3.5) получим:

(3.16)…..Fe_i=F_i*Pe|f_i .

Для пользования формулой (3.16) необходимо вычислить вероятность ложного ключа функционала Pe|f_i. Эту вероятность можно найти по формуле полной вероятности:

(3.17)…..Pe|f_i=∑_m[Per(m)*P(m)]|₀^Ni ,

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

Так как функционал по определению есть однородный многочлен от входящих в него ключей, то его ошибочное совпадение возможно только, если все ошибки значения функционала за счет отличия ложных ключей от истинных взаимно компенсируются. Именно на этом свойстве контрольного функционала основана его способность выявлять ошибки при передаче информации по каналам связи. В нашем же случае назначение контрольного функционала - выявлять ошибки абонентов при отборе ключей (выявлять не совпадения этих ключей). Взаимная компенсация ошибок функционала происходит, когда один из ложных ключей компенсирует в функционале отличия остальных ложных ключей от истинных. Следовательно, Per(0)=Per(1)=0, а вероятность компенсации ошибок Per(m)для m≥2 равна вероятности того, что один ложный ключ имеет не произвольное, а фиксированное заданное значение. Вероятность этого равна 1/M_i-1 и она не зависит от m. Следовательно, формулу (3.17) можно переписать в виде:

(3.18)…..Pe|f_i=1/M_i-1*∑_m[P(m)]|₂^Ni=1/M_i-1*(∑_m[P(m)]|₀^Ni-P(0)-P(1))=1/M_i-1*(1-P(0)-P(1)).

(Здесь учтено, что в силу нормировки ∑_m[P(m)]|₀^Ni=1.) Очевидно, что распределение вероятностей числа ложных ключей P(m) является биномиальным с вероятностью ложного ключа 1-Pg|e_i-1, равной ошибке угадывания группового ключа предыдущего уровня 1-Pg|e_i-1=1-1/(1+Fe_i-1)=Fe_i-1//(1+Fe_i-1). Поэтому с учетом (3.14) можем записать:

(3.19)…..P(m)=C^m_Ni*(1-Pg|e_i-1)^^m*Pg|e_i-1^^(Ni-m)=C^m_Ni*Fe_i-1^^m/(1+Fe_i-1)^^Ni=C^m_Ni*Fe_i-1^^m/(1+F_i) .

Отсюда для m=0 и m=1 имеем P(0)=1/(1+F_i) и P(1)=Ni*Fe_i-1/(1+F_i) и подстановка в (3.18) дает:

(3.20)…..Pe|f_i=1/M_i-1/(1+F_i)*(F_i-N_i*Fe_i-1) .

Теперь можем записать выражение для числа ложных групповых ключей с учетом функционала Fe_i в соответствии с (3.16):

(3.21)…..Fe_i=1/M_i-1*F_i/(1+F_i)*(F_i-N_i*Fe_i-1) .

Таким образом, вероятностная модель i-го уровня описывается соотношениями (3.13), (3.14) и (3.21). Для нулевого уровня в силу (3.5) и (3.11) имеем:

(3.22)…..F₀^ab=(M₀-1)*Pc|f₀^ab , F₀^ca=(M₀-1)*(1-(1-Pc|f₀^ab)^ ^(T-Nc+1)) ,

где вероятность Pc|f₀^ab определяется выражением (3.9).

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

Детальный анализ модели показывает, что надлежащим выбором ее параметров можно обеспечить уменьшение числа ложных ключей абонентов на каждом уровне и увеличение их для криптоаналитика. Иными словами, с ростом количества уровней модели можно обеспечить нарастающий выигрыш абонентов относительно криптоаналитика в вероятности угадывания общего секретного ключа или, что эквивалентно, в энтропии этого ключа. Определим этот выигрыш для i-го уровня отношением чисел ложных ключей k_i=Fe_i^ca/Fe_i^ab и оценим его. Для этого упростим модель путем разложения правой части выражения (3.14) в ряд в точке Fe_i-1=0. Получаем F_i≈N_i*Fe_i-1 и F_i-N_i*Fe_i-1≈N_i*(N_i-1)/2*Fe_i-1^². Эти приближенные равенства можно считать справедливыми для абонентов, так как для них Fe_i-1^ab<<1. Для криптоаналитика же тем самым получаем нижнюю оценку, заменяя ≈ на >. С учетом этих соотношений вместо (3.21) можем записать отдельно для абонентов и криптоаналитика:

(3.23)…..Fe_i^ab≈1/M_i-1*N_i^²*(N_i-1)/2*Fe_i-1^ab^³, Fe_i^ca>1/M_i-1*N_i^²*(N_i-1)/2*Fe_i-1^ca^³ .

Отсюда получаем формулу для гарантированной нижней оценки k_i:

(3.24)…..k_i>k_i-1^³ .

Отсюда видно, что k_i растет с ростом i очень быстро, если k₀>1. Но, как было показано в п.3.2, всегда F₀^ca>F₀^ab и, значит, k₀>1. Таким образом, вероятностный выигрыш абонентов по отношению к криптоаналитику обусловлен исключительно квантовым эффектом на нулевом уровне, а сверка функционалов на остальных уровнях усиливает этот результат.

Рассчитаем еще вероятность успешности серии Psuc, через которую определяется доля успешных серий. По определению успешной серии, вероятность Psuc равна произведению вероятности отбора всех элементарных ключей на 0-ом уровне Psuc₀ и вероятности совпадения всех функционалов у абонентов. Но событие «совпадение всех функционалов» входит в событие «угадывание общего ключа абонентами», вероятность которого есть Pg|e_I. Следовательно, имеем оценку Psuc>Psuc₀*Pg|e_I. Далее, в соответствии с выкладками п. 3 (см. рис. 3.1) вероятность того, что на нулевом уровне элементарный ключ не отобран – это вероятность P{Dt>T-Nc}=(1-Pc)^^(T-Nc+1). Таким образом, вероятность отбора всех NK элементарных ключей обоими абонентами равна:

(3.25)…..Psuc₀=(1-(1-Pc)^^T-Nc+1)^⁽²*^NK) ,

и для искомой вероятности Psuc имеем оценку:

(3.26)…..Psuc>(1-(1-Pc)^^T-Nc+1)^⁽²*^NK)*Pg|e_I .

Построенная вероятностная модель процедуры генерации общего секретного ключа была проверена экспериментально, путем численного моделирования действий абонентов и криптоаналитика. При этом все вероятности вычислялись эмпирически, через частоты соответствующих событий. Были приняты следующие исходные данные:

- длина общего секретного ключа L=15 бит;

- число совпадений элементарного ключа для его отбора Nc=2;

- длина серии Т=9;

- общий ключ разбит на 2 иерархических уровня с N₁=5, N₂=3;

- соответственно этой разбивке L₀=1 бит и M₀=2^¹=2, L₁=N₁*L₀=5 бит и M₁=2^⁵=32, L₂=N₂*L1₁=15 бит и M₂=2^¹⁵=32768;

.

Вероятность угадывания абонентов определялась эмпирически по числу серий, в которых сгенерированные ими общие ключи совпадали. Для криптоаналитика криптоанализ проводился только для тех серий, в которых отобранные абонентами общие ключи совпали. Алгоритм криптоанализа моделировался следующим образом для каждой серии сообщений. Мощность множества общих ключей равна 2^¹⁵=32768. Поочередно перебираются все десятичные общие ключи этого множества от 0 до 32767. Из каждого такого ключа формируются ключи 1-го и 2-го уровней: три 5-ти битных ключа 1-го уровня и 15-ти битный ключ 2-го уровня (это сам общий ключ). Вычисляются все групповые функционалы: 3 функционала 1-го уровня и единственный функционал 2-го уровня. Эти функционалы сравниваются с соответствующими функционалами абонентов. Если все 4 функционала совпадают, то данный общий ключ считается допустимым, а в противном случае – отбрасывается. Таким образом формируется множество (массив) допустимых общих ключей. Это – первый этап селекции множества допустимых ключей. Далее, каждый допустимый общий ключ представляется в виде набора из 15 элементарных однобитных ключей нулевого уровня (т. е. представляется в двоичном виде). Для каждого элементарного ключа отыскивается на оси t (см. рис. 3.1) интервал длиной Nc, на котором этот элементарный ключ удовлетворяет Nc уравнениям шифрования. Эта процедура производится для уравнений шифрования каждого из абонентов. Если на всем интервале серии [1, T] такие интервалы существуют для сообщений обоих абонентов, то данный элементарный ключ считается допустимым. Если допустимыми оказываются все 15 элементарных ключей, то соответствующий общий ключ сохраняется в множестве допустимых ключей, а в противном случае исключается из него. Это – второй, окончательный, этап селекции множества допустимых общих ключей для данной серии сообщений. Ясно, что в оставшемся множестве один ключ – истинный, а остальные – ложные. По всем сериям вычисляется среднее число ложных ключей, а через него – эмпирическая вероятность угадывания криптоаналитика.

Всего было смоделировано 100000 серий генерации общего секретного ключа. В результате среднее число ложных ключей абонентов составило 0,0008, а эмпирическая вероятность их ошибки угадывания общего ключа составила, соответственно, 0,08%. Для криптоаналитика среднее число ложных ключей оказалось равным 20, т. е. в 25000 раз больше. Этому числу ложных ключей отвечает вероятность угадывания ключа 5% (вероятность ошибки 95%)и энтропия ключа Log₂21=4,3, т. е. около 1/3 длины общего секретного ключа. Доля успешных серий превысила 90%. Полученные экспериментальные результаты хорошо согласуются с построенной вероятностной моделью процедуры генерации общего секретного ключа. Для тех же исходных данных по модели получается ошибка абонентов 0,07%, вероятность угадывания криптоаналитика 6%. Расхождение, по-видимому, можно объяснить не идеальностью машинного генератора случайных чисел (наличием корреляции и периодичности) и вычислением вероятностей по ограниченной выборке.