Переставленная Выборка 1 (РС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

 

1.2.2 Разделите переставленный ключ на две половины. Первые 28 бит названы С[0], последние - D[0].

1.2.3 Вычислите 16 подключей. Начните с i=1.

1.2.3.1 Выполните один или два циклических сдвига влево на оба C[i-1] и D[i-1] чтобы получить C[i] и D[i] соответственно. Число сдвигов на итерацию приведено в таблице ниже.

Итерация #     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Сдвиги влево 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

1.2.3.2. Переставьте конкотанацию C[i]D[i] как показано ниже. Это будет K[i] длиной в 48 бит.

Переставленная Выборка 2 (РС2)

 

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

 

1.2.3.2 Переход к 1.2.3.1 до тех пор пока k[16] не вычислено.

2 Обработка 64- битного блока данных.

2.1 Возьмите 64-х битный блок данных. Если блок короче чем 64 бита, его следует заполнить до 64.

2.2 Выполните следующие перестановки над блоком данных.

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

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

 

2.3 Разделите блок на две половины. Первые 32 бита названы L[0], а последние 32 - R[0].

2.4 Примените 16 подключей к блоку данных. Начните с i=1.

2.4.1 Расширьте 32-х битный R[i-0] до 48 бит согласно функции выборки битов.

Расширение (Е)

 

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

 

2.4.2 Исключающее или E(R[i-1]) с ключом K[i].

2.4.3 Разделите E(R[i-1]) xor K[i] на 6-и битные блоки. Биты 1-6 - В[1], биты 7-12 - В[2], и так далее. Биты 43-48 будут В[8].

2.4.4 Каждая из функций, или блоков выбора S_j принимает в качестве входных данных 6-битовые блоки B[j] и порождает 5-битовый блок. Начинаем с j=1.

2.4.4.1 1-й и 6-й биты B[j] как 2-битное значение (m) показывают ряд в S[j] для замены (от 0 до 3).

2.4.4.2 От 2-го до 5-го бита B[j] как 4-битное значение (n) показывают колонку (столбец) в S[j] для нахождения замены (от 0 до 15).

2.4.4.3  Замените B[j] на S[j][m][n].

Блок замены 1 (S[1])

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

S[2]

15	1	8	14	6	11	3	4	9	7	2	14	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

S[3]

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

S[4]

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	5	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

S[5]

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	14	2	13	6	15	0	9	10	4	5	3

 

S[6]

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

S[7]

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

S[8]

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

 

2.4.4.4 Переход к пункту 2.4.4.1 до тех пор пока все 8 блоков не будут заменены.

2.4.5 Переставьте конкатенацию B[1]..B[8] как показано ниже.

Перестановка Р

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

2.4.6 Исключающее или с L[i-1]. Таким образом, ваше R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])), где B[j]- это 6-и битный блок от E(R[i-1])xorK[i]. (Функция для R[i] - более кратко записана как R[i]=L[i-1] xor f(R[i-1],K[i].)

2.4.7 L[i]=R[i-1].

2.4.8 Переход к пункту 2.4.1 до тех пор пока не применен K[16].

2.5 Выполнить следующие перестановки на блоке R[16]L[16].

Последняя перестановка(IP^-1)

40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	57	25

Это было описание использования алгоритма DES для шифрования одного 64-битного блока. Для расшифровки используйте подобные вычисления, но используйте ключи K[i] в обратном порядке. То есть вместо ключа K[1] применяйте K[16], затем K[15] и так далее до K[1].

Для шифрования или расшифрования более чем 64 битного блока имеются официальные режимы (определенные в FIPS PUB 81). Один из них - вычисления для каждого блока в ряде. Он назван режимом электронной кодовой книги. Более сильный метод заключается в суммировании по модулю два блока открытого текста с блоком шифртекста, прежде зашифрованным. (Первый блок складывается по модулю два с секретным 64 - битным инициализирующим вектором (IV). Этот инициализирующий вектор - обычно случайная величина, которая содержится вместе с ключом.) Данный метод называется связыванием шифр-блоков (Сifer Block Chaining, CBC). Другие два режима - режим с выходной обратной связью (Output Feedback mode, OFB) и шифрование с обратной связью (Cifer Feedback mode, CFB), распространяющие искажения в открытом тексте, что применяется для проверки целостности информации.

Пусть открытый текст a₁, a₂,...,a_n шифруется в режиме СВС на ключе К, в результате чего получается шифротекст b₁, b₂,...,b_n. Из блока b_n шифротекста выделяются первые m битов, которые и составляют вектор аутентификации U (проверочный вектор) для сообщений, передаваемых в незашифрованном виде. Если сообщение передается в зашифрованном виде, то вектор U можно образовать из первых m битов выходного блока алгоритма, полученного при зашифровании последнего блока шифротекста b_n в режиме ECB. Изменение хотя бы одного бита открытого сообщения в обоих случаях приводит к изменению вектора U с вероятностью, близкой к 1-2^-m, в силу зависимости каждого бита проверочного вектора от каждого бита открытого сообщения.

 При хранении сообщения в файлах (или передаче его по линии связи) вектор U хранится (пересылается) вместе с сообщением. Обнаружение искажения происходит после генерации проверочного вектора и сравнения его с хранящимся (присланным) вектором. Величина m определяется пользователем исходя из требуемого уровня надежности аутентификации данных. В частности, согласно требованиям Федерального Стандарта 1027 США величина m меньше 24.

 Для заполнения блоков имеется несколько режимов. Один из них - простое дополнение нулей. Второй предлагается в FIPS PUB 81, если данные являются двоичными, заполните блок битами, противоположными последнему биту данных, или, если данные -в ASCII - формате, заполните блок случайными символами и поместите ASCII -символ, определяющий количество заполняющих символов в последний байт блока.

Число различных ключей DES-алгоритма равно 2⁵⁶ = 7*10¹⁶. После опубликования алгоритма в США открыто обсуждались его криптографические свойства. Недавние исследования показали, что современная технология позволяет создать вычислительное устройство стоимостью около 1 млн. долларов, способное вскрыть секретный ключ с помощью полного перебора в среднем за 3,5 часа. Параллельно в ходе исследований DES были разработаны два мощных метода криптоанализа итеративных шифров типа DES: дифференциальный криптоанализ и линейный криптоанализ. Эти методы реализуются быстрее полного перебора, но требуют большого количества специальных открытых текстов (около 10¹⁴ и 10¹³ блоков соответственно).

Из-за небольшого размера ключа было принято решение использовать DES-алгоритм для закрытия коммерческой (несекретной) информации. Практическая реализация перебора всех ключей в данных условиях экономически нецелесообразна, так как затраты на реализацию перебора не соответствуют ценности информации, закрываемой шифром.

Системы c открытым ключом

 Как бы ни были сложны и надежны симметричные криптосистемы, их слабое место - проблема распределения ключей. Для того, чтобы был возможен обмен конфиденциальной информацией между двумя субъектами, ключ должен быть сгенерирован одним из них, а затем каким-то образом опять же в конфиденциальном порядке передан другому, т.е. в общем случае для передачи ключа опять же требуется использование криптосистемы. Для решения этой проблемы на основе результатов, полученных классической и современной алгеброй, были предложены системы с открытым ключом, или, как их еще называют, системы асимметричного шифрования. Суть их состоит в том, что каждым адресатом генерируются два ключа, связанные между собой по определенному правилу. Один ключ объявляется открытым, а другой закрытым. Открытый ключ публикуется и доступен любому, кто желает послать сообщение адресату, а секретный сохраняется в тайне. Исходный текст шифруется открытым ключом адресата и передается ему. Зашифрованный текст не может быть расшифрован тем же открытым ключом. Дешифрование сообщение возможно только с использованием закрытого ключа, который известен только самому адресату.

Криптографические системы с открытым ключом используют так называемые необратимые, или односторонние функции, которые обладают следующим свойством: при заданном значении x относительно просто вычислить значение y=f(x), однако нет простого пути для вычисления значения x по y. Множество классов необратимых функций и порождает все разнообразие систем с открытым ключом. Однако не всякая необратимая функция годится для использования в реальных ИС. В самом определении необратимости присутствует неопределенность. Под необратимостью понимается не теоретическая необратимость, а практическая невозможность вычислить обратное значение используя современные вычислительные средства за обозримый интервал времени. Поэтому, чтобы гарантировать надежную защиту информации, к системам с открытым ключом (СОК) предъявляются два важных и очевидных требования:

1. Преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа.

2. Определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых систем и рекомендован МККТТ.

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

1. Разложение больших чисел на простые множители.

2. Вычисление логарифма в конечном поле.

3.Вычисление корней алгебраических уравнений.

Здесь же следует отметить, что алгоритмы криптосистемы с открытым ключом (СОК) можно использовать в трех назначениях.

1. Как самостоятельные средства защиты передаваемых и хранимых данных.

2. Как средства для распределения ключей. Алгоритмы СОК более трудоемки, чем традиционные криптосистемы. Поэтому часто на практике рационально с помощью СОК распределять ключи, объем которых как информации незначителен. А потом с помощью обычных алгоритмов осуществлять обмен большими информационными потоками.

3.Средства аутентификации пользователей.

Наиболее надежные и распространенные алгоритмы асимметричного шифрования приведены в таблице:

Таблица 2
Алгоритмы асимметричного шифрования

Тип	Описание
RSA	Популярный алгоритм асимметричного шифрования, стойкость которого зависит от сложности факторизации больших целых чисел.
ECC (криптосистема на основе эллиптических кривых)	Использует алгебраическую систему, которая описывается в терминах точек эллиптических кривых. Является конкурентом по отношению к другим асимметричным алгоритмам шифрования, так как при эквивалентной стойкости использует ключи меньшей длины и имеет большую производительность. Современные его реализации показывают, что эта система гораздо более эффективна, чем другие системы с открытыми ключами. Его производительность приблизительно на порядок выше, чем производительность RSA, Диффи-Хеллмана и DSA.
Эль-Гамаль.	Вариант Диффи-Хеллмана, который может быть использован как для шифрования, так и для электронной подписи.

Рассмотрим наиболее распространенные системы с открытым ключом.

Алгоритм Диффи-Хеллмана

Американские криптологи Диффи и Хеллман предложили схему распространения (рассылки) ключей для секретной связи на основе односторонней показательной функции. Ее суть состоит в следующем.

В протоколе обмена секретными ключами предполагается, что все пользователи знают некоторые числа n и a (1< a < n). Для выработки общего секретного ключа пользователи A и B должны проделать следующую процедуру:

1. Определить секретные ключи пользователей К_А и К_В.

Для этого каждый пользователь независимо выбирает случайные числа из интервала (1,..., n-1).

2. Вычислить открытые ключи пользователей Y_A и Y_B.

Для этого каждый использует одностороннюю показательную функцию Y=a^k mod n со своим секретным ключом.

3. Обменяться ключами Y_A и Y_B по открытому каналу связи.

4. Независимо определить общий секретный ключ К.

Для этого пользователи выполняют вычисления с помощью той же односторонней функции

A: Y_B^KA(mod n) = ^[ a ^{KB ]KA} mod n = a ^KA*KB mod n = K.

B: Y_A^KB(mod n) = ^[ a ^{KA ]KB} mod n = a ^KB*KA mod n = K.

Здесь каждый имеет показатель степени, а основание получает от партнера

Алгоритм RSA

Несмотря на довольно большое число различных СОК, наиболее популярна - криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.

Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин популярности этой СОК на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHTР, S-MIME, S/WAN, STT и РСT.

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

Теорема 1. (Малая теорема Ферма.)

Если р - простое число, и НОД(x,р)=1, то

x^р-1 = 1 (mod р) (1)

для любого х, простого относительно р, и

x^р = х (mod р) (2)

для любого х.

Определение. Функцией Эйлера (n) называется число положительных целых, меньших n и простых относительно n.

n 2 3 4 5 6

(n) 1 2 2 3 2

Теорема 2. Если n=рq, (р и q - отличные друг от друга простые числа), то

(n)=(р-1)(q-1).

Теорема 3. Если n=рq, (р и q - отличные друг от друга простые числа) и х - простое относительно р и q, то

x⁽ⁿ⁾ = 1(mod n).

Следствие. Если n=рq, (р и q - отличные друг от друга простые числа) и е простое относительно (n), то отображение Е_e,n:x=x^e (mod n) является взаимно однозначным на Z_n.

Очевиден и тот факт, что если е - простое относительно (n), то существует целое d, такое, что

ed = 1 (mod (n)) (3)

На этих математических фактах и основан популярный алгоритм RSA.

Пусть n=рq, где р и q - различные простые числа. Если e и d удовлетворяют уравнению (3), то отображения Е_e,n и Е_d,n являются инверсиями на Zn. Как Е_e,n, так и Е_d,n легко рассчитываются, когда известны e, d, р, q. Если известны e и n, но р и q неизвестны, то Е_e,n представляет собой одностороннюю функцию; нахождение Е_d,n по заданному n равносильно разложению n. Если р и q - достаточно большие простые, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA.

Пользователь i выбирает пару различных простых р_i и q_i и рассчитывает пару целых (e_i, d_i), которые являются простыми относительно (n_i), где n_i=р_i q_i. Справочная таблица содержит публичные ключи {(e_i,n_i)}.

Предположим, что исходный текст

x =(x₀, x₁,..., x_n-1), xÎZ_n, 0 £i < n,

сначала представлен по основанию n_i: (т.е. с_i<n_i)

N = с₀+..+с_i(n_i)+.... (конкатенация)

Пользователь i зашифровывает текст при передаче его пользователю j, применяя к n отображение E_di,ni:

N E_di,ni :n = n'.

Пользователь j производит дешифрование n', применяя E_ei,_ni:

N' E_ei,ni:n'= E_ei,ni:(E_di,ni:n) = n.

Очевидно, для того чтобы найти инверсию E_di,_ni по отношению к E_ei,_ni, требуется знание множителей n=р_i*q_i. Время выполнения наилучших из известных алгоритмов разложения при n=10¹⁰⁰ на сегодняшний день выходит за пределы современных технологических возможностей.

Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA.

Пример. Зашифруем сообщение "САВ". Для простоты будем использовать маленькие числа (на практике применяются гораздо большие).

1. Выберем р=3 и q=11.

2. Определим n=3*11=33.

3. Найдем (р-1)(q-1)=20. Следовательно, в качестве d, взаимно простое с 20, например, d=3.

4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А1, В2, С3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (3⁷) (mod 33) = 2187 (mod 33) = 9,

ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

6.Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (9³) (mod 33) = 729 (mod 33) = 3,

ИТ2= (1³) (mod 33) = 1 (mod 33) = 1,

ИТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.

Итак, в реальных системах алгоритм RSA реализуется следующим образом: каждый пользователь выбирает два больших простых числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа e и d. Как результат умножения первых двух чисел (р и q) устанавливается n. {e,n} образует открытый ключ, а {d,n} - закрытый (хотя можно взять и наоборот). Открытый ключ публикуется и доступен каждому, кто желает послать владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. После шифрования, сообщение невозможно раскрыть с помощью открытого ключа. Владелец же закрытого ключа без труда может расшифровать принятое сообщение.

В настоящее время алгоритм RSA активно реализуется как в виде самостоятельных криптографических продуктов, так и в качестве встроенных средств в популярных приложениях. Важная проблема практической реализации - генерация больших простых чисел. В принципе в качестве р и q можно использовать "почти" простые числа, то есть числа для которых вероятность того, что они простые, стремится к 1. Но в случае, если использовано составное число, а не простое, криптостойкость RSA падает. Имеются неплохие алгоритмы, которые позволяют генерировать "почти" простые числа с уровнем доверия 2^-100.

Другая проблема - ключи какой длины следует использовать? В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров.Сами авторы RSA рекомендуют использовать следующие размеры модуля n:

* 768 бит - для частных лиц;

* 1024 бит - для коммерческой информации;

* 2048 бит - для особо секретной информации.

Третий немаловажный аспект реализации RSA - вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной k бит, то для операций по открытому ключу требуется О(k²) операций, по закрытому ключу - О(k³) операций, а для генерации новых ключей требуется О(k⁴) операций.

Криптографический пакет BSAFE 3.0 (RSA D.S.) на компьютере Рentium-90 осуществляет шифрование со скоростью 21.6 Кбит/с для 512-битного ключа и со скоростью 7.4 Кбит/с для 1024 битного. Самая быстрая аппаратная реализация обеспечивает скорости в 60 раз больше. По сравнению с тем же алгоритмом DES, RSA требует в тысячи и десятки тысяч раз большее время. Поэтому часто RSA используют в качестве электронного конверта.

Криптосистема Эль-Гамаля

Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость.

В отличие от RSA, метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.

Основу системы составляют параметры р и g - числа, первое из которых - простое, а второе - целое.

П1 генерирует секретный ключ а и вычисляет открытый ключ y = gа mod р. Если П2 хочет послать П1 сообщение m, то он выбирает случайное число k, меньшее р и вычисляет

y₁ = g^k mod р и

y₂ = m*y^k,

где * означает побитовое сложение по модулю 2. Затем П2 посылает (y1,y2) П1.

П1, получив зашифрованное сообщение, восстанавливает его:

m = (y₁^a mod р)*y₂.

Алгоритм цифровой подписи DSA, разработанный NIST (National Institute of Standard and Teсhnology) и являющийся частью стандарта DSS частично опирается на рассмотренный метод.