Криптографический алгоритм «Кузнечик»: просто о сложном

В данной статье будет подробно рассмотрен алгоритм блочного шифрования, определенный в ГОСТ Р 34.12-2015 как «Кузнечик». На чем он основывается, какова математика блочных криптоалгоритмов, а так же как реализуется данный алгоритм в java.

Кто, как, когда и зачем разработал данный алгоритм останется за рамками статьи, так как в данном случае нас это мало интересует, разве что:

КУЗНЕЧИК = КУЗнецов, НЕЧаев И Компания.



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

Поля Галуа


Арифметика полей Галуа — полиномиальная арифметика, то есть каждый элемент данного поля представляет собой некий полином. Результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т.е. количество его элементов, является некоторой натуральной степенью характеристики $p^m$, где m ϵ N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m, такое поле называется расширенным. $GF(p^m) $ – обозначение поля Галуа. Порождающий полином является неприводимым, то есть простым (по аналогии с простыми числами делится без остатка на 1 и на самого себя). Так как работа с любой информацией — это работа с байтами, а байт представляет из себя 8 бит, в качестве поля берут $GF(2^8)$ и порождающий полином:

$x^8 + x^7 + x^6+x+1.$


Однако для начала разберем основные операции в более простом поле $GF(2^3)$ с порождающим полиномом $f(x)=x^3+x+1$.

Операция сложения


Самой простой является операция сложения, которая в арифметике полей Галуа является простым побитовым сложением по модулю 2 (ХОR).

Сразу обращаю внимание, что знак "+" здесь и далее по тексту обозначает операцию побитового XOR, а не сложение в привычном виде.

Таблица истинности функции ХОR



Пример: $5 + 3 = 101 + 011 = 110_2 = 6_{10}$

В полиномиальном виде данная операция будет выглядеть как

$(x^2 + 1) + (x + 1) = x^2 + x = 110_2 = 6_{10}$



Операция умножения


Чтобы осуществить операцию умножения, необходимо преобразовать числа в полиномиальную форму:

$5 = 101_2 =1*x^2 +0*x^1+1*x^0=x^2 + 1$



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

Перемножим два числа в полиномиальной форме:

$5*7=(x^2+1)*(x^2+x+1)=x^4+x^3+x^2+x^2+x+1=$


$=x^4+x^3+x+1=11011_2=27_{10}$


Результат умножения 27 не входит в используемое поле $GF(2^3)$ (оно состоит из чисел от 0 до 7, как было сказано выше). Чтобы бороться с этой проблемой, необходимо использовать порождающий полином.

Также предполагается, что x удовлетворяет уравнению $f(x)=x^3+x+1=0$, тогда



Составим таблицу умножения:



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

Пример:

$5^2=(x^2+1)^2=x^4+x^2+x^2+1=x^4+x^2+x+x^2+x+1=$


$=x(x^3+x+1)+x^2+x+1=x^2+x+1=111_2=7_{10}$



Таким образом, составим таблицу степеней:



Таблица степеней обладает цикличностью: седьмая степень соответствует нулевой, значит восьмая соответствует первой и т.д. При желании можно это проверить.

В полях Галуа существует понятие примитивного члена – элемент поля, чьи степени содержат все ненулевые элементы поля. Видно, что этому условию соответствуют все элементы (ну кроме 1, естественно). Однако это выполняется не всегда.

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



Пример:$5=2^6,7=2^5$

Воспользовавшись этим свойством, и учитывая цикличность таблицы степеней, попробуем снова перемножить числа:

$5*7=2^6*2^5=2^{(6+5)}=2^{(11mod7)}=2^4=6$


Результат совпал с тем, что мы вычислили раньше.

А теперь выполним деление:

$6/5=2^4/2^6=2^{(4-6)}=2^{((-2)mod7)}=2^5=7$


Полученный результат тоже соответствует действительности.

Ну и для полноты картины посмотрим на возведение в степень:

$5^2=(2^6)^2=2^{(6*2)}=2^{(12mod7)}=2^5=7$



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

Теперь вернемся к нашему полю $GF(2^8)$

Нулевой элемент поля — это единица, 1-й — двойка, каждый последующий со 2-го по 254-й элемент вычисляется как предыдущий, умноженный на 2, а если элемент выходит за рамки поля, то есть его значение больше чем $(2^8-1)$, то делается XOR с числом $195_{10}$, это число представляет неприводимый полином поля $x^8 + x^7 + x^6+x+1=2^8 + 2^7 ++ 2^6+2+1=451$, приведем это число в рамки поля $451-256=195$. А 255-ый элемент снова равен 1. Таким образом у нас есть поле, содержащее 256 элементов, то есть полный набор байт, и мы разобрали основные операции, которые выполняются в этом поле.



Таблица степеней двойки для поля $GF(2^8)$

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

Сеть Фейстеля


Сеть Фейстеля — это метод блочного шифрования, разработанный Хорстом Фейстелем в лаборатории IBM в 1971 году. Сегодня сеть Фейстеля лежит в основе большого количества криптографических протоколов.

Сеть Фейстеля оперирует блоками открытого текста:

  1. Блок разбивается на две равные части — левую L и правую R.
  2. Левый подблок L изменяется функцией f с использованием ключа K: X = f(L, K). В качестве функции может быть любое преобразование.
  3. Полученный подблок X складывается по модулю 2 с правым подблоком R, который остался без изменений: X = X + R.
  4. Полученные части меняются местами и склеиваются.

Эта последовательность действий называется ячейкой Фейстеля.


Рисунок 1. Ячейка Фейстеля

Сеть Фейстеля состоит из нескольких ячеек. Полученные на выходе первой ячейки подблоки поступают на вход второй ячейки, результирующие подблоки из второй ячейки попадают на вход третьей ячейки и так далее.

Алгоритм шифрования


Теперь мы познакомились с используемыми операциями и можем перейти к основной теме — а именно криптоалгоритму Кузнечик.

Основу алгоритма составляет так называемая SP сеть — подстановочно-перестановочная сеть (Substitution-Permutationnetwork). Шифр на основе SP-сети получает на вход блок и ключ и совершает несколько чередующихся раундов, состоящих из стадий подстановки и стадий перестановки. В «Кузнечике» выполняется девять полных раундов, каждый из которых включает в себя три последовательные операции:

  1. Операция наложения раундового ключа или побитовый XOR ключа и входного блока данных;
  2. Нелинейное преобразование, которое представляет собой простую замену одного байта на другой в соответствии с таблицей;
  3. Линейное преобразование. Каждый байт из блока умножается в поле Галуа на один из коэффициентов ряда (148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148, 1) в зависимости от порядкового номера байта (ряд представлен для порядковых номеров от 15-ого до 0-ого, как представлено на рисунке). Байты складываются между собой по модулю 2, и все 16 байт блока сдвигаются в сторону младшего разряда, а полученное число записывается на место считанного байта.



Последний десятый раунд не полный, он включает в себя только первую операцию XOR.

Кузнечик — блочный алгоритм, он работает с блоками данных длинной 128 бит или 16 байт. Длина ключа составляет 256 бит (32 байта).


Рисунок 2. Схема шифрования и расшифрования блока данных

На схеме показана последовательность операций, где S — нелинейное преобразование, L — линейное преобразование, Ki — раундовые ключи. Сразу возникает вопрос — откуда берутся раундовые ключи.

Формирование раундовых ключей


Итерационные (или раундовые) ключи получаются путем определенных преобразований на основе мастер-ключа, длина которого, как мы уже знаем, составляет 256 бит. Этот процесс начинается с разбиения мастер-ключа пополам, так получается первая пара раундовых ключей. Для генерации каждой последующей пары раундовых ключей применяется восемь итераций сети Фейстеля, в каждой итерации используется константа, которая вычисляется путем применения линейного преобразования алгоритма к значению номера итерации.


Схема получения итерационных (раундовых) ключей

Если вспомнить рисунок 1, то левый подблок L — левая половина исходного ключа, правый подблок R — правая половина исходного ключа, K — константа Ci, функция f — последовательность операций R XOR Ci, нелинейное преобразование, линейное преобразование.

Итерационные константы Ci получаются с помощью L-преобразования порядкового номера итерации.

Значит чтобы осуществить шифрование блока текста нам надо сначала рассчитать 32 итерационные константы, затем на основе ключа вычислить 10 раундовых ключей, и потом выполнить последовательность операций, представленных на рисунке 2.

Давайте начнем с вычисления констант:
Первая констант $C_1 = 1_{10} = 00000001_2 = 01_{16}$, однако все преобразования в нашем алгоритме выполняются с блоками длиной 16 байт, поэтому необходимо дополнить константу до длины блока, то есть дописать справа 15 нулевых байт, получим

$C_1 = 01000000000000000000000000000000$


Умножим ее на ряд (1, 148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148) следующим образом:

$a_{15}=a_{15}*148+a_{14}*32+a_{13}*133+a_{12}*16+$


$+a_{11}*194+a_{10}*192+a_9*1+a_8*251+a_7*1+a_6*192+$


$+a_5*194+a_4*16+a_3*133+a_2*32+a_1*148+a_0*1$


(данное равенство приведено в операциях полей Галуа)
Так как все кроме нулевого байта равны 0, а нулевой байт умножается на 1, то получим 1 и запишем его в старший разряд числа, сдвинув все байты в сторону младшего разряда, получим:

$C_1 = 00000000000000000000000000000001$


Повторим те же операции. На этот раз $a_{15}=1$, все остальные байты 0, следовательно из слагаемых остается только первое $ a_{15}*148=1*148=148_{10}=94_{16}$, получаем:

$C_1 = 00000000000000000000000000000194$


Делаем третью итерацию, здесь два ненулевых слагаемых:

$a_{15}*148+a_{14}*32=148*148+1*32=$


$=10010100*10010100+00000001*00100000=$


$=(x^7+x^4+x^2 )*(x^7+x^4+x^2 )+1*x^5=x^{14}+x^8+x^4+x^5=$


$=x^6 (x^8+x^7+x^6+x+1)+x^{13}+x^{12}+x^7+x^6+x^8+x^4+x^5=$


$=x^5 (x^8+x^7+x^6+x+1)+x^{11}+x^5+x^7+x^8+x^4+x^5=$


$=x^3 (x^8+x^7+x^6+x+1)+x^{10}+x^9+x^3+x^8+x^7=$


$=x^2 (x^8+x^7+x^6+x+1)+x^2+x^7=x^7+x^2=132_{10}$


$132_{10}=84_{16}$


По таблице степеней можно было решить это гораздо проще:

$148*148+1*32=2^{45}*2^{45}+2^5=2^{90}+2^5=164+32=132$


$C_1 = 00000000000000000000000000019484$


Далее все точно также, всего 16 итераций на каждую константу

$C_1 = 000000000000000000000000019484DD$


$C_1 = 0000000000000000000000019484DD10$


$C_1 = 00000000000000000000019484DD10BD$


$C_1 = 000000000000000000019484DD10BD27$


$C_1 = 0000000000000000019484DD10BD275D$


$C_1 = 00000000000000019484DD10BD275DB8$


$C_1 = 000000000000019484DD10BD275DB87A$


$C_1 = 0000000000019484DD10BD275DB87A48$


$C_1 = 00000000019484DD10BD275DB87A486C$


$C_1 = 000000019484DD10BD275DB87A486C72$


$C_1 = 0000019484DD10BD275DB87A486C7276$


$C_1 = 00019484DD10BD275DB87A486C7276A2$


И конечная константа:

$C_1 = 019484DD10BD275DB87A486C7276A2E6$


Остальные константы:

$C_2 = 02EBCB7920B94EBAB3F490D8E4EC87DC$


$C_3 = 037F4FA4300469E70B8ED8B4969A25B2$


$C_4 = 041555F240B19CB7A52BE3730B1BCD7B$


$C_5 = 0581D12F500CBBEA1D51AB1F796D6F15$


$C_6 = 06FE9E8B6008D20D16DF73ABEFF74AA7$


$C_7 = 076A1A5670B5F550AEA53BC79D81E8C9$


$C_8 = 082AAA2780A1FBAD895605E6163659F6$


$C_9 = 09BE2EFA901CDCF0312C4D8A6440FB98$


$C_{10} = 0AC1615EA018B5173AA2953EF2DADE2A$


$C_{11} = 0B55E583B0A5924A82D8DD5280AC7C44$


$C_{12} = 0C3FFFD5C010671A2C7DE6951D2D948D$


$C_{13} = 0DAB7B08D0AD40479407AEF96F5B36E3$


$C_{14} = 0ED434ACE0A929A09F89764DF9C11351$


$C_{15} = 0F40B071F0140EFD27F33E218BB7B13F$


$C_{16} = 1054974EC3813599D1AC0A0F2C6CB22F$


$C_{17} = 11C01393D33C12C469D642635E1A1041$


$C_{18} = 12BF5C37E3387B2362589AD7C88035F3$


$C_{19} = 132BD8EAF3855C7EDA22D2BBBAF6979D$


$C_{20} = 1441C2BC8330A92E7487E97C27777F54$


$C_{21} = 15D54661938D8E73CCFDA1105501DD3A$


$C_{22} = 16AA09C5A389E794C77379A4C39BF888$


$C_{23} = 173E8D18B334C0C97F0931C8B1ED5AE6$


$C_{24} = 187E3D694320CE3458FA0FE93A5AEBD9$


$C_{25} = 19EAB9B4539DE969E0804785482C49B7$


$C_{26} = 1A95F6106399808EEB0E9F31DEB66C05$


$C_{27} = 1B0172CD7324A7D35374D75DACC0CE6B$


$C_{28} = 1C6B689B03915283FDD1EC9A314126A2$


$C_{29} = 1DFFEC46132C75DE45ABA4F6433784CC$


$C_{30} = 1E80A3E223281C394E257C42D5ADA17E$


$C_{31} = 1F14273F33953B64F65F342EA7DB0310$


$C_{32} = 20A8ED9C45C16AF1619B141E58D8A75E$



Теперь произведем расчет раундовых ключей согласно схеме, представленной выше, возьмем ключ шифрования:

$K=7766554433221100FFEEDDCCBBAA9988$


$EFCDAB89674523011032547698BADCFE$


Тогда

$K_1=7766554433221100FFEEDDCCBBAA9988$


$K_2=EFCDAB89674523011032547698BADCFE$


$K_1$ будет левым подблоком сети Фейстеля, а $K_2$ — правым.
Выполним операцию $K_1+C_1$
Первый байт $K_1$ равен $77_{16}=01110111_2$
Первый байт $C_1$ равен $01_{16}=00000001_2$

$01110111_2+00000001_2=01110110_2=76_{16}$


остальные байты преобразовываются аналогично, в итоге $X(K_1,C_1)=K_1+C_1$:

$X(K_1,C_1)=76F2D199239F365D479495A0C9DC3BE6$



Далее выполняем нелинейное преобразование $S(X(K_1,C_1 ) )$. Выполняется оно по таблице:


Таблица нелинейного преобразования

Число 0 заменяется на 252, 1 на 238, 17 на 119 и т.д.

$76_{16}=118_{10}$


$S(118)=138_{10}=8A_{16}$


$S(X(K_1,C_1 ) )=8A741BE85A4A8FB7AB7A94A737CA9809$


Теперь выполним линейное преобразование $L(S(X(K_1,C_1 ) ) )$, оно было подробно рассмотрено при расчете итерационных констант, поэтому здесь приведем только конечный результат:

$L(S(X(K_1,C_1 ) ) )=A644615E1D0757926A5DB79D9940093D$


Согласно схеме ячейки Фейстеля выполним XOR с правым подблоком, то есть с $K_2$:

$X(L(S(X(K_1,C_1 ) ) ),K_2 )=4989CAD77A4274937A6FE3EB01FAD5C3$


И результат полученный на выходе первой ячейки Фейстеля:

$EFCDAB89674523011032547698BADCFE4989CAD77A4274937A6FE3EB01FAD5C3$


Это значение разбивается пополам и идет на вход второй ячейки Фейстеля, где используется уже вторая константа $C_2$. Пройдя восемь ячеек мы получим 2 следующих ключа $K_3$ и $K_4$. Выполним с ними восемь итераций сети Фейстеля, получим следующую пару ключей и так далее. Восемь итераций на пару ключей, так как первая пара у нас изначально есть, то всего выполняется 32 итерации, на каждую своя константа.

Оставшиеся ключи:

$K_3=448CC78CEF6A8D2243436915534831DB$


$K_4=04FD9F0AC4ADEB1568ECCFE9D853453D$


$K_5=ACF129F44692E5D3285E4AC468646457$


$K_6=1B58DA3428E832B532645C16359407BD$


$K_7=B198005A26275770DE45877E7540E651$


$K_8=84F98622A2912AD73EDD9F7B0125795A$


$K_9=17E5B6CD732FF3A52331C77853E244BB$


$K_{10}=43404A8EA8BA5D755BF4BC1674DDE972$



Шифрование блока


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

Возьмем блок открытого текста:

$T=8899AABBCCDDEEFF0077665544332211$


выполним последовательность операций X, S, L

$X(T,K_1)=FFFFFFFFFFFFFFFFFF99BB99FF99BB99$


$S(X(T,K_1 ) )=B6B6B6B6B6B6B6B6B6E87DE8B6E87DE8$


$L(S(X(T,K_1 ) ) )=30081449922F4ACFA1B055E386B697E2$


$T_1=30081449922F4ACFA1B055E386B697E2$


$X(T_1,K_2)=DFC5BFC0F56A69CEB18201951E0C4B1C$


$S(X(T_1,K_2 ) )=61AC3B07F47891E74524EE945F23A214$


$L(S(X(T_1,K_2 ) ) )=7290C6A158426FB396D562087A495E28$


$T_2=7290C6A158426FB396D562087A495E28$


и так далее, конечный результат будет выглядеть следующим образом:

$T_{10}=CDEDD4B9428D465A3024BCBE909D677F$



Расшифровка блока


Для расшифрования текста нужно использовать обратные операции в обратной последовательности (см. рис2).

Операция XOR обратна сама себе, обратной к операции S будет подстановка по следующей таблице:


Таблица обратного нелинейного преобразования

Обратным преобразованием к функции L будет:

$a_0=a_{15}*148+a_{14}*32+a_{13}*133+a_{12}*16+$


$+a_{11}*194+a_{10}*192+a_9*1+a_8*251+a_7*1+a_6*192+a_5*194+$


$+a_4*16+a_3*133+a_2*32+a_1*148+a_0*1$


и сдвиг в сторону старшего разряда. (Повторить операции 16 раз)

Реализация в Java


Для начала определим необходимые константы

static final int BLOCK_SIZE = 16; // длина блока
	
// таблица прямого нелинейного преобразования
static final byte[] Pi = {
(byte) 0xFC, (byte) 0xEE, (byte) 0xDD, 0x11, (byte) 0xCF, 0x6E, 0x31, 0x16,
(byte) 0xFB, (byte) 0xC4, (byte) 0xFA, (byte) 0xDA, 0x23, (byte) 0xC5, 0x04, 0x4D,
(byte) 0xE9, 0x77, (byte) 0xF0, (byte) 0xDB, (byte) 0x93, 0x2E, (byte) 0x99, (byte) 0xBA,
0x17, 0x36, (byte) 0xF1, (byte) 0xBB, 0x14, (byte) 0xCD, 0x5F, (byte) 0xC1,
(byte) 0xF9, 0x18, 0x65, 0x5A, (byte) 0xE2, 0x5C, (byte) 0xEF, 0x21,
(byte) 0x81, 0x1C, 0x3C, 0x42, (byte) 0x8B, 0x01, (byte) 0x8E, 0x4F,
0x05, (byte) 0x84, 0x02, (byte) 0xAE, (byte) 0xE3, 0x6A, (byte) 0x8F, (byte) 0xA0,
0x06, 0x0B, (byte) 0xED, (byte) 0x98, 0x7F, (byte) 0xD4, (byte) 0xD3, 0x1F,
(byte) 0xEB, 0x34, 0x2C, 0x51, (byte) 0xEA, (byte) 0xC8, 0x48, (byte) 0xAB,
(byte) 0xF2, 0x2A, 0x68, (byte) 0xA2, (byte) 0xFD, 0x3A, (byte) 0xCE, (byte) 0xCC,
(byte) 0xB5, 0x70, 0x0E, 0x56, 0x08, 0x0C, 0x76, 0x12,
(byte) 0xBF, 0x72, 0x13, 0x47, (byte) 0x9C, (byte) 0xB7, 0x5D, (byte) 0x87,
0x15, (byte) 0xA1, (byte) 0x96, 0x29, 0x10, 0x7B, (byte) 0x9A, (byte) 0xC7,
(byte) 0xF3, (byte) 0x91, 0x78, 0x6F, (byte) 0x9D, (byte) 0x9E, (byte) 0xB2, (byte) 0xB1,
0x32, 0x75, 0x19, 0x3D, (byte) 0xFF, 0x35, (byte) 0x8A, 0x7E,
0x6D, 0x54, (byte) 0xC6, (byte) 0x80, (byte) 0xC3, (byte) 0xBD, 0x0D, 0x57,
(byte) 0xDF, (byte) 0xF5, 0x24, (byte) 0xA9, 0x3E, (byte) 0xA8, (byte) 0x43, (byte) 0xC9,
(byte) 0xD7, 0x79, (byte) 0xD6, (byte) 0xF6, 0x7C, 0x22, (byte) 0xB9, 0x03,
(byte) 0xE0, 0x0F, (byte) 0xEC, (byte) 0xDE, 0x7A, (byte) 0x94, (byte) 0xB0, (byte) 0xBC,
(byte) 0xDC, (byte) 0xE8, 0x28, 0x50, 0x4E, 0x33, 0x0A, 0x4A,
(byte) 0xA7, (byte) 0x97, 0x60, 0x73, 0x1E, 0x00, 0x62, 0x44,
0x1A, (byte) 0xB8, 0x38, (byte) 0x82, 0x64, (byte) 0x9F, 0x26, 0x41,
(byte) 0xAD, 0x45, 0x46, (byte) 0x92, 0x27, 0x5E, 0x55, 0x2F,
(byte) 0x8C, (byte) 0xA3, (byte) 0xA5, 0x7D, 0x69, (byte) 0xD5, (byte) 0x95, 0x3B,
0x07, 0x58, (byte) 0xB3, 0x40, (byte) 0x86, (byte) 0xAC, 0x1D, (byte) 0xF7,
0x30, 0x37, 0x6B, (byte) 0xE4, (byte) 0x88, (byte) 0xD9, (byte) 0xE7, (byte) 0x89,
(byte) 0xE1, 0x1B, (byte) 0x83, 0x49, 0x4C, 0x3F, (byte) 0xF8, (byte) 0xFE,
(byte) 0x8D, 0x53, (byte) 0xAA, (byte) 0x90, (byte) 0xCA, (byte) 0xD8, (byte) 0x85, 0x61,
0x20, 0x71, 0x67, (byte) 0xA4, 0x2D, 0x2B, 0x09, 0x5B,
(byte) 0xCB, (byte) 0x9B, 0x25, (byte) 0xD0, (byte) 0xBE, (byte) 0xE5, 0x6C, 0x52,
0x59, (byte) 0xA6, 0x74, (byte) 0xD2, (byte) 0xE6, (byte) 0xF4, (byte) 0xB4, (byte) 0xC0,
(byte) 0xD1, 0x66, (byte) 0xAF, (byte) 0xC2, 0x39, 0x4B, 0x63, (byte) 0xB6
	};

// таблица обратного нелинейного преобразования
static final byte[] reverse_Pi = {
(byte) 0xA5, 0x2D, 0x32, (byte) 0x8F, 0x0E, 0x30, 0x38, (byte) 0xC0,
0x54, (byte) 0xE6, (byte) 0x9E, 0x39, 0x55, 0x7E, 0x52, (byte) 0x91,
0x64, 0x03, 0x57, 0x5A, 0x1C, 0x60, 0x07, 0x18,
0x21, 0x72, (byte) 0xA8, (byte) 0xD1, 0x29, (byte) 0xC6, (byte) 0xA4, 0x3F,
(byte) 0xE0, 0x27, (byte) 0x8D, 0x0C, (byte) 0x82, (byte) 0xEA, (byte) 0xAE, (byte) 0xB4,
(byte) 0x9A, 0x63, 0x49, (byte) 0xE5, 0x42, (byte) 0xE4, 0x15, (byte) 0xB7,
(byte) 0xC8, 0x06, 0x70, (byte) 0x9D, 0x41, 0x75, 0x19, (byte) 0xC9,
(byte) 0xAA, (byte) 0xFC, 0x4D, (byte) 0xBF, 0x2A, 0x73, (byte) 0x84, (byte) 0xD5,
(byte) 0xC3, (byte) 0xAF, 0x2B, (byte) 0x86, (byte) 0xA7, (byte) 0xB1, (byte) 0xB2, 0x5B,
0x46, (byte) 0xD3, (byte) 0x9F, (byte) 0xFD, (byte) 0xD4, 0x0F, (byte) 0x9C, 0x2F,
(byte) 0x9B, 0x43, (byte) 0xEF, (byte) 0xD9, 0x79, (byte) 0xB6, 0x53, 0x7F,
(byte) 0xC1, (byte) 0xF0, 0x23, (byte) 0xE7, 0x25, 0x5E, (byte) 0xB5, 0x1E,
(byte) 0xA2, (byte) 0xDF, (byte) 0xA6, (byte) 0xFE, (byte) 0xAC, 0x22, (byte) 0xF9, (byte) 0xE2,
0x4A, (byte) 0xBC, 0x35, (byte) 0xCA, (byte) 0xEE, 0x78, 0x05, 0x6B,
0x51, (byte) 0xE1, 0x59, (byte) 0xA3, (byte) 0xF2, 0x71, 0x56, 0x11,
0x6A, (byte) 0x89, (byte) 0x94, 0x65, (byte) 0x8C, (byte) 0xBB, 0x77, 0x3C,
0x7B, 0x28, (byte) 0xAB, (byte) 0xD2, 0x31, (byte) 0xDE, (byte) 0xC4, 0x5F,
(byte) 0xCC, (byte) 0xCF, 0x76, 0x2C, (byte) 0xB8, (byte) 0xD8, 0x2E, 0x36,
(byte) 0xDB, 0x69, (byte) 0xB3, 0x14, (byte) 0x95, (byte) 0xBE, 0x62, (byte) 0xA1,
0x3B, 0x16, 0x66, (byte) 0xE9, 0x5C, 0x6C, 0x6D, (byte) 0xAD,
0x37, 0x61, 0x4B, (byte) 0xB9, (byte) 0xE3, (byte) 0xBA, (byte) 0xF1, (byte) 0xA0,
(byte) 0x85, (byte) 0x83, (byte) 0xDA, 0x47, (byte) 0xC5, (byte) 0xB0, 0x33, (byte) 0xFA,
(byte) 0x96, 0x6F, 0x6E, (byte) 0xC2, (byte) 0xF6, 0x50, (byte) 0xFF, 0x5D,
(byte) 0xA9, (byte) 0x8E, 0x17, 0x1B, (byte) 0x97, 0x7D, (byte) 0xEC, 0x58,
(byte) 0xF7, 0x1F, (byte) 0xFB, 0x7C, 0x09, 0x0D, 0x7A, 0x67,
0x45, (byte) 0x87, (byte) 0xDC, (byte) 0xE8, 0x4F, 0x1D, 0x4E, 0x04,
(byte) 0xEB, (byte) 0xF8, (byte) 0xF3, 0x3E, 0x3D, (byte) 0xBD, (byte) 0x8A, (byte) 0x88,
(byte) 0xDD, (byte) 0xCD, 0x0B, 0x13, (byte) 0x98, 0x02, (byte) 0x93, (byte) 0x80,
(byte) 0x90, (byte) 0xD0, 0x24, 0x34, (byte) 0xCB, (byte) 0xED, (byte) 0xF4, (byte) 0xCE,
(byte) 0x99, 0x10, 0x44, 0x40, (byte) 0x92, 0x3A, 0x01, 0x26,
0x12, 0x1A, 0x48, 0x68, (byte) 0xF5, (byte) 0x81, (byte) 0x8B, (byte) 0xC7,
(byte) 0xD6, 0x20, 0x0A, 0x08, 0x00, 0x4C, (byte) 0xD7, 0x74
	};

// вектор линейного преобразования
static final byte[] l_vec = {
1, (byte) 148, 32, (byte) 133, 16, (byte) 194, (byte) 192, 1,
 (byte) 251, 1, (byte) 192, (byte) 194, 16, (byte) 133, 32, (byte) 148
	};

// массив для хранения констант
static byte[][] iter_C = new byte[32][16];
// массив для хранения ключей
static byte[][] iter_key = new byte[10][64];

Создадим все основные функции:

// функция X
static private byte[] GOST_Kuz_X(byte[] a, byte[] b)
{
    int i;
    byte[] c = new byte[BLOCK_SIZE];
    for (i = 0; i < BLOCK_SIZE; i++)
        c[i] = (byte) (a[i] ^ b[i]);
    return c;
}

// Функция S
static private byte[] GOST_Kuz_S(byte[] in_data)
{
    int i;
    byte[] out_data = new byte[in_data.length];
    for (i = 0; i < BLOCK_SIZE; i++)
    {
    	int data = in_data[i];
    	if(data < 0)
    	{
    		data = data + 256;
    	}	    		
        out_data[i] = Pi[data];
    }
    return out_data;
}

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

// умножение в поле Галуа
static private byte GOST_Kuz_GF_mul(byte a, byte b)
{
    byte c = 0;
    byte hi_bit;
    int i;
    for (i = 0; i < 8; i++)
    {
        if ((b & 1) == 1)
        	c ^= a;
        hi_bit =  (byte) (a & 0x80);
        a <<= 1;
        if (hi_bit < 0)
        	a ^= 0xc3; //полином  x^8+x^7+x^6+x+1
        b >>= 1;
    }	    
	return c;
}
// функция R сдвигает данные и реализует уравнение, представленное для расчета L-функции
static private byte[] GOST_Kuz_R(byte[] state)
{
    int i;
    byte a_15 = 0;
    byte[] internal = new byte[16];
    for (i = 15; i >= 0; i--)
    {
    	if(i == 0)
    		internal[15] = state[i];
    	else	    	
    		internal[i - 1] = state[i];	        
	a_15 ^= GOST_Kuz_GF_mul(state[i], l_vec[i]);
    }	    
    internal[15] = a_15;
    return internal;
}	
static private byte[] GOST_Kuz_L(byte[] in_data)
{
    int i;
    byte[] out_data = new byte[in_data.length];
    byte[] internal = in_data;
    for (i = 0; i < 16; i++)
    {
    	internal = GOST_Kuz_R(internal);
    }
    out_data = internal;
    return out_data;
}

Обратные функции:

// функция S^(-1)
static private byte[] GOST_Kuz_reverse_S(byte[] in_data)
{
    int i;
    byte[] out_data = new byte[in_data.length];
    for (i = 0; i < BLOCK_SIZE; i++)
    {
    	int data = in_data[i];
    	if(data < 0)
    	{
    		data = data + 256;
    	}	    		
      out_data[i] = reverse_Pi[data];
    }
    return out_data;
}
static private byte[] GOST_Kuz_reverse_R(byte[] state)
{
    int i;
    byte a_0;
    a_0 = state[15];
    byte[] internal = new byte[16];
    for (i = 1; i < 16; i++)
    {
        internal[i] = state[i - 1];
        a_0 ^= GOST_Kuz_GF_mul(internal[i], l_vec[i]);
    }
    internal[0] = a_0;
    return internal;
}
static private byte[] GOST_Kuz_reverse_L(byte[] in_data)
{
    int i;
    byte[] out_data = new byte[in_data.length];
    byte[] internal;
    internal = in_data;
    for (i = 0; i < 16; i++)
    	internal = GOST_Kuz_reverse_R(internal);
    out_data = internal;
    return out_data;
}
// функция расчета констант
static private void GOST_Kuz_Get_C()
{
    int i;
    byte[][] iter_num = new byte[32][16];
    for (i = 0; i < 32; i++)
    {
    	for(int j = 0; j < BLOCK_SIZE; j++)
    		iter_num[i][j] = 0;
        iter_num[i][0] = (byte) (i+1);
    }
    for (i = 0; i < 32; i++)
    {
    	iter_C[i] = GOST_Kuz_L(iter_num[i]);
    }
}
// функция, выполняющая преобразования ячейки Фейстеля
static private byte[][] GOST_Kuz_F(byte[] in_key_1, byte[] in_key_2, byte[] iter_const)
{
    byte[] internal;
    byte[] out_key_2 = in_key_1;
    internal = GOST_Kuz_X(in_key_1, iter_const);
    internal = GOST_Kuz_S(internal);
    internal = GOST_Kuz_L(internal);
    byte[] out_key_1 = GOST_Kuz_X(internal, in_key_2);
    byte key[][] = new byte[2][];
    key[0] = out_key_1;
    key[1] = out_key_2;
    return key;
}
// функция расчета раундовых ключей
public void GOST_Kuz_Expand_Key(byte[] key_1, byte[] key_2)
{
    int i;
    
    byte[][] iter12 = new byte[2][];
    byte[][] iter34 = new byte[2][];
    GOST_Kuz_Get_C();
    iter_key[0] = key_1;
    iter_key[1] = key_2;
    iter12[0] = key_1;
    iter12[1] = key_2;
    for (i = 0; i < 4; i++)
    {
        iter34 = GOST_Kuz_F(iter12[0], iter12[1], iter_C[0 + 8 * i]);
        iter12 = GOST_Kuz_F(iter34[0], iter34[1], iter_C[1 + 8 * i]);
        iter34 = GOST_Kuz_F(iter12[0], iter12[1], iter_C[2 + 8 * i]);
        iter12 = GOST_Kuz_F(iter34[0], iter34[1], iter_C[3 + 8 * i]);
        iter34 = GOST_Kuz_F(iter12[0], iter12[1], iter_C[4 + 8 * i]);
        iter12 = GOST_Kuz_F(iter34[0], iter34[1], iter_C[5 + 8 * i]);
        iter34 = GOST_Kuz_F(iter12[0], iter12[1], iter_C[6 + 8 * i]);
        iter12 = GOST_Kuz_F(iter34[0], iter34[1], iter_C[7 + 8 * i]);
        
        iter_key[2 * i + 2] = iter12[0];
        iter_key[2 * i + 3] = iter12[1];
    }
}
// функция шифрования блока
public byte[] GOST_Kuz_Encript(byte[] blk)
{
    int i;
    byte[] out_blk = new byte[BLOCK_SIZE];
    out_blk = blk;
    for(i = 0; i < 9; i++)
    {
    	out_blk = GOST_Kuz_X(iter_key[i], out_blk);
    	out_blk = GOST_Kuz_S(out_blk);
    	out_blk = GOST_Kuz_L(out_blk);
    }
    out_blk = GOST_Kuz_X(out_blk, iter_key[9]);
    return out_blk;
}
//функция расшифрования блока
public byte[] GOST_Kuz_Decript(byte[] blk)
{
    int i;
    byte[] out_blk = new byte[BLOCK_SIZE];
    out_blk = blk;

    out_blk = GOST_Kuz_X(out_blk, iter_key[9]);
    for(i = 8; i >= 0; i--)
    {
    	out_blk = GOST_Kuz_reverse_L(out_blk);
    	out_blk = GOST_Kuz_reverse_S(out_blk);
    	out_blk = GOST_Kuz_X(iter_key[i], out_blk);
    }
    return out_blk;
}

Ну, и функция main

static byte[] key_1 = 
{0x77, 0x66, 0x55, 0x44, 0x33, 0x22, 0x11, 0x00, (byte) 0xff, (byte) 0xee, 
(byte) 0xdd, (byte) 0xcc, (byte) 0xbb, (byte) 0xaa, (byte) 0x99, (byte) 0x88};
static byte[] key_2 = 
{(byte) 0xef, (byte) 0xcd, (byte) 0xab, (byte) 0x89, 0x67, 0x45, 0x23, 0x01,
0x10, 0x32, 0x54, 0x76, (byte) 0x98, (byte) 0xba, (byte) 0xdc, (byte) 0xfe};
static byte[] blk = DatatypeConverter.parseHexBinary("8899aabbccddeeff0077665544332211");

public static void main(String[] args) 
{
	GOST_Kuz_Expand_Key(key_1, key_2);
	byte[] encriptBlok = GOST_Kuz_Encript(blk);
	System.out.println(DatatypeConverter.printHexBinary(encriptBlok));
	byte[] decriptBlok = GOST_Kuz_Decript(encriptBlok);
	System.out.println(DatatypeConverter.printHexBinary(decriptBlok));
}

Мы научились шифровать блок данных, чтобы зашифровать текст, длина которого больше длины блока, существует несколько режимов, описанных в стандарте — ГОСТ 34.13-2015:

  • режим простой замены (Electronic Codebook, ECB);
  • режим гаммирования (Counter, CTR);
  • режим гаммирования с обратной связью по выходу (Output Feedback, OFB);
  • режим простой замены с зацеплением (Cipher Block Chaining, CBC);
  • режим гаммирования с обратной связью по шифротексту (Cipher Feedback, CFB);
  • режим выработки имитовставки (Message Authentication Code, MAC).

Во всех режимах длина текста всегда должна быть кратна длине блока, поэтому текст всегда дополняется справа одним единичным битом и нулями до длины блока.

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

Остальные режимы возможно будут рассмотрены подробно чуть позже.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 51

    –15
    Отличная статья! Продолжайте.
    Жаль не могу + поставить.
      +13
      Извините, так как вам понравилась статья, не поможете объяснить почему порождающий полином для 8 бит выглядит как
      x^8 + x^7 + x^6 + x + 1
      ?
        –5

        Многим из нас нравится мёд, но думаю лишь не все знают как пчелы его делают)

          –7
          Мне подход важен. Полиномы я и сам знаю как записывать. Стиль изложения важен. А формулы в Инстите Математике СОРАН Вам любой мнс напишет.
          P.S. И не понятно что набросились минусами. Я мнение своё высказал. Если хотя бы 2 человека заинтересуются и продерутся сквозь формулы — уже автор миссию свою выполнил.
            +15
            Перевод:
            я очень умный, я намного лучше понял статью чем вы,
            вы сами виноваты что не учились в Институте Математики СОРАН,
            я вам ничего объяснять не буду, вы не продрались сквозь формулы — вы сами виноваты.
            Спасибо, че.
              –5
              Я не учился в ИМ — я там работал (там никто не учится). А учатся в НГУ.
              Пожалуйста че.
              P.S. ХахА — сейчас минуса помчатся.
                +1
                Вообще-то x893 только написал, что ему понравилась статья. А всякие технические вопросы по материалу надо наверное всё таки автору направлять.
              +4

              Всё просто. Порождающий полином — это по модулю чего мы берём при умножении в группе Галуа. Соответственно, чтобы после взятия модуля осталось 8 бит — у этого полинома должна быть восьмая степень, т.е. слагаемое x^8.

                +1
                Добавлю, что порождающий полином почти всегда не единственный, но разные полиномы дают изоморфные (=одинаковые) поля.
                Английская вики говорит, что полином из статьи предпочтительный и ссылается на «Recommended Elliptic Curves for Government Use», pdf линк. Стр 88, D.1.1.3 Choice of Basis for Binary Fields. Но там тоже нет объяснения, только рекомендация
                  0
                  Прошу прощения, я в Институте Математики СОРАН не бывал, видимо поэтому мне по прежнему непонятно: куда в формуле
                  x^8 + x^7 + x^6 + x + 1
                  делись степени 5, 4, 3 и 2? Почему степеней получается 9 (единица в данном случае — это же x^0? Или это какая-то магическая константа)?
                    0
                    Простите, но вот это уже очевидно.

                    То, что в многочлене не записаны члены со степенями 5,4,3,2 — обозначает, что при этих степенях коэффициент равен нулю. Точно так же пишут x вместо 1*x, и пишут 1 вместо 1*x^0. То есть формулу можно записать как
                    1*x^8 + 1*x^7 + 1*x^6 + 0*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 1*x + 1*x^0

                    Касательно степени 8 — в статье написано, что для создания расширенного поля над p^m — требуется порождающий многочлен степени m, то есть в котором есть m+1 коэффициентов со степенями от 0 до m включительно. Здесь у нас поле над 2^8 — соответственно порождающий многочлен 8 степени, с 9 коэффициентами. И никакой магии.
                      0
                      Мне кажется, вы сейчас ответили не на тот вопрос. Уважаемый teakettle как раз и спросил, почему коэффициенты при степенях 5,4,3,2 равны нулю. Или, другими словами, почему в качестве порождающего взят _именно этот_ многочлен. Тут вопрос разделяется на два: 1) почему он является неприводимым? 2) какие его свойства выделяют его (вероятно, делают простейшим) среди других неприводимых. Там выше что-то есть про рекомендации, но тема не раскрыта.
                        0
                        Учитывая то, что второй вопрос teakettle был про «почему 9 степеней» — я думаю, что я, к сожалению, не ошибся.
                        К вашим вопросам — 1) Многочлен неприводим, потому что не раскладывается на произведение других делителей. Можете взять и проверить. 2) Никаких особых свойств: можно взять любой неприводимый многочлен 8 степени, получится изоморфное поле Галуа, как выше отметил @Wicirellis.
                          0
                          Спасибо, но вот здесь не понял:
                          Можете взять и проверить.
                          Звучит как «2^82 589 933 − 1- простое число. Можете взять и проверить», только хуже, потому что непонятно, как упорядочивать многочлены, чтобы применить перебор. Или есть какие-то другие способы исчерпывающей проверки?
                            0

                            Для 9 степени проверять надо не так уж много:
                            1) построить все неприводимые многочлены до 4 степени включительно.
                            2) проверить что тестируемый многочлен не делится нацело ни на один из построенных.
                            Пункт первый необязателен, но тогда придется проверять делимость для всех многочленов до 4 степени включительно.

                              0
                              Спасибо, я как-то пропустил тот момент, что коэффициенты всех многочленов могут быть только 0 и 1. Действительно, их не так много и можно упорядочить и перебрать.
                              0
                              а разве разложение многочлена на множители проходят ещё в школе?
                                0
                                Как и сказал Deosis, строите все многочлены до 4 степени включительно и проверяете, что не делится нацело.
                                Если вы не забыли, у нас коэффициенты могут быть только 0 и 1, то есть всего 32 возможных многочлена для проверки. Заметно меньше кандидатов, чем для 2^82 589 933 — 1.
                                  0
                                  Забыл)). Но уже вспомнил.
                  0

                  Что насчёт тайминг атак, особенно учитывая что для эффективности желательно использовать таблицу перестановок размером 1792 байта? Существуют ли оптимизированные bitsliced реализации шифра?


                  Какие реализации оптимизированные под современное железо (SIMD, instruction-level parallelism и т.д.) можете посоветовать?

                    +1
                    Присоединяюсь к вопросу про оптимизированные реализации. Особенно интересует линейное преобразование и в частности под FPGA. Когда-то заинтересовало, выглядит неочевидным, но глубоко не ковырял его, может Вы встречали и порекомендуете чего. В своё время видел данные по очень эффективным реализациям под FPGA этого алгоритма, но деталей особо не раскрывали.
                      0
                      Посмотрите статью «Способы реализации алгоритма «Кузнечик» на программируемых логических интегральных схемах», опубликованную в журнале Радиопромышленность том 28 №3
                      Там господа из Инфотекса провели некоторый разбор различных вариантов реализации линейного преобразования.
                      Со своей стороны могу сказать, что все режимы работы со сцеплением или генерацией имитовставки в чистом виде будут неэффективны в реализациях для FPGA.
                        0
                        Благодарю! Отличная ссылка.
                        Со своей стороны могу сказать, что все режимы работы со сцеплением или генерацией имитовставки в чистом виде будут неэффективны в реализациях для FPGA.

                        Да, с этим согласен.
                    +1

                    У вас в методах GOST_Kuz_Encript и GOST_Kuz_Decript лишнее выделение памяти в переменную out_blk

                      +5
                      Так а что с закладками в s-боксах? ;)
                        0
                        Однако для начала разберем основные операции в более простом поле GF(2^3) с порождающим полиномом x^3+x+1.
                        А дальше по тексту идёт полином x^2+x+1. Так и должно быть?

                        Сразу обращаю внимание, что знак "+" здесь и далее по тексту обозначает операцию побитового XOR, а не сложение в привычном виде
                        А почему тогда сразу не использовать знак для исключающего или?
                          0
                          x^3+x+1 — порождающий полином данного поля.
                          x^2+x+1 — полиномиальное представление числа 7, которое используется в примере.
                            0
                            «порождающий» звучит так, как будто он обобщает некоторое количество полиномов. Было бы понятно, если бы он имел вид x^3+x^2+x+1 — тогда можно было бы подумать, что конкретные полиномы можно получить из коэффициентов при х, приравнивая их нулю или единице, получив таким образом 8 комбинаций. Но даже для этого нужно было писать a*x^3+b*x^2+c*x+1 и определить область значений a,b,c как 0 и 1. Но тут, как я понял, всё не так.
                              0

                              Слово «порождающий» используется в нескольких местах в разных смыслах.
                              В данном случае мы берем все возможные остатки от деления всех возможных полиномов (Над полем из двух элементов) на x^3+x+1.
                              То есть данный полином порождает конкретное поле с конкретными операциями сложения и умножения.

                              0
                              Случайно обнаружил, что в википедии переменная в порождающем полиноме и переменная в полиномиальном представлении элемента поля Галуа — обозначены разными символами, x и i. У вас же и там и там х. Почему?
                            +2
                            А на чем основывается вот именно такой выбор операций?
                            Почему считается, что это дает безопасность?
                              +5

                              Sevastyan01, а сможете рассказать простым языком про последние достижения в криптоанализе Кузнечика — https://who.paris.inria.fr/Leo.Perrin/pi.html ?


                              Говорят, там нашли скрытую алгебраическую структуру в таблице преобразования (которая у вас огромным блоком из байт вставлена), такая же скрытая структура выявлена в белорусском ГОСТовом шифре, а авторы Кузнечика после публикации сливаются, говоря что это всё случайность.

                                +2
                                А вы что именно хотели бы услышать? Простым языком вы сами всё написали :) Алгоритм формирования s-блока найден сторонними разработчиками. Разработчики Кузнечика утверждают что это случайность, во что, смотря на восстановленный алгоритм вериться мягко говоря с трудом. Атак, даже с учётом алгоритма пока не обнаружено (и в этом свете заверения в случайности работают настолько против Кузнечика, что просто непонятно зачем их повторять)
                                Лично мне особо доставила вставка про французскую лотерею по ссылке Лео Перрена(не уверен в транскрипции). Просто для людей прорвавшихся до этого места необходимости в объяснении масштаба порядка в принципе не должно быть, а у тех, кому это может понадобиться, должно и раньше возникнуть тонна вопросов, так что вставка очень мило и чуждо смотрится в тексте :)
                                0
                                Автор, а чем ваша статья отличается от других подобных статей про Кузнечик?
                                И не Кузнецов, а Кузьмин Алексей Сергеевич
                                  0
                                  Во многих статьях отсутствуют понятные примеры, большинство статей не содержат в себе описания математического аппарата (да, конечно, можно отдельно почитать и про поля Галуа и про все остальное, но когда математика является частью статьи — это намного удобнее). В некоторых статьях описание ограничивается скопированным ГОСТом.
                                  На тему много статей и далеко не все из них я читал, но те, что читал, мне не понравились по выше сказанным причинам.
                                  0
                                    +2
                                    Описать алгоритм — это меньшая из проблем. Настоящая проблема — понять, почему именно такой алгоритм является хотя бы просто достаточным для современных реалий. Ну и было бы чудесно, если изложение строилось примерно так — данная часть алгоритма выполняет такое-то действие, потому что это действие необходимо для… и далее — зачем это действие, почему без него нельзя (или хуже).

                                    По простому — зачем в алгоритме 3 шага? Почему недостаточно одного xor-а? Что даёт последующее нелинейное преобразование? Что даёт наложение линейного преобразования?

                                    Возможно, проблема в размере ключа, а всё остальное каким-то образом повышает сложность вскрытия ключа небольшой длины. Но почему бы об этом не написать?
                                      +8

                                      Автор пытался объяснить "простым" языком и сделал немалую работу, но, увы, статья получилась не простая. Например, автор с ходу использует термин "поле", не объясняя, что это такое, и из-за этого многое остается непонятным. Давайте я попробую это восполнить.


                                      Поле — это конечное или бесконечное множество каких-то элементов (например: целых чисел или многочленов или латинских букв), над которыми определены операции "сложения" и "умножения" и соблюдаются определенные условия.


                                      Как известно, есть множество чисел, и над ними можно делать математические операции: складывать, вычитать, умножать, и есть связанные с ними математические правила (вроде x + 0 = x или (a + b) * c = a * c + b * c). Позже математикам захотелось обобщить математические операции, чтобы их можно было выполнять не только с числами, а с любыми объектами: с множеством из чисел от 0 до 9, множеством из многочленов, двумерных векторов, множеством латинских букв, цветных шариков, котят итд. Для этого и были придуманы группы и поля.


                                      Группа — это множество любых элементов (конечное или бесконечное), в котором есть "нулевой" (нейтральный) элемент, определена операция "сложения", и для каждого элемента есть "отрицательный" (противоположный), так, что при сложении с элементом он даст ноль. Естественно, результат сложения тоже должен быть элементом группы.


                                      Пример: множество целых чисел и операция арифметического сложения.


                                      Поле получается, если мы возьмем группу и добавим в нее вторую операцию — умножение, "единичный" элемент и "противоположный" элемент (так, что если x умножить на противоположный элемент, получится 1), а также обеспечим выполнение правила a * (b + c) = a * b + a * c.


                                      По идее, вы можете взять какое-то множество (например, множество чисел от 0 до 9), произвольно определить правила сложения и умножения (1 + 1 = 9, 1 + 2 = 5 и тд), и попробовать получить поле, но на практике у вас скорее всего не будут выполняться все требуемые условия, потому правила сложения и умножения не могут быть произвольными (попробуйте сами, если не верите).


                                      Ну например, математики считают, что если в вашем поле конечное число элементов, то это число должно быть pn, где p — простое число. То есть сделать поле из 72 = 49 элементов можно, а из 48, 50 или 6 (по мнению математиков) — никак не получится.


                                      Самый простой пример конечного поля — это поле остатков от деления на какое-то простое число. Например, поле остатков от деления на 5, состоящее из чисел (0, 1, 2, 3, 4). Пары противоположных чисел по сложению: 1 + 4 = 5 % 5 = 0, 2 + 3 = 0 (соответственно, в нашем поле 0 — 1 = 4, а 0 — 2 = 3). Пары противоположных чисел по умножению: 2 * 3 = 6 % 5 = 1, 4 * 4 = 16 % 5 = 1 (соответственно, 1 ÷ 2 = 3, 1 ÷ 4 = 4).


                                      В статье же используется немного другое поле — поле Галуа. Элементы этого поля GF(28) — это многочлены вида a * x7 + b * x6 + ...g * x + h * 1, где a, b… h — это 0 или 1. Соответственно, эти 8 коэффициентов a… h можно записать в виде двоичного 8-битного числа от 00000000 до 11111111 или от 0 до 255 в десятичной форме. Сложение определено как XOR между элементами в двоичной форме. С умножением сложнее — там используется умножение многочленов, а в случае, если результат будет слишком большим, то он упрощается с использованием порождающего многочлена, который только для этого и нужен (x8 + x7 + x6 + x + 1 = 0).


                                      К счастью, математики также выяснили, что в конечных полях всегда есть примитивный элемент g — такой элемент (то есть, многочлен), что при возведении его в степени от 0 до 255 получатся все другие элементы поля. Соответственно, любой элемент поля можно представить как gn, и вместо сложного умножения многочленов мы приводим их к виду gn * gm (по заранее подготовленной таблице), складываем степени и преобразуем обратно. В данном случае g — это 00010 (в двоичной форме) или x (в форме многочлена). Если вам кажется неочевидным, что возводя x в степень можно получить любой многочлен вроде x3 + x + 1, то напомню, что возведение в степень производится по правилам поля, а не по привычным правилам. При возведении многочлена x в 8-ю степень мы получим x8, который выходит за пределы поля и который надо упрощать через порождающий многочлен.


                                      Таким образом, если мы составим таблицу соответствия двоичной формы многочлена и степени над g, то мы можем забыть про многочлены и далее работать только с числами от 0 до 255 (почему-то в Ява-коде не используется такая таблица, а делается умножение многочленов в "столбик" с упрощением с помощью "вычитания" (XOR) порождающего многочлена).


                                      Жаль, что в источниках вроде википедии все объяснения замудреные, а не написаны простыми словами, и надо ломать голову, пока разберешься.


                                      Кстати, в Википедии написано, что свои поля Галуа открыл и описал в 18 лет в 1830 году. Какой умный!




                                      Добавлю еще про "линейность" и "нелинейность", которые упоминаются в тексте.


                                      Если использовать поле Галуа, то все операции в шифре (кроме операции замены S) — это сложения и умножения в этом поле. Посмотрите на один раунд (шаг) из операций X, S, L:


                                      В начале в операции X каждый байт блока данных C складывается по модулю 2 (ксорится) с ключом K. Это просто сложение в поле Галуа: X(C, K) = C + K.


                                      Затем делается "нелинейная" операция замены по таблице: S(). "Нелинейная" она, так как ее в теории должно быть нельзя записать в виде сложений и умножений.


                                      И наконец, делается линейное преобразование L, где каждый байт умножается в поле Галуа на определенную константу (An) и сдвигается на место соседнего байта в блоке, а на место 16-го байта подставляется сумма всех входящих байтов в поле Галуа. Если мы обозначим n-й байт на входе как In, а на выходе как On, то получим такую связь между входными и выходными данными после выполнения одного раунда шифрования (K — это ключ):


                                      O = L(S(X(I, K)))


                                      O0 = S(I1 + K1) * A1
                                      O1 = S(I2 + K2) * A2

                                      O14 = S(I15 + K15) * A14
                                      O15 = S(I0 + K0) * A0 + S(I1 + K1) * A1 +… S(I15 + K15) * A15


                                      Кроме операции S, все остальные операции — это сложения и умножения, они называются "линейными" и они легко обратимы с помощью вычитания и деления. Если операции S нет, то имея несколько пар "исходный текст" — "шифротекст", можно легко восстановить ключ K. Если операция S спроектирована неудачно, то шифр может быть уязвим к криптоанализу. Потому операция S является важным элементом шифра. И, как показали западные исследователи, таблица S не является полностью случайной, а рассчитана по какой-то формуле, о которой знают, но молчат создатели шифра.


                                      Кстати, можно попробовать "обратить" операции, так как константы A и операция S известны. Получается:


                                      I1 = S-1(O0 / A1) — K1


                                      Незнание K мешает нам получить I, и это только один раунд, а их там всего 10.


                                      Чтобы роль S была понятнее, мы можем рассмотреть примитивный шифр без блока S, когда мы просто ксорим исходный текст с ключом: O = I + K. У этого шифра есть недостаток: если мы знаем открытый текст и шифротекст, то ключ вычисляется элементарно: K = O — I (или O + I, так как сложение и вычитание тут одна и та же операция — XOR). Ну например, у нас есть зашифрованный вордовский файл, а мы знаем что заголовок в вордовских файлах всегда содержит известные "магические" байты. По ним мы вычисляем соответствующие байты ключа.


                                      И второй недостаток: если у нас есть 2 шифротекста (или два куска большого шифротекста), зашифрованных одним ключом, то мы можем их поксорить и получим ксор от исходных текстов, так как при ксоре ключи взаимоликвидируются (K + K = 0).




                                      Выше еще спрашивали, почему выбраны эти операции. Операция X — это добавление ключа к данным. S — добавляет нелинейность для защиты от обращения сложений и умножений. Зачем нужна L — я сам не очень понимаю, она просто переставляет байты местами, и заменяет 1 из 16 байтов на сумму.

                                        0
                                        Спасибо за развёрнутый комментарий, но опять же
                                        Элементы этого поля GF(28) — это многочлены вида a * x7 + b * x6 + ...g * x + h * 1, где a, b… h — это 0 или 1. Соответственно, эти 8 коэффициентов a… h можно записать в виде двоичного 8-битного числа от 00000000 до 11111111 или от 0 до 255 в десятичной форме.

                                        Ну а сам-то х — это что? Переменная? В него можно подставить конкретное значение и вычислить конкретное значение полинома, как мы привыкли это делать в школе?
                                          0

                                          Да, это переменная, да, можно подставить. Но так как идет работа с полиномами целиком, то этого никто не делает до тех пор, пока не понадобится вычислить значение полинома.
                                          Более того эти полиномы нужны только для упрощения вычислений.
                                          Можно обойтись без них. Достаточно привести табличку 256 на 256 для операции "сложения", табличку 256 на 256 для операции "умножения" и доказать, что эти операции удовлетворяют требованиям поля и можно с этим полем работать.
                                          В случае с полиномами: берете неприводимый полином и работаете.

                                            0
                                            Ну ок. Выше автор писал, что x^2+x+1 — полиномиальное представление числа 7. Чему тут равно х?
                                              0

                                              Ничему. Вы, когда ищете производную для обычной параболы (x^2), ищете её для каждой отдельной точки или сразу для всей функции целиком?

                                                0
                                                Если численно — то да, для каждой отдельной точки.
                                              0
                                              Да, это переменная, да, можно подставить
                                              А вот тут с ссылкой на Кнута пишут, что «x может рассматриваться как формальный символ без определяющего значения» — то есть нет, не переменная и нет, нельзя подставить. Кому верить?
                                                0

                                                Вы же сами пишете: «x может рассматриваться как формальный символ...»
                                                А может рассматриваться как полноценная переменная. Но пока вы работаете с элементами поля Галуа, в этом нет необходимости.
                                                Элемент можно рассматривать как полином, а можно — как строку элементов.
                                                В первом случае описать произведение элементов поля проще.

                                              +1

                                              Да, x — это обычная переменная из математики. Значение x не дано, дан только многочлен. Если вы хотите вычислить его значение в какой-то точке (точках), то выберите точку (точки) и подставьте вместо x. Можете даже график нарисовать. Это на самом деле неважно, так как элемент поля у нас — сам многочлен, а не его значение. То есть не важно, чему равен x, важны коэффициенты a… h. Мы складываем и умножаем многочлены, а не их значения в какой-то точке.


                                              Также. у нас порождающий многочлен, по которому можно определить его корни, и значения x, но опять же, это ни на что не повлияет, даже если у него нет корней.

                                                0
                                                А я так понял, что x — это никакая не переменная, а что-то типа мнимой единицы i в комплексных или дуальных числах. Его можно сокращать, заменяя x+x на 0 или x0 на 1, но нельзя вычислять.
                                                  0

                                                  Ваша аналогия не совсем верна, так как i является пусть и неизвестной, но константой, а x — нет. Мне кажется, вы делаете ошибку в том, что признаете только операции над числами. Если вы видите формулу, то вы хотите сначала вычислить значения всех переменных, а потом только делать сложения или умножения.


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


                                                  Ну например, если у меня есть функция f(x) = 3x + 1 и функция g(x) = 2x. Что такое функция? Это зависимость одной переменной от другой, в данном случае, это зависимость переменных f и g от x, выраженная формулой. Заметьте, что мы не знаем, чему равен x, это не дано, и это нам не важно, так как наша формула справедлива для любых x, и она выражает именно связь между переменными, а не конкретные их значения. Нам дана связь между f и x, а не конкретные значения.


                                                  Имея эти функции, я могу их перемножить, даже не зная, чему равен x. Я могу определить функцию h(x) = f(x) * g(x) = (3x + 1) * 2x = 6x2 + 2x. И моя формула верна для любых x — вы можете выбрать любое значение x, вычислить значения f и g в этой точке и увидеть, что их произведение равно значению h в этой точке. То есть я здесь умножил именно функции (зависимости одной переменной от другой). Мне не важно, чему конкретно равен x, так как моя формула справедлива для любых x. Если мне захочется узнать значение функции, например, при x = 5, то я просто подставлю его в формулу.


                                                  Вы пытаетесь зафиксировать какое-то одно значение x. А я предлагаю писать формулы, которые справедливы для любых x.


                                                  То же самое и с полями Галуа. Мы перемножаем не значения многочленов в какой-то точке (при каком-то конкретном значении x), не числа, а сами многочлены. Многочлен — это по сути функция, зависимость y от x. Мы перемножаем эти функции, эти зависимости, а не их значения в одной определенной точке. То есть мы работаем на более высоком уровне абстракции.


                                                  Таким образом, в многочленах x — это переменная, которая может иметь любое значение. Вы должны делать преобразования таким образом, чтобы результаты оставались верными для любых x. То есть если вы складываете многочлены a(x) + b(x) = c(x), то при подстановке любого x в c(x) мы должны получить сумму a(x) и b(x).




                                                  Хотя, я тут перечитал Википедию, и возможно, вы отчасти правы насчет аналогии с i. Вот, что там написано:


                                                  В 1830 году восемнадцатилетний Эварист Галуа опубликовал работу, которая положила основу общей теории конечных полей. В этой работе Галуа (в связи с исследованиями по теории групп перестановок и алгебраических уравнений) вводит воображаемый корень сравнения F ( x ) ≡ 0 ( mod p ), где F(x) — произвольный многочлен степени ν, неприводимый по модулю p.

                                                  После этого рассматривается общее выражение A = a0 + a1 i + a 2 i 2 + … + a ν − 1 i ν − 1, где a0, a1,..., aν − 1 — некие целые числа по модулю p. Если присваивать этим числам всевозможные значения, выражение A будет принимать pν значений.

                                                  Независимо от того, будет x константой или нет, правила операций над многочленами не поменяются, так что это не очень принципиально.

                                                    0
                                                    У меня гуманитарное мышление и я не могу воспринимать математику просто как набор формул с аксиомами — мне её нужно видеть и чувствовать как непротиворечивую часть мировосприятия. Если взять обычный полином (Чебышева например), то можно нарисовать график и мыслить этими графиками — в частности, видеть деформированную синусоиду:

                                                    А с полиномами из полей Галуа так не получится — мы не можем просто так взять и подставить x=0.5, потому что нам только нули и единицы доступны. Конечно, можно попробовать расширить модульную арифметику на поле вещественных, комплексных, гипер-комплексных и прочих чисел — но нужно ещё доказать непротиворечивость получившейся алгебры и к тому же при этом поле автоматически перестанет быть конечным.

                                              0
                                              >> Жаль, что в источниках вроде википедии все объяснения замудреные

                                              Это язык математиков. Они привыкли называть понятия своими любимыми латинизмами. Но при этом возникают ситуации, когда в математике используются одни термины, а в других областях другие. Например — биекция означает привычное для программистов отношение один к одному, но само слово биекция для программистов совершенно не знакомо, хотя обозначаемое им понятие все они отлично знают, вот и получается «замудрёность», когда математики используют свои любимые названия и без зазубривания всей этой каши из латинизмов стороннему наблюдателю просто невозможно понять, о чём вообще говорят математики.

                                              Хотя вообще обозначение одним словом некоего понятия полезно, но в математике ведь этих понятий миллион, и хоть все они такие же примитивные, как и отношение один к одному, текст из набора таких понятий неподготовленному читателю (не зазубрившему) можно читать только со словарём. При чём в словаре пояснения так же содержат латинизмы, которые нужно опять искать в словаре, и уровень вложенности такого поиска может быть очень глубоким. А при глубокой вложенности человек напрочь забывает, о чём он читал, когда начал искать первое непонятное слово. Поэтому математика — наука со страшным уклоном в зубрёжку. Если весь словарь не зазубрил — вложенность непонятных терминов (а ещё греческие да всякие еврейские буквы) убьёт смысл прочитанного. Отсюда и ассоциации математиков с заучками, сухарями, зубрилками и т.д.
                                              +4
                                              «Совершенно случайно, в багажнике моего автомобиля завалялось несколько классических фильмов ужасов… совершенно случайно» (с)
                                              Как-то делал вот такой рендер, мне кажется, будет в тему:

                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                              Самое читаемое