УСТРОЙСТВО ДЛЯ ПОСТРОЕНИЯ ОРТОМОРФИЗМОВ, ИСПОЛЬЗУЮЩЕЕ ПАРНЫЕ РАЗНОСТИ Российский патент 2017 года по МПК G06F21/60 G06F17/00 

1. ОБЛАСТЬ ПРИМЕНЕНИЯ

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

Понятие ортоморфизма было впервые введено в работах [21, 22], детально изучено в работах [24, 25], получило развитие после доклада [23]. Ортоморфизмы находят широкое применение во многих криптографических конструкциях [16, 17]. Их изучение тесно связано с задачами построения кодов аутентификации [7, 12], систем ортогональных латинских квадратов [10, 11, 14] и квазигрупп [3, 4]. В основе проекта американского стандарта хеш-функции, участника конкурса SHA-3, Edon-R [20] лежит использование квазигрупп и двух ортогональных латинских квадратов 8-го порядка. А некоторые атаки на блочные шифрсистемы существенно используют свойство неравномерности распределения суммы входных и выходных значений подстановки [13, 15, 18, 26].

2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ

В настоящем описании используются следующие обозначения:

V_n - векторное пространство размерности n над полем GF(2), ;

S(V_n) - симметрическая группа;

F_n,m - множество всех отображений из V_n в V_m;

^_ кольцо вычетов по модулю 2ⁿ;

- биективное отображение, сопоставляющее элементу u=(u_n-1, …, u₀) векторного пространства V_n элемент u=u₀+u₁⋅2+u₂⋅2²+…+u_n-1⋅2^n-1 кольца ;

- отображение, обратное к отображению ϕ;

- бинарная операция на V_n,, заданная правилом: для u, ν∈V_n справедливо равенство ;

- бинарная операция покомпонентного сложения по модулю 2 элементов векторного пространства V_n;

- бинарная операция умножения двух элементов V_n, заданная правилом: для u=(u_n-1, …, u0), ν=(ν_n-1, …, ν₀)∈V_n справедливо равенство ;

В настоящем описании используются следующие термины с соответствующими определениями.

Определение 1. Подстановка g∈S(G) называется ортоморфизмом группы G, если отображение p: G→G, определяемое условием p(x)=x^-1g(x), ∀x∈G, является подстановкой из S(G).

Упорядоченное множество значений отображения p будем называть строкой разностей подстановки g.

Определение 2. Разностной характеристикой подстановки g∈S(V_n) относительно операций называется величина ,

,

где , а вероятность вычисляется при случайном равновероятном выборе x∈V_n. Матрицу размеров (2ⁿ-1)×(2ⁿ-1), составленную из коэффициентов , будем называть разностной матрицей отображения g относительно операций .

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

Определение 3. Линейной характеристикой δ(g) подстановки g∈S(V_n) называется величина δ(g),

,

где δ_α,β(g) - спектральный коэффициент подстановки g (преобладание линейного статистического аналога), который задается парой функций . Величина преобладания вычисляется по формуле при x∈V_n, выбираемом случайно равновероятно. Матрицу размеров (2ⁿ-1)×(2ⁿ-1), составленную из коэффициентов |δ_α,β(g)|, будем называть матрицей модулей спектральных коэффициентов отображения g.

Повышение стойкости средств криптографической защиты относительно линейного метода криптографического анализа требует минимизации значения δ(g).

Определение 4. Обобщенной степенью нелинейности подстановки g∈S(V_n) называется величина ,

,

где , a deg обозначает степень нелинейности многочлена Жегалкина булевой функции.

Определение 5. Размерностью пространства полиномиальных соотношений степени не выше i>0 подстановки g∈S(V_n) называется число r⁽ⁱ⁾(g),

,

где

.

Определение 6. Минимальной степенью полиномиального соотношения подстановки g∈S(V_n) назовем число r(g),

r(g)=min{i|r⁽ⁱ⁾(g)>0}.

Замечание 7. Для подстановок g∈S(V₈) в силу неравенства имеет место неравенство r(g)≤3.

Повышение стойкости средств криптографической защиты относительно методов линеаризации требует минимизации величин r⁽ⁱ⁾(g), i=r(g), …, n и максимизации величин и r(g).

3. УРОВЕНЬ ТЕХНИКИ

Среди известных подходов к синтезу ортоморфизмов, действующих на векторном пространстве V_n достаточно большой размерности n(n≥6), можно выделить следующие.

Первый подход заключается в случайном поиске ортоморфизма g∈S(V_n) среди представителей некоторого известного класса (например, класса кусочно-линейных подстановок [2, 9]), содержащего существенно большую, относительно всей симметрической группы, долю подстановок, обладающих этим свойством. Подход удобен тем, что в некоторых известных классах подстановок сравнительно просто найти представителя с высокими значениями криптографических параметров. Недостатком подхода является наличие алгебраической структуры подстановок.

Второй подход состоит в использовании известных конструкций (например, двухраундовой схемы Фейстеля [19]), для которых доказано, что получаемые подстановки являются ортоморфизмами. Недостатком такого подхода являются низкие значения основных криптографических параметров и аналитического строения получаемых подстановок.

Третий подход состоит в случайном выборе линейного ортоморфизма g∈S(V_n). Подход заключается в генерации случайной двоичной матрицы A_n×n, вычислении матрицы , где E_n×n - единичная матрица, проверки обратимости матриц A_n×n и B_n×n. Линейность построенных подстановок g резко ограничивает возможность их использования в криптографических приложениях.

Общим недостатком представленных подходов является низкая степень полиномиальных соотношений получаемых подстановок (низкое значение параметра r_g).

4. УСТРОЙСТВО ДЛЯ ПОСТРОЕНИЯ ОРТОМОРФИЗМОВ, ИСПОЛЬЗУЮЩЕЕ ПАРНЫЕ РАЗНОСТИ

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

Для достижения цели предложено устройство, использующее парные разности.

Устройство для построения ортоморфизмов, использующее парные разности (фиг. 1 приложений), содержит:

- блок выбора режима - 0;

- управляющий блок - 1;

- блок умножения подстановки на транспозицию - 2;

- оперативное запоминающее устройство (ОЗУ) - 3.

Блок выбора режима 0 состоит из переключателя и позволяет пользователю определить используемую группу .

Управляющий блок 1 производит выборку, сравнение, изменение содержимого оперативного запоминающего устройства, принимает решение об остановке работы устройства или продолжении его работы.

Блок умножения подстановки на транспозицию 2 реализует стандартное произведение преобразований путем последовательного их выполнения.

Оперативное запоминающее устройство 3 выполняет сохранение текущей подстановки.

Устройство для построения ортоморфизмов, использующее парные разности, работает следующим образом.

На вход устройства поступает некоторый начальный ортоморфизм g₀∈S(G), с вычисленной строкой разностей p, и произвольная транспозиция (x,y), x,y∈G, x<y.

1. Управляющий блок 1 выполняет последовательность действий:

1.1. вычисляет значения p₀=x^-1*g₀(x), p₁=y^-1*g₀(y) и записывает эти значения в оперативное запоминающее устройство 3;

1.2. передает ортоморфизм g₀ и транспозицию (x,y) в блок умножения подстановки на транспозицию 2, который реализует стандартное произведение преобразований путем последовательного их выполнения:

g=(x,y)⋅g₀;

1.3. полученная подстановка g записывается в ОЗУ 3.

2. Управляющий блок 1 выполняет последовательность действий:

2.1. осуществляет поиск в ОЗУ 3 элементов x',y'∈G, x'≠x, y'≠y со свойством

p(x')=(x')^-1*g(x')=x^-1*g(x)=p(x),

p(y')=(y')^-1*g(y')=y^-1*g(y)=p(y);

2.2. передает подстановку g и транспозицию (x',y') из ОЗУ 3 в блок умножения подстановки на транспозицию 2;

2.3. вычисляет значения p[x']=(y')^-1*g(x') и p[y']=(x')^-1*g(y');

3. Управляющий блок 1 записывает g в ОЗУ 3 и сравнивает полученные значения p[x'], p[y'] со значениями p₀, p₁,

- если p[x']=p₀ или p[x']=p₁, устройство заканчивает свою работу, на выход подается подстановка g;

- в противном случае, положить x=x', y=y' и устройство повторяет цикл операций, начиная с шага 2.

Работу устройства иллюстрирует следующий пример.

Пример. Переключатель блока 0 выставлен в позицию .

Вход: ортоморфизм g₀∈S(V₄):

транспозиция (2,9).

Выход: ортоморфизм g∈S(V₄):

Реализация устройства может быть аппаратной, программной или аппаратно-программной.

5. ДОСТИГНУТЫЕ ТЕХНИЧЕСКИЕ РЕЗУЛЬТАТЫ

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

Фиг. 2 приложений содержит ортоморфизм g'∈S(V₈), построенный применением описанного устройства к ортоморфизму g∈S(V₈) представителю класса кусочно-линейных подстановок [2, 9]. Из таблицы следует, что g' имеет актуальные (как в государственном стандарте Республики Беларусь «BelT» [1, 8]) значения основных криптографических параметров , , , r(g')=3, r⁽³⁾(g')=441 и в отличие от исходного ортоморфизма не имеет квадратичных соотношений.

Фиг. 3 приложений содержит ортоморфизм g'∈S(V₈), построенный применением описанного устройства к некоторому, случайно выбранному, линейному ортоморфизму g∈S(V₈). Из таблицы следует, что g' имеет актуальные (как в национальных стандартах РФ ГОСТ Р 34.11-2015 [5] и ГОСТ P 34.12-2012 [6]) значения основных криптографических параметров , , , r(g')=3, r⁽³⁾(g')=441.

Устройство для построения ортоморфизмов было также применено более чем к сотне случайно выработанных линейных ортоморфизмов g∈S(V₈). Каждый случай применения устройства позволил построить большое число новых аффинно неэквивалентных ортоморфизмов g∈S(V₈) со следующими значениями криптографических параметров

, , , r(g')=3, r⁽³⁾(g')=441.

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

ЛИТЕРАТУРА

[1] Агиевич С.В., Галинский В.А., Микулич Н.Д., Харин Ю.С. Алгоритм блочного шифрования BelT.

[2] Бугров А.Д. Кусочно-аффинные подстановки конечных полей. Прикладная дискретная математика, 2015, №4(30), сс. 5-23.

[3] Глухов М.М. О методах построения систем ортогональных квазигрупп с использованием групп. Математические вопросы криптографии, 2011, т. 2, №4, сс. 5-24.

[4] Глухов М.М. О применениях квазигрупп в криптографии. Прикладная дискретная математика, 2008, №2(2), сс. 28-32.

[5] ГОСТ Р 34.12-2015 Информационная технология. Криптографическая защита информации. Блочные шифры. - Москва: Стандартинформ, 2015.

[6] ГОСТ Р 34.11-2012 Информационная технология. Криптографическая защита информации. Функция хэширования. - Москва: Стандартинформ, 2012.

[7] Зубов А.Ю. Математика кодов аутентификации. М.: Гелиос АРВ, 2007, 480 с.

[8] СТБ 34.101.31-2011 Информационные технологии. Защита информации. Криптографические алгоритмы шифрования и контроля целостности. - Минск: Госстандарт, 2011.

[9] Тришин А.Е. О показателе нелинейности кусочно-линейных подстановок аддитивной группы поля . Прикладная дискретная математика, 2015, №4(30), сс. 32-42.

[10] Тришин А.Е. Способ построения ортогональных латинских квадратов на основе подстановочных двучленов конечных полей. Тезисы доклада Научный журнал «Обозрение прикладной и промышленной математики». М.: ТВП, 2008, Т. 15, №4.

[11] Тужилин М.Э. Латинские квадраты и их применение в криптографии. Прикладная дискретная математика. Приложение, 2012, №3(17), сс. 47-52.

[12] Черемушкин А.В. Криптографические протоколы. Основные свойства и уязвимости. М.: Изд. Центр «Академия», 2009, 272 с.

[13] Daemen J. Limitations of the Even-Mansour construction. ASIACRYPT, LNCS, vol. 739, pp. 495-498. Springer, 1991.

[14] Denes J., Keedwell A.D. Latin squares and their applications. London: English Univ. Press, 1975.

[15] Dinur I., Dunkelman O., Keller N., Shamir A. Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES. http://eprint.iacr.org/2013/391, 2013.

[16] Evans A. Orthomorphisms graphs and groups, Springer-Verlag, Berlin, 1992.

[17] Evans A. Applications of complete mappings and orthomorphisms of finite groups.

[18] Even E. Mansour Y.A construction of a cipher from a single pseudorandom permutation. ASIACRYPT 1991. LNCS, vol. 739, pp. 210-224. Springer, Heidelberg (2013).

[19] Gilboa S., Gueron S. Balanced permutations Even-Mansour ciphers. arXiv preprint arXiv: 1409.0421, 2014.

[20] Gligoroski D., Odegard R.S., Mihova M., et al. Cryptographic Hash Function Edon-R // Proc. IWSCN. Trondheim, 2009, pp. 1-9.

[21] Johnson D.M., Dulmage A.L. and Mendelsohn N.S. Orthomorphisms of groups and orthogonal latin squares, I. Canad. J. Math. 13, 1961, pp. 356-372.

[22] Mann H.B. On orthogonal latin squares, Bull. Amer. Math. Soc. 50, 1944, pp. 249-257.

[23] Menyachikhin A. Spectral-linear and spectral-differential methods for generating cryptographicaly strong S-boxes. In: Pre-proceedings of CTCrypt'16-Yaroslavl, Russia, 2016. p. 232-252.

[24] Niederreiter H., Robinson K. Bol loops of order pq, Math. Proc. Cambridge Philos. Soc, 1981, pp. 241-256.

[25] Niederreiter H., Robinson K. Complete mappings of finite fields. J. Austral. Math. Soc. Ser., 1982, pp. 197-212.

[26] Nikolic I., Wang L., Wu S. Cryptoanalysis of Round-Reduce LED. In Fast Software Encryption, 2013. LNCS, vol. 8424, pp. 112-130. Springer, Heidelberg (2014).

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

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