Combinatorial polynomially computable characteristics of substitutions and their properties

Full Text

Введение В настоящее время наблюдается постоянно растущий интерес к изучению биективных отображений, во многом сопряженный с построением систем блочного шифрования. Различные подходы к анализу таких систем привели исследователей к необходимости изучения целого ряда специальных характеристик подстановок, таких как разностные ([5-7] и др), дифференциальные ([11-14] и др.) и т.п. Особенности развиваемых методов анализа привели к выделению специфических характеристик подстановок, поиск которых обладает высокой вычислительной сложностью. Задачей настоящей статьи авторы ставили введение и описание таких свойств подстановок, которые были бы легко вычислимы и позволяли прямо или косвенно судить о внутренней сложностной природе биективного преобразования. Исходя из этих соображений в статье рассмотрены разностные, квадратичные и, в общем случае, степенные характеристики, для которых удалось посчитать математическое ожидание, а для разностной характеристики еще и дисперсию. Значение математического ожидания и дисперсии разностной характеристики позволяет путем ее вычисления судить о мере близости конкретной подстановки к случайной, или о ее удаленности от нее. Важнейшей отличительной особенностью характеристик, рассматриваемых в статье, является простота их вычисления, имеющая линейную трудоемкость. 1. Параметры близости подстановок Пусть S (0, n - 1) - группа всех подстановок степени n. Каждая подстановка π ∈ S (0, n - 1) исходный символ i, i ∈ 0, n - 1, переводит в образ π (i). Рассмотрим некоторые характеристики подстановок из S (0, n - 1), которые позволят судить о криптографическом качестве этих подстановок, под качеством подразумевается близость подстановки к случайной. Определение 1. Разностной характеристикой подстановки π ∈ S (0, n - 1) будем называть величину: (1) Определение 2. Квадратичной характеристикой подстановки π ∈ S (0, n - 1) будем называть величину: (2) Кубической характеристикой подстановки π ϵ S (0, n - 1) будем называть величину: (3) Для подстановки π ∈ S (0, n - 1) степенной характеристикой близости будем называть величину: (4) Замечание. Квадратичная и кубическая характеристики являются частным случаем степенной характеристики. Теорема 1. Выражение n ∙ ξ0 (π) принимает четные значения в отрезке от 0 до [n2/2], где [x] - целая часть x, то есть Доказательство Сначала докажем, что Доказательство разобьем на два случая. 1. Пусть n = 2k и существует i ∈ {0, … , k - 1} такой, что π (i) ∈ {0, … , k - 1}. Тогда очевидно, что существует такой j ∈ {k, … , 2k - 1}, что π (j) ∈ {k, … , 2k - 1}. Нетрудно проверить, что в каждом из четырех случаев: i < π (i) < j < π (j); π (i) < i < j < π (j); i < π (i) < π (j) < j; π (i) < i < π (j) < j выполняется неравенство |π (i) - j| + |π (j) - i| > |π (i) - i| + |π (j) - j|. В таком случае, разностная характеристика подстановки πʹ: πʹ (i) = π (j); πʹ (j) = π (i); πʹ (s) = π (s); ∀s ∈ {0, … , 2k - 1}/{i, j} строго больше разностной характеристики π: Теперь нетрудно понять, что разностная характеристика может достигать своего максимального значения только на таких перестановках π у которых π ({0, … , k - 1}) = {k, … , 2k - 1}; π ({k, … , 2k - 1}) = {0, … , k - 1}. Рассмотрим произвольную подстановку вида, описанного выше и посчитаем ее разностную характеристику, умноженную на n: 2. Пусть n = 2k + 1 и, без ограничения общности, пусть π (k) ∈ {k + 1, … , 2k}. Если π-1 (k) = i ∈ {k + 1, … , 2k}, то существует t ∈ {0, … , k - 1}, такой, что π (t) ∈ {0, … , k - 1}. Тогда очевидно, что существует такой j ∈ {k, … , 2k ؘ- 1} и нетрудно проверить, что в каждом из четырех случаев: t < π (t) < k < i < j, π (t) < t < k < i < j, t < π (t) < k < j < i, π (t) < t < k < j < i выполняется неравенство |j - t| + |π (t) - i| > |π (t) - t| + |j - k|+ |k - i|. В таком случае, разностная характеристика подстановки πʹ: πʹ (t) = j; πʹ (k) = k; πʹ (i) = π (t); πʹ (s) = π (s); ∀s ∈ {0, … , 2k}/{i, t, k} строго больше разностной характеристики π: Если же π-1 (k) = i ∈ {0, … , k - 1}, то легко показать, что разностная характеристика подстановки πʹ: πʹ (i) = j; πʹ (k) = k; πʹ (s) = π (s); ∀s ∈ {0, … , 2k}/{i, k} совпадает с разностной характеристикой π: Теперь нетрудно понять, что разностная характеристика может достигать своего максимального значения только на таких перестановках π у которых π ({0, … , k - 1}) = {k + 1, … , 2k}; π (k) = k, π {k + 1, … , 2k} = {0, … , k - 1}. Рассмотрим произвольную подстановку вида, описанного выше и посчитаем ее разностную характеристику, умноженную на n: Осталось показать, что для любого Очевидно, что разностная характеристика тождественной подстановки, обозначим ее - π0, равна 0. Построим последовательность подстановок π0, … , πr, где для любого k ∈ 0, r; πk (i) = πk - 1 (i), для любого i = 0, n - 1 / {l - 1, l}, l = (k - 1 mod n) и πk (l - 1) = πk - 1 (l), πk (l) = πk - 1 (l - 1). Количество подстановок в последовательности Рассмотрим последовательность Нетрудно показать, что это неубывающая последовательность и разница между последовательными членами либо 0, либо 2. Для этого рассмотрим разность n ξ0 (πk) - n ξ0 (πk - 1), заметим, что в этой разности не сократится только четыре члена: n ξ0 (πk) - n ξ0 (πk - 1) = |πk (l) - l| + |πk (l - 1) - (l - 1)| - - |πk - 1 (l) - l| - |πk - 1 (l - 1) - (l - 1)|, учитывая, что, по построению последовательности {πk - 1 (l)}, πk - 1 (l) > πk - 1 (l - 1), рассмотрим три случая. 1) πk - 1 (l) > πk - 1 (l - 1) ≥ l n ξ0 (πk) - n ξ0 (πk - 1) = πk - 1 (l - 1) - l + πk - 1 (l) - - (l - 1) - πk - 1 (l) + l - πk - 1 (l - 1) + (l - 1) = 0, 2) πk - 1 (l) ≥ l > l - 1 ≥ πk - 1 (l - 1) n ξ0 (πk) - n ξ0 (πk - 1) = -πk - 1 (l - 1) + l + πk - 1 (l) - - (l - 1) - πk - 1 (l) + l + πk - 1 (l - 1) - (l - 1) = 2, 3) l - 1 ≥ πk - 1 (l) > πk - 1 (l - 1) n ξ0 (πk) - n ξ0 (πk - 1) = -πk - 1 (l - 1) + l - πk - 1 (l) + + (l - 1) + πk - 1 (l) - l + πk - 1 (l - 1) - (l - 1) = 0, Следовательно, последовательность n ξ0 (π0), … , n ξ0 (πr) содержит все четные числа из отрезка [0, [n2 - 2]]. Пример 1. Приведем пример последовательности подстановок из доказательства теоремы для S (0, 4). Таблица 1 Пример последовательности r Вторая строка подстановки n ξ0 (πr) 0 0 1 2 3 4 0 1 0 1 2 4 3 2 2 0 1 4 2 3 4 3 0 4 1 2 3 6 4 4 0 1 2 3 8 5 4 0 1 3 2 8 6 4 0 3 1 2 10 7 4 3 0 1 2 12 8 4 3 0 2 1 12 9 4 3 2 0 1 12 10 4 3 2 1 0 12 Следствие 1. Разностная характеристика ξ0 (π) достигает своего максимума [n2/2] на подстановках вида π ({0, … , k - 1}) = {k + 1, … , 2k}; π (k) = k, π ({k + 1, … , 2k}) = {0, … , k - 1} при n = 2k + 1; π ({0, … , k - 1}) = {k, … , 2k - 1}; π ({k, … , 2k - 1}) = {0, … , k - 1} при n = 2k. 2. Вероятностные параметры введенных характеристик Пусть на S (0, n - 1) задано равномерное распределение. Тогда для дальнейшего изучения введенных характеристик найдем их математические ожидания. Теорема 2. Справедливо следующее равенство (5) Доказательство Заметим, что если зафиксировать i ∈ (0, n - 1) и некоторое j, то |i - π (i)| = j. при π (i) = i - j и π (i) = i + j, если j ≤ i или только при π (i) = i + j если j > i, а также, что при фиксированном i количество подстановок, принимающих некоторое конкретное значение |i - π (i)| будет (n - 1)! шт. Тогда Теорема 3. Для любого s ∈ ℕ справедливо следующее равенство при m = 2s, (6) при m = 2s - 1. Доказательство Заметим, что выражение (i - π (i))m принимает все целые значения от i - (n - 1) до i, а также, что количество подстановок c фиксированными π (i) - (n - 1)! шт. Тогда В случае m = 2s теорема доказана. Осталось рассмотреть случай m = 2s - 1 (*) Рассмотрим сумму слагаемых с номерами при i = t и i = (n - 1 - t), . Для случая нечетного n в сумме (*) нет слагаемых, которые не взаимоуничтожаются и в этом случае Mξ2s - 1 (π) = 0. Для случая четного n в сумме (*) остается одно слагаемое при а следовательно Mξ2s + 1 (π) = 0 и в этом случае. Замечание. Для практического подсчета Mξm (π) надо уметь вычислять , где k ∈ ℕ. Согласно [10] можно воспользоваться, например, рекуррентной формулой: где S0 = n, . Следствие Теорема 4. Справедливо следующее равенство (7) Доказательство В последнем равенстве первая сумма равна (1/n) M ξ2 (π). При подсчете второй суммы необходимо учесть, что (i - π (i)) пробегает все целые значения от i - (n - 1) до i, а (j - π (j)) - все целые значения от j - (n - 1) до j, причем, так как π - подстановка, то π(i) ≠ π (j), при i ≠ j, а также то, что количество подстановок c фиксированными значениями π (i), π (j) - (n - 2) шт. Тогда Пример 2. Рассмотрим какие значения может принимать ξ0 (π) если π ∈ S (0, 7). Таблица 1 Значения ξ0 (π) Количество Пример π (i) с характеристикой ξ0 (π) ξ0 (π) Количество Пример π (i) с характеристикой ξ0 (π) 0 1 2 3696 0,25 7 2,25 4852 0,5 33 2,5 5708 0,75 115 2,75 5892 1 327 3 5452 1,25 765 3,25 4212 1,5 1523 3,5 2844 1,75 2553 3,75 1764 4 576 Тогда Пример 3. Пусть π ∈ S(0, 255), тогда рассмотрим несколько подстановок из действующих стандартов, подстановки взяты из [13]. Напомним, что в этом случае M ξ0 (π) = 85, D ξ0 (π) ≈ 11,42. 1. BelT (см. [1; 2]) - государственный стандарт симметричного шифрования и контроля целостности Республики Беларусь (СТБ 34.101.31-2007). Подстановка представлена на рис. 1. В этом случае ξ0 (π) = 88,8828185. 2. Skipjack (см. [9]) - блочный шифр, разработанный АНБ США в рамках проекта Capstone. Подстановка представлена на рис. 2. В этом случае ξ0 (π) = 89,1796875. X0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF 0x a3 d7 09 83 f8 48 f6 f4 b3 21 15 78 99 b1 af f9 1x e7 2d 4d 8a ce 4c ca 2e 52 95 d9 1e 4e 38 44 28 2x Oa df 02 aO 17 f1 60 68 12 b7 7a c3 e9 fa 3d 53 3x 96 84 6b ba f2 63 9a 19 7c ae e5 f5 f7 16 6a a2 4x 39 b6 7b Of c1 93 81 1b ee b4 1a ea dO 91 2f b8 5x 55 b9 da 85 3f 41 bf eO 5a 58 80 5f 66 Ob d8 90 6x 35 d5 cO a7 33 06 65 69 45 OO 94 56 6d 98 9b 76 7x 97 fc b2 c2 bO fe db 20 e1 eb d6 e4 dd 47 4a 1d 8x 42 ed 9c 6c 49 3c cd 43 27 d2 07 d4 de c7 67 18 9x 89 cb 30 1f 8d c6 8f aa c8 74 dc c9 5d 5c 31 a4 Ax 70 88 61 2c 9f Od 2b 87 50 82 54 64 26 7d 03 40 Bx 34 4b 1c 73 d1 c4 fd 3b cc fb 7f ab e6 3e 5b a5 Cx ad 04 23 9c 14 51 22 fO 29 79 71 7e ff 8c Oe e2 Dx Oc ef be 72 75 6f 37 a1 ec d3 8e 62 8b 86 10 e8 Ex 08 77 11 be 92 4f 24 c5 32 36 9d cf f3 A6 bb ac Fx 5e 6c a9 13 57 25 b5 e3 bd a8 3a 01 05 59 2a 46 Рис. 2. Подстановка π шифра Skipjack 3. KHAZAD (см. [3, 4]) - симметричный блочный шифр, представленный на конкурсе NESSIE в 2000 году, где в модифицированной (tweaked) форме стал одним из алгоритмов-финалистов. Подстановка представлена на рис. 3. В этом случае ξ0 (π) = 92,890625. 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 BA 54 2F 74 53 D3 D2 4D 50 AC 8D BF 70 52 9A 4C 1 EA D5 97 D1 33 51 5B A6 DE 48 A8 99 DB 32 B7 FC 2 E3 9E 91 9B E2 BB 41 6E A5 CB 6B 95 A1 F3 B1 02 3 CC C4 1D 14 C3 63 DA 5D 5F DC 7D CD 7F 5A 6C 5C 4 F7 26 FF ED E8 9D 6F 8E 19 AO FO 89 OF 07 AF FB 5 08 15 OD 04 01 64 DF 76 79 DD 3D 16 3F 37 6D 38 6 B9 73 E9 35 55 71 7B 8C 72 88 F6 2A 3E 5E 27 46 7 OC 65 68 61 03 C1 57 D6 D9 58 D8 66 D7 3A C8 3C 8 FA 96 A7 98 EC B8 C7 AE 69 4B AB A9 67 OA 47 F2 9 B5 22 E5 EE BE 2B 81 12 83 1B OE 23 F5 45 21 CE A 49 2C F9 E6 B6 28 17 82 1A 8B FE 8A 09 C9 87 4E B E1 2E E4 EO E B 90 A4 11 E 85 60 OO 25 F4 F1 94 OB C E7 75 EF 34 31 D4 DO 86 7E AD FD 29 30 3B 9F F8 D C6 13 06 05 05 11 77 7C 7A 78 36 1C 39 59 18 56 E B3 BO 24 20 B2 92 A3 CO 44 62 10 B4 84 43 93 C2 F 4A BO 8F 20 BC 9C 6A 40 CF A2 80 4F 1F CA AA 42 Рис. 3. Подстановка π шифра KHAZAD 4. «Кузнечик» (см. [7]) - симметричный алгоритм блочного шифрования, утвержденный в качестве стандарта ГОСТ Р 34.12-2015. Подстановка, используемая в «Кузнечике»: (252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241, 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182). В этом случае ξ0 (π) = 85. В итоге, во всех рассмотренных выше примерах, подстановки, обладающие хорошими разностными и дифференциальными характеристиками, имеют разностную характеристику, отличающуюся от математического ожидания на величину меньшую, чем дисперсия.

About the authors

Vladimir G. Nikonov

Russian Academy of Natural Sciences

Dr. Sci. (Eng.), Full Professor, Member of the Presidium Moscow, Russian Federation

Anton I. Zobov

Secure Information Technology Assistance Foundation

Email: zobowai@gmail.com
research employee Moscow, Russian Federation

References

Supplementary files