Финитные функции в алгоритмах криптографии | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/6

Финитные функции в алгоритмах криптографии

Предлагается применять ортогональные финитные функции (ОФФ) в алгоритмах криптографии в том случае, когда ОФФ не обладают свойством ортогональности. При этом последовательность сеточных наборов ОФФ, утративших свойство ортогональности, по-прежнему является базисом в пространстве Соболева. Потеря свойства ортогональности придает ОФФ новое свойство - множественность вариантов задания параметра ОФФ, что позволяет создавать дополнительные ключи в криптографических алгоритмах. Предложен алгоритм шифрования, основанный на использовании ОФФ, утративших свойство ортогональности. Использование ОФФ, не имеющих свойства ортогональности, в алгоритмах криптографии предложено В. Л. Леонтьевым. Реализация алгоритма выполнена в основном А. В. Щуренко.

Compactly supported functions in cryptography algorithms.pdf В работе предлагается алгоритм симметричного шифрования, основанный на применении ортогональных финитных функций. Теория ОФФ-базисов и её применение в алгоритмах численных методов изложены в [1-3]. Основная идея предлагаемого алгоритма заключается в аппроксимации многочлена, содержащего в себе исходное сообщение, с использованием функций ОФФ-базиса, не обладающих свойствами ортогональности. После представления блока информации в виде многочлена проводится его аппроксимация с помощью ОФФ-базиса в выбранных узлах сетки, затем вычисляются значения ОФФ-аппроксимации с учётом произвольно заданного значения ключа, после чего результат шифрования представляется в виде блока ОФФ-аппроксимации. Информация о координатах точек, в которых проводилась аппроксимация, и о дополнительном ключе позволяет восстановить исходный многочлен и содержащееся в нём сообщение. Операции по получению коэффициентов аппроксимации проводятся в кольце многочленов степени, не превосходящей n, над кольцом наименьших неотрицательных вычетов Zn , элементы которого образуют полную систему вычетов по модулю N. При этом n - чётное число, равное длине сообщения, а N - простое число. Сообщение длины, большей n, при шифровании следует разбить на блоки длины n. Количество функций в используемой части ОФФ-базиса должно быть не меньше n. Для выполнения этого требования на равномерной сетке x1 < x2 < ... < xj, l ^ n, с целыми неотрицательными Xj и шагом h задаётся набор t = (t1, t2,... , tn), состоящий из n точек tj = (хг,уг), где все Xj, i = 1,... , n, попарно различны. При этом все y принадлежат Zn , но их точные значения вычисляются уже в процессе шифрования. Далее задаётся соответствующий набор ОФФ f = (f1, f2,..., fn). В качестве примера берутся ОФФ, являющиеся частным случаем [1, с. 11]. При использовании равномерной сетки с шагом h каждому узлу сетки Xj ставится в соответствие сеточная функция вида fi(x) = (х - Xj-1)/h, х G [xj-1,Xj-1 + h1] и [xj-1 + h2,Xj], -а + 2(ah + h^x*- + dn - x)/(h(h2 - h^)), x G [xj_1 + hbXj_1 + dn], -а + 2(ah + h2)(x - Xj_1 - dn)/(h(h2 - h1)), x G [xj_1 + dn,Xj_1 + h2], (xj+1 - x)/h, x G [xj,xj + h1] U [xj + h2,Xj+1], (1) в + 2(eh + h1 - h)(x - Xj - dn)/(h(h2 - h1)), x G [xj + hbXj + dn], в + 2(eh + h2 - h)(xj + dn - x)/(h(h2 - h1)), x G [xj + dn,x» + h2], 0, x G [xj-1, Xj+1], где dn = (h1 + h2)/2; h1 = H1h; h2 = H2h; 0 ^ h1 < h2 ^ h; Н1,Н2,а,в - некоторые константы; а > 0, в > 1. Каждая f представляет собой сумму В-сплайна первой степени с конечным носителем [xj_1,Xj+1] и двух В-сплайнов первой степени, взятых с разными знаками, с более компактными по сравнению с [xj_1,Xj+1] конечными носителями. За счёт двух дополнительных В-сплайнов и с помощью выбора значений a,e,h1, h2 достигается выполнение условий ортогональности: (fj,fj) = 0 для всех i = j. Функции fj(x), i = 1,... , n, линейно независимы, а их аппроксимирующие свойства представлены следующей теоремой. Теорема 1 [1]. Если u(x) G W2(R) и H + Я2 = 1 (hx + h2 = h), а a = в - 1, то n существует функция uh = £ af G Mn (aj - некоторые постоянные), такая, что j=1 < ||u - uh||L2(R) ^ ch||u||wl (R), £ |aj|2 ^ c1||u| 2 |L2(R)' j=1 где Mn - линейная оболочка fj(x); постоянные c и c1 не зависят от u и h; W2 - функциональные пространства Соболева; L2 = W0 Основная идея алгоритма состоит в том, чтобы, отказавшись от выполнения условия [1] ортогональности финитных функций, имеющего, например, в случае h1 = 0, h2 = h вид 4ав + а - в = 0, подбирать ОФФ, исходя только из условия а = в - 1 теоремы. При этом числовое значение параметра в может быть любым вещественным числом, большим единицы, что является основой дополнительного шага шифрования исходного сообщения, связанного не только с деталями алгоритма шифрования, но и с дополнительным произвольно задаваемым значением параметра в. В общем случае значения в могут быть разными на различных участках выбранной сетки с узлами xj, что порождает множество дополнительных ключей и поэтому значительно повышает уровень защищённости передаваемого сообщения. Отказ от ортогональности ОФФ значительно расширяет область применения ОФФ, которые, не обладая уже свойством ортогональности, представляют собой особую часть исходного множества ОФФ. Функции (1) в случае h1 = 0, h2 = h принимают следующий вид: 2a(xi-1 - x)/h, x G [xi-1,xi-1 + h/2], 2(a + 1)(x - xj)/h +1, x G [xi-1 + h/2, xj], fi(x)= 1). Используемые здесь и далее усечённые квадратные скобки означают операцию округления до ближайшего целого числа. Запишем исходное сообщение a G A в векторном виде: a = (a1, a2,..., a„). Пусть также выбран вектор k G K, k = (k1, k2,... , kn), и значения в, h и x1, связанные с используемой сеткой. При этом все компоненты k попарно различны и для всех i = 1,..., n/2 имеет место km G [xj,, xii+1 ], m = 2i - 1, 2i, km G [xji-i, xj,+2], m = 2i - 1, 2i, где xj, и xji+1 (jj,jj+1 G Zj) -узлы сетки, между которыми лежат k2j-1 и k2j. Другими словами, каждая компонента kj является координатой на оси Ox точки, лежащей между двумя соседними узлами сетки xj, и xji+1. Кроме того, если k2j-1 и k2j лежат в [xj, ,xji+1 ], то в данном интервале и в соседних [xji-1 ,xji ], [xji+1 ,xji+2 ] не лежит более ни одна из компонент kj, отличная от k2j-1 и k2j. Для большей определённости в предлагаемом алгоритме пусть k2j G [xj, + h/2, xji+1 ], k2j-1 G [xj,,xj, + h/2]. Вместе с тем возможны другие варианты расположения точек с координатами k2j-1, k2j и связанные с этим другие варианты алгоритма. При к2г-1 G [xj;, xj; + h/2], k2j G [xj; + h/2,xj-i+1 ], для исключения многозначности результатов расшифрования, пусть (в - 1)(k2j-1 - Х;) > в(xii+i - k2j). (3) В силу ограничений, наложенных на элементы k, целесообразно проводить их выбор в три этапа. На первом шаге выбирается конкретный участок [xj; ,xji+1 ], на втором шаге - k2i-1, на третьем шаге - значение k2j с учётом условия (3): k/ >Xj+i - (в - 1)(кв-1 - j) . (4) При невозможности выбора k2j второй и третий шаги повторяются. При этом следует отметить, что условия выбора элементов вектора k не препятствуют использованию для их генерации криптографически стойких генераторов случайных чисел. На всех трёх этапах, а также при генерации значений в, h и х1 возможно использование таких алгоритмов, как алгоритм Блюм - Блюма - Шуба или криптографически стойкая хэш-функция. Это сводит задачу генерации ключей к передаче начальных значений генераторов, что упрощает задачу генерации, рассылки и хранения ключей без ущерба для криптостойкости алгоритма. Обозначим х' вектор узлов сетки, используемых при аппроксимации многочлена. При этом x/j-1 = Xj, x'2i = xji+1 (i = 1,...,n/2). В качестве f возьмем набор f = (f1, f2,... , fn), где каждая f - ОФФ-функция, соответствующая узлу xj. Вектор (k, в, h, x1) является ключом, вектор b G B, b = (b1, b2,... , bn), -шифртекстом. Алгоритм шифрования состоит из следующих четырёх шагов. Шаг 1. Вектору a сопоставляется многочлен a(x) = a1 + a2x + a3x2 + ... + anxn-1. (5) Шаг 2. Проводится аппроксимация многочлена a(x) с помощью функций fj. При этом аппроксимирующая функция F(x) является суммой произведений ОФФ-функций fj и соответствующих коэффициентов аппроксимации r^ n F(x) = Е rifi(x). i=1 Так как fj(xj) = , где - символ Кронекера (i,j G {1,...,n}), коэффициент i-й ОФФ-функции равен значению многочлена в точке с координатой xj. Значения этих коэффициентов - неотрицательные целые числа. Таким образом, значения вектора коэффициентов аппроксимации r = (r1, r2,..., rn) находятся по формуле Г = a(xj) mod N. Шаг 3. Формируется вектор b = (b1, b2,... , bn), где b равно значению аппроксимирующей функции в точке с координатой по оси Ox равной kj, то есть bj = F (kj), i = 1,..., n. Поскольку для всех i G {1,... ,n/2} точки k2j-1 и k2j лежат между узлами x/j_ 1 и x/j, значения аппроксимирующей функции в данных точках равны линейным комбинациям соответствующих значений f2j-1 и f2j функций (2): F (k/j-1) = r2j- 1 f2j- 1 (k/j-1) + r2if2i(k2i-1), F (k2j) = r2j-1f2j-1(k2j) + r2jf2j(k2j). Согласно (2), /2i-1(fc2i-1) = 2(в - 1)(k2i-1 - x'2-1)/h + 1, f2i(k2i-1) = 2a(x2i-1 - k2i-1)/h, /2i-1(k2i) = 2в(x2i - k2i)/h, /2i(k2i) = 2(a + 1)(k2i - x2i)/h + 1. Таким образом, F(k ) ,'2(в - 1)(k2i-1 - x2i-1) N 2(в - 1)(x2i-1 - k2i-1) F(k2i-1) = r2i-1\ -;--+ 1 ) + r2ih 2(в - 1)(k2i-1 - x2i-1) h (r2i-1 - r2i) + r2i-1, (r2i-1 - r2i) + T'2i. h ( 2/3(x>2i - k2i) + {2ft(k2i - x2i) + _ F (k2i) = r2i-1-h--+ r2i I -h--+ 1 2в(x2i - k2i) h Шаг 4. Вектор b, являющийся шифртекстом, записывается в виде b =(LF(k1)l, LF(fc2)l,..., LF(kn)]). Алгоритм расшифрования заключается в нахождении коэффициентов исходного многочлена a(x) на основе вектора шифртекста b, известных значений k и в, а также параметров сетки h и x1. Запишем шифртекст b G B в векторном виде b = (b1,b2,... ,bn), где n - чётное натуральное число. Пусть известен вектор k G K, k = (k1, k2,... , kn), использованный при шифровании, а также значения в, h и x1. При этом все ki попарно различны и все k2i-1 и k2i (i = 1,... ,n/2) являются координатами на оси Ox точек, лежащих между двумя соседними узлами сетки x!2i_ 1 и x'2i. Шаг 1. Вектору а исходного сообщения при шифровании был сопоставлен многочлен (5). При проведении аппроксимации a(x) с помощью ОФФ-функций / в точках x' получился вектор коэффициентов аппроксимации r = (r1,r2,..., rn), компоненты которого находятся по формуле ri = a(xi) mod N. Для нахождения значений вектора r при расшифровании значения вектора b берутся парами и первый элемент в паре складывается с элементом, обратным второму, то есть определяются значения bi = b2i-1 - b2i (i = 1,... , n/2): 2(в - 1)(k2i-1 - x2i-1) 2в(x2i - k2i) b' h + 11 (f'2i-1 - T'2i). h Далее находятся значения (r2i-1 - r2i) по формуле b' (r2i-1 - r2i) L2(e - 1)(k2i-1 - x2^ 1)/h - 2в(x2i - k2i)/h + 1 Шаг 2. Вычисляются значения вектора r. Для этого используется формула (6) b2i = |_f (ы! 2в(x2i - k2i) (r2i-1 - Г2г) + Г2г h где i = 1,..., n/2. Отсюда следует, что r2i-1 = (r2i-1 - r2i) + r2i 2в(х2г - k2i) h (r2i-1 - r2i) Г2г = b2i - Шаг 3. Вектор коэффициентов аппроксимации r теперь известен, по значениям вектора k определяются все xi (k2i G [x'2i-1,x'2i], i = 1,...,n/2). Решение системы уравнений 'а(ж1) = r1, a(x'2) = r2, 7) 60 - 17,07, 19 > 20 - 39 > 40 - 37,8, 57,8 3,75 показывает его выполнение. Случайные величины x1 и h получили в результате генерации значения x1 - 0, h - 10, поэтому вектор координат узлов сетки имеет вид x' - (10, 20, 30,40, 50, 60). Шаг 1. Вектору a сопоставляется многочлен a(x) - 20 + 13x + 2x2 + 4x3 + 5x4 + x5. Шаг 2. Проводится аппроксимация a(x) с помощью ОФФ-функций /. При этом используется значение в - 3,75. В результате получается вектор коэффициентов аппроксимации r - (r1, r2, r3, r4, r5, r6): Г1 - a(10) - 154350 = 150 (mod 257), r2 - a(20) - 4033080 = 236 (mod 257), r3 - a(30) - 28460210 = 30 (mod 257), r4 - a(40) - 115459740 = 177 (mod 257), r5 - a(50) - 344255670 = 58 (mod 257), r6 - a(60) - 843272000 = 2 (mod 257). Получился вектор r - (150, 236, 30,177, 58, 2). Ш а г 3. Строится вектор b: b1 - l_F (k1)l - b2 - LF(k2)l : Ьз - LF (k3)l - b4 - LF (k4)l - b5 - LF (k5)l - b6 - LF (k6)l (150 - 236) + 236 2(3,75 - 1)(14 - 10) 10 2 ■ 3,75(20 - 19) (150 - 236) + 150 - -39, 172, -213, 67, 150, 10 2(3,75 - 1)(33 - 30) 10 2 ■ 3,75(40 - 39) (58 - 2) + 58 (30 - 177) + 30 (30 - 177) + 177 10 2(3,75 - 1)(53 - 50) 10 2 ■ 3,75(60 - 58) 86, (58 - 2) + 2 10 b - (-39,172, -213, 67,150, 86). Вектор b является шифртекстом. Расшифрование. При расшифровании шифртекста b - (-39,172, -213,67,150, 86) используются сформированные при шифровании векторы и величины k - (14,19, 33, 39, 53, 58), в - 3,75, h - 10, x1 - 0, x' - (10, 20, 30, 40, 50, 60), определяющие ключ. Шаг 1. Находятся значения выражений (r2j-1 - r2j), i = 1,... , n/2: 2(в - 1)(k1 - x1) 2в (X2 - k2) h + 1 J (r1 - r2) = -39 - 172 = -211, h - 211 211 -86, r1 - r2 2,2 - 0,75 + 1 _(2(в - 1)(k1 - x1)/h - 2в (X2 - k2)/h + 1) 2(в - 1)(k3 - x3) 2в (x4 - k4) b/ h + 11 (гз - r4) = -213 - 67 = -280, h 280 280 147, Гз - r4 1,65 - 0,75 + 1 _2(в - 1)(k3 - x'3)/h - 2в(х4 - k4)/h +1 2(в - 1)(k5 - x5) 2в (хб - k6) b/ h + 11 (Г5 - Гб) = 150 - 86 = 64, h 64 64 56. Г5 - Гб 1,65 - 1,5 + 1 L2(e - 1)(k5 - x5)/h - 2в (хб - k6)/h + 1 Ш а г 2. Для определения значений компонент вектора r вычисляются 2 ■ 3,75(20 - 19) 10 ■ (-86) b + r 2 = -64 + r 2 = 172, 2= r2 = 172 + 64 = 236, r1 = (r1 - r2) + r2 = -86 + 236 = 150, 2 ■ 3,75(40 - 39) (-147) b4 + Г4 = -110 + Г4 = 67, 10 r4 = 67 + 110 = 177, r3 = (r3 - r4) + r4 = -147 + 177 = 30, 2 ■ 3,75(60 - 58) b 56 б= + Гб = 84 + Гб = 86, 10 Гб = 86 - 84 = 2, Г5 = (Г5 - Гб) + Гб = 56 + 2 = 58. Поэтому r = (150, 236, 30,177, 58, 2). Шаг 3. Решается система уравнений вида (7): 'a(10) = 150 (mod 257), a(20) = 236 (mod 257), a(30) = 30 (mod 257), a(40) = 177 (mod 257), a(50) = 58 (mod 257), ^a(60) = 2 (mod 257). В итоге получается многочлен a(x) = 20 + 13х + 2х2 + 4х3 + 5x4 + x5. Шаг 4. По значениям коэффициентов многочлена a(x) строится вектор a = = (20,13, 2, 4,5,1), являющийся исходным сообщением. Замечание 1. Для обоснования выбора простого N запишем систему (7) в мат- K)n-1\ (х')п-1/ ричной форме: 1 X1 1 Если N простое и все точки xj, i = 1,... , n, различны, то основная матрица системы невырожденная и, следовательно, система имеет единственное решение. Замечание 2. В рассмотренном примере показано использование алгоритма в режиме простой замены, однако в практических реализациях, за исключением случаев шифрования коротких сообщений, целесообразно использование иных режимов. При этом разницу в объёмах блоков открытого текста и шифртекста можно компенсировать, заменяя в процессе шифрования очередной блок открытого текста x на результат обратимой функции g(x), по объёму равный блоку шифртекста. Поскольку алгоритм оперирует с блоками текста фиксированной длины n, уместно его сравнение с алгоритмами блочного шифрования. К достоинствам предложенного алгоритма относится динамическая длина ключа, что упрощает переход на версии алгоритма с большей длиной n блока текста. Более того, значения N и L также не фиксированы, что позволяет алгоритму шифрования на основе ОФФ оперировать с множествами A, K и B, имеющими алфавит любой длины, а также задавать сетки с любым максимальным значением x^. Параметр в может принимать любые вещественные значения больше единицы, однако в практических реализациях алгоритма целесообразно взять некоторую конечную область значений в, разбить её на интервалы, например длины 1/N, и выбрать значения в, лежащие на концах данных интервалов. При этом поскольку число возможных значений в на каждом участке [i,i + 1], i = 0,... , N - 1, зависит от N, при увеличении N расширяется множество допустимых значений в. Значительно увеличивается преимущество алгоритма в стойкости шифрования при использовании любых вещественных значений в по сравнению с целыми значениями. Увеличение максимального значения в расширяет множество допустимых значений ключа, однако вместе с тем значительно возрастает объём шифртекста по сравнению с открытым текстом. В связи с этим в практических реализациях алгоритма рекомендуется ограничивать максимальное значение в, находя баланс между возрастающим объёмом шифртекста и количеством допустимых значений ключа. Сравним алгоритм с поточным шифром гаммирования. При многократном использовании ключа существенно повышается стойкость шифрования в предложенном алгоритме по сравнению с шифром гаммирования к таким видам криптоанализа, как атаки на основе шифртекста, известного открытого текста, выбранного открытого текста и выбранного шифртекста. При шифровании гаммированием знание открытого текста и шифртекста позволяет определить точное значение гаммы, что исключает многократное использование одного и того же ключа. В случае шифрования предложенным методом знание двух сообщений a и b не позволяет однозначно подобрать параметры (k, в, h, x1). Изменение любого из них, при соответствующих изменениях других параметров, приведёт к тому, что данному открытому тексту a будет соответствовать тот же шифртекст b. Уровень сложности дешифрования в предложенном алгоритме характеризуется необходимостью перебора возможных значений параметров h и x1 и решения со всеми возможными парами (h,x1) уравнений (6) с неизвестными в, r2i-1 и r2i, а также необходимостью решения системы (7). Увеличение n приводит к увеличению мощности множества допустимых значений ключа, вместе с тем растёт сложность шифрования и расшифрования, поскольку максимальная степень многочлена (5), а также количество уравнений (7) зависят от n. Пусть, например, N = 65537, h = 4, n = 30, x^ = 65536, а максимальное допустимое значение в равно 256. Пусть также x1 = 0. Тогда сетка разбивается на 65536/(2h) = = 8192 различных участка, каждому из которых могут принадлежать две компоненты вектора k. С учётом условия (4), каждому участку [x'2i-1, x2i+1] могут соответствовать 16 допустимых значений пар (k2j, k2j-1). Общее число допустимых значений компонент вектора k в таком случае равно 8192! |K| = A8192 ■ 8 = 8192' ■ 8 « 3,2 ■ 1063. 1 1 8192 (8192 - 15)! ' Разобьём область допустимых значений в (в > 1) на интервалы длины 1/N. Таким образом, для каждого возможного значения вектора k существует 255 ■ 65536 - 1 = = 16711679 допустимых значений в. Множество допустимых значений ключа содержит 3,2■ 1063 -16711679 ~ 5,3■ 1070 элементов, что даже при многократном использовании ключа делает абсурдными задачи полного перебора либо записи всех подобранных сочетаний (k, в, h, x1) с целью вскрытия следующего шифртекста перебором лишь записанных заранее значений. При этом следует учесть, что в практических реализациях алгоритма возможно разделение области допустимых значений в на интервалы длины меньше 1/N, а также нефиксированное значение x1, что дополнительно расширяет множество допустимых значений ключа. Вместе с тем при уменьшении n распределение символов шифртекста становится все более схожим с распределением символов открытого текста, что значительно упрощает задачу дешифрования без знания ключа. В дальнейшем предполагается более подробное исследование стойкости предложенных алгоритмов к различным атакам в зависимости от выбранных параметров и ключа. Методы использования базисов в криптографических алгоритмах развиваются и в других работах [4, 5], новизна предложенного здесь алгоритма шифрования заключается в использовании принципиально иных базисных функций - ОФФ, не обладающих свойством ортогональности.

Ключевые слова

ОФФ, финитные функции, криптография, шифрование, OFF, finite functions, cryptography, encryption

Авторы

ФИООрганизацияДополнительноE-mail
Щуренко Александр ВасильевичУльяновский государственный университетаспирантtshurens@yandex.ru
Леонтьев Виктор ЛеонтьевичУльяновский государственный университетдоктор физико-математических наук, профессорLeontievVL@ulsu.ru
Всего: 2

Ссылки

Леонтьев В. Л. Ортогональные финитные функции и численные методы. Ульяновск: Изд-во УлГУ, 2003. 178 с.
Леонтьев В. Л., Лукашенец Н. Ч. Сеточные базисы ортогональных финитных функций // Журн. вычисл. матем. и матем. физ. 1999. Т. 39. №7. С. 1158-1168.
Леонтьев В. Л. Ортогональные сплайны и вариационно-сеточный метод // Математическое моделирование. 2002. Т. 14. №3. С. 117-127.
Лукомский Д. С., Лукомский С. Ф. Всплесковые базисы и криптография // Математика. Механика. 2011. №13. С. 55-58.
Левина А. Б. Сплайн-вэйвлеты и их некоторые применения: дис.. канд. физ.-мат. наук. СПб., 2009. 214с.
 Финитные функции в алгоритмах криптографии | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/6

Финитные функции в алгоритмах криптографии | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/6