<< Предыдущая

стр. 9
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

дулю (Xn – 1), т.е.
a(X) = a0 * Xn?1 + a1 * Xn?2 + ... + an?2 * X + an?1 ,
совпадает с идеалом, порожденным многочленом g (X) в алгебре многочленов по модулю (Xn – 1).
Доказательство этой теоремы можно найти в [69].
Заметим, что если при таком определении многочлена a(X) элементы a 0 , a1, a 2 ,... вычисля-
ются в порядке возрастания номеров, то коэффициенты многочлена a(X) вычисляются, начиная с
коэффициентов при степенях высших порядков. Следует также отметить, что вид многочлена h(X) =
k
j
? hj X определяет конфигурацию обратных связей (отводов) hj в генераторе со сдвиговым регист-
j=0
ром. Другими словами, если у многочлена h(X) коэффициент hj= 1, это означает, что отвод hj в схе-
ме генератора присутствует, если же у многочлена h(X) коэффициент hj = 0, то отвод hj в схеме
генератора отсутствует. В [58] показано, что в качестве h(X) необходимо выбирать неприводимый
примитивный многочлен (см. также приложение). При таком выборе многочлена h(X) со старшей
степенью m генератор обеспечивает выдачу псевдослучайной последовательности двоичных чисел с
максимально возможным периодом 2m – 1.
Рассмотрим в качестве примера трехразрядный сдвиговый регистр с линейной обратной свя-
зью (рис. 2.13), построенный в соответствии с неприводимым примитивным многочленом
h(X) = X3 + X2 + 1,
где коэффициенты h3 = 1, h2 = 1, h1 = 0, h0 = 1.
Пусть ключом является 101. Регистр начинает работать с этого состояния; последователь-
ность состояний регистра приведена на рис. 2.13. Регистр проходит через все семь ненулевых со-
стояний и снова возвращается в свое исходное состояние 101. Это – наиболее длинный период дан-
ного регистра с линейной обратной связью. Такая последовательность называется последователь-
ностью максимальной длины для сдвигового регистра (Maximal Lenght Shift Register Sequence –
MLSRS). Питерсон и Уэлдон [69] показали, что при любом целом m существует m-битовая последо-
вательность MLSRS с периодом 2m – 1. В частности, при m =100 последовательность будет иметь
период 2100 – 1 и не повторится 1016 лет при передаче ее по линии связи со скоростью 1 Мбит/с.
3-битовый ключ
Ключевой поток 101
Гш = 1010011 010
h3 =1 h2 =1 h1 =1 h0 =1
001
100
110
111
011
C = Гш ? M
M
Гш
Рис. 2.13. Трехразрядный регистр сдвига с обратными связями
(генератор гаммы шифра Гш)


В нашем примере выходной последовательностью (гаммой шифра) Гш сдвигового регистра с
обратной связью является последовательность 1010011, которая циклически повторяется. В этой
последовательности имеется четыре единицы и три нуля, и их распределение настолько близко к
равномерному, насколько это возможно в последовательности, имеющей длину 7. Если рассмотреть
пары последовательных битов, то пары 10 и 01 появляются по два раза, а пары 00 и 11 – один
раз, что опять оказывается настолько близким к равномерному распределению, насколько это воз-
можно. В случае последовательности максимальной длины для m-разрядного регистра это свойство
равнораспределенности распространяется на тройки, четверки и т.д. битов, вплоть до m-битовых
групп. Благодаря такой близости к равномерному распределению последовательности максимальной
длины часто используются в качестве псевдослучайных последовательностей в криптографических
системах, которые имитируют работу криптостойкой системы одноразового шифрования.
Хотя такая криптографическая система осуществляет имитацию заведомо криптостойкой сис-
темы одноразового шифрования, сама она не отличается стойкостью и может быть раскрыта за не-
сколько секунд работы компьютера при условии наличия известного открытого текста [29].
Если отводы регистра с обратной связью зафиксированы, то для нахождения начального со-
стояния регистра достаточно знать m битов открытого текста. Чтобы найти m битов ключевого по-
тока, m битов известного открытого текста складывают по модулю 2 с соответствующими m битами
шифртекста. Полученные m битов дают состояние сдвигового регистра с обратной связью в обрат-
ном направлении на некоторый момент времени. Затем, моделируя работу регистра назад, можно
определить его исходное состояние.
Если отводы регистра с обратной связью не фиксированы, а являются частью ключа, то дос-
таточно 2m битов известного открытого текста, чтобы сравнительно быстро определить расположе-
ние отводов регистра и его начальное состояние. Пусть S(i) – вектор-столбец, состоящий из m сим-
волов 0 и 1, который определяет состояние регистра в i-й момент времени. Тогда
S(i + 1) = A ? S(i) mod 2,
где A – матрица размером m?m, определяющая положение отводов регистра с обратной связью.
Для трехразрядного регистра (рис.2.13)
101
A= 1 0 0.
010
Матрица A всегда имеет следующую структуру: в ее первой строке отражена последова-
тельность отводов в регистре, непосредственно под главной диагональю располагаются единицы, а в
остальных позициях располагаются нули.
2m битов известного открытого текста позволяют вычислить 2m последовательных битов
ключевого потока. Для упрощения обозначений предположим, что это – первые 2m битов ключевого
потока. Следовательно,
• S(1) – первая группа m известных битов ключевого потока;
• S(2) – следующая группа (начиная с номера 2) из m известных битов ключевого потока;
• S(m+1) – последняя группа из m известных битов ключевого потока.
Далее можно образовать две матрицы размером m?m:
X(1) = [S(1), S(2), …, S(m)],
X(2) = [S(2), S(3), …, S(m+1)],
которые связаны соотношением
X(2) = A ? X(1) mod 2.
Можно показать, что для любой последовательности максимальной длины матрица X(1) все-
гда несингулярна, поэтому матрицу A можно вычислить как
A = X(2) [X(1)]–1 mod 2.
Обращение матрицы X(1) требует (самое большее) порядка m3 операций, поэтому легко вы-
полняется при любом разумном значении m.
Для криптографии последовательности максимальной длины MLSRS можно сделать более
криптостойкими, используя нелинейную логику. В частности, предложен вариант [29], в котором в ка-
честве ключевого потока используется нелинейно "фильтрованное" содержимое сдвигового регистра,
а для получения последовательности максимальной длины – линейная обратная связь, как показано
на рис. 2.14. M
f
C = Гш ? M
Гш



h3 = 1 h2 = 1 h1 = 1



Рис. 2.14. Линейный сдвиговый регистр с нелинейными
логическими цепями на выходе
Функция f должна выбираться так, чтобы обеспечить хороший баланс между нулями и еди-
ницами, а фильтрованная последовательность имела распределение, близкое к равномерному. Не-
обходимо также, чтобы фильтрованная последовательность имела большой период. Если (2m – 1)
является простым числом (как в примере: при m = 3 имеем 23 – 1 = 7), то фильтрованная последо-
вательность может иметь период (2m – 1) (при выборе структуры сдвигового регистра в соответствии
с неприводимым примитивным многочленом h(X) степени m).
К таким значениям m относятся, в частности, следующие:
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, а полученные таким образом про-
стые числа называются простыми числами Мерсенна.
Несмотря на то, что фильтрованную выходную последовательность обычно нельзя получить
с помощью m-разрядного сдвигового регистра с линейной обратной связью, ее всегда можно полу-
чить с помощью сдвигового регистра большей длины с линейной обратной связью [59]. Регистр дли-
ной (2m – 1) всегда позволит это сделать, а иногда пригоден и более короткий регистр.
Еще более привлекательно использование в цепи обратной связи нелинейной логики, однако
теория таких схем недостаточно хорошо освещена (в открытой литературе).
ГЛАВА 3. СОВРЕМЕННЫЕ СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ
По мнению К. Шеннона [101], в практических шифрах необходимо использовать два общих
принципа: рассеивание и перемешивание.
Рассеивание представляет собой распространение влияния одного знака открытого текста на
много знаков шифртекста, что позволяет скрыть статистические свойства открытого текста.
Перемешивание предполагает использование таких шифрующих преобразований, которые
усложняют восстановление взаимосвязи статистических свойств открытого и шифрованного текстов.
Однако шифр должен не только затруднять раскрытие, но и обеспечивать легкость зашифрования и
расшифрования при известном пользователю секретном ключе.
Распространенным способом достижения эффектов рассеивания и перемешивания является
использование составного шифра, т.е. такого шифра, который может быть реализован в виде неко-
торой последовательности простых шифров, каждый из которых вносит свой вклад в значительное
суммарное рассеивание и перемешивание.
В составных шифрах в качестве простых шифров чаще всего используются простые переста-
новки и подстановки. При перестановке просто перемешивают символы открытого текста, причем
конкретный вид перемешивания определяется секретным ключом. При подстановке каждый символ
открытого текста заменяют другим символом из того же алфавита, а конкретный вид подстановки так-
же определяется секретным ключом. Следует заметить, что в современном блочном шифре блоки
открытого текста и шифртекста представляют собой двоичные последовательности обычно длиной
64 бита. В принципе каждый блок может принимать 264 значений. Поэтому подстановки выполняются
в очень большом алфавите, содержащем до 264 ? 1019 "символов".
При многократном чередовании простых перестановок и подстановок, управляемых достаточ-
но длинным секретным ключом, можно получить очень стойкий шифр с хорошим рассеиванием и пе-
ремешиванием. Рассмотренные ниже криптоалгоритмы DES, IDEA и отечественный стандарт шиф-
рования данных построены в полном соответствии с указанной методологией.


3.1. Американский стандарт шифрования данных DES
Стандарт шифрования данных DES (Data Encryption Standard) опубликован в 1977 г. Нацио-
нальным бюро стандартов США. Стандарт DES предназначен для защиты от несанкционированного
доступа к важной, но несекретной информации в государственных и коммерческих организациях
США. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980
г. был одобрен Национальным институтом стандартов и технологий США (НИСТ). С этого момента
DES превращается в стандарт не только по названию (Data Encryption Standard), но и фактически.
Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для
шифрования и расшифрования информации в сетях передачи данных.
К настоящему времени DES является наиболее распространенным алгоритмом, используе-
мым в системах защиты коммерческой информации. Более того, реализация алгоритма DES в таких
системах становится признаком хорошего тона.
Основные достоинства алгоритма DES:
• используется только один ключ длиной 56 бит;
• зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использо-
вать любой другой пакет программ, соответствующий стандарту DES;
• относительная простота алгоритма обеспечивает высокую скорость обработки;
• достаточно высокая стойкость алгоритма.
Первоначально метод, лежащий в основе стандарта DES, был разработан фирмой IBM для
своих целей и реализован в виде системы "Люцифер". Система "Люцифер" основана на комбиниро-
вании методов подстановки и перестановки и состоит из чередующейся последовательности блоков
перестановки и подстановки. В ней использовался ключ длиной 128 бит, управлявший состояниями
блоков перестановки и подстановки. Система "Люцифер" оказалась весьма сложной для практиче-
ской реализации из-за относительно малой скорости шифрования (2190 байт/с – программная реали-
зация, 96970 байт/с – аппаратная реализация).
Алгоритм DES также использует комбинацию подстановок и перестановок. DES осуществляет
шифрование 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими явля-
ются 56 бит (остальные 8 бит – проверочные биты для контроля на четность). Дешифрование в DES
является операцией, обратной шифрованию, и выполняется путем повторения операций шифрова-
ния в обратной последовательности. Обобщенная схема процесса шифрования в алгоритме DES по-
казана на рис.3.1. Процесс шифрования заключается в начальной перестановке битов 64-битового
блока, шестнадцати циклах шифрования и, наконец, в конечной перестановке битов.


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


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


ключ
16 раз Шифрование



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


Шифртекст


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

Следует сразу отметить, что все приводимые таблицы являются стандартными и должны
включаться в реализацию алгоритма DES в неизменном виде.
Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы мак-
симально затруднить процесс расшифровки путем подбора ключа. При описании алгоритма DES
(рис. 3.2) применены следующие обозначения:
L и R – последовательности битов (левая (left) и правая (right));
Входная последовательность битов
1,2,... 64
Начальная перестановка Р



L0 R0
1,2,... 32 1,2,... 32

K1
f


L1 = R0 R1= L0 ? f (R0,K1)
K2
f


L2 = R1 R2= L1 ? f (R1,K2)
Ki
f


L15 = R14 R15=L14? f(R14,K15)
K16
f

R14=L15? f(R15,K16) L16 = R15

Конечная перестановка IР
-1



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

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

LR – конкатенация последовательностей L и R, т.е. такая последовательность битов, длина
которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за
битами последовательности L;
? – операция побитового сложения по модулю 2.
2
Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот
блок Т преобразуется с помощью матрицы начальной перестановки IP (табл. 3.1).
Таблица 3.1
Матрица начальной перестановки 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

<< Предыдущая

стр. 9
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>