- •Содержание
- •Введение
- •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
- •ЗАКЛЮЧЕНИЕ
- •ЛИТЕРАТУРА
58 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
Известно, что возможно построение равновероятных булевых функций с нелинейностью, удовлетворяющей неравенствам 2n−1 − 2n2 ≤ Ng < Nmax и
2n−1 − 2(n−1)2 ≤ Ng < Nmax для четного и нечетного n соответственно.
4.2. Критерии распространения и корреляционная иммунность
Криптографическая практика показывает, что булевы функции, используемые для построения генераторов гаммы, кроме равновероятности и высокой нелинейности должны обладать рядом более тонких свойств, ослабляющих связи между выходами функций и последовательностями соответствующих аргументов [11].
Для формулировки соответствующих определений используются понятия подфункции булевой функции и ее производной.
Назовем производной булевой функции |
f (x) по направлению |
u GF n , |
|
|
2 |
u ≠ 0, функцию вида Du f (x)= f (x) f (x u). Введем также обозначение Du,t f (x)= Du f (x), при ограничении 1 ≤ wt(u)≤ t .
Подфункцией булевой функции f (x1, x2 ,K, xn ), полученной фиксацией k
переменных на местах 1≤ i1 < i2 <K< ik ≤ n с помощью вектора значений
a = (a ,a |
2 |
,Ka |
k |
), называется функция f a (x), определяемая строками таблицы |
|||
1 |
|
|
|
I |
|
||
x1, x2 ,Kxn , f (x1, x2 ,K, xn ), для которых xi j = a j , |
j =1,K,k . |
||||||
В каждой такой строке аргументами функции |
fIa (x) являются аргументы |
||||||
f (x) с номерами, |
не принадлежащими множеству I ={i1,i2 ,K,ik }, а значение |
||||||
f a (x) равно f |
(x , x ,K, x ). |
|
|||||
I |
|
|
|
1 |
2 |
n |
|
Изучение свойств булевых функций в связи с задачей конструирования преобразований, используемых при построении блочных шифров, привело к идее строгого лавинного критерия (Strict Avalanche Criteria, SAC).
Критерии распространения и корреляционная иммунность 59
Подобные критерии, в той или иной мере, отражают свойство непредсказуемости поведения функции f при модификации (неизвестных) аргументов. Например, требуется, чтобы минимальное отклонение от истинного значения аргумента приводило к максимально быстрому, лавинному, распространению ошибок в рекуррентной последовательности
xn+1 = f (x1, x2 ,K, xn ).
|
Булева функция |
f (x) удовлетворяет строгому лавинному критерию SAC, |
|
если |
D |
f (x) - равновероятная функция для любого u GF n . |
|
|
u,1 |
|
2 |
|
Обобщением SAC является SAC(k) - строгий лавинный критерий порядка k, |
||
1 ≤ k < n . Функция |
f (x) удовлетворяет SAC(k), если любая ее подфункция |
fIa (x), полученная фиксацией k переменных, удовлетворяет обычному критерию SAC.
Заметим, что в самом SAC переменные не фиксируются, поэтому для критерия SAC часто используется обозначение SAC(0).
В критерии SAC(k), по определению, допускается модификация произвольного, но только одного из аргументов.
Модификация нескольких аргументов рассматривается в т.н. критерии распространения PC(l) степени l (Propagation Criterion).
Функция f (x) удовлетворяет критерию распространения PC(l) степени l,
если любая ее производная Du,l f (x), u GF2n , равновероятна.
В случае, если известно, что Du,l f (x) равновероятна для конкретного вектора u, говорят, что f (x) удовлетворяет критерию распространения PC(l)
степени l относительно вектора u.
Общий случай приводит к формулировке критерия распространения степени l, порядка k.
60 Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ |
|
|
|
||||||||||
|
|
Функция |
f (x) удовлетворяет критерию распространения PC(l,k) степени |
||||||||||
l, |
|
порядка k, |
1<l ≤n, |
1≤k <n, |
если |
для любой ее |
подфункции fIa (x), |
||||||
полученной фиксацией k |
переменных, |
все производные |
D |
f a (x), |
u GF n , |
||||||||
|
|
|
|
|
|
|
|
|
|
|
u,l |
I |
2 |
равновероятны. |
|
|
|
|
|
|
|
|
|
|
|||
|
|
Для таких функций, в частности, нецелесообразно при известной |
|||||||||||
последовательности ur = xr |
|
x , |
ur , xr |
GF n , искать в короткой гамме вида |
|||||||||
|
|
|
i |
i+1 |
|
i |
i |
i |
2 |
|
|
|
|
γ |
i |
= f (xr ) номера тактов, |
для |
которых |
биты гаммы зависимы. Причем это |
||||||||
|
i |
|
|
|
|
|
|
|
|
|
|
|
верно, даже если k битов аргумента x1 , а значит k битов для всех xi , известны.
|
|
В самом деле, |
если функция удовлетворяет PC(l,k), то при фиксации |
||||||||
соответствующих |
k |
переменных |
зависимые |
биты |
гаммы |
|
γi , |
||||
γ |
j |
= f (x (x |
j |
x ))могут появиться лишь в том случае, когда |
wt(xr x |
j |
)> l . |
||||
|
i |
i |
|
|
|
|
i |
|
|||
Очевидно, при заданном u , вероятность повторения векторов вида ur = xi |
xj , |
содержащих l единиц на фиксированных местах, уменьшается с возрастанием l. Поэтому, чем больше l, тем длиннее требуется отрезок гаммы для появления зависимых битов.
Формулировки критериев распространения показывают, что подфункции булевых функций, приемлемых для соответствующих криптографических приложений, должны обладать специальными свойствами.
Со свойствами подфункций связано также понятие корреляционной иммунности порядка m, которое отражает отсутствие статистической зависимости между значениями функции f (x) и подмножествами мощности m
переменных, входящих в состав полного аргумента
Функция f (x) удовлетворяет критерию корреляционной иммунности порядка m, если для любой совокупности I ={i1,i2 ,K,im } номеров m
Критерии распространения и корреляционная иммунность 61
переменных |
|
1≤ i1 < i2 <K< im ≤ n |
и |
для |
любых |
наборов |
|
a = (a ,a ,Ka |
m |
) GF m |
выполняется равенство wt(f a )= wt(f ) 2m . |
|
|||
1 2 |
2 |
|
|
I |
|
|
Рассмотрим случай m = n. Таблица, определяющая каждую подфункцию, состоит в этом случае из одной строки.
Свободных переменных нет, элемент вектора значений может равняться нулю или единице. Таким образом, подфункция fIa = const и wt(fIa ) {0,1}.
Если критерий выполняется, |
wt(f ) {0,2n }, т.е. функция f (x) постоянна. |
|
||
Оказывается, что только две функции достигают корреляционного |
||||
иммунитета |
степени |
m=n−1: |
f (x1,K,xn )=x1 K xn |
и |
g(x1,K,xn )=1 x1 K xn .
Заметим, кроме того, что не все корреляционно иммунные функции, отличные от констант, являются равновероятными.
В случае, когда функция f (x) равновероятна, wt(f )=2n−1. Для каждой пары a,I таблица, определяющая подфункцию, состоит из 2n-m строк, количество переменных равно n-m. В этом случае критерий корреляционной иммунности
приобретает вид |
wt(fIa )= 2n−m−1 , т.е. соответствующая подфункция должна |
||||||||
быть равновероятной. |
|
|
|
|
|||||
Критерий корреляционной иммунности эквивалентен следующему |
|||||||||
определению в вероятностных терминах. |
|
|
|
||||||
Функция f (x1,K, xn ) является корреляционно иммунной порядка m, если |
|||||||||
для любой |
совокупности |
I ={i1,i2 ,K,im } |
номеров m |
переменных |
|||||
1≤i1 <i2 <K<im ≤ n , |
1≤ m ≤ n , |
при |
любых |
значениях |
|||||
a = (a ,a |
2 |
,Ka |
m |
) GF m выполняется соотношение |
|
||||
1 |
|
|
2 |
|
|
|
|
c(m,a, I )= P xi j = aj f (x)= 0, j =1,Km = 21m .