Модулярная интерпретация сообщений в системах защиты информации

Полный текст

Введение В современном процессе развития высокопроизводительных средств защиты информации, компьютерно-арифметической базой которых служит арифметика модулярных систем счисления (МСС) - модулярная арифметика (МА), ключевая роль отводится проблематике оптимизации применяемых немодульных операций [1-11]. В случае криптосистем базирующихся на умножении Монтгомери, оптимизации подлежат главным образом операции расширения модулярного кода (МК) и процедуры кодовых преобразований (процедуры позиционно-модулярного интерфейса). Что касается расширения кода МСС и преобразования его в позиционный код (ПК), то эти операции в значительной мере удается оптимизировать в рамках избыточного кодирования и в частности в рамках так называемого минимально избыточного модулярного кодирования [2-5; 12-14]. Среди других активно развиваемых оптимизационных направлений в современных криптографических МА-приложениях следует отметить направление, которое охватывает разработки по применению наборов модулей специального вида [6; 15-19], обеспечивающих упрощение как модульных, так и немодульных операций. Роль кодовых преобразований в системах защиты информации (СЗИ) модулярного типа состоит прежде всего в согласовании принятой формы представления входных сообщений и результатов дешифрования данных с базовой конфигурацией МА. Традиционно для синтеза требуемых процедур позиционно-модулярного интерфейса СЗИ рассматриваемого класса применяется двоичное представление входной и выходной информации, то есть ее позиционная интерпретация [1]. Получение МК числа, отождествляемого в СЗИ с входным сообщением и выполнение обратного (декодирующего) преобразования с привлечением промежуточных форм целых чисел (ЦЧ), сопряжено с высокой трудоемкостью итоговых алгоритмов. Вместе с тем, сложность и время реализации кодовых преобразований в СЗИ на основе МА удается свести практически к предельно низким уровням в рамках так называемой модулярной интерпретации сообщений. Предлагаемый альтернативный подход базируется на том, что составные элементы компонент или сами компоненты исходной формы записи входного сообщения по тому или иному правилу группируются в слова, которые рассматриваются (интерпретируются) как цифры МК по требуемому набору модулей ЦЧ, отождествляемого с заданным сообщением. Как нетрудно видеть, конкретная модификация отображения, ставящего в соответствие каждому сообщению единственное ЦЧ из диапазона МСС, принципиального значения не имеет. В статье дана математическая формализация принципа модулярной интерпретации сообщений в СЗИ, сформулированы кодирующий и декодирующий алгоритмы, реализующие применяемый принцип, а также приведены оценки эффективности предлагаемого подхода. Минимально избыточное модулярное кодирование Введем следующие обозначения: · ëaû и éaù - наибольшее и наименьшее ЦЧ соответственно не большее и не меньшее вещественной величины a; · Zm = {0, 1, …, m-1}, ={- ëm/2û, - ëm/2û + 1, … ém/2ù - 1} - множества наименьших неотрицательных и абсолютно наименьших вычетов по натуральному модулю m; · |A|m - элемент кольца Zm, сравнимый с A (в общем случае рациональным числом) по модулю m; · sn(a) - знаковая функция вида · «<<b» и «>>b» - операции сдвига двоичного кода ЦЧ на b бит влево и вправо соответственно; · {m1, m2, ..., ms} - базис МСС, состоящий из s>1 попарно простых модулей. В МСС с базисом {m1, m2, ..., ms} ЦЧ X представляется кодом . Максимальная мощность множества DМСС чисел X, на котором отображение X→ взаимно однозначно составляет элементов. В этом случае DМСС выполняет роль диапазона МСС. Обычно в качестве диапазона используют или . Из Китайской теоремы об остатках следует, что ЦЧ XÎDМСС может быть получено по своему МК с помощью равенства , (1) где ; ; - интервальный индекс (ИИ) числа X [20]. Выражение (1) называется интервально-модулярной формой ЦЧ X. При |DМСС|=Ms МСС с базисом {m1, m2, ..., ms} является неизбыточной. Между тем использование в системах счисления кодовой избыточности, как правило, позволяет существенно улучшить их арифметические и иные свойства. Так называемое минимально избыточное модулярное кодирование: предусматривает применение диапазона DМИМСС, мощность которого меньше мощности диапазона DМСС неизбыточной (классической) МСС с базисом {m1, m2, ..., ms}. Сущность реализуемого принципа раскрывает нижеследующее утверждение. Теорема 1 «О минимально избыточном модулярном кодировании». Для того, чтобы в МСС с попарно простыми основаниями m1, m2, …, ms ИИ Is(X) каждого элемента X = диапазона = {-M, -M + 1, ... M -1} ( - вспомогательный модуль) полностью определялся компьютерным ИИ - вычетом , необходимо и достаточно, чтобы s-ое основание удовлетворяло условию: ms ³ 2m0 + s- 2 (m0 ³ s - 2). При этом для Is(X) верны расчетные соотношения: (2) ; (3) .. (4) Переход от МСС с базисом {m1, m2, ..., ms} и к минимально избыточной МСС (МИМСС) с тем же базисом и диапазоном предельно упрощает вычисление базовой интегральной характеристики МК - ИИ Is(X): см. (2)-(4). Это приводит к адекватной оптимизации и немодульных процедур, базирующихся на интервально-модулярной форме (1). Тривиальность процедуры расчета в МИМСС интервально-индексной характеристике дает также дополнительные возможности для упрощения реализации принципа модулярной интерпретации сообщений в СЗИ. Это достигается за счет использования наряду с минимально избыточным МК (МИМК) и вспомогательного так называемого интервально-модулярного кода (ИМК), который для ЦЧ Х определяется как набор вычетов: . Для перехода от ИМК к МИМК достаточно воспользоваться равенством ,(5) вытекающим из (1-(3). Формирование ИМК ЦЧ Х по его МИМК фактически сводится к вычислению характеристики (Х): см. (3)-(4). Принцип модулярной интерпретации сообщений в криптосистеме RSA Применение принципа модулярной интерпретации данных в системах защиты информации становится возможным благодаря присущему им свойству замкнутости относительно входных сообщений. В настоящей статье предлагаемый подход демонстрируется на примере криптосистемы RSA, базирующейся на операциях умножения и возведения в степень по большому модулю р, которые реализуются с использованием модифицированной минимально избыточной модулярной схемы Монтгомери в рамках таблично-сумматорной вычислительной технологии [2-5]. Как известно [21], для системы RSA с модулем р базовые криптографические преобразования имеют вид , , (6) где и - соответственно открытый и секретный ключи; е - элемент множества , взаимно простой с j(р) (j(р) - функция Эйлера от р); d =; Х - ЦЧ из диапазона Zp, отождествляемое с входным сообщением Х. Из (6) вытекает равенство (), (7) в котором и заключается свойство замкнутости криптосистемы относительно входного сообщения. Обозначим последовательность битов, в совокупности образующих запись сообщения Х, через (8) Получение конкретного значения числа Х, отождествляемого с сообщением Х, осуществляется согласно некоторому взаимнооднозначному отображению, ставящему в соответствие каждой последовательности вида (8) слово (Х0, Х1, … Хn-1) () из кодового пространства применяемой рабочей системы счисления. Иначе говоря, выбор базового правила присвоения значений аргументу Х реализуемой целевой функции (см. (6), (7)): X = (Х0, Х1, … Хn-1) () предполагает определенную кодовую интерпретацию набора булевых величин (8), которая описывается тем или иным взаимно однозначным отображением вида: (9) При любом таком отображении, не выводящем Х=(Х0, Х1, …, Хn-1) за пределы диапазона Zp, свойство (7) криптосистемы в случае ее функционирования в системе счисления, отвечающей принятой кодовой интерпретации входных сообщений Х сохраняется. Если преобразования (6) реализуются в позиционной системе счисления (ПСС) с основанием r>1, то последовательность (8) отображается в ПК . При этом ( rn < p). (10) Модулярная интерпретация сообщения Х предполагает объединение элементов последовательностей (8) в группы, которым отвечают числовые значения, принимаемые в качестве цифр МК (c1, c2 … cs) числа Х по модулям m1, m2, … ms. Отметим, что выполнение условия Х Î Zp в рамках рассматриваемой кодовой интерпретации сообщения Х на практике более просто обеспечивается при использовании композиции отображений Х®и , второе из которых реализуется с помощью (5). В этом случае декодирующее преобразование также должно иметь композиционную структуру: , требующую вычисления согласно (3)-(4) характеристики . Обозначенный подход, в сущности, позволяет говорить об интервально-модулярной интерпретации сообщений, выполняющей роль вспомогательной стадии итоговой модулярной интерпретации. Предположим, что входное сообщение Х задано в виде последовательности Х = , состоящей из n байтовых величин и пусть модули базовой МСС являются 16-битовыми простыми ЦЧ из промежутка (215;216]. Тогда для получения цифр МК (c1, c2, …, cs) числа Х, отождествляемого с сообщением Х при его модулярной интерпретации, можно воспользоваться величинами , (11) которые имеют разрядность 16 бит. Поскольку величины (11) могут выходить за пределы , то использовать xi в качестве цифр МК по модулям mi непосредственно нельзя. В предлагаемом способе формирования требуемого МК в качестве базового применяется правило , согласно которому в двоичном коде величины xi старший бит замещается значением 0. При этом прежнее значение данного бита сохраняется в дополнительном слове соответствующего блока цифр, конструируемого МК. Каждый полный блок состоит из 16 слов. Вводя (s + 1)-элементный массив МС_Х для МК ЦЧ Х с учетом изложенного реализуемое предложенным способом кодирование входного сообщения Х основополагающее правило запишем в виде: (12) Количество цифр конструируемого МК, формируемых согласно (12), составляет (13) Отметим, что в процессе кодирования входного сообщения Х в массив МС_Х в качестве нулевого элемента записывается длина сообщения (МС_Х[0] = n), а остальные элементы, не охваченные правилом (12), обнуляются (МС_Х[i] = 0 ()). Таким образом, получаемый в соответствии с (12) на вспомогательной стадии кодирования сообщения Х ИМК имеет вид: (c1, c2 …, c, c, …, cs-1, ) = = (c1, c2 … c, 0, …, 0, 0). (14) Следовательно, искомый результат модулярной интерпретации Х представляет собой МК (c1, c2, …, c, c, …, cs-1, ) = = (c1, c2, …, c, 0, …, 0, ). (15) С учетом (5) и (14) цифра кода (15) определяется по расчетному соотношению . (16) Из (1) и (14) для ЦЧ Х, отождествляемого с Х при рассматриваемой модулярной интерпретации, вытекает равенство (17) Найдем верхний ограничительный порог ХВП для числа вида (17). Из (17) имеем: (18) В применяемых базисах МСС основания упорядочиваются по возрастанию - поэтому из (18) следует, что . Изложенное позволяет сформулировать следующее утверждение. Теорема 2. Если модуль р, базис {m1,m2,…,ms} применяемой МИМСС, параметры s, , а также длина n (в байтах) сообщений (см. (9), (13), (18)) удовлетворяют условиям: (19) то двухкаскадная композиционная конфигурация модулярной интерпретации сообщений в криптосистеме RSA с модулем р, базирующаяся на схеме (12), корректна, то есть является реализуемой. Отметим, что первое условие в (19) можно ослабить, если в (12) цифры ci МК заменить на их нормированные аналоги ci, s-1 (см. (17)). В этом случае (17) дает: (20) В сравнении с (19) оценка (20) дает существенно большую свободу для выбора р. Вместе с тем, указанная альтернативная модификация модулярной интерпретации сообщений требует дополнительных реализационных затрат на получение цифр МК (15) согласно формуле . Что касается цифры cs МК (15), то ее вычисление в сравнении с (16) упрощается: . Алгоритмическое обеспечение модулярной интерпретации сообщений в СЗИ На базе изложенных положений разработанной технологии модулярной интерпретации данных в криптосистемах RSA на основе МА синтезированы алгоритмы кодирования и декодирования сообщений. Для определенности предполагается, что сообщения задаются в виде байтовых последовательностей. Алгоритм кодирования сообщений. Параметры алгоритма удовлетворяют условиям (19) теоремы 2, модуль p криптосистемы, основания m1, m2, … ms применяемой МИМСС ( и длина n сообщений (в байтах). Входные данные: Сообщение Х = объемом n байтов, расположенное в массиве с идентификатором М_Х (М_Х [j]=Xj ). Выходные данные: МК (c1, c2, …, cs)= (c1, c2, … c, 0, …, 0, cs) () отождествляемого с входным сообщением Х числа Х (ХÎZp), который наряду с n помещается в (s + 1)-элементный массив МС_Х (МС_Х[0] = n, МС_Х[i] = ci Тело алгоритма кодирования модулярно интерпретируемого сообщения К_МИ.1. Инициализировать параметры и константы кодового преобразования: Определить параметры и константы преобразования: · число полных 16-битовых слов в сообщении - N_W =(символом « >> b» обозначается операция сдвига целого число (ЦЧ) вправо на b бит); · количество 16-элементных блоков из цифр формируемого МК, отвечающих 16-битовым словам сообщения, - N_B =; · количество оставшихся не вошедших в полные блоки 16-битовых слов - R_W=; · BExp_7 = 27, Mask_7 = BExp-1. К_МИ.2. Активизировать (s+1)-элементный массив MC_X для выходного МК, положив MC_X [0] = n, MC_X [i] = 0 (). К_МИ.3. Переменным цикла j и i по компонентам входного сообщения и выходного кода, а также счетчику C_B блоков цифр МК присвоить начальные значения: j = 0, i = 1, C_B = 1. К_МИ.4. Обнулить порядковый номер слова в блоке: u = 0, и положить v = 0, BExp = 1. К_МИ.5. Получить очередное цифру МК текущего блока, реализуя операционную последовательность: К_МИ.5.А. Из массива М_Х извлечь j-ый элемент, полагая w = М_Х[j]=Xj . К_МИ.5.Б. Если BExp_7w 0, то положить v= v BExp, w = wMask_7. К_МИ.5.В. Выполнить операции: w = w << 8, MC_X [i] = w + М_Х[ j + 1] = w + Xj+1 , i = i + 1, j = j + 2. К_МИ.6. Если u14, то u инкрементировать (u = u + 1), переменную BExp сдвинуть на один бит влево и перейти к К_МИ.5. По достижении равенства u = 14 в массив MC_X записать очередную цифру: MC_X [i] = v, после чего i инкрементировать ( i= i + 1). К_МИ.7. При C_B ¹ N_B счетчик блоков увеличить на 1 (C_B = C_B+1) и перейти к К_МИ.4. Получить цифры МК заключительного (неполного) блока К_МИ.8. Если R_W = 0 и n четно, то перейти к К_МИ.16. Если же R_W = 0, но n нечетно, то выполнить операцию присвоения MC_X [i] = М_Х[n - 1] = Хn-1 и перейти к К_МИ.16. К_МИ.9. Положить: u = 0, v = 0, BExp = 1. К_МИ.10. Получить очередную цифру МК заключительного блока, реализуя операционную последовательность: К_МИ.10.А. Переменной w присвоить значение w = М_Х[j] = Xj. К_МИ.10.Б. При BExp_7w0 положить v = v BExp, w = wMask_7. К_МИ.10.В. Выполнить операции: w = w << 8, MC_X [i] = w + М_Х[j + 1] = w + Xj+1 , i = i + 1, j = j + 2. К_МИ.11. Если uR_W, то u увеличить на 1 (u = u + 1), переменную BExp сдвинуть на один бит влево и перейти к К_МИ.10. К_МИ.12. При четном n в массив MC_X записать последнюю цифру блока: MC_X [i] = v и перейти к К_МИ.16. К_МИ.13. Выполнить операцию присвоения w = М_Х[j] = Xj . К_МИ.14. Если u < 8, то положить MC_X [i] = (v << 8) + w и перейти к К_МИ.16. К_МИ.15. В случае, когда u 8 в массив MC_X поместить две последние цифры МК заключительного блока: MC_X [i] = w, MC_X [i + 1] = v. К_МИ.16. Используя (4) и (16) рассчитать s-ю цифру искомого МК согласно правилу (ci= =MC_X[i]) и завершить работу алгоритма. Алгоритм декодирования сообщений Параметры алгоритма: удовлетворяющие условиям (19) теоремы 2 модуль p криптосистемы, основания m1, m2 … ms применяемой МИМСС (и длина n сообщений (в байтах). Входные данные: Подлежащий декодирующему преобразованию МК (c1, c2 … cs) некоторого ЦЧ Х Î Zp, расположенный в (s + 1)-элементном массиве с идентификатором МС_Х (МС_Х[0] = n, МС_Х[i] = ci ). Выходные данные. Отождествляемое с числом Х сообщение Х =, элементы которого помещаются в массив с идентификатором N_X. Тело алгоритма декодирования модулярно интерпретируемого сообщения Д_МИ.1. Инициализировать параметры и константы декодирующего преобразования: · длина (в байтах) формируемого сообщения - n = МС_Х[0]; · число 16-битовых слов вида (11) в сообщении Х - N_W = ; · количество полных (16-элементных) блоков из цифр МК, отвечающих 16-битовым словам вида (1), - N_B = ; · число цифр МК, отвечающих словам вида (11) в неполном блоке - R_W = ; · BExp_15 = 215, Mask_8 = 28 - 1. Д_МИ.2. Следуя (3)-(4) вычислить интервально-индексную характеристику (ci =МС_Х[i]). Д_МИ.3. В случае нарушения равенства МС_Х[+ 1] = МС_Х[+ 2] =…= МС_Х[s - 1] = = 0 (см. (19)) завершить работу алгоритма по причине фиксации ошибки в ИМК (c1, c2 … cs - 1, ). Д_МИ.4. Активизировать n-байтовый массив М_Х для формируемого сообщения. Д_МИ.5. Переменным i и j цикла по элементам массивов МС_Х и М_Х, а также счетчику С_В_4 блоков цифр МК и параметров N_B_4 присвоить значения: i = 1, j = 0, C_B_4 = 16, N_B_4 = 16×N_B = N_B << 4. Д_МИ.6. Положить v = MC_X[C_B_4]. Д_МИ.7. Получить очередную пару символов (байтов) сообщения, отвечающую паре одноименной цифре МК текущего блока, выполняя операционную последовательность: Д_МИ.7А. Из массива МС_Х извлечь очередную цифру МК: w = МС_Х[i]. Д_МИ.7Б. При 1Ùv¹0 осуществить коррекцию слова w согласно правилу w = wÚBExp_15. Д_МИ.7В. В массив М_Х поместить пару компонент сообщения: М_Х[j + 1] = Mask_8Ùw, М_X[j] = w >>8. Д_МИ.7Г. Положить v = v >> 1, i = i + 1, j = j + 2. Д_МИ.8. Если i ¹ C_B_4, то перейти к Д_МИ.7. Д_МИ.9. Инкрементировать переменную i (i = i + 1), согласовав тем самым ее значение с переходом к очередному блоку цифр МК. Д_МИ.10. При С_В_4¹N_B_4 увеличить C_B_4 на 16 (С_В_4 = С_В_4 + 16) и перейти к Д_МИ.6. Получить компоненты сообщения, отвечающие заключительному (неполному) блоку цифр МК Д_МИ.11. Если R_W = 0 и n четно, то завершить работу алгоритма. Если же R_W = 0, но n нечетно, то выполнить операцию М_X[n - 1] = MC_X[i] и завершить работу алгоритма. Д_МИ.12. Положить: u = i + R_W. Д_МИ.13. В случае четного n переменной v присвоить значение v = MC_X[u]. Д_МИ.14. При нечетном n положить М_Х[n - 1] = Mask_8ÚMC_X[u]. Кроме того, если R_W < 8, то выполнить операцию v = MC_X[u] >> 8, если же R_W > 7, то - операцию v = MC_X[u + 1]. Д_МИ.15. Сформировать пару компонент сообщения, отвечающую текущей цифре МК заключительного блока, реализуя операционную последовательность: Д_МИ.15А. Из массива МС_Х извлечь очередную цифру МК: w = МС_Х[i]. Д_МИ.15Б. При 1Ùv¹0 осуществить коррекцию слова w по правилу w = wÚBExp_15. Д_МИ.15В. В массив М_Х поместить искомую пару компонент сообщения: М_Х[j + 1] = Mask_8Ùw, М_X[j] = w >>8. Д_МИ.15Г. Положить v = v >> 1, i = i + 1, j = j + 2. Д_МИ.16. Если i ¹ u, то перейти к Д_МИ.15. По достижении равенства i = u завершить работу алгоритма. Приведенные алгоритмы кодирования и декодирования сообщений в СЗИ отличаются простотой и высоким быстродействием. Это обусловлено тем, что их реализация практически требует лишь логических операций и операций присвоения. Для традиционно применяемых кодирующих и декодирующих процедур, основанных на позиционной интерпретации сообщений [14; 22] согласно формуле вида (10) необходимые временные затраты составляют величину порядка О(sn) модульных операций. Заключение Основные результаты представленной разработки по проблематике оптимизации средств позиционно-модулярного интерфейса СЗИ, компьютерно-арифметической базой которых служит МА, кратко можно охарактеризовать следующим образом. 1. Проведена математическая формализация принципа модулярной интерпретации сообщений для криптосистем RSA, функционирующих в МСС. В частности, описано базовое взаимно однозначное отображение множества сообщений на кодовое пространство используемой МСС и для построенного отображения получены достаточные условия корректности - реализуемости в рамках таблично-сумматорной вычислительной технологии. 2. Показано, что по критерию простоты выполнения требования принадлежности чисел, отождествляемых с соответствующими сообщениями, к рабочему диапазону криптосистемы оптимальной конфигурацией модулярной интерпретации данных является двухкаскадная композиционная конфигурация, которая порождается парой отображений - интервально-модулярным и модулярным. Это обеспечивается тривиальностью процедур перехода ИМК к МК и МК к ИМК. 3. Синтезированы эффективные кодирующий и декодирующий алгоритмы, реализующие композиционную модификацию принципа модулярной интерпретации сообщений в СЗИ. Предложенные алгоритмы включают лишь логические операции и операции присвоения, вследствие чего они отличаются простотой и высоким быстродействием. В рамках традиционной позиционной интерпретации сообщений в СЗИ модулярного типа прямое и обратное кодовые преобразования занимают время порядка О(sn) модульных операций каждое.

Об авторах

Андрей Алексеевич Коляда

Белорусский государственный университет

Стелла Юрьевна Протасеня

Белорусский государственный университет

Николай Иванович Червяков

Северо-Кавказский федеральный университет

Email: сhervyakov@yandex.ru

Список литературы

Дополнительные файлы