Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 65

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 59 60 61 62 63 64 < 65 > 66 67 68 69 70 71 .. 126 >> Следующая


У(0 = а 1,1 (0 + ^2,1 (0 + лз,і (0, t>\.

249
І лава 9

В системах GSM алгоритм AS используется для защиты информации между абонентом и базовой станцией, так что фактически в сеансе связи двух абонентов шифрование происходит дважды. Это дает возможность использования атаки на основе известного открытого текста. Кроме того, следует отметить, что 64-битовый секретный сеансовый ключ (которым служит совокупность начальных заполнений JIPC ) генерируется с помощью другого алгоритма, исходя из “основного” (master) ключа, специфического для каждого пользователя, и открытого случайного 128-битового ключа, передаваемого в незащищенной форме с базовой станции абоненту. Тем самым успешное вскрытие одного или нескольких сеансовых ключей дает подходы к определению основного ключа пользователя.

Шифрсистема Гиффорда

Д. Гиффорд предложил схему поточного шифра, которая использовалась с 1984 по 1988 г. агентством Associated Press. Криптосхема генератора (см. рис. 35) представляет собой 8-байтовый регистр сдвига с линейной функцией обратной связи f и нелинейной функцией выхода h. Ключом являются 64 бита начального заполнения регистра. Схема реализует шифр гаммирования.

В 1994 г. Кейном и Шерманом был предложен метод определения ключа данной криптосхемы, использующий память

объема 218 бит и имеющий сложность 227 элементарных операций, что существенно меньше сложности тотального перебора всех 264 начальных состояний. Программа, реализующая данный метод на сети из 8 станций Sparc, находила ключ по одному шифрованному сообщению достаточной длины в среднем за 4 часа.

250
I юточные системы шифрования

Рис. 35

§ 9.4. Линейные регистры сдвига

Широкое распространение в криптографических приложениях линейных регистров сдвига над конечными полями и кольцами обусловлено целым рядом факторов. Среди них можно отметить:

— использование только простейших операций сложения и умножения, аппаратно реализованных практически на всех вычислительных средствах;

— высокое быстродействие создаваемых на их основе криптографических алгоритмов;

— большое количество теоретических исследований свойств линейных рекуррентных последовательностей (ЛРП), свидетельствующих об их удовлетворительных криптографических свойствах.

Введем ряд определений.

Последовательностью над полем P будем называть любую функцию и: Nq -> P, заданную на множестве целых неотрицательных чисел и принимающую значения в поле.

251
Глава 9

Последовательность и называют линейной рекуррентной последовательностью (ЛРП) порядка т > 0 над полем P, если существуют константы /0,...,/и еР такие, что

и(і + т)= Ё/, • u(i + j), і > О.

J=о

ЛРП реализуется схемой линейного регистра сдвига, изображенной на рис. 36.

Рис. 36

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

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

/ \

рекурсии, многочлен F{x) = Xm — f. • Xj — характери-

J=о

стическим многочленом ЛРП и, а вектор »(о,/и — l) =

252
/ юточные системы шифрования

= (и(0),...,и(т — 1))— начальным вектором ЛРП (или начальным заполнением ЛРС).

Характеристический многочлен ЛРП и, имеющий наименьшую степень, называется ее минимальным многочленом, а степень минимального многочлена — линейной сложностью ЛРП и.

Линейная сложность ЛРП определяет минимальную длину линейного регистра сдвига, реализующего данную последовательность.

Периодом последовательности и называется наименьшее натуральное число t, для которого существует натуральное число Л> О такое, что для всех / > 0 справедливо равенство

и(л -+"/ + /)= и{л + /).

Из вида закона рекурсии следует, что в случае, когда P — конечное поле из q элементов, максимальное значение

периода ЛРП порядка т равно qm — I. В самом деле, нулевой начальный вектор порождает последовательность, состоящую из одних нулей, а число различных заполнений регистра длины т равно qm.

Последовательности, имеющие максимально возможный период, получили название линейных рекуррентных последовательностей максимального периода или просто максимальных линейных рекуррентных последовательностей.

Значения периодов линейных рекуррентных последовательностей определяются свойствами их минимальных многочленов. В частности, для того чтобы линейная рекуррентная последовательность порядка т над полем из q элементов имела максимальный период, необходимо и достаточно, чтобы ее минимальный многочлен был примитивным многочленом [Лид88]. Так называется неприводимый многочлен, корень которого имеет в мультипликативной группе поля разложения порядок qm -1.

253
Гпава 9

Несмотря на то, что имеется достаточно много критериев проверки неприводимости многочленов над конечными ПОЛЯМИ и методов их построения, доказать то, что заданный неприводимый многочлен примитивен, удается в исключительных случаях.
Предыдущая << 1 .. 59 60 61 62 63 64 < 65 > 66 67 68 69 70 71 .. 126 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed