Rising of efficiency of enciphering on the basis of summation of products

Full Text

Сначала напомним, что какой-либо фактор скрытности повышает собственную эффективность при создании того или иного шифра, если в пределах своего изменения его влияние на результат преобразования, производимого с составленным шифровальщиком математическим выражением M E, соответственно увеличивается [1]. Целью настоящей статьи является описание нескольких разновидностей шифра на основе сумм со слагаемыми - произведениями, свободные компоненты которых имеют сомножители показателей и оснований степеней, принадлежащие числовому множеству R. В качестве основного математического выражения примем [2, 3] p Φ= bl cl , (1) l=1 ISSN: 2310-7081 (online), 1991-8615 (print); doi: http://dx.doi.org/10.14498/vsgtu1316 © 2014 Самарский государственный технический университет. Образец цитирования: А. И. Н и к о н о в, “Повышение эффективности шифрования на основе суммирования произведений” // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2014. № 2 (35). С. 199-207. 199 А. И. Н и к о н о в где bl - весовые коэффициенты - компоненты произведений M E, выражающие шифруемые буквы первичного алфавита, bl ∈ N; cl ∈ R+ - свободные от шифруемых букв множители - компоненты произведений M E, образующие основную (cl , l ∈ Ip = 1, . . . , p) и остаточную (cl , l ∈ 1, . . . , p - g, g ∈ 1, . . . , p - 1) конечные последовательности; p - объём передаваемой посылки шифротекста, то есть общее количество весовых коэффициентов в посылке, причем p 2. Математическое выражение, дополняющее основное выражение (1) и служащее инструментом определения условия выделимости весовых коэффициентов рассматриваемого шифра [1, 4], имеет вид относительного суммарного остатка (ОСО) υ ϕ(υ) = l=1 bl cl , cυ+1 υ = p - g, g = 1, . . . , p - 1. В настоящей статье будут рассмотрены следующие типовые случаи задания функциональных последовательностей [5, 6] со свободными компонентами, где эти компоненты выступают: как одинаковые степени членов арифметической прогрессии, в качестве оснований которых берутся произведения натуральных и действительных чисел (верхний индекс члена этой последовательности - а); как члены геометрической прогрессии, в качестве степенных показателей которых также берутся произведения указанного вида (верхний индекс члена этой последовательности - г); как члены последовательности комбинированного типа, в качестве сомножителей степенных показателей и оснований которых берутся одинаковые натуральные числа, а другие их сомножители представляют собой действительные числа (верхний индекс члена этой последовательности - к ). Общее представление рассматриваемых типовых случаев имеет следующий вид: υ ϕm (υ) = bm l=1 (l1 ψ)l2 ν ((υ1 + 1)ψ)(υ2 +1)ν ν ∈ R+ \ [0, 1), ; l1 , l2 ∈ {l}, ψ ∈ R+ \ [0, 1]; υ1 , υ2 ∈ {0, υ}; bm = max bl > 1. Выявление интервала выделимости весовых коэффициентов, в пределах которого значения его точечных элементов имеют одинаковый знак либо нулевое значение, а протяженность этого интервала снижена сравнительно с единицей [1, 4], предполагает получение соответствующих граничных значений параметров формулы ОСО. То есть имеются в виду значения ОСО такие, что 0 ϕm (υ) < 1. (2) При этом первоначально граничное значение числа свободных множителей из последовательности ОСО, отвечающее длине участка (2), может задаваться исходя из каких-либо предметных соображений. Например, это может быть длина используемого алфавита (bl , max l = p). Более подробное выражение каждого из перечисленных выше типовых случаев задания ОСО может быть представлено таким образом: - случай последовательности (ϕa (υ)): l1 = l, l2 = 1, υ1 = υ, υ2 = 0; m - случай последовательности (ϕг (υ)): l1 = l, l2 = l, υ1 = 0, υ2 = υ; m 200 Повышение эффективности шифрования на основе суммирования произведений - случай последовательности (ϕк (υ)): l1 = l2 = l, υ1 = υ2 = υ. m В пределах каждого из перечисленных случаев имеем три подслучая со следующим сочетанием параметров ν, ψ: 1) ν = constν , ψ = constψ ; 2) ν = varν , ψ = constψ ; 3) ν = constν , ψ = varψ . Далее мы будем рассматривать свойства исследуемых относительных суммарных остатков, заключающиеся в определении направленности изменений их величин при изменении аргументов υ, ν, ψ. Указанные изменения величины ОСО в случае исследования аргумента υ будут иметь дискретный, а в случаях исследования аргументов ν, ψ - непрерывный характер. Рассмотрим сначала искомые свойства суммарных остатков нашего шифра, выражаемые - в относительной форме - как одинаковые степени членов арифметической прогрессии. Тогда, использовав обозначение υg = υ + 1 > l, при изменении соответствующей величины ОСО можем записать: υ ϕa (υ) m = bm l=1 υ+1 ϕa (υg ) = bm m l=1 (lψ)ν ((υg + 1)ψ)ν = bm (lψ)ν = (υg ψ)ν υ δϕa (υ), ml l=1 1 + (υg + 1)ν υ (l + 1)ν (υg + 1)ν l=1 υ δϕa (υg ). ml = l=0 В зависимости от общего числа веcовых коэффициентов p будем иметь следующую разность (случай а, подслучай 1), относящуюся к составным частям рассматриваемой последовательности: ∆ (δϕa (υ)) = δϕa (υg ) - δϕa (υ), ml ml ml l = 1, . . . , υ, в которой δϕa (υ) = ml bm lν , ν υg δϕa (υg ) = ml bm (l + 1)ν . (υg + 1)ν Следовательно, ∆ (δϕa (υ)) = bm ml ((l + 1)υg )ν - (l(υg + 1))ν . ν (υg + 1)ν υg Поскольку lυg + υg > lυg + l и, кроме того, δϕa 0 (υg ) = m bm > 0, (υg + 1)ν получаем суммарно ϕa (υg ) > ϕa (υ). Таким образом, с увеличением числа υ m m или p общая величина ОСО тоже возрастает. При изменении значений сомножителей показателя степени и затем - сомножителя её основания получим следующие выражения, содержащие соответствующие производные (случай а, подслучаи 2 и 3): (δϕa (υ))ν = ml d d (δϕa (υ)) = bm ml dν dν lν ν υg = bm lν (ln l - ln υg ) < 0, ν υg l = 1, . . . , υ; 201 А. И. Н и к о н о в υ (ϕa (υ))ν m (δϕa (υ))ν < 0; ml = l=1 d d (δϕa (υ))ψ = (δϕa (υ)) = bm ml ml dψ dψ lν ν υg = 0, l = 1, . . . , υ; υ (ϕa (υ))ψ m (δϕa )ψ = 0. ml = l=1 Итак, в случае а при увеличении параметра ν члены функциональной последовательности (ϕa (υ)) уменьшаются, а при увеличении параметра ψ они m остаются неизменными. Вычисление ОСО в данном случае может производиться, в частности, по методике комбинированного представления суммы взвешенных одинаковых степеней [1, 2, 7]. Функциональную последовательность для случая, индексируемого символом г, рассмотрим исходя из того, что известна формула её члена [1]: υ ϕг (υ) m = bm l=1 ψ lν bm ψ υν - 1 = ν · . ψ υg ν ψ -1 ψ υν Разность между соседними членами рассматриваемой последовательности (случай г, подслучай 1) выглядит следующим образом: ∆ϕг (υ) = ϕг (υg ) - ϕг (υ) = m m m bm ν -1 ψ ψ υg ν - 1 ψ υν - 1 - ψ υg ν ψ υν = bm > 0. ψ υg ν Производная, определяемая в целях указания характера возрастания или убывания уровня ϕг (υ) в зависимости от соответствующих изменений параm метра ν (случай г, подслучай 2), имеет вид (ϕг (υ))ν = m d d г (ϕm (υ)) = dν dν bm 1 1 - υν = -1 ψ bm ln ψ = ν (-ψ ν (ψ υν - 1) + υ(ψ ν - 1)) . (ψ - 1)2 ψ υν ψν Последний сомножитель данного выражения, заключенный в скобки, разложим с использованием формулы бинома [8, 9]: - ψ ν ((ψ ν - 1 + 1)υ - 1) + υ(ψ ν - 1) = = -ψ ν (ψ - 1)υ + υ(ψ ν - 1)υ-1 + . . . + υ(ψ ν - 1) + 1 - 1 + υ(ψ ν - 1). Поскольку в области задания наших значений ν, ψ имеем -(ψ ν - 1) < 0, получаем: (ϕг (υ))ν < 0. m Производная, определяемая с той же целью, что и рассмотренная относительно значения ϕг (υ) в зависимости от соответствующих изменений паm раметра ψ (случай г, подслучай 3), может быть найдена как 202 Повышение эффективности шифрования на основе суммирования произведений (ϕг (υ))ψ = m d d (ϕг (υ)) = m dψ dψ 1 bm 1 - υν = -1 ψ bm νψ -1 = ν (-ψ ν (ψ υν - 1) + υ(ψ ν - 1)) . (ψ - 1)2 ψ υν ψν Но выше было доказано, что член -ψ ν (ψ υν - 1) + υ(ψ ν - 1) в пределах заданных ν, ψ всегда имеет значение, меньшее нуля, и поэтому можно заключить, что (ϕг (υ))ψ < 0. m К таким же результатам - по знакам исследуемых разности и производных для случая г - можно прийти, рассматривая разновидность задания той же функциональной последовательности по её отдельным составным частям, как это было сделано в случае а. Итак, при увеличении числа υ (или p) в случае г общая величина ОСО тоже возрастает, а при увеличении любого из параметров ν, ψ она уменьшается. Поступим аналогично с ОСО, содержащим слагаемые комбинированного вида степеней арифметической прогрессии и геометрической прогрессии (этот случай индексируется символом к ), и определим соседние члены последовательности относительных суммарных остатков: υ ϕk (υ) = bm m l=1 (lψ)lν = (υg ψ)υg ν υ+1 ϕk (υ + 1) = bm m l=1 = bm ψν ((υg + 1)ψ)(υg +1)ν υ δϕk (υ), ml l=1 (lψ)lν = ((υg + 1)ψ)(υg +1)ν υ l=1 ((l + 1)ψ)(l+1)ν ((υg + 1)ψ)(υg +1)ν + = υ = δϕk (υg ) + m0 δϕk (υg ), ml l=1 а также разность соответствующих составных частей членов данной последовательности δϕк (υg ) - δϕк (υ) = bψ (l) ml ml bψ (l) = ((l + 1)ν )l+1 ((υg + 1)ν )υg +1 - ν υ (lν )l υg g bm ψ (l+1)ν llν = δϕк (υg )(ψl)lν ; m0 ((υg + 1)ψ)(υg +1)ν ; l = 1, . . . , υ. Пользуясь методом математической индукции, докажем следующее неравенство: ((l + 1)ν )l+1 ((υg + 1)ν )υg +1 < . (3) ν (υg )υg (lν )l Преобразуя (3) в пределах задания наших значений ν, ψ, легко получаем 203 А. И. Н и к о н о в эквивалентное ему неравенство (l + 1)l+1 (υg + 1)υg +1 < ; υ ll υg g (4) именно оно и будет доказано ниже. Первый индукционный шаг выглядит применительно к выражению (4) таким образом: l=1: gmax 22 < (υg min + 1)υg min +1 , υ υg g min min υg min = υmin + 1 = p - gmax + 1, = p - 1 ⇒ υmin = 1, υg min = 2, υg min + 1 = 3. Следовательно, 22 < 33 /22 ⇒ 42 < 33 . Но если неравенство (4) с такими значениями l = 1 и υg = υg min верно, то оно останется справедливым и для любой пары чисел l = 1, υg υg min : l=1: 22 < (υg + 1)υg +1 . υ υg g (5) Переходя к выполнению второго индукционного шага, заметим, что с допущением правильности (4) при l 2 (υ l, υg > l) должна выполняться следующая система неравенств:   (υg + 1)υg +1 ll   , <  υ  (l - 1)l-1 υg g  ............  2 υg +1 2   < (υg + 1)  .  1 υg 1 υg Перемножая левые и правые части (4) и этой системы, имеем: (l + 1)l+1 (υg + 1)(υg +1)l < . υ l 11 υg g Применяя к правой части данного неравенства биномиальное выражение и учитывая, что l + 1 υg , получаем: υ l (υg +1)l (l + 1)(l + 1)l υg g < υg (υg +1)l-1 + (υg + 1)lυg = (υ +1)l υg g (l + ... = (υg +1)l-1 + 1) + lυg + . . . . (6) Итак, правая часть неравенства (6) оказывается больше левой, а отсюда следует и справедливость неравенства (3). Тогда имеем: 204 Повышение эффективности шифрования на основе суммирования произведений υ (ϕк (υg ) m - δϕк (υg )) m0 - ϕк (υ) m (δϕк (ϕg ) - δϕк (ϕ)) = ml ml = l=1 υ = (l + 1)(l+1)ν (υg + 1)(υg +1)ν - υ ν llν υg g bψ (l) l=1 < 0. (7) Урегулируем вопрос с членом δϕк (υg ) = m0 bm ψ ν , ((υg + 1)ψ)(υg +1)ν (8) для чего рассмотрим составную часть из (7), в сущности, такую же, что и на первом индукционном шаге (5), только с учётом сомножителя δϕк (υg ). А m0 именно, используем применительно к составной части из (7) при l = 1 запись ряда Ньютона [6, 10]: δϕк (υg ) - δϕк (υ) = δϕк (υg ) ψ ν · 22 - m1 m1 m0 (υg +1)ν -ψ ν υg (υg +1)ν-1 + (υg + 1)νυg + ... . (9) Прибавим сюда член (8), в результате чего нетрудно убедиться, что знак модифицированного таким образом выражения (9) остаётся отрицательным. Учитывая затем остальные слагаемые левой части неравенства (7), получаем: ϕк (υg ) - ϕк (υ) < 0. m m Это означает, что с увеличением параметра υ (или p) значение произвольного члена последовательности (ϕк (υ)), в данном случае к (подслучай 1), m уменьшается. Теперь определим производную составной части произвольного члена функциональной последовательности (ϕк (υ)), а также самого данного члена по m переменной ν (случай к, подслучай 2): (δϕк (υ))ν = ml = d d (δϕк (υ)) = bm ml dν dν bm llν υg ν (υg -l)ν υg ψ (lψ)lν (υg ψ)υg ν = ln(lψ)l - ln(υg ψ)υg < 0; υ (ϕк (υ))ν = m (δϕк (υ))ν < 0. ml l=1 Поступая аналогичным образом в отношении составной части и члена в целом той же функциональной последовательности, получаем следующий вид соответствующих производных по переменной ψ (случай к, подслучай 3): (δϕк (υ))ψ = ml d d (δϕк (υ)) = bm ml dψ dψ (lψ)lν (υg ψ)υg ν = 205 А. И. Н и к о н о в = (ϕк (υ))ψ m bm νllν (l - υg ) < 0; υ ν υg g ψ (υg -l)ν+1 d = (ϕк (υ)) = dψ m υ (δϕк (υ))ψ < 0. ml l=1 Как видим, при увеличении любого из параметров ν, ψ в рассаматриваемом случае (подслучаи 2, 3) уровень произвольного члена функциональной последовательности ϕк (υ) уменьшается. m Приведенные выводы по характеру изменения свободных компонентов рассматриваемого шифра могут быть полезны при выборе основы используемого математического выражения M E, когда оказывается необходимым привести его параметры в соответствие с требуемым числом элементов шифра, участвующих в формировании данной шифрованной посылки. В заключение обратим внимание на параметр шифра, также связанный с его эффективностью и определяемый границей используемой памяти. То есть несколько исследованных выше разновидностей M E потребует для своей реализации, при равном количестве элементов шифра и отсутствии введения соответствующих дополнительных множителей, различных границ используемой памяти и, соответственно, различной плотности размещения данных элементов. Здесь надо учитывать, что указанное размещение, представляющее рассматриваемый шифр, может вступить в противоречие с техническимим возможностями практических средств его реализации.

About the authors

Alexander I Nikonov

Samara State Technical University

Email: nikonovai@mail.ru
(Dr. Sci. (Techn.)), Professor, Dept. of Electronic Systems and Information Security 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

References

Supplementary files