- •Содержание
- •Введение
- •1.1. Общая система секретной связи (по К. Шеннону)
- •1.1.1. Основные криптографические термины
- •1.1.2. Модель системы секретной связи К.Шеннона
- •1.2. Подходы к оценке надежности реальных криптосистем
- •1.2.2. Метод сведения к общей алгоритмической проблеме
- •Глава 2. ОБЩИЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ АНАЛИЗА ОСНОВНЫХ ТИПОВ ШИФРОВ
- •2.1. Элементарные шифры
- •2.2. Основные типы шифров
- •2.2.1 Потоковые шифры. Последовательность выбора шифрпреобразований
- •2.2.2. Качество гаммы
- •2.2.3. Периодичность гаммы
- •2.2.4. Блочные шифры
- •2.2.5. Алгоритмические проблемы, связанные со стойкостью основных типов шифров
- •Глава 3. ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ
- •3.1. Компрометация шифров
- •3.2. Задача тестирования линейной рекуррентной составляющей криптоузла
- •3.3. Задача восстановления параметров искаженной линейной рекурренты
- •3.3.1. Представление элементов рекурренты через элементы начального заполнения
- •3.3.2. Производные соотношения
- •3.3.4. Качественная характеристика задачи восстановления параметров линейной искаженной рекурренты
- •Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
- •4.1. Нелинейность булевой функции
- •4.2. Критерии распространения и корреляционная иммунность
- •4.3. Устойчивые булевы отображения
- •Глава 5. ОСОБЕННОСТИ ПРИМЕНЕНИЯ АЛГОРИТМА ГОСТ 28147-89
- •5.1. Криптоэквивалентная схема алгоритма ГОСТ 28147-89
- •5.2. Влияние блока подстановки на последовательности выходов итераций
- •5.2.1 Расшифрование в режиме простой замены
- •5.2.2. Возможность ослабления шифра за счет структуры сеансового ключа
- •5.3. Замечания о режимах шифрования и имитовставки
- •Глава 6. ВЫБОР ДОЛГОВРЕМЕННОГО КЛЮЧА АЛГОРИТМА ГОСТ 28147-89
- •6.1. Область сильных ключей
- •6.1.1. Достаточность условия равновероятности псевдогаммы для выбора сильного блока подстановки
- •6.2. Контроль долговременного ключа алгоритма ГОСТ 28147-89
- •6.2.1. Угроза внедрения слабых параметров
- •6.2.2. Подход к выявлению слабых долговременных ключей
- •6.2.3. Свойства теста
- •6.2.4. Тестирование долговременного ключа
- •Глава 7. ЭЛЕМЕНТЫ ТЕОРИИ СРАВНЕНИЙ
- •7.1.1. Расширенный алгоритм Эвклида
- •7.2. Модульная арифметика
- •7.2.1. Функция Эйлера и малая теорема Ферма
- •7.3. Сравнения первой степени от одного неизвестного
- •7.3.1. Китайская теорема об остатках
- •7.3.2. Степенные сравнения по простому модулю
- •Глава 8. ВЫЧИСЛЕНИЕ КВАДРАТНОГО КОРНЯ В ПРОСТОМ ПОЛЕ
- •8.1.1. Символ Лежандра
- •8.1.2. Символ Якоби
- •8.2. Алгоритм нахождения квадратного корня в простом поле
- •9.1. Построение криптосистемы RSA. Идея цифровой подписи
- •9.2. Смешанные криптосистемы. Протокол Диффи-Хэллмана ключевого обмена
- •9.3. Цифровая подпись Эль-Гамаля
- •9.3.1. Криптосистема Эль-Гамаля
- •9.3.2. Механизм цифровой подписи Эль-Гамаля
- •9.3.3. Ослабление подписи Эль-Гамаля вследствие некорректной реализации схемы
- •9.3.4. Варианты цифровой подписи типа Эль-Гамаля
- •10.1 Обозначения и постановка задачи
- •10.2. Построение корней из единицы в поле
- •10.3. Алгоритм дискретного логарифмирования
- •10.3.1. Пример вычисления дискретного логарифма
- •10.4. Фальсификация подписи Эль-Гамаля в специальном случае выбора первообразного элемента и характеристики поля
- •10.4.1. Слабые параметры в подписи Эль-Гамаля
- •Глава 11. МЕТОДЫ ФАКТОРИЗАЦИИ ПОЛЛАРДА
- •11.2.1. Оценка вероятности выбора критической пары
- •11.2.2. Оптимизация выбора критической пары
- •Глава 12. НЕКОТОРЫЕ СЛУЧАИ ОСЛАБЛЕНИЯ КРИПТОСИСТЕМЫ RSA
- •12.1. Атаки на RSA, не использующие факторизацию модуля
- •12.2. Атаки на RSA, использующие факторизацию модуля
- •12.2.1. Алгоритм факторизации Диксона
- •Глава 13. ТЕСТ ФЕРМА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
- •13.1. Решето Эратосфена и критерий Вильсона
- •13.2. Тест на основе малой теоремы Ферма
- •13.2.1. Основные свойства псевдопростых чисел
- •13.2.2. Свойства чисел Кармайкла
- •13.2.3. (n-1) - критерий Люка
- •13.2.3. Понятие о последовательностях Люка. (n+1) - критерий Люка
- •Глава 14. ТЕСТЫ СОЛОВЕЯ-ШТРАССЕНА И РАБИНА-МИЛЛЕРА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
- •14.1. Тест Соловея-Штрассена
- •14.1.1. Эйлеровы псевдопростые числа
- •14.2. Тест Рабина-Миллера
- •14.2.1. Сильно псевдопростые числа
- •Глава 15. ПОСТРОЕНИЕ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ
- •15.1. Детерминированный тест, основанный на обобщенном критерии Люка
- •15.1.1. Теорема Поклингтона
- •15.1.2. Обобщение критерия Люка
- •15.2. Детерминированный тест, основанный на теореме Димитко
- •Глава 16. ВЫБОР ПАРАМЕТРОВ КРИПТОСИСТЕМЫ RSA
- •16.1. Общие требования к выбору параметров
- •16.2. Метод Гордона построения сильно простых чисел
- •16.3. Пример построения сильно простого числа
- •Глава 17. ОБЩИЕ СВЕДЕНИЯ ОБ ИНОСТРАННЫХ КРИПТОСРЕДСТВАХ
- •17.1. Аппаратные криптосредства
- •17.2. Основные принципы построения систем управления ключами
- •17.2.1. Ключевые системы потоковых шифров
- •17.3. Блочные шифры в смешанных криптосистемах
- •17.3.2. Смешанная криптосистема на основе алгоритмов RSA и IDEA
- •ЗАКЛЮЧЕНИЕ
- •ЛИТЕРАТУРА
62 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
Из определения следует, что для такой функции никакое подмножество m переменных не обладает особенностями, позволяющими сузить множество их возможных значений, исходя из распределения c(m,a, I ).
Оказывается, что |
функция |
f (x1,K, xn ) |
является корреляционно |
||
иммунной порядка m тогда и только тогда, когда |
ее коэффициенты Уолша- |
||||
Адамара удовлетворяют |
условию |
a GF n : 1 |
≤ wt(a)≤ m, W |
f |
(a)= 0 . |
|
|
2 |
|
|
Следовательно, свойство корреляционной иммунности инвариантно при аффинных преобразованиях координат.
Для построения булевых функций, удовлетворяющих тем или иным
критериям нелинейности, существуют различные методы. |
|
|
|
||||||||||
Например, в |
[37] |
показано, |
что |
если |
|
|
функции |
f1(x1, x2 ,Kxn ) и |
|||||
f2 (x1, x2 ,Kxn ) |
- |
корреляционно |
иммунные |
порядка |
k, |
то |
функция |
||||||
f (u, x1, x2 ,Kxn )= (u 1)f1(x1, x2 ,Kxn ) uf2 (x1, x2 ,Kxn ) |
|
от |
n +1 |
||||||||||
переменной также корреляционно иммунная порядка k. |
|
|
|
|
|||||||||
В качестве другого примера можно привести функцию g от |
n = 2k +1 |
||||||||||||
переменных вида |
g(x1, x2 ,Kx2k +1 )= x1 f (x1 x2 ,K, x1 x2k +1 ), |
где f (x) |
|||||||||||
- максимально нелинейная функция от n переменных [11]. |
|
|
|
||||||||||
Заданная таким образом функция g удовлетворяет критерию |
|||||||||||||
распространения PC(2k ) и обладает высокой нелинейностью: Ng |
≥ 22k −2k . |
||||||||||||
В качестве обобщения корреляционно иммунных функций можно указать |
|||||||||||||
т.н. устойчивые булевы отображения. |
|
|
|
|
|
|
|
|
|
|
|||
4.3. Устойчивые булевы отображения |
|
|
|
|
|
|
|
||||||
Отображение |
|
f: GFn →GF k , |
f = |
(f , f |
2 |
,K f |
k |
), называется |
(n,k,d )- |
||||
|
|
2 |
2 |
|
1 |
|
|
|
|
|
|
устойчивым, если для любых наборов I ={i1,i2 ,K,id }, 1≤ i1 < i2 <K< id ≤ n ,
Устойчивые булевы отображения 63
a = (a ,a |
,Ka |
) GF d производное отображение |
f a: GF n−d →GF k |
вида |
||
1 2 |
d |
2 |
I |
2 |
2 |
|
fIa (x)= (f1aI (x),K, fkIa (x))является равновероятным.
Устойчивое отображение f = (f1, f2 ,K fk ) называется линейным, если линейны все его функции-компоненты.
Согласно определению равновероятности булевого отображения, область значений вектор-функции fIa (x) совпадает с GF2k и мощности прообразов элементов из GF2k одинаковы. Поскольку мощность области определения fIa (x) равна 2n−d , то мощность каждого прообраза равна 2n−d −k ,
следовательно, необходимо n −k ≥ d . |
|
|
|
|
|
|
|
|
|
|
|
|
||
Можно показать, что отображение |
f: GFn →GF k , |
f = |
(f |
, f |
2 |
,K f |
k |
), |
||||||
|
|
|
2 |
2 |
|
|
1 |
|
|
|
|
|
||
1≤ k ≤ n является (n,k,d )-устойчивым тогда |
и только |
тогда, |
когда |
для |
||||||||||
любого набора b = (b ,b ,Kb ) GF k |
функция |
ϕ = b f b f |
2 |
K b |
|
f |
k |
|||||||
1 2 |
k |
2 |
|
1 1 |
2 |
|
|
|
|
k |
|
является (n,1,d )-устойчивой, т.е. равновероятной, корреляционно иммунной функцией порядка d.
Для построения устойчивых отображений существует ряд подходов, позволяющих строить их, например, из устойчивых отображений меньшей размерности [38, 39].
Кроме того, практическое значение имеет подход, позволяющий строить устойчивые отображения из линейных устойчивых отображений, основанный на следующем утверждении [40].
Пусть f: GF2n →GF2k является (n,k,d )-устойчивым, а g: GF2k →GF2k -
отображение, осуществляющее перестановку своих агрументов, то отображение также (n,k,d )-устойчиво. Кроме того, нелинейность h
удовлетворяет условию
Приведем примеры (n,k,d )-устойчивых линейных отображений [11].
64 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
1. k = n −1, d =1, f = (f1, f2 ,K fn−1 ), fi (x)= xi xi+1 , i =1,K, n −1. 2. n =3h, k = 2, d = 2h −1,
f=(f1, f2 ), f1(x)= x1 K x2h , f2 (x)= x2h+1 K x3h .
Взаключение, отметим значение инвариантности ряда свойств булевых
функций относительно множества G аффинных преобразований координат
x = g(x′).
Поскольку эти преобразования образуют группу, то на множестве булевых функций можно ввести т.н. отношение G-эквивалентности.
Функции f (x) и h(x) эквивалентны, если одна из другой получается аффинным преобразованием координат: g G : h(x′)= f (g(x′)).
При этом булевы функции разбиваются на непересекающиеся классы, каждый из которых содержит все функции, эквивалентные некоторой одной функции, называемой образующей класса эквивалентности.
Любые свойства образующей класса эквивалентности, инвариантные относительно аффинных преобразований координат, переносятся на любую функцию из этого класса. Поэтому при изучении совокупности функций ряд параметров можно получить, рассматривая лишь образующие классов.
Для примера рассмотрим множество B равновероятных булевых функций от четырех переменных.
Это множество разбивается на четыре класса эквивалентности [12] с образующими:
f (1)(x)= x1 , f (2)(x)= x1 x2 x3 , f (3)(x)= x1 x2 x3 x4 ,
f (4)(x)= x1 x2 x3 x1 x4 x2 .
Устойчивые булевы отображения 65
Табличный вид образующих представлен в следующей таблице.
Таблица 2. Образующие классов аффинной эквивалентности функций
|
|
|
|
|
|
|
|
x1 |
x2 |
x3 |
x4 |
f (1) |
f (2) |
f (3) |
f (4) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
Покажем, что для каждой функции f B существует аффинный статистический аналог, совпадающий с f c вероятностью не менее 3/4.
Значения преобразования вида (−1)a,x линейных функций la = a, x , для a =1,2,4,8 , представлены ниже (тетрады аргументов и коэффициентов функции
записаны в виде шестнадцатиричных чисел).
Таблица 3. Последовательности значений функций (−1)a,x , a =1,2,4,8 .
|
|
a |
Значения аргумента x = 0,1,K, E, F |
1=0001 |
+1,-1,+1,-1,+1,-1,+1,-1,+1,-1,+1,-1,+1,-1,+1,-1 |
2=0010 |
+1,+1,-1,-1,+1,+1,-1,-1,+1,+1,-1,-1,+1,+1,-1,-1 |
4=0100 |
+1,+1,+1,+1,-1,-1,-1,-1,+1,+1,+1,+1,-1,-1,-1,-1 |
8=1000 |
+1,+1,+1,+1, +1,+1,+1,+1,-1,-1,-1,-1,-1,-1,-1,-1 |
При вычислении статистической структуры получаем большие коэффициенты: Wf (1) (8)=16 , Wf (2 ) (2)=8 , Wf (3) (1)=12 , Wf (4 ) (4)=8 .
66 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
Следовательно, исходя из минимального значения Wf (a)=8, вероятность совпадения значений любой образующей со значениями соответствующей аффинной функции не ниже n+ 16 =3 4 . Значит, тем же свойством обладают все функции f B .
Рассмотренные примеры понадобятся нам при рассмотрении подхода к построению долговременных ключей алгоритма ГОСТ 28147-89.