Лекция. 12 База данных

Н

К

R

1,2.

Начальная перестановка!?

	1,2,...
					к,
I

R. =L₀©f(R₀,K,)

Исходный текст

Начальная перестановка

L, =R,

R₂=L,ef(R,,K₂)

16 раз

Шифрование

Ключ

©«-

г «

к,

Конечная перестановка

- ^R

R₁₅=L,₄©f(R₁₄,K₁₅)

Шифртекст

Рис.3.1. Обобщенная схема шифрования в алгоритме DES

R_w=L₁₅ef(R_1J,K_w)

-1

Следует сразу отметить, что все приводимые таблицы яв­ляются стандартными и должны включаться в реализацию алго­ритма DES в неизменном виде.

Все перестановки и коды в таблицах подобраны разработ­чиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. При описании алгоритма DES (рис. 3.2) применены следующие обозначения:

L и R - последовательности битов (левая (left) и пра­вая (right));

1,2...

Конечная перестановка IP

Выходная последовательность битов (шифртекст)

Рис.3.2. Структура алгоритма DES

LR - конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

© - операция побитового сложения по модулю 2.

Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помо­щью матрицы начальной перестановки IP (табл. 3.1).

Таблица 3.1 Матрица начальной перестановки IP

Биты входного блока Т (64 бита) переставляются в соот­ветствии с матрицей IP: бит 58 входного блока Т становится битом 1, бит 50 - битом 2 и т.д. Эту перестановку можно описать выра­жением Т_о = IP(T). Полученная последовательность битов Т_о разделяется на две последовательности: L_o - левые или старшие биты, R_o - правые или младшие биты, каждая из которых содер­жит 32 бита.

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Tj - результат i-й итерации:

Т: = Li R,,

где Li = U t₂... t₃2 (первые 32 бита); R_s = t₃31₃4... t₆4 (последние 32 бита). Тогда результат i-й итерации описывается следующими формулами:

Lj = R_i_₁, i = 1, 2 16;

R_i = L_i_₁©f(R_M,K_i), i= 1,2 16.

Функция f называется функцией шифрования. Ее аргумен­тами являются последовательность Rm, получаемая на предыду­щем шаге итерации, и 48-битовый ключ Kj, который является ре­зультатом преобразования 64-битового ключа шифра К. (Подроб­нее функция шифрования f и алгоритм получения ключа К, описаны ниже.)

На последнем шаге итерации получают последовательно­сти R^ и L₁₆ (без перестановки местами), которые конкатенируются в 64-битовую последовательность R₁₆ L₁₆.

По окончании шифрования осуществляется восстановле­ние позиций битов с помощью матрицы обратной перестановки IP"¹ (табл.3.2).

Таблица 3.2 Матрица обратной перестановки IP"¹

Пример того, как соотносятся элементы первой строки матрицы 1Р~¹ с элементами матрицы IP приведен в табл. 3.3.

Таблица 3.3

Связь элементов	матриц
Элемент матрицы IP"'		Элемент матрицы IP

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровы­ваемые данные сначала переставляются в соответствии с матри­цей IP"¹, а затем над последовательностью битов R₁₆L₁₆ выпол­няются те же действия, что и в процессе шифрования, но в обрат­ном порядке.

Итеративный процесс расшифрования может быть описан следующими формулами:

Ri-i = Li, 1=1,2 16;

L+.1 = R,-Ф f (Ц K|), i = 1,2,..., 16.

Таким образом, для процесса расшифрования с перестав­ленным входным блоком R16L16 на первой итерации используется ключ «16, на второй итерации - К₁₅ и т.д. На 16-й итерации ип-пользуется ключ Ki. На последнем шаге итерации будут получены последовательности L_o и R_Ol которые конкатенируются в 64-битовую последовательность LoR_o. Затем в этой последователь­ности 64 бита переставляются в соответствии с матрицей IP. Ре-

LR - конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

©-операция побитового сложения по модулю 2.

Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помо­щью матрицы начальной перестановки IP (табл. 3.1).

Таблица 3.1 Матрица начальной перестановки IP

Биты входного блока Т (64 бита) переставляются в соот­ветствии с матрицей!Р: бит 58 входного блока Т становится битом 1, бит 50 - битом 2 и т.д. Эту перестановку можно описать выра­жением Т_о = IP(T). Полученная последовательность битов То разделяется на две последовательности: Lo - левые или старшие биты, R_o-правые или младшие биты, каждая из которых содер­жит 32 бита.

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Т,- результат i-й итерации:

Т, = Ц R_i(

где Lj = ti t₂... t32 (первые 32 бита); R, = t₃₃1₃₄... t₆4 (последние 32 бита). Тогда результат i-й итерации описывается следующими формулами:

Li = R_M, i = 1.2 16;

Ri = LM©f(RM, Ki), i= 1,2 16.

Функция f называется функцией шифрования. Ее аргумен­тами являются последовательность R_w, получаемая на предыду­щем шаге итерации, и 48-битовый ключ Kj, который является ре­зультатом преобразования 64-битового ключа шифра К. (Подроб­нее функция шифрования f и алгоритм получения ключа К, описаны ниже.)

На последнем шаге итерации получают последовательно­сти Ri6 и 1_1б (без перестановки местами), которые конкатенируются в 64-битовую последовательность R₁₆ Це.

-.-1

По окончании шифрования осуществляется восстановле­ние позиций битов с помощью матрицы обратной перестановки

IP"¹ (табл. 3.2).

Таблица 3.2 Матрица обратной перестановки IP"¹

Пример того, как соотносятся элементы первой строки матрицы IP"¹ с элементами матрицы IP приведен в табл. 3.3.

Таблица 3.3

Связь элементов	матриц
Элемент матрицы IP"'		Элемент матрицы IP

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровы­ваемые данные сначала переставляются в соответствии с матри­цей IP"¹, а затем над последовательностью битов R₁₆L₁₆ выпол­няются те же действия, что и в процессе шифрования, но в обрат­ном порядке.

Итеративный процесс расшифрования может быть описан следующими формулами:

Ri-i = Li, 1 = 1,2 16;

LM = Ri©f(UK,). i = 1,2 16.

Таким образом, для процесса расшифрования с перестав­ленным входным блоком R₁₆Li6 на первой итерации используется ключ «16, на второй итерации - К^ и т.д. На 16-й итерации ис­пользуется ключ Ki. На последнем шаге итерации будут получены последовательности L_o и R_o, которые конкатенируются в 64-битовую последовательность L_oRo. Затем в этой последователь­ности 64 бита переставляются в соответствии с матрицей IP. Ре-

зультат такого преобразования - исходная последовательность битов (расшифрованное 64-битовое значение).

Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f (Ri_i,Kj) показана на рис. 3.3.

Ri_-i (32 бита)

		Расширитель Е
48 бит -"^	г	К, (48 бит)
Г
Si £	>2 S	з £	4 £	5 £	к £	>7 £>8
			Г
	Перестановка битов Р

I 32 бита

f(RM,Ki)

Рис.3.3. Схема вычисления функции шифрования f

Для вычисления значения функции f используются:

• функция Е (расширение 32 бит до 48);

• функция Sl S₂,..., S₈ (преобразование 6-битового числа в 4-
битовое);

• функция Р (перестановка битов в 32-битовой последователь­
ности).

Приведем определения этих функций.

Аргументами функции шифрования f являются R_M (32 би­та) и К; (48 бит). Результат функции Е (Rm) есть 48-битовое чис­ло. Функция расширения Е, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), опре­деляется табл. 3.4.

В соответствии с табл. 3.4 первые три бита Е (Rj_i) - это биты 32, 1 и 2, а последние - 31, 32, 1. Полученный результат (обозначим его E(R,_₁)) складывается по модулю 2 (операция XOR)

Таблица 3.4 Функция расширения Е

с текущим значением ключа К, и затем разбивается на восемь 6-битовых блоков Bi, В₂,..., Be:

Е (Ri-i) Ф Kj = Bi В₂... В₈.

Далее каждый из этих блоков используется как номер эле­мента в функциях-матрицах S'l S₂,..., S₈, содержащих 4-битовые значения (табл. 3.5).

Следует отметить, что выбор элемента в матрице Sj осу­ществляется достаточно оригинальным образом. Пусть на вход матрицы Sj поступает 6-битовый блок Bj = b-i b₂ b₃ b₄ Ьб b₆, тогда двухбитовое число bi b₆ указывает номер строки матрицы, а че­тырехбитовое число Ь₂ Ь₃ b₄ b₅ - номер столбца. Например, если на вход матрицы S! поступает 6-битовый блок Bi= bi b₂ b₃ b₄ b₅ b₆ ⁼ = 100110, то 2-битовое число Ь, b₆ = 10₍₂₎ = 2₍₁₀j указывает строку с номером 2 матрицы S^ а 4-битовое число b₂ b₃ b₄ Ь₅=0011₍₂)=3(₁₀) указывает столбец с номером 3 матрицы S^ Это означает, что в матрице St блок Вт = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8₍₁₀₎ = =1000(2). Совокупность 6-битовых блоков Bl B₂,..., В₈ обеспечивает выбор четырехбитового элемента в каждой из матриц Si, S₂,..., S₈.

В результате получаем S^BO S₂(B₂) S₃(B₃)... S₈(B₈), т.е. 32-битовый блок (поскольку матрицы Sj содержат 4-битовые элемен­ты). Этот 32-битовый блок преобразуется с помощью функции пе­рестановки битов Р (табл.3.6).

Таким образом, функция шифрования

f(R_i_₁,K_i) = P(S₁(B₁)....... S_e(B₈)).

Как нетрудно заметить, на каждой итерации используется новое значение ключа К, (длиной 48 бит). Новое значение ключа Kj вычисляется из начального ключа К (рис.3.4). Ключ К представ­ляет собой 64-битовый блок с 8 битами контроля по четности, рас­положенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл. 3.7).

зультат такого преобразования - исходная последовательность битов (расшифрованное 64-битовое значение).

Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f (Ri_i,Kj) показана на рис. 3.3.

R_M (32 бита)

			Расширитель Е
	48 бит -— \ Л	r	Kj (48 бит)
r
	Si S	2 S	з £	A S	5 £	>6 £	>7 S8
		r
Перестановка битов Р

I

32 бита

Рис.3.3. Схема вычисления функции шифрования f

Для вычисления значения функции f используются:

• функция Е (расширение 32 бит до 48);

• функция Si, S₂,..., S₈ (преобразование 6-битового числа в 4-
битовое);

• функция Р (перестановка битов в 32-битовой последователь­
ности).

Приведем определения этих функций.

Аргументами функции шифрования f являются Rm (32 би­та) и К| (48 бит). Результат функции Е (R_M) есть 48-битовое чис­ло. Функция расширения Е, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), опре­деляется табл. 3.4.

В соответствии с табл. 3.4 первые три бита Е (Rj_i) - это биты 32, 1 и 2, а последние - 31, 32, 1. Полученный результат (обозначим его E(R,_i)) складывается по модулю 2 (операция XOR)

Таблица 3.4 Функция расширения Е

с текущим значением ключа Kj и затем разбивается на восемь 6-
битовых блоков Bi, B_2.......... В₈:

Е (Rj_i) © Kj = Bi В₂... Be.

Далее каждый из этих блоков используется как номер эле­мента в функциях-матрицах S'l S₂,..., S₈, содержащих 4-битовые значения (табл. 3.5).

Следует отметить, что выбор элемента в матрице Sj осу­ществляется достаточно оригинальным образом. Пусть на вход матрицы Sj поступает 6-битовый блок B_f = bi b₂ b₃ b₄ b₅ b₆, тогда двухбитовое число bi b₆ указывает номер строки матрицы, а че­тырехбитовое число Ь₂ Ь₃ b₄ b₅ - номер столбца. Например, если на вход матрицы Si поступает 6-битовый блок Bi= bi b₂ b₃ b₄ b₅ b₆ = = 100110, то 2-битовое число b₁ b₆ = 10₍₂₎ = 2₍₁₀₎ указывает строку с номером 2 матрицы S_1t а 4-битовое число b₂ b₃ b₄ Ь₅=0011₍₂)=3₍₁₀) указывает столбец с номером 3 матрицы S-|. Это означает, что в матрице Si блок В, = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8₍₁₀₎ = =1000(2). Совокупность 6-битовых блоков Bi, B₂,..., В₈ обеспечивает выбор четырехбитового элемента в каждой из матриц Si, S₂,..., S₆.

В результате получаем S^B-,) S₂(B₂) S₃(B₃)... S₈(B₈), т.е. 32-битовый блок (поскольку матрицы Sj содержат 4-битовые элемен­ты). Этот 32-битовый блок преобразуется с помощью функции пе­рестановки битов Р (табл.3.6).

Таким образом, функция шифрования

f(R_i_₁,K_i) = P(S₁(B₁)....... S₈(B₈)).

Как нетрудно заметить, на каждой итерации используется новое значение ключа Kj (длиной 48 бит). Новое значение ключа К, вычисляется из начального ключа К (рис.3.4). Ключ К представ­ляет собой 64-битовый блок с 8 битами контроля по четности, рас­положенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл. 3.7).

I -i.

Таблица 3.6 Функция Р перестановки битов

Таблица 3.5

Функци»

i преобразования

S,,

S2...

.s,

Номер

столбца

Si

S?

s3

н

м

.0

' 3

s4

е

Р

s5

с

1?

т

sB

к

и

.1

s7

^7

s8

Ключ К

Функция G

C_o (28 бит)

Do (28 бит)

Сдвиг влево

Сдвиг влево

Функция Н

Сдвиг влево

Сдвиг влево

D₂

Функция

Сдвиг влево

Сдвиг влево

■Мб

N16

Функция н

Рис.3.4. Схема алгоритма вычисления ключей К,

Табл. 3.7 разделена на две части. Результат преобразова­ния G(K) разбивается на две половины С_о и D_o по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбирают-

Таблица 3.7

20 28 23 31 24 3 30

12 15 18 8 27 13 11

32 19 22

Функция G первоначальной подготовки ключа (переставленная выборка 1)

						36..........
~63~				~3~1 ~
			46.
					37 -

ся биты последовательности С_о (первым битом С_о будет бит 57 ключа шифра, затем бит 49 и т.д., а последними битами - биты 44 и 36 ключа).

Следующие четыре строки матрицы G определяют, как выбираются биты последовательности D_o (т.е. последователь­ность D_o будет состоять из битов 63, 55, 47,...,12, 4 ключа шифра).

Как видно из табл. 3.7, для генерации последовательно­стей С_о и D_o не используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут слу­жить для других целей (например, для контроля по четности). Та­ким образом, в действительности ключ шифра является 56-битовым.

После определения С_о и D_o рекурсивно определяются Q и D_it i = 1, 2,..., 16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в табл. 3.8.

Операции сдвига выполняются для последовательностей BMCHMO. Например, последовательность С₃ получается посредством циклического сдвига влево на две позиции последо­вательности С₂, а последовательность D₃ - посредством сдвига влево на две позиции последовательности D₂, C₁₆ и D₁₆ получают­ся из С₁₅ и D15 посредством сдвига влево на одну позицию.

Таблица 3.8

Таблица сдвигов s, для вычисления ключа

Номер итерации	Количество s, сдвигов влево, бит	Номер итерации	Количество & сдвигов влево, бит

Ключ К|, определяемый на каждом шаге итерации, есть результат выбора конкретных битов из 56-битовой последователь­ности С, D| и их перестановки. Другими словами, ключ Kj=H(Cj Dj), где функция Н определяется матрицей, завершающей обработку.ключа (табл. 3.9).

Таблица 3.9

Функция Н завершающей обработки ключа (переставленная выборка 2)

ключа Ki будет 14-й

Как следует из табл.3.9, первым битом ivi.гили ,^^_yM4, •-,-„ бит последовательности С, Dj, вторым - 17-й бит, 47-м битом клю­ча К, будет 29-й бит Cj Dj, а 48-м битом - 32-й бит Cj Dj.

3.2.0сновные режимы работы алгоритма DES

Алгоритм DES вполне подходит как для шифрования, так и для аутентификации данных. Он позволяет непосредственно пре­образовывать 64-битовый входной открытый текст в 64-битовый выходной шифрованный текст, однако данные редко ограничива­ются 64 разрядами.

Чтобы воспользоваться алгоритмом DES для решения разнообразных криптографических задач, разработаны четыре рабочих режима:

• электронная кодовая книга ЕСВ (Electronic Code Book);

• сцепление блоков шифра СВС (Cipher Block Chaining);

• обратная связь по шифртексту CFB (Cipher Feed Back);

• обратная связь по выходу OFB (Output Feed Back).

Режим "Электронная кодовая книга"

Длинный файл разбивают на 64-битовые отрезки (блоки) по 8 байтов. Каждый из этих блоков шифруют независимо с ис­пользованием одного и того же ключа шифрования (рис.3.5).

Основное достоинство - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков. Из-за фиксированного характера шифрования при ограниченной длине блока 64 бита возможно проведение криптоанализа "со словарем". Блок такого размера может повто­риться в сообщении вследствие большой избыточности в тексте

Дата добавления: 2014-12-16