Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

281

конкретной реализации со —( /, а ) случайной системы (4.1); О(у) -

множество реализаций заведомо совместной системы (4.1) с истинным

решением х = х(у}, ?}(]) - число решений заведомо совместной системы с

истинным решением х(у).

Очевидно, что

П - 0 П , .	О ( П . п П , ) . 0 ,	1=	У=1
/=0	/=1

Определение 4.1. Назовем случайную систему уравнений с независимыми частями и заведомо совместную случайную систему уравнений

вида(5) согласованными, если для любого 1 = 1,...,Я

1)а , = П ( / ) ;

2)р ( / \ = р{со)1 ), со = ( / , /(* (/))) е О ,;

3)распределение Т]{г) не зависит от номера г.

Лемма 4.1. Если правая часть случайной системы уравнений с независимыми частями (5) имеет равномерное распределение на множестве допустимых правых частей, то первое и второе условия согласованности выполняются.

ДОКАЗАТЕЛЬСТВО. В элементарное событие со включаются

конкретная левая часть системы / =

и конкретная правая часть

системы а = {ах,...,а, ). Поэтому для случайной системы с независимыми

частями

р(со) = р (/)р (а )

а для заведомо совместной системы с истинным решением х(у) и а = /(^ (у))

вероятность этого события*равна вероятности появления левой части р (у )9так

как правая часть однозначно определяется левой частью.

Первое условие согласованности выполняется, поскольку в случайной системе правые части могут принимать все возможные значения. Для второго

282

условия находим, учитывая, что Г2, содержит ровно одно элементарное

событие® = ( /,а ) при каждой левой части / :

/Ф ,) =2^(/МЛ*М))= <Г'\

/

р (со )/р (а 1) = р ( / )р (а )/

=р ( / )

Лемма доказана.

Замечание. Лемма 4.1 верна и при более слабом ограничении на распределение правых частей. Действительно, для выполнения первого условия согласованности С1. =П(/) достаточно потребовать выполнения неравенства

р ( /( * Ш > °

при р ( / ) > 0 >

а второе условие согласованности

М /(* 0 )))= р (п Д р { 7 )> 0 ,

указывает на одинаковые значения вероятности появления правых частей для систем уравнений из

Приведем несколько простейших примеров согласованности случайной

системы и заведомо совместной системы.
а)	Линейная система уравнений над полем СГ(#) с независимыми и
равномерно распределенными в СР(^) коэффициентами и правыми частями:
	а д + - +а,„х„ =Ъп 1 =1,...,*	(6)
Покажем, что случайная система (6) согласована с заведомо совместной
системой
	аахх+--- + а д , =Ъ, = а пх° +--- + аых°п, 1 = 1,...,/,	(7)

коэффициенты которой имеют такое же распределение, как и в случайной системе (6).

Действительно, в силу равновероятности правых частей линейных уравнений системы (6) по лемме 4.1 выполнены первое и второе условия согласованности. Далее, число решений заведомо совместной системы (7) равно числу решений соответствующей однородной системы уравнений

283

апУ\ + Л + атУп = 0, 1 =

у( = *,. +Х,°, 1= 1,..., и,

или, что то же самое, числу решений заведомо совместной системы (7) с истинным решением х° = (0,0,...,0)

Следовательно, распределение числа решений системы (7) не зависит от вида истинного решения, и системы (6) и (7) согласованны.

б) Рассмотрим систему уравнений (5) с целочисленными неизвестными

' хх,...,х„ еАГ,|лг| = ^г:
<р1(хх,...,хп) = с1,	/ = \,..Х.	(8)

Пусть функции (рх,...,(Р[ - независимые случайные величины, имеющие

равномерное распределение на множестве всех возможных.функций, отображающих множество И" в множество М , |М| = т . Всего таких функций

тч . Правая часть с не зависит от левой части Тр .
Соответствующая заведомо совместная система имеет вид
^/(х1,...,хя) = ^,.(х1,...,хи0)1 / = 1,..7.	' (9)

Так как случайные функции имеют равномерное распределение, то число решений одного уравнения из системы (9) не зависит от истинного решения

х°. В силу независимости выбора уравнений этот факт имеет место и для всей системы уравнений.

Следовательно, если в случайной системе (8) с,,...,с, - независимые

случайные величины, имеющие равномерное распределение на множестве М, то системы уравнений (8) и (9) согласованны.

в) Псевдобулева система уравнений

/.(х ) = а,., I =

с линейным псевдобулевым ограничением на неизвестные

х{ +л;2 +Л + х я =п,

284

Пусть в указанной системе уравнений

где 5, = (5,4 |Г) при любом 7 = 1,...,7 есть выборка без возвращения объема г

из совокупности {1,2 все выборки независимы и равновероятны.

Для заведомо совместных систем этого вида с истинным решением л;0, удовлетворяющим условию л:, + х2 + А + х„ = п, , распределение числа

решений не зависит от л:0, что следует из симметрии и равновероятности выборок неизвестных. Поэтому случайная система и заведомо совместная система согласованны при выполнении условий леммы 4.1.

Связь между распределениями чисел решений согласованных случайных и заведомо совместных случайных систем уравнений.

Теорема 4.1> Если случайная система уравнений с независимыми частями и заведомо совместная случайная система уравнений согласованны, то между распределениями их чисел решений % и Т] существует следующая

связь:

(10)

ДОКАЗАТЕЛЬСТВО. Представим случайную величину 4 в виде суммы

индикаторов

7=1

В силу согласованности систем уравнений

285

е (Г '7 * = 1 )= Е 7 * ''

Отсюда следует основное соотношение для моментов случайных величин % и г/

Е^к =Е%Ег|к-1,			к > 1.
Очевидно,
	к>0			к>О
Но в силу формулы Е^к = Е^Ег^”1,		к > 1 находим
ЕЕ^-1+вф;в**^]А.
*>о	К-				К- у
Следовательно,
					Л
2 р {<Г = Ф * = 1 + Е # }				Е	Р!7 = Ф кг йг.
*>0			о \
В это равенство введем новые переменные х = е \ у - е 1. Получим
соотношение между производящими функциями
2 р { # = *}** = 1+ щ	\ [ Х р Ь	= *Ь>“		V	- 1 + Е ^ у р{7 = к } ^ 2 .
к>0	1 V * 2 1			)	Ш	К
Сравнивая коэффициенты при одинаковых степенях х, приходим к
формулам (10). Теорема доказана.
Сл е д с т в и е 4.1. Для вероятности			совместности случайной			системы

уравнений с независимыми частями имеет место оценка

РЙ>0} = Е ^ М ( Е 7 -1)1

где 0 < в < 1.

ДОКАЗАТЕЛЬСТВО. Из формул (10) следует:

Р{^ > 0} = Е ^ Т - ^ =-^ < Е$

тк

286

Очевидно, что Р\т] >\}<Ет]-\. Отсюда получаем неравенство

Р{^>0}>Е^Р{/7 = 1 }> Е Й 2 -Е 7 ) из которого следует требуемое равенство.

Лемма 4.2. Пусть случайная система уравнений и заведомо совместная система уравнений согласованны. Тогда Р{^ > 1} (вероятность совместности случайной системы) и Р{^ = 1} (вероятность единственности решения заведомо совместной системы) связаны следующими неравенствами и соотношениями:

Р{<Г>1} = Е#[1 —0(1-Р{/7 = 1})1 \ < в < \

Р{^ > 1}< Е<^ 4-+-	^
	12

ДОКАЗАТЕЛЬСТВО. Из формул (10) находим

Р { ^ 1 } = Е 5 Х р {п = < к>1

< ЕЁ,

Нижняя оценка для Р{^ > 1} очевидна:

Р{<Г > 1) > Р{^ = 1} = Е^Р{^ = 1) = Е ^ 1 - (1 - Р{»; = 1})]

Докажем верхнюю оценку для Р{<^ > 1}. Легко проверить, что

	=	и Р{7 = 2}	1-Р{7 = 1}-Р{»7 = 2}.,	2 + 4Р{|/ = 1}+Р{|7=2)
&	*	2	3	6

Е 77> Р{/7 = 1}+ 2Р{?7 = 2 }, Р{7 = 2 }< - ^ ^ — — —

287

Отсюда и следует верхняя оценка для Р{<^ > 1}, приведенная в утверждениии леммы 4.2.

Лемма 4.3. Для согласованных случайной системы уравнений и заведомо совместной системы уравнений выполняется неравенство

Р{# > 1} >

Е г)

ДОКАЗАТЕЛЬСТВО. Рассмотрим выражение
	*>1 к	/>1
Неравенство Р{<^ > 1} >	следует из соотношения
	Е?7
5 = Х И 7? = *}]2 + 2 р {»7 = *'}р {7 = у)		> 2 рЬ =у} = 1.
к>1	!</<у

так как 2 + д-1 > 2 при 2 > 0.

Найдем условное распределение % при условии %> 1. Очевидно, что

Р{^=Л /#>1} = р & = * } , к * 1;

1 -Р {^ = 0 }

Поэтому из (10) следует, что

Л	= Р ^ . ^ > 1 } = Е ( ^ > 1 ) 1 % Д * > 1 .
	к
П р и А :< Е (^ > 1 )
	Л >Р{т7 = ^},

Р к < р{*7 = ^}-

(

288

Следовательно, по числу решений можно статистически различать заве­ домо совместную систему и случайную систему, имеющую решения.

В заключение отметим, что связь (10) имеет место и в том тривиальном

случае, когда все индикаторы	, независимы и одинаково распределены:
Р{&=1 } = Л	Р { ё = 0 } = 1 - р , .’ =
и случайная величина т} имеет такое же распределение, как и
6 + Л + ^ _ 1+ 1.
Действительно, для к > 1 в этом случае
?{4 = к } = с \ . р к( \- р У '- к = я " р \ с ™ . у - ' ( \ - Р у - ‘ = е ^ ^ .

5. Системы уравнений с искаженной правой частью.

Рассмотрим систему булевых уравнений (1)

/ ( х) = Ь ,	(11)
в которой Ь = а Ф с ,а = /(х°)> ^ =	есть вектор ошибок, не

зависящий от левой и правой частей исходной системы уравнений. Такие системы уравнений (5.1) называются системами уравнений с искаженной

правой частью. Обычно координаты вектора ошибок			, - независимые
случайные величины и
р к	= 1) = Рг <	* = Ъ -» * -	(12)
Система (11) при р { =	I = 1,...,/, является случайной системой
уравнений с независимыми частями, а при р ( = 0		(/ = 1,...,?) - заведомо
совместной системой.

Ставится задача статистической оценки вектора х° по реализации системы (11).

Каждому вектору х соответствует вектор ошибок

289

который определяется подстановкой вектора х в левую часть системы (11). Вероятность появления такого вектора ошибок при условии (12) есть

р к	=	= е((х)}= П р !'(~х)0 - Р г Г*,(лс) •
		/=1
Если вектор х ° , по которому строится правая часть (11), случаен, не
зависит от /	и е и имеет равномерное распределение на множестве

возможных решений X, то вектор х*, удовлетворяющий условию тахР {? = ?(х)} = р{? = ?(х*)}

естественно считать максимально правдоподобным.

Такой способ построения оценки вектора х° называется методом максимума правдоподобия (ММП). В теории кодирования аналогичная процедура, применяемая при р ( = р ,г = 1,...,/ , для декодирования блоковых кодов, задаваемых преобразованием

(х,,..., х„) -» (/, (х,,..., х„),...,/, (х,,..., хл)), называетсяметодом декодирования в ближайшее кодовое слово.

Основной задачей анализа систем уравнений с искаженной правой частью является оценка величины р|х* = х 0}, которая характеризует надежность метода максимума правдоподобия. Приведем оценки р{х* = х° } для случаев фиксированной и случайной левых частей системы.

Если р 1= р , 1 = 1,...,?, то каждому вектору х соответствует «невязка»

Ф )= Е *,•(*)>

/=1

т. е. число уравнений в системе (11) которым не удовлетворяет вектор х . При этом для истинного решения

8 (х ° )= е { +Л + е п

ЮЗак.5

290

где ех,...,е( - биномиально распределенные случайные величины с Р{^( =1} = /7 = 1 - Р{^( = О}, / = 1,...,/, а для ложного решения х Фх°

8 (х) = Е	е, (х) = Е [ / (х) 0 Л (*°)0 1
/= 1	1=1

Таким образом, если левая часть системы (11) фиксированна, то

Р Ь ( * ) = 1 } - { '	ПРИ
[ 1 - / ?	при / , [ х ) * / , [ х )

Во втором случае при случайном выборе функций в системе уравнений

р{г,(г )= 1 } = р { /;(г )ф /;(г “) ® е, = 1 } = |+ ( 1 - 2 ^ р ( /; ( г ) * / ,( ж ', ) ) - 2

В силу того, что

5'(х*)= тт5'(х),

вероятность ошибки при решении задачи ММП можно оценить следующим образом:

р{х* ^х°}<У^р|б(х°)=/, ш|П)5(х)</|<тц р{5(х0)>с)+ ^Р{5’(х)<с} (13)

Теорема 5.1. Пусть р. = р < 1/2, / = 1,...,? , и выполняются следующие условия:

1) функции	независимо выбираются из некоторого мцожества
функций Ф ;

2)р[/].(х)^ / . (х°)}> р для любого х ^ х ° , 0 < / ? < 1 ;

3)если 77 —» со, |х| —» со, и

, р* = р + р ( \- 2 р ) ,

У