Message modular interpretation for information protection systems

Full Text

Введение В современном процессе развития высокопроизводительных средств защиты информации, компьютерно-арифметической базой которых служит арифметика модулярных систем счисления (МСС) - модулярная арифметика (МА), ключевая роль отводится проблематике оптимизации применяемых немодульных операций [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) модульных операций каждое.

About the authors

Andrey Alekseevich Kolyada

Belarusian State University, Minsk, Belarus

Stella Jurjevna Protasenia

Belarusian State University, Minsk, Belarus

Nikolay Ivanovich Chervyakov

North-Caucasus Federal University

Email: сhervyakov@yandex.ru

References

Supplementary files