- •Содержание
- •Введение
- •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
- •ЗАКЛЮЧЕНИЕ
- •ЛИТЕРАТУРА
88 Глава 6. ВЫБОР ДОЛГОВРЕМЕННОГО КЛЮЧА АЛГОРИТМА ГОСТ 28147-89
Значит, для ключа X = X1 X2 X2 X1 X1 X2 X2 X1 стандартного алгоритма ГОСТ выбор подключей в соответствии с последовательностью (0,1…7, 0,1…7, 0,1…7, 7,6…1,0) совпадет с восьмикратным выбором построенных нами подключей X1, X2 в порядке X1, X2, X2, X1.
Иными словами, GA(A) совпадает с восьмикратным применением GA4
кблоку A. Следовательно, A = GA(A).
6.2.3.Свойства теста
Соотношение назовем тестом. Используем его для
определения долговременного ключа K методом тестирования «черного ящика», на вход которого подаются блоки вида A = U||U и соответствующие ключи вида X = X (K,U )= X (h,U )= X1 X 2 X 2 X1 X1 X 2 X 2 X1 при различных позициях подблока h.
Предположим, что блок A = U||U и позиция I подблока h фиксированы, а неизвестное значение h определяется перебором. При каждом варианте h
вычисляется ключ X = X (h,U )и проверяется соотношение A = GA(A).
Напомним, что истинное значение h, как было показано, проходиттест.
Предположим, что все узлы замены являются подстановками. Рассмотрим ситуацию, когда тест проходит вариант, являющийся ложным, обозначив истинные, т.е. не зависящие от наших предположений относительно h, значения
рассматриваемых |
далее |
подблоков через |
z |
(с индексами). |
В |
этом |
случае |
|||||||||||
(U |
−2 |
,U |
−1 |
,U |
0 |
,U |
,U |
2 |
,U |
3 |
)= (U,U,U z1 ,U z1 |
,U z1 |
z1 ,U z1 |
z1 ), |
где |
|||
|
|
|
1 |
|
|
|
1 |
2 |
1 |
3 |
2 |
4 |
|
|||||
z1k (k =1,2,3,4) |
- выходы цикловой функции на соответствующих тактах с |
|||||||||||||||||
подключами X k . |
|
|
|
|
|
|
|
|
|
|
|
Контроль долговременного ключа алгоритма ГОСТ 28147-89 89
Покажем, что |
z1 ≠ z2 . |
Очевидно, |
z1 - |
истинное |
значение подблока, |
|||||||
позиция которого равна I, причем |
z1 ≠ h1 |
, поскольку все |
K |
i |
- подстановки. |
|||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
Вход в блок подстановки K при переходе от третьего к четвертому члену |
||||||||||||
последовательности |
u, имеет |
вид |
(U + z1 )+ X |
2 |
≠ (U + h1 )+ X |
2 |
= I , иными |
|||||
|
|
|
|
1 |
|
|
|
|
|
|
||
словами, позиция подблока z2 отличается от позиции подблока |
z1 . Отсюда, |
|||||||||||
поскольку все Ki - подстановки, следует, что z1 ≠ z2 . |
|
|
|
|
|
|||||||
Покажем теперь, что если подблок проходит тест, то для произвольных |
||||||||||||
K выполняются равенства z1 |
= z1 |
= z1 = z1 . |
|
|
|
|
|
|
|
|
||
|
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
Действительно, для рассматриваемого отрезка последовательности u
|
|
|
|
~ |
|
|
|
|
~ |
1 |
|
|
|
~ |
1 |
|
|
|
|
|
соотношение U−1 U0 =U1 дает U0 = z2 |
. Аналогично, U1 = z3 . |
|
|
|
|
|||||||||||||||
|
Поскольку |
блок |
проходит тест, |
то |
U2 =U3 =U . |
Таким |
|
образом, |
||||||||||||
U =U z1 z1 |
, U =U z1 z1 |
, т.е. |
z1 |
= z1 |
, z1 |
= z1 . |
|
|
|
|
|
|||||||||
|
|
1 |
3 |
|
|
|
|
2 |
4 |
|
|
1 |
3 |
2 |
4 |
|
|
|
|
|
|
Однако |
1 |
- просто |
другая |
запись подблока |
~ |
|
|
|
|
|
|||||||||
|
z4 |
U2 (вспомните процесс |
||||||||||||||||||
перехода от U2 |
к U3 |
в последовательности u). Поскольку U2 =U3 =U , то |
||||||||||||||||||
1 |
~ |
~ |
и, |
кроме того, |
вход |
в |
цикловую |
функцию равен |
|
U. |
Для |
|||||||||
z4 |
=U2 =U |
|
||||||||||||||||||
вычисления |
~ |
~ |
использовался |
подключ |
X 4 |
= X1 . Поэтому |
|
позиция |
||||||||||||
U2 |
=U |
|
||||||||||||||||||
подблока |
z4 |
(она совпадает |
с |
входом |
в блок |
подстановки |
K) |
|
равна |
|||||||||||
U + X1(mod232 )= I . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Это влечет равенство |
z |
4 |
= z . Но мы получили ранее, что |
z1 = z1 |
, |
z1 |
= z1 , |
||||||||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
3 |
|
2 |
4 |
|
откуда следует, что z1 |
= z1 |
= z1 |
= z1 . |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
1 |
2 |
|
|
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
Поскольку для обратимых K, при ложных вариантах h, |
z1 ≠ z2 , |
|
то имеет |
||||||||||||||||
место следующее утверждение. |
|
|
|
|
|
|
|
|
|
|
|
|
90 Глава 6. ВЫБОР ДОЛГОВРЕМЕННОГО КЛЮЧА АЛГОРИТМА ГОСТ 28147-89
Пусть K −1 . Тогда для любой позиции I соответствующий подблок h принадлежит K тогда и только тогда, когда h проходит тест.
Рассмотрим теперь случай, когда отображение K необратимо. В этом случае существуют две позиции, в которых расположены одинаковые
подблоки. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Истинное |
значение |
|
h = z1 |
по-прежнему |
проходит |
тест, |
причем |
||||||||
z1 |
= z1 = z1 = z1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Напомним, что каково бы ни было предполагаемое значение h, мы таким |
|||||||||||||||
образом строим ключ |
X1 , |
что «в черном ящике» при первом обращении к |
||||||||||||||
блоку подстановки K выбирается подблок, позиция которого равна I, т.е. |
||||||||||||||||
подблок |
z1 . Поэтому и для истинного, |
и для ложного подблока, проходящего |
||||||||||||||
тест, в цепочке |
z1 |
= z1 |
= z1 |
= z1 фигурируют одни и те же величины. Покажем, |
||||||||||||
|
|
|
1 |
2 |
|
3 |
4 |
|
|
|
|
|
|
|
|
|
что при ложном значении |
h ≠ z1 , |
позиции подблоков |
z1 |
и |
z2 различаются, |
|||||||||||
хотя сами подблоки равны. |
|
|
|
|
|
|
|
|
|
|
||||||
|
Действительно, |
подключ |
X 2 |
|
выбирается |
|
из |
соотношения |
||||||||
|
|
1 |
|
(mod2 |
32 |
|
|
|
|
~ |
1 |
. |
Это |
значит, |
что в |
|
I = (U h )+ X2 |
|
). Вспомним, что U0 |
= z2 |
|||||||||||||
соответствующем цикле из K был выбран подблок |
z2 . Соответствующая |
|||||||||||||||
позиция, очевидно, равна J = (U z1 ) |
+ X |
2 |
(mod232 ). |
Поскольку h ≠ z , то |
||||||||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
I ≠ J .
Следствие. Если ложный блок проходит тест, то отображение K необратимо.
6.2.4. Тестирование долговременного ключа
Подход для тестирования долговременного ключа состоит в следующем. Пусть необходимо определить 128 тетрад, входящих в узлы замены и
Контроль долговременного ключа алгоритма ГОСТ 28147-89 91
расположенных в матрице K. Будем определять тетрады последовательно, зафиксировав предварительно U.
Выберем позицию I = (i1,K,i8 ) искомого подблока h. Пусть, например,
I = (i1,K,i8 )= (0,K,0), что соответствует первой строке матрицы K.
Определим состав восьми тетрад, находящихся в позиции матрицы K перебором.
Вычисляем соответствующий сеансовый ключ X = (h,U ). Подаем на вход «черного ящика» X и комбинацию A = U||U. Если на выходе получаем ту же комбинацию, то располагаем тетрады подблока h = h1||…||h8 в соответствующих местах формируемого долговременного ключа. Очевидно, для этого достаточно 232 циклов шифрования ГОСТ.
Остальные 120 тетрад можно определять последовательно, каждую в 16 вариантах. Например, для определения оставшихся тетрад узла замены K1 можно зафиксировать i2,…, i8 и выбирать позиции, отличающиеся лишь значениями i1. Это соответствует выбору h с переменной левой тетрадой. Всего для восстановления обратимого блока подстановки K потребуется 232+1920 циклов шифрования ГОСТ.
Качество блока подстановки K оцениваем, исходя из следующих соображений.
Если блок подстановки K восстановить не удалось, то он необратим, следовательно, не является корректным. Если восстановленный блок
~ |
то он |
также |
не является |
|
подстановки K |
оказывается необратимым, |
|||
корректным. |
|
|
|
|
При необратимом блоке K, в принципе, можно восстановить ложный |
||||
обратимый вариант долговременного ключа. |
Таким |
образом, |
необходимо |
|
|
~ |
|
|
|
проверить истинность восстановленного K . |
|
|
|
92 Глава 6. ВЫБОР ДОЛГОВРЕМЕННОГО КЛЮЧА АЛГОРИТМА ГОСТ 28147-89
Для этого моделируем процесс зашифрования нескольких открытых текстов
~
достаточной длины на реальных сеансовых ключах и долговременном ключе K . Зашифровываем те же тексты на тех же сеансовых ключах с помощью «черного ящика». Если результаты не совпадают, то ключ K - не корректный.
Если результаты совпадают, то и необходимо протестировать ключ на принадлежность к области сильных ключей. Принципиально это возможно, например, при обращении в компетентные организации.