Компактная реализация функции обращения элемента в конечном поле F216 | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/44

Компактная реализация функции обращения элемента в конечном поле F216

Предложено расширение известного метода поиска компактной реализации функции обращения элемента в конечном поле F28 на случай поля F216. Получена верхняя оценка на размер схемы, выполняющей взятие обратного элемента в поле F216, и доказана теорема о том, что существует реализация функции обращения элемента в поле F216, использующая для вычисления не больше 336 XOR и 189 AND, или 777 GE.

A compact realisation of the multiplicative inverse function in the finite field F216.pdf Легковесная криптография занимается вопросами компактной реализации шифров и их компонент, в частности S-блоков, главных нелинейных преобразований блочного шифра. S-блок - это, как правило, взаимно однозначная векторная булева функция, которую можно задать как функцию над конечным полем порядка 2n. Одной из самых простых, но тем не менее криптографически хороших функций для использования в качестве S-блока является функция обращения элемента в поле Галуа. Такая функция является, например, основой S-блока криптосистемы AES. В [1,2] предлагается компактная реализация функции обращения над полем F28, опирающаяся на идею Винсента Рэймена [3] представления элемента поля как линейного многочлена над полем меньшей размерности и метод Акиры Сато [4], позволяющий ещё более компактно реализовать такую функцию. В данной работе рассматривается расширение данной реализации на поле большей размерности и даётся оценка на размер схемы, выполняющей взятие обратного элемента в поле F216. Обращение элементов в поле F2n напрямую, как многочленов степени n - 1 по модулю многочлена степени n, - непростая задача. Но, как показано в [3], обратить элемент как многочлен первой степени по модулю многочлена второй степени сравнительно легко. Для этого представим элемент g Е F2n как линейный многочлен от некоторой формальной переменной у над F2n-1: g = YiУ + Yo, Yo,Yi Е Fan-1, с умножением по модулю неприводимого многочлена r(y) = y2 + ту + v, т, v Е F2n-1. После перехода к нормальному базису [Y2n , Y] поля F2n /F2n-1, где Y, Y2 - корни r(y) = у2 + ту + v = (у + Y)(у + Y2п ), получим g = YiY2n-1 + YoY. Тогда т = Y2n 1 + Y = TrF2n/F2n-1 (Y) -след, а v = Y2n 1Y = NF2n/F2n-1 (Y) -норма Y. Выразив аналогичным образом элементы поля F216 через многочлены над F28, а элементы этого поля - через многочлены над F24 и так далее, можно значительно упростить вычисления и находить обратный элемент в поле F216 следующим способом. Утверждение 1. Пусть x = x1K256 + x0K, где x0, x1 Е F216; [K256, K] -нормальный базис поля F216 /F28; t = K256+K - след K; n = K256K - норма K. Тогда обратный элемент равен у = x-1 = y1K256 + y0K, где yi = [x1Xot2 + (x1 + x0 )n]-1Xo, yo = [x1xot2 + (x1 + x0 )n]-1x1. Можно сделать вычисления ещё более компактными, оптимизируя их схему. Во-первых, можно найти такие неприводимые многочлены, след которых равен единице. Это немного сократит сложность вычислений, поэтому будем считать, что всюду далее след равен единице. Во-вторых, Сато Акира [4] предлагает реорганизовать вычисления так, что возможно вынести часто встречающиеся выражения в отдельные переменные. Здесь и далее ф и 0 обозначают сложение и умножение в поле. Утверждение 2. Пусть x Е F2i6, x = x1K256 + x0K, x1,x0 E F28, [K256,K] - нормальный базис поля F2i6 /F28; n = K 256 K - норма K. Тогда x 1 можно найти следующим образом: Ф = [n 0 (x1 ф xo)2 ф (x1 0 xo)]-1, x-1 = [Ф 0 xo]K256 + [Ф 0 x1]K. Можно заметить, что часто мы умножаем не два произвольных элемента поля, а некоторый элемент поля на известную константу. Если использовать для этой операции собственную схему и наложить некоторые ограничения на выбор констант, возможна ещё более компактная реализация функции обращения элемента в поле Галуа. В результате получены оценки сложности вычислений для функции обращения элемента в поле F2i6 и всех её составляющих. Теорема 1. Существует реализация функции обращения элемента в поле F2i6, использующая для вычисления не больше 336 XOR и 189 AND, или 777 GE.

Ключевые слова

блочный шифр, поле Галуа, функция обращения элемента в поле Галуа, легковесная криптография, gate equivalent (GE), block cipher, Galois field, Galois field multiplicative inverse function, lightweight cryptography, gate equivalent (GE)

Авторы

ФИООрганизацияДополнительноE-mail
Кокошинский Игорь ЕвгеньевичНовосибирский государственный университетстудент ММФkokoshinskiy.igor@gmail.com
Всего: 1

Ссылки

Canright D. A Very Compact Rijndael S-box. Naval Postgraduate School Technical Report: NPS-MA-05-001, 2004.
Canright D. A very compact S-box for AES // LNCS. 2005. V. 3659. P. 440-455.
Rijmen V. Efficient Implementation of the Rijndael S-box. Katholieke Universiteit Leuven, Dept. ESAT, Belgium, 2001.
Satoh A., Morioka S., Takano K., and Munetoh S. A compact Rijndael hardware architecture with S-box optimization // ASIACRYPT 2001. LNCS. 2001. V.2248. P. 239-254.
 Компактная реализация функции обращения элемента в конечном поле F216 | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/44

Компактная реализация функции обращения элемента в конечном поле F216 | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/44