MODULAR ROUNDING NUMBERS BY THE ELLIPTIC CURVE FIELD’S MODULE DURING CRYPTOGRAPHIC TRANSFORMATIONS IN THE SYSTEM OF RESIDUAL CLASSES

Abstract

This article offers a solution for the problem of defining number’s modular reduction by the elliptic curve field’s module, calculated for rounding intermediate results of cryptographic transformations in the system of residual classes.

Full Text

Введение. Постановка задачи Использование модулярной арифметики и системы остаточных классов (СОК) - одно из наиболее перспективных направлений в области оптимизации времени выполнения сложных математических расчетов. Многие трудоемкие вычисления, которые раньше приходилось проводить в длинной арифметике естественным образом можно заменить на модулярные, за счет чего существенно сократится размерность операндов и уменьшится время их обработки. Среди прикладных областей для применения СОК особое место занимает защита информации с ее не теряющей актуальности проблемой повышения качества и скорости выполнения криптографических преобразований. Использование СОК в криптографии для распараллеливания криптографического вычислительного процесса связано с необходимостью разработки эффективного метода округления результатов промежуточных операций по модулю большого конечного поля Fp, в котором указанные операции должны выполняться. Эллиптическая криптография и модулярная арифметика В современном мире наиболее эффективными считаются криптосистемы, построенные на точках эллиптической кривой (ЭК). Это обусловлено тем, что ЭК обеспечивает максимально возможную надежность СКЗИ на один бит размера задачи. Сравнительная оценка надежности криптосистем при различной длине ключей представлена Червяков Н.И. в работе [1]. На основе использования ЭК в криптографии разработан действующий в РФ ГОСТ Р 34.10-2012. При использовании уравнения ЭК Е: у2 = х3 + ax+b(modp), а,Ъ е F (1) над большим конечным полем F с дискриминантом (4а3+2762)*0 для реализации любого известного алгоритма криптографических преобразований (например, по схеме Эль-Гамаля) требуется выполнять операции сложения точек P и Q ЭК вида Я(хъ ,у3) = Р(хг ,у{) + Q(x2 ,у2), по общим формулам: - при Р Ф ±Q у,-У V*2' v2, (2а) Уз = ~У\ + Уг У1 (*i -*3). - при P-Q JC, = Уз ^Зх2 +оЛ --- -х, -х7, Зх?+а , . -У1+--(*, ~х3). 2ji (26) Поскольку при выполнении арифметических операций по формулам (2) над большим конечным полем Fp потребуется выполнение трудоемкой операции инверсии, то данный метод предлагается заменить альтернативными преобразованиями в проективной системе координат (X,Y,Z) по формулам: - при Р Ф ±Q хъ =v7v12, Уз = v6 (viov3 - vu) ~ vi ivi» (3) z3 =vnv5, «Инфокоммуникационные технологии» Том 12, № 2, 2014 Лавриненко А.Н., Червяков Н.И. 5 где *1 = ^2> V2 = V3 - x1z2, V4 = x2zj, V5 =Z1Z2> V6 II to ] < II < -U -v3, V8 = V4+V3> V9 2 = V6 , (S > II о Vn = :v73 =V7 -v10, V12 II < 40 Ul 00 0 1 - при P-Q где *3 = 2V11V4 .Уз =v6(4v7-vn)-8v2vg , z3 = 8v9 Vi = *Ду2 =y*,v3 = zj2; П =yizi’vs =xlyl; v6 = av3 +3v15 v7 = v4v5, v8 = v42; v9 = v4v8, v10 = v62, vn = v10 -8v7, a - коэффициент из E в (1); />(х1,yx,z^), Q(x2,y2,z2), R{x3,y3,z3) - точки ЭК в проективной системе координат [2]. Вычисления по формулам (3) целесообразнее проводить в модулярной арифметике СОК. Для любых двух чисел а и b в СОК справедливо (4) а°Ь = {{ах ° Д)тос1 рх,(а2 ° fl2)modp2, •••>(«„ ° fin)Ш0&Рп)> где (° )- любая модульная операция («+», «-», «*» - все кроме деления), через «г- и Д обозначены цифры СОК-представления чисел а и b по соответствующим модулям Pi системы, n - размер- П ность СОК, q = Pi - диапазон вычислений 1=1 выбранной СОК. Эффективность применения СОК для вычислений была показана в работе [3]. Таким образом, основные криптографические вычисления с помощью (3) сводятся к модулярным. Проводя арифметические операции над координатами точек ЭК (1) по формулам (3), мы должны выполнять редукцию по модулю поля ЭК на каждом этапе промежуточных вычислений, так как в противном случае будет происходить переполнение динамического диапазона СОК q и искажение конечного результата. Как показано в работе [4] наиболее эффективной является редукция средствами СОК и предпочтительнее, чтобы модуль p поля ЭК (1) был большим простым числом. Редукция методами СОК задача не из легких, однако нас интересуют только методы вычисления остатка от деления двух чисел в СОК, не связанные с реальной необходимостью выполнения процедуры деления. Поскольку все промежуточные результаты криптографических вычислений не должны превышать p, то для того, чтобы в вычислениях по формулам (3) не происходило переполнение диапазона СОК при выполнении одной бинарной арифметической операции, необходимо обеспечить выполнение условия (5) где q - диапазон СОК, p - модуль поля ЭК (1). Поскольку модуль p в соответствии с ГОСТ Р 34.10-2012 должен быть большим простым числом, то использование методов расширения остаточного представления числа в СОК в конечном итоге окажется малоэффективным. Для успешного выполнения модулярной редукции двух чисел в СОК нам потребуется разработать модулярный метод округления, позволяющий эффективно вычислять искомый остаток от деления. Модулярный алгоритм округления двух чисел в СОК Итак, нам необходимо вычислить модулярный остаток от деления числа А = (а1,а2,...,ап) , представленного в СОК с диапазоном q, по модулю поля p ЭК, где p и q удовлетворяют условию (5). Воспользуемся тем обстоятельством, что модуль p поля ЭК (1) - большое простое число, заранее известное и взаимно простое со всеми модуля ми Pi выбранной СОК, где q = pt,i = l.Jt ;=i - ее диапазон; n - размерность. При этом модули р. , которые также являются простыми числами, напротив, должны быть числами небольшой или относительно малой размерности, с тем чтобы выполнялось условие малой размерности компонент операндов по любому произвольно выбранному каналу СОК, и тем самым обеспечивалась высокая скорость обработки результатов промежуточных вычислений. Будем считать, что промежуточный результат вычислений по формулам (3) записан в числе A. Разделив поразрядно A на p, получим «Инфокоммуникационные технологии» Том 12, № 2, 2014 6 Лавриненко А.Н., Червяков Н.И. A ps + t + kq t + kq а = - = --- = s +-- Р Р Р (6) где a - формальное частное от деления; s = [A!p] - реальное частное от деления; t - искомый модулярный остаток; q - диапазон СОК; к - целое. Таким образом, t + kq делится на p и t + kq-р или t-p-kq. (7) Поскольку искомый остаток t не должен превышать p, то без потери общности можно взять модулярный вычет от обеих частей (7): t = l-k\q\p(vao6.p). (8) Ввиду того, что числа p и q заранее известны, то вычисление |<у| можно провести заблаговременно, и это не представляет серьезных проблем, даже ввиду большой размерности операндов. Кроме того, зная заранее соотношение чисел \q\p и p, можно предварительно рассчитать, какое ко -личество интервалов длиной \q\p содержится в p, и использовать это для предотвращения выхода числа за границы p при вычислении произведения к\а\ . Что касается величины к, то, как по-I I р казано в работе [5], на базе теории рангов можно считать, что к - это разница в рангах числа ра и фактического делимого. Иными словами к = ГА~Гра- (9) Очевидно, что для удобства дальнейших вычислений по формулам (3) все вычисления по формуле (8) необходимо вести в исходной СОК с диапазоном q. Процесс определения формального частного а состоит в выполнении операции поразрядного деления на p в СОК, что так же несложно организовать, учитывая, что p заранее известно, и поэтому получить представление p и р 1 в СОК можно заблаговременно, используя стандартные вычислительные средства. Для окончательного раскрытия неопределенности в вопросе эффективного определения модулярного остатка в СОК согласно (8) следует подобрать эффективный метод определения ранга числа. Воспользуемся приближенным методом определения ранга числа в СОК, эффективность которого была теоретически и практически показана в работе [6]. Для этой цели в выбранной СОК следует заранее запастись вещественными w\ к.=-константами ' р ’ где Qi =QIPi,i = \.n. Тогда, как показано в [8], получить ранг числа гА можно, вычислив целую часть выражения ХМ, • Поскольку нас интересует только вычисление ранга числа, то размерность хранимых констант kt можно заранее ограничить, исходя из теоретических знаний о вычислительных погрешностях, возникающих при выполнении элементарных арифметических операций. Ввиду того, что в операции вычисления ранга числа используются умножение целого числа ctj на константу kt и попарное сложение полученных произведений, а в конечном итоге должен получиться целочисленный результат, то достаточно в записи констант к{ в десятичной части числа оставлять столько разрядов, сколько содержится в соответствующем целочисленном pt, плюс один-два дополнительных разряда, которые будут использоваться при округлении промежуточных результатов. Это существенно сократит размерность операндов при вычислении ранга числа и повысит скорость выполнения данной операции. Выводы Использование модулярной арифметики в эллиптической криптографии открывает новые горизонты для повышения скорости выполнения криптографических преобразований. Реализация механизма криптографических вычислений средствами СОК влечет необходимость разработки эффективного механизма редукции результатов промежуточных вычислений по модулю p поля ЭК. Очевидно, что редукцию двух чисел в СОК следует также выполнять средствами СОК, для того чтобы исходные данные, промежуточные вычисления и результат редукции были представлены в модулярной форме. Таким образом, удастся избежать дополнительных операций по переводу чисел в СОК и, следовательно, не нарушится общая математическая модель модулярных криптографических вычислений по формулам (3). В работе представлен специализированный метод вычисления модулярного остатка в СОК по большому заранее известному модулю p. Указанный метод может быть обобщен для любого заранее известного и неизвестного модуля p. При этом, если этот модуль будет числом малой размерности, то предпочтительнее использовать метод расширения остаточного представления числа, показанный в [4; 7], а если число p достаточно большое, то эффективнее будет использовать метод на основе формулы (8). 1=1 «Инфокоммуникационные технологии» Том 12, № 2, 2014 Лавриненко А.Н., Червяков Н.И. 7 Кроме того, метод расширения остаточного представления числа может понадобиться и в случае, если p будет составное, при условии, что в числе его сомножителей окажутся числа pt. В общем же случае если p заранее неизвестно, то потребуется еще одна трудоемкая операция вычисления мультипликативной инверсии \р 1 . Тем не менее предложенный I I q метод в целом является универсальным.