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

К

Пример нелинейной функции y=1+x5+x1x2+x2x3x4

Назначение нелинейных узлов

 

		ШГ

19). Шифр А5/1, характеристика шифра, принцип построения, применение.

 

Генератор гаммы потокового шифра А5/1 состоит из трех ЛРР длины

19, 22 и 23 с отводами обратных связей, соответствующих примитивным полиномам

(рис. 3.30). Это обеспечивает периоды выходных последовательностей

данных ЛРР, равные соответственно 2¹⁹ -1,2²² -1,2²³ -1.

Все три регистра используют псевдослучайное тактирование, которое

работает по следующему правилу: биты с отвода 8 первого ЛРР, а также с

отводов 10 второго и третьего ЛРР подаются на так называемый мажоритарный

элемент. Последний выдает на выходе значение 0 или 1 в зависимости

от того, появляется ли больше на его входах нулей или единиц. Далее

выход этого мажоритарного элемента сравнивается со значениями выходов

на трех отводах ЛРР с номерами 8, 10, 10 (которые подавались ранее на входы

этого мажоритарного элемента), и каждый ЛРР продвигается на один такт

тогда и только тогда, когда сравниваемые биты оказываются одинаковыми.

Шифрующая гамма формируется как сумма по модулю 2 выходов всех трех

Стойкость шифра A5/1

При разработке этого шифра предполагалось, что он будет иметь высокую

стойкость, так как количество его ключей достаточно велико, однако

дальнейшие исследования, проводившиеся независимыми криптографами

[24], показали, что у этого шифра есть слабые стороны. Одна из них состоит

в том, что ЛРР, входящие в состав шифратора, имеют малые длины, и поэтому

они подвержены некоторым модификациям статистических атак, а также

атакам на основе обменных соотношений между требуемым объемом памяти

и временем анализа.

В конечном итоге исследования, которые проводились начиная с

2000 г. (т. е. почти сразу после введения этого стандарта), показали, что данный

шифр может быть «взломан» с использованием обычного ПК в реальном

времени.

22.Возведение в степень, нахождение дискретного логарифма

 

Возведение в степень по модулю — это вычисление остатка от деления натурального числа b (основание), возведенного в степень e (показатель степени), на натуральное число m (модуль).
. Быстрый способ возведения Д.Кнута.

- представим показатель степени в двоичном виде;

- каждую единице заменим парой букв КУ (квадрат+умножение);

- каждый ноль заменим буквой К (квадрат);

- в образовавшейся последовательности вычеркнем первую пару КУ;

- над основанием a проводим вычисления, согласно полученной последовательности.

Пример: 3³⁷(mod7)

37 = 100101 = КУКККУККУ= КККУККУ

3®3²(mod7)=2®2²(mod7)=4®4²(mod7)=2®2×3(mod7)=6®6²(mod7)= 1®1²(mod7)= 1®1×3(mod7)=3

Сложность вычислений для операции возведения в степень: N@O(2logx).

Сложность вычислений для операции дискретного логарифмирования: N@O((n)^1/2).

Нахождение дискретного логарифма методом «встречи посредине»

Строим базу данных размера O((n)^1/2) вида a^z(modn) для случайных чисел zÎ[1,n] и сортируем ее.

• Для случайных чисел b, таких что НОД(b,n-1)=1 вычисляем y^b(modn) и сравниваем с числами базы данных.

• С большой вероятностью после нескольких попыток получаем

a^z(modn)= y^b(modn)

4. Возводим обе части в степень b^-1, получим a^{z· b-1} (modn)= y (modn). Откуда следует

zb^-1=x.

Этот метод имеет сложость N_t@O((n)^1/2logn), N_v@O((n)^1/2)
Возвести в степень по модулю довольно легко, даже при больших входных значениях. А вот вычисление дискретного логарифма, то есть нахождение показателя степени e при заданных b, c и m, намного сложнее. Такое одностороннее поведение функции делает её кандидатом для использования в криптографических алгоритмах.