Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
У(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
Несмотря на то, что имеется достаточно много критериев проверки неприводимости многочленов над конечными ПОЛЯМИ и методов их построения, доказать то, что заданный неприводимый многочлен примитивен, удается в исключительных случаях.