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

стр. 24
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Sj = Sj-i © 5j_3.

Допустим, что перед началом процесса в регистре записана после­
довательность [0,0,1], тогда период генерируемого потока битов
будет равен 7, и мы получаем последовательность, представленную
в табл. 5.8.
Поскольку внутреннее состояние на седьмом шаге вернулось к
исходному, то начиная со следующего шага мы будем получать по­
вторения. Иными словами, период последовательности оказался ра­
вен 7, что произошло ввиду примитивности многочлена Х^ +Х + 1.
Мы не будем здесь обсуждать существующие алгоритмы, ге­
нерирующие примитивные многочлены. Ограничимся лишь неболь-
Глава 5. Симметричные шифры

шим списком таких многочленов с малым числом отводов. Очевид­
но, что чем меньше отводов в многочлене, тем быстрее работает
соответствующий регистр сдвига.
Х^^+Х^ + 1, Х^^+Х^ + 1,
^ 3 9 + Х^ + 1, Х^° + X + 1, Х^^ + Х + 1,
Х^^ + Х^ + 1,
X'^^ + X^ + l,


Хотя РСЛОС быстро генерирует поток битов, исходя из ключа
малого размера, особенно при аппаратной реализации, они плохо
подходят для целей криптографии ввиду их линейности, собственно,
именно того свойства, которое придает им высокую эффективность
в аппаратных средствах.

Таблица 5.8. Пример генерируемой последовательности бит
Номер шага состояние генерируемый бит
0 [0,0,1] -
1 1
[1,0,0]
2 [1,1,0] 0
0
3 [1,1,1]
4 1
[0,1,1]
1
5 [1,0,1]
б [0,1,0] 1
0 1
7 [0,0,1]

Обосновывая слабую криптостойкость линейных регистров, по­
кажем, что зная длину / регистра и 21 последовательных битов, вы­
шедших из РСЛОС^ можно вычислить весь генерируемый поток.
Заметим, что для этого нам достаточно определить значения от­
водов, т. е. набор Ci коэффициентов ассоциированного многочлена,
поскольку стартовое состояние регистра 5о, . . . , Si-i можно взять
из известной нам последовательности сгенерированных битов. Та­
кие данные можно получить с помощью атаки с известным откры­
тым текстом, когда мы получаем шифрограмму, соответствуюш;ую
известной нам части исходного сообш;ения. Напомним, что функ­
ция обратной связи в этой ситуации — просто сложение значений
отводов по модулю 2, действующая по формуле

Sj = y^Ci • Sj-i (mod2).
j-i
5.6. Современные поточные шифры 155

Используя это соотношение р^ля j = Z, . . . , 2/ — 1, получим систе­
му / линейных уравнений с неизвестными с^, которые нам и нужно
определить. В матричной форме эта система выглядит следующим
образом:
/ Si-i / Cl
гЛ
So \
Sl-2 Si
Si Si Si-\-i
Si-1 52 C2




S2I-3 S2I-A ••• Si-i Sl-2 Q_i S2I-2
\S21-2 S21-3 ••• Si Si-iJ \ Q/ \S21-1J
Предположим, что мы перехватили последовательность битов
1,1,1,1,0,1,0,1,1,0,0,1,0,0,0,... ,
созданную 4-битовым РСЛОС. Подставляя в предыдущую систему
уравнений элементы перехваченной последовательности и решая ее
по модулю 2, найдем, что многочлен, ассоциированный с РСЛОС,
равен Х"^ -\-Х +1. Можно сделать вывод, что поточный шифр, осно­
ванный на единственном РСЛОС^ беззап1;итен перед атаками с из­
вестным открытым текстом.
Мерой криптографического качества последовательности бит слу­
жит понятие линейной сложности последовательности.

Определение 5.2. Линейной слоэюностью бесконечной последова­
тельности битов
S= 5 0 , ^ 1 , .§2, « 5 3 , . . . ,

называется величина L{s)^ равная
- О, если S — последовательность нулей,
- ОС, если S нельзя получить с помош;ью какого-нибудь РСЛОС^
- длине наименьшего РСЛОС^ выдаюш;его последовательность s
в остальных случаях.

Поскольку бесконечную последовательность битов просмотреть
невозможно, ограничиваются ее первыми п элементами, обозначая
эту часть как 5^. Имеют место следующие свойства.
- Для любого п ^ 1 выполнено неравенство О ^ L{s^) ^ п.
- Если последовательность s периодична и ее период равен iV,
то L{s) < N,
- L{s®t) ^L{s)-\-L{t),
Глава 5, Симметричные шифры

Ожидаемая линейная сложность случайной двоичной последователь­
ности 5^ (именно ее мы и хотели бы видеть в качестве потока
ключей) должна быть больше, чем п/2. С другой стороны, РСЛОС
длины / выдает последовательность, чья линейная сложность удо­
влетворяет соотношению: L{s'^) = I для всех п ^ I. Таким образом,
линейный регистр генерирует потоки битов слишком далекие от
случайных.
Как мы видели, зная длину РСЛОС и генерируемую им последо­
вательность битов, можно вычислить ассоциированный с регистром
многочлен. Для определения длины регистра используется ряд ли­
нейных сложностей, т.е. последовательность L{s^), L{s'^)^ L{s^)^
Кроме того, суш;ествует эффективный алгоритм Берлекэмпа - Мэс-
си, вычисляющий ряд линейных сложностей L{s^), L{s'^)^ . . . , L{s^)
для данной конечной последовательности s^.
Следовательно, при генерировании потока ключей регистром сдви­
га с линейной обратной связью длины /, атакуюш;ий, получив не
более 21 последовательных битов этого потока, может раскрыть ре­
гистр полностью и самостоятельно производить бегуш;ий ключ лю­
бой нужной ему длины. Поэтому возникает необходимость найти
нелинейный способ эксплуатации РСЛОС^ при котором генерируе­
мая последовательность обладает высокой линейной сложностью.

5.6.2. Комбинирование РСЛОС
На практике используют несколько ре­
гистров с линейной обратной связью од­
\LFSR-4\-
нелинейная
новременно, генерируя совокупность по­
\LFSR'3\-
комбинирующая
\LFSR-2\- следовательностей д;| , • • •, Хп • Ключом
функция
UFSR'l такого способа эксплуатации служит на-
Р 5 19 К б чальное положение всех РСЛОС ^ а генери-
ние РСЛОС руемый поток битов получается в резуль­
тате применения нелинейной комбиниру­
ющей функции к их выходным последовательностям, как показано
на рис. 5.19.
В качестве комбинирующей выбирают булеву функцию, равную
сумме различных произведений переменных, например,
f{xi,X2, Хз, Х4, Х^) = 1 ® Х2 ® Хз ® Х4 • Xs ® XI • Х2 ' Хз • Х^.

Предположим, что у нас есть п РСЛОС с максимальным периодом
(т. е. ассоциированные многочлены примитивны) с попарно различ­
ными периодами Zi, . . . , In, каждый из которых больше двух. Тог-
5.6. Современные поточные шифры

да линейная сложность потока ключей, генерируемого функцией
/ ( ^ 1 , . . . , ж^), вычисляется с помощью функции / :
/(Zi,...,Zn).
Здесь сложение и умножение по модулю 2 заменено на обычные сло­
жение и умножение целых чисел, так что / записывается в привыч­
ной алгебраической форме. Над развитием способов комбинирова­
ния РСЛОС с целью создания поточных шифров работают много­
численные творческие коллективы. Мы оставляем читателю иссле­
дование этого вопроса по дополнительной литературе, поскольку
объем книги ограничен и мы не можем позволить себе разрабаты­
вать здесь эту тему.

5.6-3. RC4
RC — сокращение от английского Ron's Cipher (шифр Рона). Этот
шифр разработал Рон Ривест (Ron Rivest) из Массачуссетского тех­
нологического института (MIT). Не следует думать, что шифр RC4
— более ранняя версия блочных шифров RC5 и RC6, На самом де­
ле, RC4 — очень и очень быстрый поточный шифр, на удивление
простой для запоминания.
Массив 5 [ 0 . . . 255], заполненный целыми числами от О до 255, пе­
реставленными некоторым, зависящим от ключа, способом, подает­
ся на вход ДС^. В результате работы алгоритма получается поток
ключей fc, который складывается по модулю 2 с открытым текстом
по одному байту за один раз. Поскольку алгоритм оперирует с бай­
тами, а не с битами, и использует наиболее простую операцию, он
является быстрым и в программной реализации. Опишем его по­
дробно. Сначала обнуляются переменные г и jf, а затем повторяется
следующая процедура:

i=(i+l)y.256;
j = (j+S[i])7.256;
swap(S[i], S [ j ] ) ;
t=(S[i]+S[j])y.256;
K=s[t];

Напомним, что %256 обозначает оператор вычисления остатка по
модулю 256 (см. стр. 23), а функция swap меняет местами свои аргу­
менты. Стойкость шифра основана на следующем наблюдении: даже
если нападающий узнал ключ К и номер шага г, он может вычислить
всего лишь значение S[t]^ но не все внутреннее состояние массива.
Глава 5. Симметричные шифры

Это следует из того, что нападающий не в состоянии определить
значение переменной ^, не зная j , S[i] или S[j]
Это очень сильный алгоритм, поскольку каждый его шаг увели­
чивает криптостойкость.
- i=(iH-l)%256 обеспечивает использование каждого элемента
массива, причем однократное.
- j=(j+S[i])%256 обеспечивает нелинейную зависимость выход­
ных данных от массива.
- swap(S[i],S[j]) изменяет массив в процессе итераций.
- t=(S[i]+S[j])%256. Благодаря этому этапу генерируемая по­
следовательность мало говорит о внутреннем состоянии мас­
сива.
Начальная перестановка массива S определяется ключом по сле­
дующему правилу. На старте алгоритма значения ячеек весьма не­
замысловаты: ^[г] = г. В другой массив длиной 256 байтов заносится
необходимое число копий ключа. После этого присваивают параме­
тру j нулевое значение и выполняют следующие шаги, последова­
тельно увеличивая параметр i от О до 255:

j = (j+S[i]+K[i])y.256;
swap(S[i],S[j]);


К р а т к о е с о д е р ж а н и е главы

- Современные шифры с симметричным ключом относятся к
блочным или поточным шифрам.
- Наиболее известный и широко используемый блочный шифр —
это DES^ обобщающий шифр Фейстеля.
- Относительно новый блочный шифр — это Rijndael.
- Как DES^ так и Rijndael добиваются высокой криптостойко-
сти благодаря повторяющимся простым раундам, состоящим
из замен, перестановок и сложений с ключом.
- Нри эксплуатации блочного шифра необходимо уточнять ре­
жим его использования. Простейший режим — это ЕСВ^ кото­
рый, к сожалению, имеет недостатки. Поэтому, как правило,
используется более подходящий режим, а именно, СВС.
- Поточные шифры могут быть получены нелинейным комби­
нированием простых генераторов битовых строк, называемых
5.6. Современные поточные шифры 159

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

Дополнительная литература
Описание алгоритма Rijndael.^ представление о AES и подроб­
ное обсуждение атаки на блочный шифр (в частности и на Rijn­
dael) можно найти в книге Димена и Риймена. В учебнике Стинсона,
предназначенном студентам, наилучшим образом объясняется диф­
ференциальный анализ. В книге Шнайера содержится очень много
сведений о блочных и поточных шифрах.
J. Daemen and V. Rijmen. The Design of Rijndael: AES — The Ad­
vanced Encryption Standard, Springer-Verlag, 2002.
D. Stinson. Cryptography Theory and Practice. CRC Press, 1995.
B. Schneier. Applied Cryptography. Wiley, 1996.

Контрольные вопросы
5.1.1. В чем состоит принцип Керкхоффа?

5.1.2. Опишите операции шифра Фейстеля.

5.1.3. В чем главное отличие криптосистемы DES от оригинально­
го шифра Фейстеля?

5.1.4. Что меняется в шифре Фейстеля при переходе от шифрую-
ш;ей функции к расшифровывающей?

5.1.5. Опишите операции тройного DES.

5.1.6. В чем состоит роль замен и перестановок в шифре DES1

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

стр. 24
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>