Криптографические свойства ортоморфизмов | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/7

Криптографические свойства ортоморфизмов

Рассмотрены взаимно однозначные отображения F : Zn ^ Zn, называемые ортоморфизмами, такие, что отображения G(x) = F(x) ® x также являются взаимно однозначными. Они используются в схеме Лая - Месси в качестве перемешивающего элемента между раундами, а также для построения криптографически стойких S-блоков. Исследованы основные криптографические свойства: нелинейные характеристики и дифференциальная равномерность. Выявлено, что ортоморфизмы от малого числа переменных не устойчивы к линейному и дифференциальному криптоанализам.

Cryptographic properties of orthomorphic permutations.pdf В симметричной криптографии часто используются отображения множества Zn, состоящего из двоичных наборов длины n, на себя. В частности, в [1] в шифрах FOX (IDEA NXT), использующих схему Лая - Месси, предлагается использовать отображение, называемое ортоморфизмом. Ортоморфизм Zn - это взаимно однозначное отображение F : Zn ^ Zn, такое, что отображение G(x) = F(x) ф x также является взаимно однозначным. В литературе в основном освещаются перемешивающие свойства ортоморфизмов. Например, в [2] ортоморфизмы характеризуются свойством отображать каждую максимальную подгруппу группы двоичных наборов длины n наполовину в себя и наполовину в своё дополнение. В рамках данной работы разработан и программно реализован рекурсивный алгоритм построения всех ортоморфизмов для заданного n. Алгоритм перебирает все значения для k-го элемента и проверяет выполнение определения ортоморфизма. Если проверка успешна, то переходим к (k + 1)-му элементу, иначе проверяем следующее значение k-го. Когда проверены все возможные значения для k-й позиции, происходит возврат к дальнейшей проверке значений для позиции k - 1 . С помощью этой программы получены все ортоморфизмы для малых значений n и один ортоморфизм для n =16 для исследования модификации шифра Simon 32/64 [3], где вместо сети Фейстеля использована схема Лая - Месси. Получено, что: - при n = 2 существует 8 ортоморфизмов; - при n = 3 существует 384 ортоморфизма; - при n = 4 существует 244744192 ортоморфизма. Для всех полученных ортоморфизмов экспериментально исследованы основные криптографические свойства: нелинейные характеристики и дифференциальная равномерность. Обозначим вход и выход функции F : Zn ^ Zn через x = (xi,...,xn) и y = = (y1,... ,yn) соответственно. Для линейного криптоанализа строится таблица линейного преобладания, где на пересечении строки u G Zn и столбца v G Zn находится число А, такое, что соотношение (u,x) = (v,y) выполняется с вероятностью (2n-1 + A)/2n, где (u, x) = uixi ф ... ф Unxn. Утверждение 1. При n = 2, 3 и 4 таблицы линейного преобладания ортоморфизмов состоят из значений 0 и ±2n-1. Для дифференциального криптоанализа в таблице дифференциалов на пересечении строки u G Zn и столбца v G Zn находится число А, такое, что равенство F(x ф u) ф F(x) = v выполняется в точности для А различных x. Утверждение 2. При n = 2, 3 и 4 таблицы дифференциалов ортоморфизмов состоят из значений 0 и 2n. Для полученного ортоморфизма при n = 16 также исследовались таблицы линейного преобладания и дифференциалов. Таблица линейного преобладания состоит из значений 0 и ±2n-1, а таблица дифференциалов - из 0 и 2n. Утверждения 1, 2 и точечное исследование ортоморфизма для n =16 позволяют предположить, что для любого значения n таблицы дифференциалов и линейного преобладания ортоморфизмов имеют вид, описанный выше. Из этого следует, что ортоморфизмы не устойчивы к линейному и дифференциальному криптоанализам и должны использоваться в шифрах в качестве вспомогательных элементов для построения более устойчивых к криптоанализу перемешивающих отображений.

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

ортоморфизм, таблица линейного преобладания, таблица дифференциалов, orthomorphic permutation, linear approximation table, difference distribution table

Авторы

ФИООрганизацияДополнительноE-mail
Максимлюк Юлия ПавловнаИнститут математики им. С. Л. Соболева СО РАН; Новосибирский государственный университетмладший научный сотрудник; студентка; исследователь Лаборатории криптографии JetBrains Researchyumaximlyuk@gmail.com
Всего: 1

Ссылки

Nakahara J. Jr. Lai-Massey Cipher Designs. History, Design Criteria and Cryptanalysis. Springer, 2018. 726 p.
Mittenthal L. Block substitutions using orthomorphic mappings // Adv. Appl. Math. 1995. V. 16. Iss. 1. P. 59-71.
Beaulieu R., Shors D., Smith J., et al. The Simon and Speck Families Of Lightweight Block Ciphers. Cryptology ePrint Archive, Report 2013/404, 2013.
 Криптографические свойства ортоморфизмов | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/7

Криптографические свойства ортоморфизмов | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/7