Применение минимально избыточной модулярной арифметики для выполнения криптографических преобразований в системе RSA

В современных фундаментальных исследованиях и конкретных разработках в области защиты информации особое место занимают криптографические приложения на основе модулярной арифметики (МА) – арифметики модулярных систем счисления (МСС) [1-10]. Это обусловлено тем, что кодовый параллелизм модулярных вычислительных структур (МВС) обеспечивает им ряд существенных преимуществ над позиционными структурами при оперировании в диапазонах больших чисел.

Весьма показательную в этом отношении сферу применения МСС составляют алгоритмы умножения и возведения в степень по большим модулям, основанные на мультипликативной МА-схеме Монтгомери, которые активно используются для высокоскоростной реализации базовых криптографических преобразований в системах RSA [1-2; 5-8; 11-14].

Наиболее трудоемкую часть МА-алгоритмов умножения Монтгомери составляют операции расширения модулярного кода (МК). По уров- ню простоты процедур немодульных операций, включая расширение кода, среди известных версий МА на текущий момент выделяется так называемая минимально избыточная МА (МИМА) [15]. Синтезированная на базе МИМА оптимизированная модификация мультипликативной схемы Монтгомери для умножения по большим модулям позволяет сократить временные затраты на вычисление интегральных характеристик МК в операциях расширения до теоретического минимума.

Другим важным свойством указанной схемы является обеспечение замкнутости динамического числового диапазона для криптографических преобразований относительно умножения Монтгомери, благодаря чему отпадает необходимость в коррекции произведений при выполнении операций возведения в степень по системному модулю. Наряду с отмеченным при использовании минимально избыточной МСС (МИМСС) достигается также значительное упрощение решения сложных задач параметризации криптосистемы RSA. В частности, это относится к проблемам генерирования ключей шифрования и дешифрования, вычисления денормирующего коэффициента (ДНК) для процедуры возведения в степень по системному модулю и др.

В статье представлена минимально избыточная модулярная конфигурация алгоритма возведения в степень по большим модулям, который служит основой для реализации базовых преобразований в МИМА-криптосистеме RSA. При этом для синтезированного алгоритма предложены методологические и алгоритмические средства расчета ДНК. Для разработанных средств получены оценки эффективности.

Компьютерно-арифметическая база для криптографических преобразований по схеме RSA модулярного типа

Введем обозначения:

- Ш и Г«1 - наибольшее и наименьшее целые числа (ЦЧ), соответственно, не большее и не меньшее вещественной величины a ;

- Z_m = {О, 1,     т-1}, Z;,={-Lm/2_L -Lm/2J + 1,

Гт/21 -1} – множества наименьших неотрицательных и абсолютно наименьших вычетов по натуральному модулю ^ • |^ | m И \A | _m – элементы множеств ^m ^ ^ m-> сравнимые с A (в общем случае рациональным числом) по модулю m ;

- sn(a) – знаковая функция вида sn(a)=

О, если a > 0;

1, если a < 0,

- р – рабочий модуль криптосистемы (большое число).

В МСС с базисом Mi {/ni, mi, ..., mi}, состоящим из 1 > 1 попарно простых модулей (оснований), ЦЧ X представляется кодом (Xb X2 viX/)(Xz — I ^ \т, ?z —1>0 • Максимальная мощность множества D{M,} чисел X, на котором отображение -^(Zi^-,Z/) взаимно / однозначно, составляет Mi =Ib элементов. В этом случае D{M,} выполняет роль диапазона МСС. Обычно в качестве диапазона используют ^M, или

Из Китайской теоремы об остатках следует, что ЦЧ X может быть получено по своему МК (Zi,Z2>".,Zz) с помощью равенства х=^мц_х. Хи_г +Мм1,(Х} Z=1

(x,v-i = I ^/v-iX/l b

I                        lz»,'

/-1

где M_u__x = М_м / m,; М_м = П mj ; I, (X) - 7=1

интервальный индекс (ИИ) числа X [15].

При |D{M!}|

Теорема 1. О минимально избыточном модулярном кодировании. Для того чтобы в МСС с попарно простыми основаниями m_x, nil, ..., m, ИИ h(X} каждого элемента X= (ZpZ₂--^i) диапазона ^ж= {-M, -M + 1, ..., M - 1} ( M = m₀M_l-x; m₀ - вспомогательный модуль) полностью определялся компьютерным ИИ – вычетом /,(Л-) = |/,(Л-)| необходимо и достаточно, чтобы l-ое основание удовлетворяло условию: nii> 2m₀ + / - 2 (m₀ > / - 2). При этом для I№ верны расчетные соотношения:

1ЛХ) =

i№, 1ДХ)-т„

если 1ДХ} < m₀, если I, (X) > m₀;

1ДХ)-

I ТЛДхО !=1

Ri,l^i)= -m^Mj^i RiM) = \M;_1Zi\mi.

ml

Определение 1. Выражение (1) называется интервально-модулярной формой (ИМФ), а набор величин ^х^-..,Х1-\ЛДХД или (Zi,/-i > Z2./-1 ’•••’ Z/-i,/-i 1Л (^)) - интервально-модулярным кодом (ИМК) числа Х по базису Mi. В указанных формах ИМК допускается также использование вместо 1ДХ) характеристики 1ДХУ

Как следует из теоремы 1, переход от неизбыточной МСС с базисом M, и диапазоном ^M к МИМСС тем же базисом и диапазоном Z2M предельно упрощает вычисление базовой интегральной характеристики кода – ИИ У(Х) (см. (2)-(4)). Это приводит к адекватной оптимизации и немодульных процедур, базирующихся на ИМФ (1). В частности, для расширения минимально избыточного МК (МИМК) – (Xi^Xi’-’Xi) на модули некоторого базиса M2 = svmM,ml^,...,mk\y <к) достаточно согласно (2)-(4) вычислить ТО и затем воспользоваться расчетным соотношением:

IXH +MMX)

CM TOY

Аппарат ИМФ успешно может применяться и для синтеза других немодульных процедур, на- пример процедуры детектирования знака числа.

//(27) -1/; (Л")|

Наряду с компьютерным ИИ

введем другую евклидову составляющую

МХ)Ц.1ЛХ)/т^ ИИ TO, определяемую равенством

и называемую главным ИИ числа Х в МСС с базисом Mj. Справедливо [16-17] нижеследующее утверждение.

Теорема 2. Пусть в МСС с основаниями Ml, M₂М/ > / - 2 (Z > 2) целому числу Х отвечает код Mn-Ai) и пусть A (X) – главный ИИ данного ЦЧ. Знаки чисел Х и J\ (Х) совпадают при l = 2, а также при l > 2, если7,(X)^-1.

Применение теоремы 2 для определения знаков чисел в классе решаемых задач криптографических МА-приложений обеспечивает высокую эффективность.

Алгоритм возведения в степень по большому модулю для криптографических преобразований

Процедуры умножения Монтгомери предназначены в первую очередь для вычисления степеней натуральных чисел по рабочему модулю p криптосистемы RSA – целочисленных величин вида

Y=\X\PAX, e>lY

Исходя из сказанного эффективность разработанных мультипликативных алгоритмов, синтезированных на основе МИМА-схемы Монтгомери [14], так же, как и других алгоритмов умножения рассматриваемого класса, следует оценивать в контексте проблемы вычисления функции (7), которая описывает криптографические преобразования, выполняемые в системе RSA.

В данном случае основание степени (7) представляет собой число, отождествляемое в системе с шифруемым или дешифруемым сообщением, а показатель является ключом шифрования или дешифрования.

Примем в качестве основы для расчета степеней (7) традиционно применяемый метод умножения с квадрированием (square multiply method) [18], который предполагает двоичное кодирование показателя: e — (e/,-1 e/,-2 ... £0)2 (e/,-i = 1; b - разрядность ЦЧ e) и использует мультипликативную декомпозицию функции Y вида:

I X^е" (X^е- (X^е2 (...(Л^-²(Х^еи )²)²...)²)²)²| .

Применяемый для реализации (8) алгоритм умножения Монтгомери по модулю р работает в модулярном базисе M = {/«1, nil, ..., /И/, W/+1, m_to, ..., mA (1 < /< k), который объединяет два базиса: Mi = {mi, m₂, ..., mA и M₂ = {m_/+i, т_и,..., mA- При этом мультипликативная схема, положенная в основу базового способа умножения операндов A = (a_b a₂ , ..., a_k) и S = (Pi, P2 , -, Pk) по модулюP — (ль л₂ , •••, л_к) ((“/ =И1,_Й/’Р' =1⁸Ц’^л' ⁼И_т/ (^/=1’^л», описывается в виде операционной последовательности:

( С = А-В = (у1,/1,...,уА = =Wx\mxWi\mp-A«kPk\mY о=^л^за=(ki^il„„ 'V^V-V^L)

{^ = |- ^’ L (/ = \?1А; D = <3_V 3₂ ,.„3,.,, I, (DA;

D = (5_М,,8_М,5_к) = ЕСф; М,, М₂);       (9)

Г = (у₁₊х,у_м,-,УА = (уJ \y.i + 5j • Л,|_mМ-¹

U = i + U-A; у = ф,У2,-ФА = ЕСфм2,МА.

Корректность мультипликативной МИМА-схемы Монтгомери (9) обеспечивается в условиях нижеследующего утверждения.

Теорема 3. Пусть базисы Mi и М2 неизбыточной и минимально избыточной МСС, соответ- ственно, с диапазонами

ZM, и ^m6Mk-JM, ^т^ >тах{/-2,^-/-2}, к-\

тк > 2т0 + к - I - 2, Мк_х = П т;), совместно с модулем р, взаимно простым с Mt, удовлетворяют условию: 2p < min{m0 -Мм, т0МкЛ1МД и пусть операнды А, В мультипли- у = \лвмух I кативной операции ' I \р принадлежат множеству ^р . Тогда величина у, вычисляемая в рамках схемы (9), также является элементом множества ^2 ц . При этом у = / (mod р) и для верна формула У =y-(i-sn(/-ру)р.

Введем для операции умножения по модулю p, выполняемой согласно схеме (9), условное обозначение MM(A, B) (A и B – операнды, представленные в базовой МИМСС с основаниями т_А, т₂, ..., т_к\ Тогда на базе (8) с учетом теоремы 3 можно сформулировать нижеследующий алгоритм возведения в степень.

Входные данные: ^ = (Хъ /2, -■-, Ха) (X/ = И_т.) (* = ^))’ X&Z_2p; e = (e₆-i е_ь_₂... е₀)₂ (ей = !,/)>!).

Выходные данные: У= (^, ^ ..., Ы (^ = И _m (z — 1, к )), Y = Л mod р), У е Z_2p.

Предварительно вычисляемые данные:

N=\M² \=^_{,У₂,...,У_к) (у, =|7V|_m, (z = U)),

M, = П Ш; (1 < / < к).

Тело алгоритма возведения в степень по модулю p:

ВС.1. Получить МИМК (z;,z;,...,z:)44^ = MM(X,N).

ВС.2. Присвоить переменной Y=^v, ^2, ^А-) начальное значение Y = X.

ВС.3. Для всехj = b-2,b-3, ...,0 выполнить:

ВС.3A. Y=MM(Y, У).

ВС.3B. Eсли ej = 1, то найти Y = MM(Y,X\

ВС.4. Определить МИМК (Xi, X2, -.., Xa) искомого значения степени: Y = MM(Y, 1) и завершить работу алгоритма.

Временные затраты на реализацию алгоритма ВС.1…ВС.4 составляют ^bc^_ (b + A^i_-e)/_MM, где b-A

^N^=IL^ej- количество единиц в двоичном коде '      7=0

ЦЧ e; /мм – время операции умножения по модулю р.

Пусть b = r_p/2(r_p – разрядность (в битах) модуля р) и пусть количество единичных цифр в двоичном коде показателя степени (7) подчиняется равномерному закону распределения. Тогда ^.e - Ы2 и /вс⁼0,75г_р-/_Мм Для (1024…2048)-битовых р криптографическое RSA- преобразование с применением алгоритма ВС.1…ВС.4 на основе мультипликативной процедуры, реализующей схему Монтгомери (9), на ПЭВМ с процессором Intel Core i5 (тактовая частота 2,27 ГГц) в среднем занимает время порядка 0,56 … 5, 67 с.

Математическая формализация мультипликативно-субстрактивного метода вычисления денормирующего коэффициента для криптографических RSA-преобразований

Используемая в алгоритме ВС.1…ВС.4 константа ^ = |м_/²| обеспечивает отсутствие в конечном результате Y коэффициента |m_z *| нормировки произведений Монтгомери по модулю р. Поскольку р является большим числом, то вычисление ДНК N относится к разряду сложных задач. Благодаря мультипликативной структуре цч м для расчета N удалось разработать метод, который весьма прост в реализации. Демонстрируемый далее подход к решению рассматриваемой задачи базируется на мультипликатив-но-субстрактивном способе приведения числа M_t к остатку по модулю р с помощью теоремы 2 и вычислительной схемы, конструируемой согласно сравнению вида

— ихр^п2

— и2р^..^т1

— UjP^xm^ —vvpY^m[

= 7V(mod p),

где U\, U₂, ... Ut, V1,V2,---, V/ – адаптивно выбираемые подходящие целочисленные множители.

Запишем (10) в более наглядной и приемлемой для компьютерной реализации форме:

(Nq" = 1, ^^(l’ = №)J ■ m -u. ■ p (z = 1,/),

N^ = N^, N*^T) = кЬД • m₍ -v_rp (z = 1,/) )-

Процесс приведения ЦЧ M, к остатку по модулю р, осуществляемый по схеме (11), является рекурсивным. На каждой итерации этого процесса выполняется одна и та же типовая операция, которая состоит в выделении из множества

Nim) = ^n = nm - fp\f e Z,„} (n e Z_p;

meMv =\mv,m2,...,m1^b элемента, принадлежащего также и к '^р . Поиск искомого значения параметра f требует детектирования знаков ЦЧ вида

п'= пт-fp (f eZJ. (12)

При использовании сравнительно небольших модулей МСС, например т е (2¹⁵; 2¹⁶) , для выполнения указанных операций может быть применен упрощенный алгоритмический инструментарий, основанный на ИМФ чисел и теореме 2.

Пусть ЦЧ n и р заданы своими ИМФ в базисе Mi:

^{n =} lAi-Ai-i^+Mi-i'W (u_iH = k”_/¹_₁ -ц| ,Ц=Ы ),

Z-l

Р^М,м-7г,м+М,_А-1,(р)

Z=1

к^ =k,v-rk >^=H„)’

где I,(n) и I,(p) – интервальные индексы чиселпир, соответственно. Обозначим через (u'i,^,..., u',) код числа n в МСС с модулями т^тп-^...^ и его ИИ через 11 (11') . Для получения ИМФ ЦЧ вида

n'=i.Mt.H.

достаточно в (12) подставить (13)-(14) и затем, применяя лемму Евклида, выполнить преобразование

/ z-l                                      A н' = т\ ^Mia_x-u, ,., +M,_1-I, (n) -

V                              }

Д^м.^.т^кр.аАр)

+ МИ(1П-1,(11)- fli(p() =

об)

Из (15)-(16) следует, что

^U',M = |^m ^.м - A/./-I |™, G" = v-1), (17)

I,(n) = m-I,(n)-fI,(p)*

Согласно теореме 2, число n и его главный ИИ G, (n') – см. (6), который, в соответствии с (18), вычисляется по формуле

J^^i^lmA

имеют одинаковые знаки, если J, (ii') ^ -1, то есть sn(/7 ) = sn(Jz(/;')) (J^n') * -1).     (20)

Случай J! (n')="\ отвечает неопределенной ситуации при детектировании знака ЦЧ 11 по правилу (20) с использованием (19). Возникновение указанной ситуации на той или иной итерации вычислительной схемы (11) маловероятно и не является критичным. На последующих итерациях возможная неопределенность устраняется с вероятностью практически близкой к единице.

Цель анализа знаков ЦЧ (12) состоит в отыскании значения f параметра / e Z_m, которое обеспечивает выполнение условия:

nm — Jp>0;

nm -(f + \)p< 0.

Поскольку в (12) п&г_р, то nm > 0, a nm - mp = m(n — p)< 0. Следовательно, в ^/И всегда существует единственный элемент /, удовлетворяющий (21).

Мультипликативно-субстрактивный алгоритм расчета денормирующего коэффициента для криптографических RSA-преобразований

На базе изложенных теоретико-методологических положений синтезирован алгоритм расчета денормирующего коэффициента, состоящий в нижеследующем.

Параметры алгоритма:

Модуль р криптосистемы.

Набор М = {mi, mi, ..., mi, mi+i, • •■, mi) из k 16-битовых простых модулей, который объединяет базисы Mi = {mb mi, ..., m^ и M2 = (m!+i, mi+2, ..., mk) (Kl 2mо + / - 2, mk > 2m0 + к -1 - 2, m0 > max}/ - 2, к -1 - 2},

РДНК.2. Сформировать интервально-модулярный код (кс^км^/а)) числа 1, где

7/(1), если 7/(1)?7о, It (1) - Ш], если I] (1) > т0;

1ЛУ=УТП1Щ .

2^>0-Мщ, m₀-M_k__x /МД.

РДНК.3. Выполнить операцию присвоения:

Входные данные алгоритма: МК (Л1, л2, ...,

Л/) модуля р в базисе М1(л,= И,„. (^{/ = 1}’ ПУ

Выходные данные:

МК (vi, v₂, ..., V/, v_/+i, ..., v_k) денормирующего коэффициента ^ = lk| по полному базису ^4' l^lm/ ^ ^’^4

Предварительно получаемые данные:

Коэффициенты нормировки цифр МК в бази-сеМ,: ckkjJ (/ = 1,/-1).

Коэффициенты денормировки цифр МК в ба-зисем^с-Ы o = i,/-i).

Коэффициенты для операции расшире- ния интервально-модулярного кода по базису Mi на модули m^ m^y, m^ c<.iAm

Таблицы Till интервального индекса, генерируемые по правилу:

И— (ц./_1, ^₂,/-р •••; Ч-1.М ’ Л(^и))

и/,(!))=!.

РДНК.4. Положить f = 1.

РДНК.5. Порядковому номеру текущего модуля базиса Mi = {mi, т₂, ..., тД присвоить начальное значение: 7 ^- 1-

РДНК.6. Применяя (22)-(23) при /= О, рассчитать циы интервально-модулярного кода (^и'1,7-Р ^и2,/-1’ —’ ^и/-1,/-11 ^/(^и')) ЦЧ и =п-т_;;

ц'/_1 =|w •ц./_1| (/= !,/-!),

1Ли')-т;

■tM^yy^j-Ui.t-ilm^

Z=1

РДНК.7. Выполнить операцию присваивания:

77 = П ^ (Ц /.,, U2 /_,, ..., Uw, 1,(11)) = к./-1’ ^2,7-1’ "•’ Ц-1,7-1’ ^1^ )) •

TIRYz^Ru^-m-y^vX^

(% = 0,т, -1, z = 1,7 — 1),

TIIIUA = Ru (z) - K-1 • 4„, ^ = okTk).

РДНК.8. Получить интервально-модулярный код (ц,/-1’ ^2,7-1’ •■•’ Ц-1.7-1’ ПО¹^

^— (ц_?/-1, ^2,7-1’ •"’ Ц-1,7-1’ А(^))^—(^Л1- ^,-1’ ^Л2. 1-1, ..., л_м. м, 1,(р)) разности п =п' - р , используя формулы типа (17)-(18):

Тело алгоритма расчета денормирующего коэффициента.

РДНК.1. Для модуля P^- Ul, ^л2, •••, Л/./, Л/) криптосистемы сформировать интервально-модулярный код (Л1. 7-1, Л 2. l-l, • • •, ^/-1, l-l, У(рУ согласно формулам

л;./_1=|с/-л;.|   (/ = 1,/-1),

I ^ = . У ^ если У ^Р">< т0 ’

Il (^) - m_t, если //(/?)>т₀;

1М =

Ъп1\иД

7=1

(см. (2)-(4)).

пч

и;./ч =|и;.,/_1-л/;/_1|т (/= i,/-i),

РДНК.9. Вычислить главный ИИ числа n: Ji^Ah^lm^.

РДНК.10. Если J_l(n')<-\ (ЦЧ 11<О) или ^(»')=-1 (случай неопределенности знака ЦЧ ^п')’ то при j ф / увеличить j на 1 (j=j^) и перейти к РДНК.6, а по достижении равенства j = 1 перейти к РДНК.12.

РДНК.11. В случае J](n')>0, указывающем на iT >0, перейти к РДНК.7.

РДНК.12. При S = 2 инкрементировать S (5 = 5 + 1) и перейти к РДНК.5.

РДНК.13. Полученный интервально-модулярный код (ц,/-1’ ^2,/-I’ •••’ Ц-1./-1’ Л(^и)) ЦЧ ^^ = |м_/²| на модули _mi,m_ux,...,m_k согласно правилу:

РДНК.14. Получить цифры МК числа N=n по модулям ™v m₂, .„, m_M : ц. = С,, -ц, J

РДНК. 15. Зафиксировать МК (u_vu₂,..„ u_k) по полному базису M = {mi, m₂, •••, ^mk^ в качестве искомого кода денормирующего коэффициента ^ = |м_/²| и завершить работу алгоритма.

Общие временные затраты на реализацию приведенного алгоритма ограничены сверху оценкой

^РДНК.МАКС = 2^ (m; - 1)((3/ - 1)(^сл + ^УМ ) + ^ ' ^ДЕЛ ’ (22) Z=1

где ^СЛ ’ ^УМ И ^ДЕЛ – длительности операций сложения и вычитания, умножения и деления 32-битовых ЦЧ соответственно. Пусть в качестве инструментальной базы для реализации схемы (11) используется ПВМ Intel Core i5, тактовая частота которого составляет 2,27 ГГц. Согласнотестамско- ростных характеристик для данного процессора ^ум >”"гсл’ ^дел > 2,7?ум > 22,5?сл , ^сл —5 нс. С учетом этого при р разрядностью 2462 бита оценка (22) дает ^РДНК, МАКС ^ 13,25 мин. Время расчета ДНК N по схеме (11) сокращается в

^((т, -1)/Plog₂т^ = — ^(m, -1) раз, если

'='                   „         16 '=1

для поиска / G Zm вместо простого перебора элементов последовательности 1, 2, ..., т - 1

применить процедуру направленного поиска, основанную на делении отрезков, начиная с [1; /и-1], пополам с последующим переходом к одному из получаемых отрезков.

Основные результаты представленной разработки по проблематике создания и параметризации математического обеспечения криптографических RSA-преобразований, базирующихся на МА-алгоритмах умножения и возведения в степень по большим модулям, кратко можно охарактеризовать следующим образом.

• 1.    Рассмотрены важнейшие отличительные свойства МИМА на диапазонах больших чисел, обеспечивающие ей существенные преимущества над неизбыточными аналогами при выполнении криптографических преобразований в системах RSA и решении задач параметризации систем данного класса. Главным из таких преимуществ является снижение до предельно низкого уровня сложности и времени вычисления базовых интегральных характеристик МК – интервальноиндексных характеристик, а также синтезированных на их основе процедур расширения кода и сравнения больших чисел.

• 2.    На базе метода умножения с квадриро-ванием, выполняемых по оптимизированной мультипликативной МИМА-схеме Монтгомери, синтезирован алгоритм возведения в степень по большим модулям. Реализация криптографического RSA-преобразования по модулям разрядностью 1024…2048 бит с помощью этого алгоритма на ПЭВМ с процессором Intel Core i5 (тактовая частота 2,27 ГГц) в среднем занимает время порядка 0,56…5,67 с.

• 3.    Проведена математическая формализация нового мультипликативно-субстрактивного метода вычисления денормирующего коэффициента для криптографических RSA-преобразований, осуществляемых применением МИМА. Теоретическую базу метода составляет аппарат ИМФ чисел, который позволяет определять знаки чисел в рамках реализуемой вычислительной схемы с помощью интервально-индексных характеристик по упрощенной процедуре.

• 4.    Предложен эффективный алгоритм формирования минимально избыточного МК денормирующего коэффициента для криптографических RSA-преобразований. Разработанный алгоритм имеет рекурсивную организацию, требуя выполнения на каждой итерации простых операций умножения малоразрядных вычетов на основание МСС и серии вычитаний чисел в интервальномодулярном коде. На множестве модулей криптосистемы разрядности порядка 2462 бита время работы алгоритма не превышает 13,3 мин.

Kolyada A.A.1, Kuchynski P.V.1, Chervyakov N.I.2

1Institute of Applied Physics Problems of А.N. Sevchenko Belarusian State University, Minsk, Belarus 2North-Caucasus Federal University, Stavropol, Russia Federation