APPLICATION OF MINIMALLY REDUNDANT MODULAR ARITHMETIC TO PERFORM THE CRYPTOGRAPHIC TRANSFORMATIONS IN RSA-SYSTEM

Full Text

Введение В современных фундаментальных исследованиях и конкретных разработках в области защиты информации особое место занимают криптографические приложения на основе модулярной арифметики (МА) - арифметики модулярных систем счисления (МСС) [1-10]. Это обусловлено тем, что кодовый параллелизм модулярных вычислительных структур (МВС) обеспечивает им ряд существенных преимуществ над позиционными структурами при оперировании в диапазонах больших чисел. Весьма показательную в этом отношении сферу применения МСС составляют алгоритмы умножения и возведения в степень по большим модулям, основанные на мультипликативной МА-схеме Монтгомери, которые активно используются для высокоскоростной реализации базовых криптографических преобразований в системах RSA [1-2; 5-8; 11-14]. Наиболее трудоемкую часть МА-алгоритмов умножения Монтгомери составляют операции расширения модулярного кода (МК). По уровню простоты процедур немодульных операций, включая расширение кода, среди известных версий МА на текущий момент выделяется так называемая минимально избыточная МА (МИМА) [15]. Синтезированная на базе МИМА оптимизированная модификация мультипликативной схемы Монтгомери для умножения по большим модулям позволяет сократить временные затраты на вычисление интегральных характеристик МК в операциях расширения до теоретического минимума. Другим важным свойством указанной схемы является обеспечение замкнутости динамического числового диапазона для криптографических преобразований относительно умножения Монтгомери, благодаря чему отпадает необходимость в коррекции произведений при выполнении операций возведения в степень по системному модулю. Наряду с отмеченным при использовании минимально избыточной МСС (МИМСС) достигается также значительное упрощение решения сложных задач параметризации криптосистемы RSA. В частности, это относится к проблемам генерирования ключей шифрования и дешифрования, вычисления денормирующего коэффициента (ДНК) для процедуры возведения в степень по системному модулю и др. В статье представлена минимально избыточная модулярная конфигурация алгоритма возведения в степень по большим модулям, который служит основой для реализации базовых преобразований в МИМА-криптосистеме RSA. При этом для синтезированного алгоритма предложены методологические и алгоритмические средства расчета ДНК. Для разработанных средств получены оценки эффективности. Компьютерно-арифметическая база для криптографических преобразований по схеме RSA модулярного типа Введем обозначения: - ëaû и éaù - наибольшее и наименьшее целые числа (ЦЧ), соответственно, не большее и не меньшее вещественной величины a; - Zm = {0, 1, …, m-1}, ={- ëm/2û, - ëm/2û + 1, …, ém/2ù -1} - множества наименьших неотрицательных и абсолютно наименьших вычетов по натуральному модулю m.|A|m и |A|-m - элементы множеств Zm и Z--m, сравнимые с A (в общем случае рациональным числом) по модулю m; - sn(a) - знаковая функция вида - р - рабочий модуль криптосистемы (большое число). В МСС с базисом М1 {m1, m2, ..., ml}, состоящим из l > 1 попарно простых модулей (оснований), ЦЧ X представляется кодом . Максимальная мощность множества D{M1} чисел X, на котором отображение X→ взаимно однозначно составляет элементов. В этом случае D{M1} выполняет роль диапазона МСС. Обычно в качестве диапазона используют или . Из Китайской теоремы об остатках следует, что ЦЧ X может быть получено по своему МК с помощью равенства (1) где ; ; - интервальный индекс (ИИ) числа X [15]. При |D{M1}| < Ml МСС с базисом M1 является неизбыточной. Использование кодовой избыточности позволяет существенно улучшить арифметические и иные свойства МСС. Сущность применяемого минимально избыточного модулярного кодирования раскрывает нижеследующее утверждение. Теорема 1. О минимально избыточном модулярном кодировании. Для того, чтобы в МСС с попарно простыми основаниями m1, m2, …, ml ИИ Il(X) каждого элемента X = диапазона = {-M, -M + 1, ..., M - 1} ( - вспомогательный модуль) полностью определялся компьютерным ИИ - вычетом , необходимо и достаточно, чтобы l-ое основание удовлетворяло условию: ml ³ 2m0 + l - 2 (m0 ³ l - 2). При этом для Il(X) верны расчетные соотношения: (2) ; (3) (4) Определение 1. Выражение (1) называется интервально-модулярной формой (ИМФ), а набор величин или - интервально-модулярным кодом (ИМК) числа Х по базису М1. В указанных формах ИМК допускается также использование вместо характеристики . Как следует из Теоремы 1 переход от неизбыточной МСС с базисом M1 и диапазоном к МИМСС тем же базисом и диапазоном предельно упрощает вычисление базовой интегральной характеристики кода - ИИ Il(X) (см. (2)-(4)). Это приводит к адекватной оптимизации и немодульных процедур, базирующихся на ИМФ (1). В частности, для расширения минимально избыточного МК (МИМК) - на модули некоторого базиса M2 = достаточно согласно (2)-(4) вычислить Il(X) и затем воспользоваться расчетным соотношением: (5) Для операции расширения, реализуемой по формуле (5) далее употребляется условное обозначение: или его сокращенная форма: . Аппарат ИМФ успешно может применяться и для синтеза других немодульных процедур, например, процедуры детектирования знака числа. Наряду с компьютерным ИИ введем другую эвклидову составляющую ИИ , определяемую равенством (6) и называемую главным ИИ числа Х в МСС с базисом M1. Справедливо [16-17] нижеследующее утверждение. Теорема 2. Пусть в МСС с основаниями M1, M2, …, Ml ≥ l - 2 (l ≥ 2) целому числу Х отвечает код и пусть Jl (Х) - главный ИИ данного ЦЧ. Знаки чисел Х и Jl (Х) совпадают при l = 2, а также при l > 2, если Jl (Х) ≠ -1. Применение Теоремы 2 для определения знаков чисел в классе решаемых задач криптографических МА-приложений обеспечивает высокую эффективность. Алгоритм возведения в степень по большому модулю для криптографических преобразований Процедуры умножения Монтгомери предназначены, в первую очередь, для вычисления степеней натуральных чисел по рабочему модулю p криптосистемы RSA - целочисленных величин вида Y = |Xе|p,(Х, е >1). (7) Исходя из сказанного эффективность разработанных мультипликативных алгоритмов, синтезированных на основе МИМА-схемы Монтгомери [14], так же, как и других алгоритмов умножения рассматриваемого класса, следует оценивать в контексте проблемы вычисления функции (7), которая описывает криптографические преобразования, выполняемые в системе RSA. В данном случае основание степени (7) представляет собой число, отождествляемое в системе с шифруемым или дешифруемым сообщением, а показатель является ключом шифрования или дешифрования. Примем в качестве основы для расчета степеней (7) традиционно применяемый метод умножения с квадрированием (square multiply method) [18], который предполагает двоичное кодирование показателя: е = (eb-1 eb-2 … e0)2 (eb-1 = 1; b - разрядность ЦЧ e) и использует мультипликативную декомпозицию функции Y вида: (8) Применяемый для реализации (8) алгоритм умножения Монтгомери по модулю р работает в модулярном базисе М = {m1, m2, …, ml, ml+1, ml+2, …, mk} (1 < l < k), который объединяет два базиса: М1 = {m1, m2, …, ml} и М2 = {ml+1, ml+2,…, mk}. При этом мультипликативная схема, положенная в основу базового способа умножения операндов А = (α1, α2 , …, αk) и B = (β1, β2 , …, βk) по модулю р = (π1, π2 , …, πk) ( описывается в виде операционной последовательности: Корректность мультипликативной МИМА-схемы Монтгомери (9) обеспечивается в условиях нижеследующего утверждения. Теорема 3. Пусть базисы М1 и М2 неизбыточной и минимально избыточной МСС, соответственно, с диапазонами совместно с модулем р, взаимно простым с Ml, удовлетворяют условию: 2p < min{m0×Ml-1, m0×Mk-1/Ml} и пусть операнды А, В мультипликативной операции принадлежат множеству . Тогда величина , вычисляемая в рамках схемы (9), также является элементом множества . При этом и для верна формула . Введем для операции умножения по модулю p, выполняемой согласно схеме (9), условное обозначение MM(A, B) (A и B - операнды, представленные в базовой МИМСС с основаниями m1, m2, ..., mk). Тогда на базе (8) с учетом теоремы 3 можно сформулировать нижеследующий алгоритм возведения в степень. Входные данные: X = (c1, c2, …, ck) (ci = |X|) ()), XÎZ2p; е = (eb-1 eb-2 … e0)2 (eb-1 = 1, b ³1). Выходные данные: Y = (x1, x2, …, xk) (xi = |Y|()), Y º Xe(mod p), Y Î Z2p. Предварительно вычисляемые данные: Тело алгоритма возведения в степень по модулю p: ВС.1. Получить МИМК () ЦЧ X¢ = MM(X, N). ВС.2. Присвоить переменной Y = (x1, x2, …, xk) начальное значение Y = X¢. ВС.3. Для всех j = b-2, b-3, …, 0 выполнить: ВС.3A. Y = MM(Y, Y). ВС.3B. Eсли ej = 1, то найти Y = MM(Y, X¢). ВС.4. Определить МИМК (c1, c2, …, ck) искомого значения степени: Y = MM(Y, 1) и завершить работу алгоритма. Временные затраты на реализацию алгоритма ВС.1…ВС.4 составляют tВС = (b + N1,e)tММ, где количество единиц в двоичном коде ЦЧ е; tММ - время операции умножения по модулю р. Пусть b = r_p/2(r_p - разрядность (в битах) модуля р) и пусть количество единичных цифр в двоичном коде показателя степени (7) подчиняется равномерному закону распределения. Тогда N1,e = b/2 и tВС=0,75r_p×tММ. Для (1024…2048)-битовых р криптографическое RSA- преобразование с применением алгоритма ВС.1…ВС.4 на основе мультипликативной процедуры, реализующей схему Монтгомери (9), на ПЭВМ с процессором Intel Core i5 (тактовая частота 2,27 ГГц) в среднем занимает время порядка 0,56 … 5, 67 с. Математическая формализация мультипликативно-субстрактивного метода вычисления денормирующего коэффициента для криптографических RSA-преобразований Используемая в алгоритме ВС.1…ВС.4 константа обеспечивает отсутствие в конечном результате Y коэффициента нормировки произведений Монтгомери по модулю р. Поскольку р является большим числом, то вычисление ДНК N относится к разряду сложных задач. Благодаря мультипликативной структуре ЦЧ , для расчета N удалось разработать метод, который весьма прост в реализации. Демонстрируемый далее подход к решению рассматриваемой задачи базируется на мультипликативно-субстрактивном способе приведения числа к остатку по модулю р с помощью Теоремы 2 и вычислительной схемы, конструируемой согласно сравнению вида (10) где u1, u2, … ul, v1,v2,…, vl - адаптивно выбираемые подходящие целочисленные множители. Запишем (10) в более наглядной и приемлемой для компьютерной реализации форме: (11) Процесс приведения ЦЧ к остатку по модулю р, осуществляемый по схеме (11), является рекурсивным. На каждой итерации этого процесса выполняется одна и та же типовая операция, которая состоит в выделении из множества элемента, принадлежащего также и к Zр . Поиск искомого значения параметра f требует детектирования знаков ЦЧ вида . (12) При использовании сравнительно небольших модулей МСС, например, m Î (215; 216) для выполнения указанных операций может быть применен упрощенный алгоритмический инструментарий, основанный на ИМФ чисел и Теореме 2. Пусть ЦЧ n и р заданы своими ИМФ в базисе М1: (13) (14) где и - интервальные индексы чисел n и p соответственно. Обозначим через код числа в МСС с модулями и его ИИ через . Для получения ИМФ ЦЧ вида (15) достаточно в (12) подставить (13)-(14) и затем, применяя лемму Эвклида, выполнить преобразование Из (15)-(16) следует, что (17) (18) Согласно теореме 2, число и его главный ИИ - см. (6), который, в соответствии с (18), вычисляется по формуле (19) имеют одинаковые знаки, если ≠ -1, то есть (20) Случай = -1 отвечает неопределенной ситуации при детектировании знака ЦЧ по правилу (20) с использованием (19). Возникновение указанной ситуации на той или иной итерации вычислительной схемы (11) маловероятно и не является критичным. На последующих итерациях возможная неопределенность устраняется с вероятностью, практически близкой к единице. Цель анализа знаков ЦЧ (12) состоит в отыскании значения параметра f Î Zm, которое обеспечивает выполнение условия: (21) Поскольку в (12) , то nm ≥ 0, а nm - mp = m(n - p) < 0. Следовательно, в всегда существует единственный элемент , удовлетворяющий (21). Мультипликативно-субстрактивный алгоритм расчета денормирующего коэффициента для криптографических RSA-преобразований На базе изложенных теоретико-методологических положений синтезирован алгоритм расчета денормирующего коэффициента, состоящий в нижеследующем. Параметры алгоритма: Модуль р криптосистемы. Набор М = {m1, m2, …, ml, ml+1, …, mk} из k 16-битовых простых модулей, который объединяет базисы M1 = {m1, m2, …, ml} и M2 = {ml+1, ml+2, …, mk} (1<l<k) МИМСС с диапазонами и , удовлетворяющие условиям Входные данные алгоритма: МК (p1, p2, …, pl) модуля р в базисе M1(pi = . Выходные данные: МК (n1, n2, …, nl, nl+1, …, nk) денормирующего коэффициента по полному базису . Предварительно получаемые данные: Коэффициенты нормировки цифр МК в базисе . Коэффициенты денормировки цифр МК в базисе . Коэффициенты для операции расширения операции расширения интервально-модулярного кода по базису М1 на модули ml, ml+1, …, mk: где . Таблицы TIIi интервального индекса, генерируемые по правилу: Тело алгоритма расчета денормирующего коэффициента. РДНК.1. Для модуля р = (p1, p2, …, pl-1, pl) криптосистемы сформировать интервально-модулярный код (p1, l-1, p2, l-1, …, pl-1, l-1, Il(p)) согласно формулам (см. (2)-(4)). РДНК.2. Сформировать интервально-модулярный код числа 1, где . РДНК.3. Выполнить операцию присвоения: РДНК.4. Положить f = 1. РДНК.5. Порядковому номеру текущего модуля базиса M1 = {m1, m2, …, ml} присвоить начальное значение: j = 1. РДНК.6. Применяя (22)-(23) при f = 0, рассчитать цифры интервально-модулярного кода ЦЧ : РДНК.7. Выполнить операцию присваивания: РДНК.8. Получить интервально-модулярный код (p1, l-1, p2, l-1, …, pl-1, l-1, Il(p)) разности , используя формулы типа (17)-(18): РДНК.9. Вычислить главный ИИ числа n: . РДНК.10. Если (ЦЧ ) или (случай неопределенности знака ЦЧ ), то при увеличить j на 1 () и перейти к РДНК.6, а по достижении равенства перейти к РДНК.12. РДНК.11. В случае , указывающем на , перейти к РДНК.7. РДНК.12. При инкрементировать S и перейти к РДНК.5. РДНК.13. Полученный интервально-модулярный код ЦЧ на модули согласно правилу: РДНК.14. Получить цифры МК числа N=n по модулям . РДНК. 15. Зафиксировать МК по полному базису M = {m1, m2, …, mk} в качестве искомого кода денормирующего коэффициента и завершить работу алгоритма. Общие временные затраты на реализацию приведенного алгоритма ограничены сверху оценкой , (22) где - длительности операций сложения и вычитания, умножения и деления 32-битовых ЦЧ соответственно. Пусть в качестве инструментальной базы для реализации схемы (11) используется ПВМ Intel Core i5, тактовая частота которого составляет 2,27 ГГц. Согласно тестам скоростных характеристик для данного процессора , , 5 нс. С учетом этого при р разрядностью 2462 бита оценка (22) дает мин. Время расчета ДНК N по схеме (11) сокращается в раз, если для поиска вместо простого перебора элементов последовательности 1, 2, …, m - 1 применить процедуру направленного поиска, основанную на делении отрезков, начиная с , пополам с последующим переходом к одному из получаемых отрезков. Заключение Основные результаты представленной разработки по проблематике создания и параметризации математического обеспечения криптографических RSA-преобразований, базирующихся на МА-алгоритмах умножения и возведения в степень по большим модулям кратко можно охарактеризовать следующим образом. 1. Рассмотрены важнейшие отличительные свойства МИМА на диапазонах больших чисел, обеспечивающие ей существенные преимущества над неизбыточными аналогами при выполнении криптографических преобразований в системах RSA и решении задач параметризации систем данного класса. Главным из таких преимуществ является снижение до предельно низкого уровня сложности и времени вычисления базовых интегральных характеристик МК - интервально-индексных характеристик, а также синтезированных на их основе процедур расширения кода и сравнения больших чисел. 2. На базе метода умножения с квадрированием, выполняемых по оптимизированной мультипликативной МИМА-схеме Монтгомери синтезирован алгоритм возведения в степень по большим модулям. Реализация криптографического RSA-преобразования по модулям разрядностью 1024…2048 бит с помощью этого алгоритма на ПЭВМ с процессором Intel Core i5 (тактовая частота 2,27 ГГц) в среднем занимает время порядка 0,56…5,67 с. 3. Проведена математическая формализация нового мультипликативно-субстрактивного метода вычисления денормирующего коэффициента для криптографических RSA-преобразований, осуществляемых применением МИМА. Теоретическую базу метода составляет аппарат ИМФ чисел, который позволяет определять знаки чисел в рамках реализуемой вычислительной схемы с помощью интервально-индексных характеристик по упрощенной процедуре. 4. Предложен эффективный алгоритм формирования минимально избыточного МК денормирующего коэффициента для криптографических RSA-преобразований. Разработанный алгоритм имеет рекурсивную организацию, требуя выполнения на каждой итерации простых операций умножения малоразрядных вычетов на основание МСС и серии вычитаний чисел в интервально-модулярном коде. На множестве модулей криптосистемы разрядности порядка 2462 бита время работы алгоритма не превышает 13,3 мин.

About the authors

Andrey Alekseevich Kolyada

Belarusian State University

Email: razan@tut.by

Petr Vasiljevich Kuchynski

Belarusian State University

Email: niipfp@bsu.by

Nikolay Ivanovich Chervyakov

North-Caucasus Federal University

Email: сhervyakov@yandex.ru

References

Supplementary files