Перестановки, инверсные начальным

Вывод данных блоками по 64 бит

Рис.2.1. Алгоритм шифрования DES.

Затем входной блок с переставленными битами поступает на схему пересчетов, которая состоит из 16 последовательно включенных узлов- повторителей (преобразования в каждом из них повторяют предыдущие).

Здесь информационный блок (64 бита) разбивается на две части L и R по 32 бита, которые поступают на два входа повторителя. Входной блок теперь может быть обозначен как LR. На третий вход повторителя поступают блоки К по 48 бит со схемы образования ''ключа''. Блоки R и K обрабатываются по закону, который задается шифровальной функцией f(R,K). Каждый бит полученного блока длиной 32 бита складывается по модулю два с битами блока L.

При этом выходные блоки L’ и R’ повторителя при входных блоках L и R и ключе К будут равны:

L’=R

R’=L (+) f(R,K)

где (+)- обозначает сложение по модулю два информационных бит, поступающих с одного и другого направления.

Алгоритм вычисления f(R,K) приведен на рисунке 2.2.

R (32 бита)

48 бит

K(48 бит)

32 бит

Рис.2.2. Вычисление f(R,K).

Здесь Е- функция которая преобразует 32 бита (на входе) в 48 бит (на выходе). 48 бит выхода (8 блоков по 6 бит) получаются выбором битов (входных) в соответствии с таблицей 2.2.

Таблица 2.2. ''Е''(таблица битового выбора)
32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

Далее функция Sn 6 бит (на входе) преобразует в 4 бита (на выходе). Рассмотрим это преобразование на примере функции S1:

Строка	Номер столбца
№		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0		14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1		0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2		4	1	14	8	13	6	2	11	15	12	9	7	13	10	5	0
3		15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	3

Если S1- функция определенная в этой таблице и В- блок из 6 бит, то S(B) определяется: первый и последний биты в блоке В в двоичной системе представляют число в области 0-3. Пусть это число равно i. Средние 4 бита в блоке В в двоичной системе представляют число в области 0-15. Пусть это число равно j. Найдем в таблице число в i-той колонке и j-том столбце. Это число в области от 0 до 15 и в двоичной системе представляется 4-х битовым блоком. Этот блок является выходом S1 для введенного В. Например, если В=011011, то номер колонки равен 1 (01В), номер столбца 13 (1101В). По таблице находим а колонке 1 и столбце 13 число 5, то есть на выходе число 0101. Функции S1,S2…S8 приведены в таблице 2.4.

Функция перестановки Р определяется таблицей 2.3.

Таблица 2.3. Функция перестановки Р.
16	7	20	21
29	12	28	17
1	15	23	26
5	18	31	10
2	8	24	14
32	27	3	9
19	13	30	6
22	11	4	25

Выходное значение P(L) для P определенного этой таблицей получается следующим образом: с блока L берется 16-й бит L как первый бит P(L), 7-й бит как второй бит P(L), и так далее пока 25-й бит L не взят как 32-й бит P(L).

Теперь пусть S1,...,S8 будут восемь функций выбора, P-функция перестановки и пусть E будет функция определенная выше.

Для того, чтобы определять f(R,K) мы сначала определяем B1,...,B8 (по 6 битов каждый):

B1B2...B8 = K(+)E(R) (2.1)

блок f(R,K) затем определяется:

P(S1(B1)S2(B2)...S 8(B8)) (2.2)

Таким образом K(+)E(R) сначала разделяется на 8 блоков как указано в (2.1). Затем каждый Bi взят как ввод в Si и 8 блоков (S1(B1)S2(B2)...S8(B8) по 4 бита каждое преобразовываются в 1 блок 32 бита, который вводится в P. Выход Р (2.2) является затем выходом функции f для вводов R и K.

Таблица 2.4. Функции S1…S8
S1
14	4	13	1	2	15	11	8	3	10	6	12	5	9		0	7
0	15	7	4	14	2	13	1	10	6	12	11	9	5		3	8
4	1	14	8	13	6	2	11	15	12	9	7	3	10		5	0
15	12	8	2	4	9	1	7	5	11	3	14	10	0		6	13
S2
15	1	8	14	6	11	3	4	9	7	2	13	12	0		5	10
3	13	4	7	15	2	8	14	12	0	1	10	6	9		11	5
0	14	7	11	10	4	13	1	5	8	12	6	9	3		2	15
13	8	10	1	3	15	4	2	11	6	7	12	0	5		14	9
S3
10	0	9	14	6	3	15	5	1	13	12	7	11	4		2	8
13	7	0	9	3	4	6	10	2	8	5	14	12	11		15	1
13	6	4	9	8	15	3	0	11	1	2	12	5	10		14	7
1	10	13	0	6	9	8	7	4	15	14	3	11	5		2	12
S4
7	13	14	3	0	6	9	10	1	2	8	5	11	12		4	15
13	8	11	5	6	15	0	3	4	7	2	12	1	10		14	9
10	6	9	0	12	11	7	13	15	1	3	14	5	2		8	4
3	15	0	6	10	1	13	8	9	4	5	11	12	7		2	14
S5
2	12	4	1	7	10	11	6	8	5	3	15	13	0		14	9
14	11	2	12	4	7	13	1	5	0	15	10	3	9		8	6
4	2	1	11	10	13	7	8	15	9	12	5	6	3		0	14
11	8	12	7	1	4	2	3	6	15	0	9	10	4		5	3
S6
12	1	10	15	9	2	6	8	0	13	3	4	14	7		5	11
10	15	4	2	7	12	9	5	6	1	13	14	0	11		3	8
9	14	15	5	2	8	12	3	7	0	4	10	1	13		11	6
4	3	2	12	9	5	15	10	11	14	1	7	6	0		8	13
S7
4	11	2	14	15	0	8	13	3	12	9	7	5	10		6	1
13	0	11	7	4	9	1	10	14	3	5	12	2	15		8	6
1	4	11	13	12	3	7	14	10	15	6	8	0	5		9	2
6	11	13	8	1	4	10	7	9	5	0	15	14	2		3	12
S8
13	2	8	4	6	15	11	1	10	9	3	14	5	0		12	7
1	15	13	8	10	3	7	4	12	5	6	11	0	14		9	2
7	11	4	1	9	12	14	2	0	6	10	13	15	3		5	8
2	1	14	7	4	10	8	13	15	12	9	0	3	5		6	11

Принято, что KS (n,KEY) есть фунеция, которая определяется целым числом n, которое изменяется от 1 до 16 (n- номер повторителя) ключом (KEY) из 64 бит. Алгоритм вычисления Kn приведен на рис.2.3. Рассмотрим алгоритм получения функции KS. Сначала 64 бит ключа подвергаются перестановке PC-1 (таблица 2.5).

Таблица 2.5. Дополнительные перестановки PC-1.
57	49	41	33	25	17	9
1	58	50	42	34	26	18
10	2	59	51	43	35	27
19	11	3	60	52	44	36
63	55	47	39	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

Таблица разделена на две части, в первой части выбираются биты C0 , во второй- биты D0. Биты ключа перечислены с 1 по 64. Биты C0 являются соответственно битами 57, 49, 41,..., 44 и 36 ключа, биты D0, являются битами 63, 55, 47,..., 12 и 4ключа.