Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




К
Пример нелинейной функции y=1+x5+x1x2+x2x3x4
Назначение нелинейных узлов

 

       
 
   
ШГ
 


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

 

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

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

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

данных ЛРР, равные соответственно 219 -1,222 -1,223 -1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

времени.

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

 

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

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

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

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

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

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

Пример: 337(mod7)

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

3®32(mod7)=2®22(mod7)=4®42(mod7)=2®2×3(mod7)=6®62(mod7)= 1®12(mod7)= 1®1×3(mod7)=3

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


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

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

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

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

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

az(modn)= yb(modn)

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

zb-1=x.

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

 


Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...