Invariant subspaces of functions affine equivalent to the finite field inversion.pdf В работе рассматриваются аффинные подпространства, образ которых под действием функции, обращающей элементы конечного поля, также является аффинным подпространством. Обозначим эту функцию через а, т.е. а : Fpn Fpn, такая, что x-1, если x = 0, а(х) = < 0, если x = 0, где Fpn -конечное поле, состоящее из pn элементов. Здесь и далее p - простое число. Под линейным подпространством L поля Fpn мы подразумеваем его линейное подпространство над Fp, другими словами, аддитивную подгруппу Fpn. Через a+L обозначим аффинное подпространство. Отметим, что для любого множества S С Fpn, элемента a G Fpn и функции f : Fpn Fpn a+S = {a+s : s G S}, aS = {as : s G S} и f(S) = {f(s) : s GS}. Известно, что у Fpn существует подполе Fpk тогда и только тогда, когда k|n. В этом случае будем полагать, что Fpk С Fpn. Рассмотрим аффинные подпространства U С Fpn, такие, что a(U) также является аффинным подпространством. Выделим нетривиальные подпространства, такие, что 2 < |U | < pn , поскольку любое множество мощности 1, 2 (если p = 2) или pn является аффинным подпространством. Интерес к этим подпространствам обусловлен их связью с инвариантными подпространствами отображений. Знание всех таких U позволяет определить все инвариантные аффинные подпространства относительно функций, аффинно эквивалентных а. Напомним, что множество S С Fpn называется инвариантным относительно f, если f (S) С S. Функция а, на базе которой построен S-блок AES [1, 2], а также её инвариантные подпространства интересны в криптографическом контексте. Например, они использовались для исследования групповых свойств раундовых функций у AES-подобных шифров [3 - 5]. В [6] предложена атака, использующая инвариантное подпространство для нескольких раундов шифрования, которая к настоящему времени рассмотрена для многих схем [7]. Известна также более общая атака [8], построение которой можно начинать с S-блоков [9]. Отметим, что все линейные подпространства, являющиеся инвариантными относительно а, описаны в работах [10, 11]. Таким образом, мы обобщаем эти результаты, во-первых, на аффинные подпространства и, во-вторых, на подпространства, являющиеся инвариантными не для а, а для некоторой функции, аффинно эквивалентной а. Если f(U) не является аффинным подпространством для любого аффинного подпространства U С F2n размерности 2, то f принадлежит к классу APN-функций [12], имеющих большую криптографическую значимость. Более того, только APN-функции обладают этим свойством. С ними связано множество открытых вопросов [13]. Сначала покажем, что для функции а достаточно рассматривать только линейные подпространства. Теорема 1. Пусть U и a(U) - аффинные подпространства Fpn, |U| > 2. Тогда U является линейным подпространством Fpn. Следующая теорема описывает все искомые подпространства U. Теорема 2. Пусть U - аффинное подпространство Fpn, |U| > 2. Тогда a(U) является аффинным подпространством Fpn, если и только если U = qFpk, где k|n и q G Fpn. Доказательство теоремы использует тождество Хуа [14] аналогично рассмотренному в [10, 11] случаю линейных подпространств, инвариантных относительно а. Теорема 2 также показывает, что при простых n > 2 существуют APN-функции, такие, что образ нетривиального аффинного подпространства (любой размерности, а не только размерности 2) никогда не является аффинным подпространством. Покажем, что теоремы 1 и 2 позволяют построить с помощью а функции без нетривиальных инвариантных подпространств, имеющие вид аА,ь (x) = A(a(x)) + b, где A : Fpn Fpn -обратимая линейная функция; b G F*n и x G Fpn. Рассматривая линейные отображения, мы, аналогично подпространствам, подразумеваем, что Fpn является векторным пространством над полем Fp. Определим также подмножество поля S(Fpn) = {x G Fpn : x G/ Fpk, где k|n и k < n}. Другими словами, оно содержит все элементы Fpn, не лежащие в его подполях, и всегда является непустым. Теорема 3. Пусть A : Fpn Fpn -обратима и линейна, b G F*n, причём b 1^A,b(b) G S(Fpn). (1) Тогда не существует инвариантных аффинных подпространств U относительно ра,ь, таких, что 2 < |U| < pn. Даже если ^а,ь не удовлетворяет условию (1), можно привести её к нужному виду. Следствие 1. Пусть A : Fpn Fpn -обратима и линейна, b G Fpn. Определим функцию A : Fpn Fpn следующим образом: A'(x) = авА(х), где а G S(Fpn) и в = (b-1A(b-1))-1. Тогда функция ^ах,6 удовлетворяет условию (1). Отметим, что S-блок SAES шифра AES, имеющий вид ида в поле F28, удовлетворяет условию (1) теоремы 3. Тем не менее существует аффинное подпространство размерности 1, инвариантное относительно SAES [1, табл. 7]: SAES(0x73) = 0x8F и SAES(0x8F) = 0x73. Таким образом, утверждения выше не гарантируют отсутствия инвариантных подпространств U, где 1 С |U| С 2. В дополнение к примеру выше, функция вида &а,ь может удовлетворять условию (1), но при этом иметь неподвижные точки (т. е. инвариантные аффинные подпространства размерности 0). Следующая теорема гарантирует существование функций, единственным инвариантным подпространством которых является Fpn. Теорема 4. Пусть aa,b(x) = aa(x) + b, где a, b G Fpn, x G Fpn. Тогда aa,b не имеет инвариантных аффинных подпространств, кроме Fpn, если и только если - ab-2 G M2 при p =2, где M2 = {x G S(F2n) : tr(x) = 1}, tr(x) = x2 + x2 + . . . + x2 - ; (2) - ab-2 + 4-1 G Mp при p =2, где Mp = {x G S(Fpn) : x = y2 для любого y G Fpn}. (3) Множества Mp, определённые в (2) и (3), всегда непустые. Однако функции аа,ь из теоремы 4 имеют очень простую алгебраическую структуру. Заметим также, что при непростых n всегда существует некоторое линейное подпространство L = Fpn, такое, что aa,b(u + L) = v + L для некоторых u, v G Fpn.

Скачать электронную версию публикации