О свойствах рюкзачных систем защиты информации с открытым ключом в ZP

Обозначим через Z_p множество натуральных чисел {0, 1, .., p - 1}, а через Z n_p - множество всех числовых наборов длины n с компонентами из Z _p .

Задача о рюкзаке для заданных w е N и вектора A = ( а 1 , а ₂ , ., a n ), где а . е N , i = 1. п , имеет решение в Z p , если существует решение уравнения

Ax T = w , x е / п .                 (1)

Вектор А уравнения (1) будем называть рюкзачным вектором.

Рюкзачный вектор A = (ар а2, ., an) - инъективный, если для любого натурального w уравнение (1) имеет не более одного решения. Рюкзачный вектор, у которого существуют два элемента a. = aj, i * j не является инъективным. Инъективность рюкзачного вектора позволяет говорить об однозначности восстановления исходного текста по криптограмме. Самыми простыми с точки зрения понимания и алгоритмизации инъективными рюкзачными векторами являются сверхрастущие рюкзачные векторы, для компонентов которых в Z выполняются соотношения j-1      p aj>E (Р -1) a.-j = 2... n.             (2)

i = 1

Рюкзачный вектор A = ( а 1 , а ₂ , ., а _п ) - является неубывающим, если его компоненты упорядочены по правилу а . < а, , i = 2. п . Соответственно, вектор является возрастающим, если его компоненты упорядочены по правилу а. _-1 <  а. , i = 2 п .

Определение. Вариацией вектора A = (а 1, а2, ., ап) (а.еN, i = 1 ...п) в Zp назовем вектор AA = (51,52, ., 5п), для компонентов которого выполняются соотношения j-1

5 1 = a 1 , 5 j = a j ^-E ⁽ p ^{- 1)} a . , j = 2... п .      (3)

i = 1

На основе вектора A A можно однозначно определить соответствующий ему рюкзачный вектор А в Z p :

а= 1 v 1 ’ i-1                                       i-1 .- ., a. = 5i +(Р-1)Eaj = 5.+(Р-1)Ep‘ J 5j, j=1                           j=1

i = 2 ...п.                             (4)

Обозначим через p ( p , А ) множество различных значений w , для которых уравнение (1) имеет решение. Мощность р ( р , А ) не превышает p ⁿ , так как количество различных векторов в Zⁿ_p равно p ⁿ . Значение | ц ( р , А )| достигает верхней грани, если

V x 1 , x ₂ е z p x 1 * x ₂ fi A x 1 T * A x ₂ T .        (5)

Таким образом, мощность u(p, А) достигает верхней грани, тогда и только тогда вектор A инъективен. Действи- тельно, если вектор A - инъективный, то выполняются соотношения (5) и различных значений AxT(x е znp) столько, сколько различных элементов в z"p , т. е. pn. С другой стороны, если |p(p, А)| = pn, то существует взаимнооднозначное соответствие между элементами p(p, А) и Z"p , а следовательно, имеет место единственность решения уравнения (1) для любого w е p(p, А). Из последнего следует инъективность рюкзачного вектора А.

Определение. Величину

10( p, A )l dp (A) = п1 Р "                    (6)

E ⁽ p ^{- 1)} a .

. = 1

назовем плотностью рюкзачного вектора A в Z _p .

Плотность определяет отношение мощности p ( p , А) к

n длине отрезка [0, E(p- 1)a.]. Очевидно, что Vxе zp i =1 п значение AxTе [0, E(p-1)a. ]. Таким образом, i =1

0 < dp(A) < 1. Причем для инъективных рюкзачных векторов плотность равна 1, тогда и только тогда, когда все компоненты вариации вектора A равны единице [1], а криптоана- лиз таких рюкзачных систем состоит в нахождении p.

Каждому набору x = ( a 1 , a ₂ , ., a _п ) е z" „ соответствует w x = Ax T , w x е p ( p , А ) . Выпишем последовательность ^W М A) = ⁽ w t , ’ w 1 , w 2 , ., w k ) где w i = Ax T ’ x i = ^{( a} 1 , a 2 , ., a п ), i = E a .p"^-i’ i = 0 ^^k , k = Р ⁿ -1. В случае, если вектор A не i = 1

Последовательность A W _{i (p} A ) является симметричной относительно середины и может быть определена рекурсивно относительно размерности рюкзачного вектора A .

Пусть А _п = ( а 1 , а ₂ , ., а^ ( а. е N , i = 1... п ) - рюкзачный вектор. Вектор А _{п +1} = ( а , , а ₂ , ., а _п , a _{n +1} ) получен из A _n добавлением компонента a _{n +} 1 е N . Тогда

^A Wм Лп +1)    ^{( W}i( p , Лп ) ’ ⁵ п +1 ’ ^{A W}i( p , Лп ) ’

5 п + 1’ A W,p ’ Лn)’.’ 5 п +1’ A W,p ’ Лn))’ где 5п+,, AWi(p Лn) повторяетсяp-1 раз.

Последовательность A W^_p A ) описывает расстояния между элементами последовательности W _{i (p} A ) , т. е. ее «разреженность», а следовательно, является характеристикой p ( p , А ).

Из симметричности A W^p A) следует, что любой w е W^p A) может быть представлен двумя способами nnn w = Eaj E (p - 1)a k-Eea., j=1               k=1                      i=1

где a i , P i e Z p , i = 1... n.                (7)

Лемма 1. A n = ( a 1 , a ₂ , ..., a n ) - инъективный рюкзачный вектор, где a i e N , I = 1 ...n . Вектор A n ₊₁ = ( a 1 , a ₂ , _, a n , a n ₊1 ) получен из A n добавлением компонента a _n+ 1 e N , ^A A n +i = (⁸p ⁸ - - -’ ⁵ n , ⁵ n +1 )^- вариация вектора А _п +i и 8 „ +1 > 0. Тогда A n ₊₁ = ( a 1 , a ₂, ..., a n , a n ₊₁ ) - инъективный рюкзачный вектор.

Докaзaтельство. Покажем, что V w x e u ( p, A n ₊₁ ) уравнение (1) имеет единственное решение.

Из принадлежности w x множеству u ( p, A n ₊₁ ) следует, что 3 x = ( a ₁ , a ₂, ..., a _n , a _{n +1} ) e Z p ⁺¹ , для которого выполняется w x = A n+ ₁ x ^T .

• 1.    Если a _{n+ 1} = 0, то w x e u ( p , A n ), тогда (1) имеет единственное решение в силу инъективности A _n .

• 2.    Пусть 0 <  a _{n +1} Так как 8 _{n+ 1} > 0, то любой элемент p ( p , A n ) меньше a n ₊₁ . Таким образом, существуют единственные a _{n +1} и w' x e u ( p , A n ) такие, что w x = a _{n +1} a n ₊₁ + w' x , а следовательно, уравнение (1) имеет единственное решение.

Из произвольности w x ep ( p , A n+ ₁ ) следует, что A n ₊₁ является инъективным рюкзачным вектором.

Лемма 2. A n = ( a _р a ₂ , ..., a n ) - инъективный возрастающий рюкзачный вектор, где a i e N , i = 1... n . Вектор A n ₊₁ = ( a _p a ₂ , ..., a n , a n ₊₁ ) получен из A n добавлением компонента a n ₊₁ e N , A n ₊₁ = (8_p 8 2 , _, 8 _n , 8 _{n +1} ) - вариация вектора ^A n +1 ^{и 8} n +1 < 0.

Вектор A ^ 1 = ( a 1 , a 2, ..., a n , a n+ 1 ) является инъективным возрастающим рюкзачным, если выполняется

( a„ — У ( P — 1) a, <  8 ,) & (18 ,| g W , . 3.

• ^{v n vr}     ' j n+ И ^{v 1} n +1¹ ц ( 2p- 1, An у

• j=1

Докaзaтельство. Прежде всего определим условие, при котором An+1 будет возрастающим. Так как An - возрастающий вектор, то необходимо выполнение условия n an < an+1 = У (P -1)aj + 8n+1.

j = 1

Следовательно an-У(P-1)aj< 8n+1.

j = 1

Пусть An+1 = (a p a2, ..., an, an +1) является возрастающим, но не является инъективным вектором, т е. существует юx e p(p, An+1), т е. уравнение (1) имеет не единственное решение. Из инъективности An и свойств последовательностей WAn) и Wx(p An+1) следует, что все такие юx принадле-n жат отрезкам [an+1 + k an+1, У(p-1)aj + k an+1], j=1

где k = 0... p - 2.

Также если an+1 = У(p-1)a,+6n+1 S»x 2У(p-1)aj    (8)

j = 1                                       j = 1

и для ю _х уравнение (1) имеет более одного решения, то для ю _x + ka n ₊₁ , где k = 0... p - 2, уравнение (1) также имеет более одного решения, и наоборот.

На основании вышеизложенного рассмотрим ю _х , удовлетворяющее (8), тогда ю _x ep ( p , A n ) и ю _x e p ( p , A n ₊₁ ).

Из принадлежности юx множеству ^(p, An +1) имеем следующее юx - an+1 + У в ja, - |У (p -1) a. + 8 n+11 + У Pja., j=1            V k=1                       / j=1

где P i e Z, , I = 1... n , 0 <  a < p - 1 .

Из принадлежности юx множеству u(p, An) и справедливости (7) имеем ю = УYjаj= У(p -1) ak-Уфу-aj, где у., V.e Z, i = 1...n.

• ^x j = 1              k = 1                    j = 1                    ^{1 1} p

Таким образом, имеет место равенство

У (p -1) a,-Уф naj-У (p -1) ak + 8 n+1 + Уpjaj- k=1                   j=1             k=1                             j=1

n

• - 8 _{n +1} = У ^{( p} j ⁺ %0 a j .

j = 1

Из последнего равенства следует - 8 _{n +1} e W _{i (2 p -1 An} ) . Следовательно, для инъективности A n ₊₁ необходимо 1⁸ n +11 ^g W i(2 p -1, An ) .

На множестве p ( p , A ) рюкзачного вектора A = ( a ₁ , a ₂ , ^, a n ) определим операцию сложения Ф следующим образом:

V w ₁ , w ₂ ep ( p , A ) w = w ₁ Ф w ₂ =

• . У a , a , Ф У Р , a , = У , , a„           (9)

i = 1                 i = 1                i = 1

где Y i = ( a i + P i ) mod p ; a i , P i e Z p , i = 1_ n .

Множество u ( p , A ) с операцией сложения Ф образует аддитивную конечную абелевую группу ( p ( p, A ), Ф ).

Определение . Два рюкзачных вектора A = ( a ₁ , a ₂ , ^, a n ) и B = ( b ₁ , b ₂ , _, b_k ) - векторы вариаций A A и A B которых отличаются только значением первого компонента, являются изоморфными, будем обозначать A « B , если существует изоморфизм f: p (p , A ) ^p ( p , B ).

Два рюкзачных вектора могут быть изоморфными только тогда, когда они имеют одинаковую размерность и | p ( p , A )| =| p ( p , B )|.

Рассмотрим два изоморфных рюкзачных вектора A = ( a ₁ , a ₂ , _, a n ) и B = ( b ₁ , b ₂ , _, b k ). Из (4) имеем

• a , = 8 , . a i = 8 i + ( p - 1) У p i ^- ' -р .

j = 1

b 1 = 8' 1 , b i = 8 i + ( p - 1) f p ^{i - 2} 8‘ 1 + У pi^A , i = 2_ n.

• V            j = 2           )

Назовем коэффициентом изоморфизма двух векторов A и B значение e ( A , B ) = 8' ₁ - 8 ₁ .

Тогда b 1 = 81 + £, bi=8i + (p-1)I p-^p-H8j\,

• V          j=1

b 1 = a 1 + e, bi = ai + (p - 1)pi-2e, i = 2...n, e = e(A, B) (10) и справедливо соотношение j-1

У(p -1) bi =(p -1)( a 1+ e) + У(p - D( ai+ (p -1) pi-2e) = i=1

j■ -1

У(p -1)ai+ (p - 1)e(1 + У p -2) = i=1

j - 1

= У(p -1)ai + (p -1)epJ-2.

i = 1

На основании свойств последовательностей Wi(p A) и Wi(p B) можно сделать вывод, что Wx(p B) получается из Wi(p A) «рекурсивным масштабированием» на e относительно «узловых» значений (a2, ^, an), а каждое значение a i смещается согласно (10). А последовательность A W^p B) получается из A WA) заменой всех вхождений 51 на 51 + е.

Если для рюкзачных векторов А = ( а 1, а ₂, ..., a n ), B = ( b 1, b ₂ , ..., b n ) и C = ( c 1 , c ₂ , ..., c n ) выполняется А ® B и B ® C , то А та C . Действительно, в силу биекции f ц ( р , А ) ^ц ( р , B ) и g: Ц ( Р , B ) ^Ц ( Р, C ) следует, что h = g°f: ц ( р , А ) ^ ц ( р , C ) -биективна и е ( А , C ) = е ( А , B ) + е ( B , C).

Изоморфизм рюкзачных векторов является отноше нием эквивалентности, а следовательно, множество изоморфных векторов образует класс эквивалентности. В каждом классе существует вектор, для которого коэффициент изоморфизма с любым другим вектором этого класса неотрицательный; назовем такой вектор базовым вектором класса эквивалентности.

Пусть 0 = ( 0 1 , 0 ₂ , ..., 0 n ) - базовый вектор некоторого класса эквивалентности и А = ( а _р а ₂ , ..., a n ) - произвольный элемент этого же класса, т. е. 0 ® А , е ( 0 , А ) > 0. Так как | ц ( р , А )| = | ц ( р , 0 ) |, то из определения плотности рюкзачного вектора в Z имеем следующее.

nn

|ц(р,А)| = dp(А) Е(Р-1)ai = d(0) Е(Р-1)0i= Iц(р, 0)|. p        i=1                       pi

В силу (11) выполняется следующее.

n

= d _p ( 0 ) Е( Р ^Г|0'

Из последнего выразим d p ( 0 ).

г

)

n - 2 ^Р

n

Е о -

d p ( 0 ) = d ( А )

, здесь е = е ( 0 , А );

х      i=1 7

p d ( 0 ) = d ( А ))1 + к е ( 0 , А )) , где к = —— = cont. (12)

Ео- i =1

Таким образом, базовый вектор имеет наибольшую плотность среди всех векторов его класса эквивалентности.

В случае если базовый вектор 0 является сверхрасту-щим, то вектор А также является сверхрастущим. Действительно, из (2) и (10) имеем j-1

Е ⁽ Р ^{- 1) а} * = ⁽ Р ^{- 1)(} 0 1 ^{+ е ) +} i = 1

j - 1

+ Е ( Р - 1)( 0 i + ( Р - 1) Р ^{/ - 2} е ) = i = 2

j - 1                                      j - 1

= Е ( Р - 1) 0 i + ( Р - 1) е (1 + Е Р ^{/ - 2} ) <  i = 1                                           i = 2

• < о j + ( p - 1) е p^{j - 2} = a j , е = е ( 0 , А ) .

Из последнего неравенства следует, что для любого класса эквивалентности с базовым сверхрастущим вектором существует рюкзачный вектор из данного класса для любого положительного коэффициента изоморфизма. В общем случае данное утверждение неверно. Например, для инъективного вектора (15,42,51,83) не существует изоморфного вектора в Z2 с коэффициентом изоморфизма равным 10, так как вектор (25, 52, 71, 123) не является инъективным.

Таким образом, РСЗИ с рюкзачным вектором А, можно преобразовать к эквивалентной РСЗИ с рюкзачным вектором 0, где 0 - базовый вектор класса эквивалентности вектора А. Целесообразность данного преобразования обусловливается меньшим объемом вычислений (Р, 0) и затрат памяти. Например, для хранения каждого элемента ц(2, А) сверхрастущего рюкзачного вектора А = (45,69,218,415,796,1752,3588,7375,17897,36073) необходимо 17 бит памяти, а для хранения соответствующих значений базового вектора 0 = (1,25,130,239,444, 1048,2180,4559,12265,24809) достаточно выделить по 16 бит. При больших значениях компонентов рюкзачного вектора и соответствующей размерности, объем памяти требуемой для хранения элементов ц(р, А) может превысить размеры стандартных типов языков программирования, а следовательно, потребует дополнительных процедур по хранению и выполнению операций над такими «большими» числами, что, естественно, влечет увеличение затрат по времени и памяти. В частности, для вышеуказанного примера, для хранения значений ц(2, B) сверхрастущего вектора B = (444444444,444444468,888889016, 1777778011, 3555555988, 7111112136, 14222224356, 28444448911,56888900969,11377780227), принадлежащему этому же классу эквивалентности необходимо выделять уже по 38 бит.

Теорема. Пусть А = ( а _р а ₂ , _, а _n ) - инъективный рюкзачный вектор размерности n и t ^ 0 - целое число. Тогда не существует инъективного рюкзачного вектора размерности n , посредством компонентов которого в Z _p выражаются все элементы множества { w + t\w е ц ( р , А )}.

Доказательство. Предположим, что существует инъективный рюкзачный вектор B = ( b ₁ , b ₂ , ^, b n ), т. е. { w + tIw е ц ( р , А )} с ц ( р , B ):

• 1. 1    >  0. Тогда | ц ( р , B)|i | ц ( р , А ) I + 1, так как ноль входит в ц ( р , B ), но не входит в { w +11 w е ц ( р , А )}. Но в силу инъективности векторов А и B выполняется | ы ( р , B ) | = | ц ( р , А ) |. Противоречие .

• 2.    t <  0. Так как 0 е ц ( р , А ), то t е ц ( р , B ), что противоречит b i е N , i = 1, _, n.

Таким образом, модификация РСЗИ путем изменения числового значение криптотекста на некоторую величину приводит к увеличению сложности ее криптоанализа.

Определение. Два рюкзачных вектора А = ( а ₁ , а ₂ , ^, a _n ) и B =( b ₁ , b ₂ , _, b n ) подобны, будем обозначать А = B , тогда и только тогда, когда существует взаимно однозначное отображение f: А ^ B такое, что.

• 1)    V a е Аf(Ca) = Cf(a) , где С е Z ;

• 2)    V a ‘ , a" е А выполняется f(a ‘ + a ') = f(a ') +f(a ").

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

Исследуем свойства двух подобных инъективных рюкзачных векторов А = ( а ₁ , а ₂ , ^, а _n ) и B = ( b ₁ , b ₂ , _, b n ), отображение которых определяется функцией f ( x ) = cx в некотором поле, где с - некоторая константа.

F ( a i ) = ca . = b., i = 1... n , n

V w _a е ц ( р, А ) f ( w ) = f ( Е ^a i ^{a i} ) = i = 1 nnn

= Ео- f ^{( a})= Е^и - ^{( ca}) = Ео- b i. i = 1                        i = 1                         i = 1

Плотности таких векторов связаны соотношением

I^v p ( B >1 -- A _     I ^а p ⁽ A )

dp (B) n                n                  Г nA

E(p-1)b. E(p- 1)cai clE(p- 1)ail i=1                     .=1                          i.=1

dp (A )= cdp (B).(13)

Последовательности W _{i (p} A _} и W _{i (p} B _} обладают свойствами, определенными соотношением (10). Элементы последовательностей A W A _} и A W B _} связаны следующим образом:

m i . = ch, i = 1... n , где m i e ^A W* , B ) , h i e ^A W , a_y

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

Аналитические методы основаны на методах решений уравнения (1) на основе известных значений из ц ( р , А ). Применимость данных методов основана на объемах проводимых вычислений. Верхняя граница числа решений (1) приведена в [3] и в общем случае является NP-полной задачей.

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

Методы криптоанализа открытого ключа заключаются в восстановлении рюкзачного вектора РСЗИ по вектору открытого ключа. В частности, для двух сверхрасту-щих рюкзачных векторов, полученных один из другого посредством сильного модульного умножения, А. Шамиром предложен алгоритм нахождения рюкзачного вектора A РСЗИ, если известен вектор B [2].

На основе вышеописанных свойств рюкзачных векторов можно сформулировать следующие выводы:

• -    криптоанализ РСЗИ можно проводить не только на основе статистики значений элементов криптотекстов, но и на распределении значений. В силу того, что вероятность появлений последовательностей эле ме нтов A W^ A ) рюкзачного вектора A = ( а ₁ , а ₂ , ..., a n ) в Z_p есть величина постоянная для заданной размерности n , то таблица вероятностей рассчитывается на этапе предварительной подготовки криптоанализа. Анализ криптотекстов проводится на основе разностей между парами значений его элементов. В этом случае существенным является не объем известных криптотекстов, а количество различных значений его элементов. Построение инъективного рюкзачного вектора базируется на основе свойств W A ) и Лемме 1;

• -    применимость статистических методов анализа криптотекстов базируется на его объеме. Поэтому при малых объемах такой информации данные методы практически не применимы. Модификация РСЗИ с одним рюкзачным вектором в систему с динамически генерируемыми рюкзачными векторами [4; 5] приводит к практической неприменимости статистических методов анализа криптотекстов;

• -    для повышения криптостойкости классических систем защиты информации с открытым ключом и с рюкзаком необходимо использовать неизоморфные и неподобные рюкзачные векторы, а также изменять значения выходов блока шифрования РСЗИ на значение некоторой константы. Например, видоизменив классическую систему защиты информации с открытым ключом и с рюкзаком на основе секретного ключа ( m , t ) [2], можно существенно повысить криптостойкость системы.

Рассмотрим простой пример. Пусть A = (2, 5,6) - инъективный возрастающий рюкзачный вектор, перед определением открытого ключа - вектора B , применим фун-кцию fx ) = x ² - х к элементам вектора А и, учитывая, что f (2) = 2, f( 5) = 20, f (6) = 30, получим А' = (2,20,30). Используя пару m = 220 и t = 17 как секретный ключ [1 ],сильным модульным умножением [1] получим открытый ключ B = (34,120, 70). Криптоанализ вектора B согласно алгоритма А. Шамира может привести только к получению сверхрастущего вектора А' [2], в котором шифротекст w = 7 недопустим. Таким образом, использование в качестве секретного ключа ( m , t , f(х )) приводит к тому, что известные методы анализа системы защиты информации с открытым ключом, в частности, использующие сильное модульное умножение, не применимы или требуют дополнительных затрат по поиску преобразования f ( x ).