Спросить
Войти
УДК 621.391 А.Б. Лось
Исследование информационных характеристик преобразований замены и перестановки
Излагаются результаты исследования информационных характеристик преобразований замены и перестановки, являющихся основой построения криптографических алгоритмов. Получены оценки взаимной информации входных и выходных сообщений дискретного канала связи при применении указанных преобразований.
В настоящей статье излагаются результаты исследования информационных характеристик преобразований замены и перестановки, являющихся основой построения криптографических алгоритмов [1-2]. Для указанных преобразований найдены верхние оценки взаимной информации входных и выходных сообщений дискретного канала связи. Полученные результаты позволяют оценивать эффективность данных преобразований в различных криптографических ситуациях.
Пусть знаки аі входного сообщения Бпє<з(п) длины N аи = (aь...,aN) дискретного канала
связи, выбираются из алфавита А = {1,2,...,п}, аі є А , і = 1,2,...,N, а знаки Ъ выходного сообщения
Ъы, bN = (Ь1,...,bN) образуются из знаков сообщения aN путем применения преобразований замены и перестановки, выражаемых уравнениями:
Ъ = агБ, (1)
Ъ = а, (і), і = 1,2,..., N, (2)
где Бп — некоторая подстановка степени п, выбираемая из множества ст(и) - всех подстановок
степени п ; а SN = | | - некоторая подстановка степени N, выбираемая из множества
v s(1),...,s (N )j
o(N) всех подстановок степени N.
Обозначим через MN = {aN } и EN = {bN } множества входных и выходных сообщений длины N соответственно.
Зададим на множестве входных сообщений MN и множествах подстановок ст(и) и ct(N) некоторые вероятностные распределения:
P(MN ) = {P(aN X aN еMN } , p(u(n)) = {p(Sn X Sn е ст(и)}, p(CT( N))={p( Sn ), Sn ео( N)}.
Нетрудно видеть, что при этом в том и другом случае будут индуцироваться некоторые
вероятностные распределения на множестве выходных сообщений EN.
Назовем далее H(A) - энтропию вероятностной схемы (ансамбля) A ; H(A/B) - условную энтропию ансамбля A при заданном ансамбле B, а I(A,B) — взаимную информацию ансамблей A и B . Пользуясь известными свойствами энтропии [3—4], получаем
H (MN)+H (EN /MN)=H (EN)+H (MN / EN),
откуда следует равенства:
H(MN /En ) = H(MN)-H(En)+H(En /Mn), (3)
I (A, B) = H (MN) - H (MN / EN) = H (EN) - H (EN /MN), (4)
H (MN) = - £ p (Qn )-log p(aN ), (5)
— „ rN
a, тєМ
H (En ) = -_£ p(bN)-log p(bN), (6)
а логарифм берется по основанию 2.
Рассмотрим вначале задачу оценки взаимной информации для преобразования замены.
В соответствии с определением условной энтропии получаем:
H(eN /Mn ) = - £ £ p(aN) -pipN /aN)-logp(bN /aN), (7)
- wNr ,,N
^n M b eM
где _ _
p(bN ) = £ p(aN) • p(bN /aN), (8)
p(bN/aN) = £ p(Sn ) • 1{i>, = aSN, =i,N}>
I(R) - индикатор условия R .
Дальнейшие расчеты будем проводить в предположении, что рассматриваемый канал связи есть дискретный канал без памяти, при этом, очевидно,
p(«N ) = p(ai) •...• p(aN h
а также в предположении, что подстановка Sn выбирается случайно и равновероятно из множества ст(и) - всех подстановок степени п.
В этом случае:
p(bN /aN,Sn ) = £ p(Sn )p(bN /aN,Sn ) = £ p(bN /aN,Sn ),
Sn^a(n) n*Sn£a(n)
где p(bN/aN,Sn) = 1, если b = aiSn, i = 1,2,...,N и 0 - в противном случае.
Последнее соотношение можно переписать в виде условий:
a S Л [n— bN)]! (9)
p(bN& aN,Sn) = . , (9)
если существует такая подстановка Sn ea(n), что bt = atSn, i =1,...,N ; p(bN/aN,Sn) = 0 в противном случае, где u = u(b1,...,bN) - число различных элементов в последовательности (b1,...,bN).
Пусть далее (a(1),...,a(n)) - первичная спецификация последовательности (b1,...,bN), а именно: a(r) - число элементов последовательности (b1,...,bN), равных r, r = 1,...,n .
Тогда из (9) получаем:
p(bN) = [n-U(b^r-bN)]! £ П [p(r, )]a( r >, (10)
n! , /=1
Г ,...,Ги =1 ^=1 ri * rj, i * i
где a(rk) > 0, k = 1,2,...,и , т.е. a(rk) - элементы последовательности первичной спецификации,
отличные от 0.
Подставляя (10) в (6) и (7), получаем
H (En /Mn ) = - £ -N— p(1)l1...p(n)In x £ [n - Ц(4,..., 4)]! - log[n - Ц(А ,...,^n)]! (11)
L! I ! i \\ n n
l1,...,In =0 k (1),...,k (n(l1,...,In ))=1
L1+..+Ln =N k(i) * k (j), i* j
Н(Е*) =- 2 ^-Ц(&тЛ))! £ "п.....[Ж*))]™*» х
/! ;...;/„ =0 Г (1);...;Г (Ц )=1 ^ =1
/1+---+/„ = М г(Г)^г(]&)
х1о§2(«-ц(/ьр/„))! £ ц(/1п;/п)[ ^(Г (к))/(Г (к)); (12)
Г (1);...;Г (Ц) = 1 к=А Г (г) ^Г (])
где Ц = ц(/1,...,/„) - число ненулевых элементов В последовательности (/ь.../„); (/ (г (1),...,/(г(ц)) -последовательность самих ненулевых элементов.
N! (n-ц(1ь...,1п ))! n )
Подставляя (11) и (12) в равенство (4) получаем выражение для взаимной информации входных и выходных сообщений рассматриваемого канала связи I (М* ; Е* ); явный вид которого; в силу громоздкости выражений; приведем для случая р(аг) = 1/и; г = 1;. ..;И :
,ы лп____ „-N Е N! , п!
I(М ;Е*) = N 1о§п -п* • £ —-1ов-------- • ; . (13)
Ч +...+/п = *
В силу очевидных неравенств
Н (М* /Е*) > п *
( \\ п *
* !• 1об
(п - *)!’
-X > 1п(1- X) > - ; 0 < X < 1;
из соотношения (12); в условиях п > * ; получаем оценку для I(М*,Е*) - величины взаимной информации входных и выходных сообщений при применении преобразования простой замены:
—I (М* ;Е* )<-—[1+1ови]. (14)
* п - 1
Рассмотрим теперь преобразование перестановки.
Заметим; что в соответствии с введенными выше предположениями; вероятность появления входного сообщения ап = (а1;...;ап); где ц е А = {1;...;И}; равна
р(а*) = р(а1)•...• р(а*) = рД..РпГп ; (15)
где рк - вероятность появления знака входного сообщения равного к; а вектор частот Г = (/1;...;Гп) - первичная спецификация последовательности а*; гк - число исходов; равных к. Будем также предполагать; что подстановка Б* выбирается случайно и равновероятно из множества о(Ы) - всех подстановок степени *.
Нетрудно видеть; что все множество входных сообщений М* можно представить в виде объединения непересекающихся множеств М* (Г); соответствующих первичным спецификациям векторов Г :
М* = иМ* (Г).
Аналогичным образом можно представить и множество выходных сообщений Е* :
Е* = иЕ* (Г).
Далее заметим; что условная вероятность р(Ь* /а*) появления выходного сообщения Ь* при заданном входном сообщении а* еМ* (Г) имеет вид
р(Ь* /а*) = ^!; если Ь* е Е*(Г);
р(Ь* /а*) = 0; если Ь* € Е* (Г). (16)
Следовательно; при Ь* е Е* (Г)
р(Ь*) = £ р(а*)р(Ь*/а*) = £ р1п...р/п!=р^..рпп. (17)
а* еМ* а* еМ* (Г) !
Для энтропии Н (Е*) ансамбля выходных сообщений имеем
н(Е*)=-_£ р(Ь*)1оёр(Ь*)=- £ _ £ рп...рпГп 1оё(р1Г1...рпГ)=
Ь*еЕ* Г=(Г1;...;Г„) Ь*еЕ*(Г)
Г1+...+Г„ = *
= - £ *! , руп... рпГп 1оё[ р1Г ... рпп ]. (18)
Г=(г1...гп) П!...Гп!
Г1+...+Гп = *
А.Б. Лось. Исследование информационных характеристик преобразований замены и перестановки 101 В соответствии с определением условной энтропии имеет место равенство
H(En/Mn) = - £ p(aN)_ £ p(bN/aN)logp(b"/aN) =
aNeMN bN eEN
v V r r r1!...rn I -!..-„ I ^ - rn NI N! (19)
= - £ £ p!...pn n log^^) = £ F11...pn n—-------:log(—-------).
-( л- TlNN! N! -( ) n!...rn! ri!...rn!
r =(r1,...‘&n) aNeM" (r) r = Оъ...—) 1 n 1 n
n+...rn =N bNeEN(-) - +...+rn="
С учетом (4), (18) и (19) получаем
H(En /MN) - H (En ) = £ _"L p1r1...pnrn [log^-NL) + log(p1r1...pnrn)] =
-=(-1,..-п) --гп! -L-!
-1+...-п ="
= £ —"—г pr.pnrn tog[-N-!n&1..pnrn]- (20)
-*(n,...rn) -1! & Гп ! ^. &п !
-+..-n=N
С учетом (20) из соотношения (4) получаем
I (MN, En ) =H"(p1,...pn), (21)
HN(P1,...,pn) = - £ —N—.pi1...pnrn log[ "! p-1...pnrn ] (22)
-= (-1,...-n) 1!...rn ! l^n !
-+... rn = "
есть энтропия полиномиального распределения.
Далее в работе исследуется асимптотическое поведение величины H" (p1,..., pn) при N и n / N ^ 0.
Рассмотрим полиноминальную схему с числом испытаний N и вектором вероятностей
P = (Д,...,Pn), где Pk - вероятность появления исхода, равного k, k = 1,...,n .
Обозначим через lk случайную величину, равную числу исходов в данной полиноминальной схеме, равных k, k = 1,...,n .
Тогда, очевидно,
P(lk = k) = Pk, E^k = NPk, D^k = NPk (1-Pk), k=1,...,n,
P(l1 = 1,...,^n = rn) = "! .p1-1...p/n . (23)
Учитывая соотношение (23), величину H" (P_,..., Pn) можно представить в виде
H" (P1,..., Pn) = -log N!+ £e log(^k!) - £e^ log Pk . (24)
Нетрудно видеть, что
£ Elk log Pk = N • Hp , (25)
где Hp = £Pk log Pk .
Для оценки первого слагаемого в (24) используем формулу Стирлинга ([5]):
х! = л/2Пxx+1/2e“ х+0/12 х, (26)
где х > 0, 0 <0<1.
Тогда
log N !=N log N+-2 log N - N log e+log л/2п+~~ l°g e, (27)
где -------log e = O (-) = 0(1).
Оценим сумму £ Еloglk! Применяя формулу (26), получаем k=1
Еlog lk! = £ logS! C-P— (1 - PK)N-s = £ Slog S • C—P— (1 - Pk )- + - £ log S • S (1- Pk )N~S S =0 S=0 2 S=1
-loge £ SC"pN(1-Pk)n-s + logT^0^ £1C-pK(1-Pk)N-— . (28)
S=0 12 S=1S
Для первой суммы в (28) имеем:
£ Slog S • C—p) (1-Pk )N-S = NBn (Pk ) + NP) log N, (29)
где Bn (Pk ) = £ - log— C-P) (1-Pk )N-— . s=0 N N
Заметим, что функция U(x) = x • log x непрерывна на отрезке [0,1] и имеет конечную производную 2-го порядка в точке х = Pk > 0.
Тогда, применяя теорему о порядке приближения с помощью полиномов Бернштейна [6], получаем
Bn (Pk ) = U (Pk ) + U"(^ = Pk P (1-P )+£""« ,
где pn(k) ^0 при Nравномерно по k = 1,...,n.
Отсюда, определив U"(х)| x = Pk , получаем
£ S log S •C—P— (1 - Pk )N- - = NPk log NPk +(1 - P)2)log e + Pn (K), (30)
где p n (k) ^ 0 при N .
Далее с учетом (24) получаем
n N v v м ? n-1
£ £ Slog S • C-Pk- (1 - Pk )N-- = N log N - NHp + (—)log e + pS (K), (31)
K=1-=0 2
где p’N(K) = £ pN(K)<nmaxpN(K)^0 при N^да.
Вторую и четвертую сумму в правой части (28) оценим с помощью неравенства Чебышева [7],
положив s = N3 P)2 и разбив область суммирования по — на 2 части:
Для второй суммы в правой части (28) имеем
£ (log—)cJpk— (1-PN )S-— = £ (logs)C—pn— (1-Pn )n-— + £ (log—)С"Р)— (1- Pk N.
—=1 2 1 2 1
|—-SPn|>N3Pn2 |s-NPK |<S3Pn2
Для первой суммы в (32) с учетом (23) имеем
£ (log-) C—P)- (1-Pn )N-S < (logS) P{| Ik - S7N | > N3 Pn2} < N-1/3 (1-Pk )log N=O(S-1/3logS) ->0.
|—-SP)|>S 3Pn2
при N .
Для второй суммы в (32) справедливы неравенства:
N 3 “ 1
S S - SP) |< N3 Pk 2
или при N ^да :
log NPk - 0(1) < £ (log-)С—Рк— (1 - Pk )n-— < log NPk + 0(1).
|— - NP) |< S3 Pk 2
На основании (33) и (34) имеем асимптотическое равенство
£ (log S )С—Рк— (1-Рк)N-— = log NPk + 0(1).
Отсюда при условии N ^да получаем
- £ £ (log S) С—Рк— (1-Рк )N-— = - log N+- £ log Рк + 0(1).
Вычислим четвертую сумму в правой части (28):
£ — С—Рк— (1 - Рк )N-— = £ - С—Рк— (1 - Рк)S-— + £ -с"Рк— (1 - Рк )"
—=1 - 2 1 - 2 1 |— - NPn |> N3 Рк 2 |— - NPn |< N3Рк 2
откуда при условии N ^да получаем
£ -1 С—Рк- (1 - Рк )N-— < Р{| 1к - NPk | > N3 Рк 2} < = O() 1/3) -> 0
при условии N ^да, а для второй суммы в (37) имеет место неравенство
— 2 1 -N 3 |—-SPN |< N 3 PN 2
откуда следует, что
£ 1С—Рк— (1 - Рк )S-— = O(N-1).
Из (37)-(38) следует, что при N ^да
£ N С—Рк— (1 - Рк)S-S = O(N-1),
HPT £ £ - С—Рк— (1 - Рк)"-— = 0(1).
N-(loge) £ SC—Pк— (1-Рк )N-— = NPk loge,
откуда,
откуда
loge £ £ SC-P/ (1-Pk )N-S = Sloge.
K=1 —=0
С учетом (28), (31), (36)-(40) получаем асимптотическое выражение для суммы £ Еlog 1к!
условии Pk = const, k = 1, ..., n:
n n 1 n i— n-1
£ Е log к! = Nlog N - N (Hp + log e) +—log N +— £ log P) + n logv2rc + H-log e+0(1). (41)
K=1 2 2 K=1 2
Из (25), (27) и (41) получаем асимптотическое выражение для энтропии полиноминальной схемы HN Ob..^Pn ):
hnСръ-.р)=n^logN+2 £ logрк + n-1log2ne+0(1). (42)
Окончательно для взаимной информации I (MN, En ) получаем асимптотическое равенство:
I(MN,En )=n^log2 N -1 £ log2 Pk -n^log22ne + 0(1), (43)
Выражения (14) и (43) позволяют оценить значения параметров, в частности длину выходного сообщения N, при котором обеспечиваются важные криптографические качества рассматриваемых преобразований.
Лось Алексей Борисович
Канд. техн. наук, доцент каф. компьютерной безопасности Московского института электроники и математики
Национального исследовательского университета «Высшая школа экономики»
Тел.: 8-910-477-88-27 Эл. почта: alos@hse.ru
Los A.B.
The study of information characteristics transformations substitution and permutation
In the paper the results of the research information characteristics of conversion substitution and permutation, which is the basis for building cryptographic algorithms. The obtained value of the mutual information of the input and output messages of discrete communication channel in the application of these reforms.
