- •Содержание
- •Введение
- •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
- •ЗАКЛЮЧЕНИЕ
- •ЛИТЕРАТУРА
Возможность ослабления шифра за счет структуры сеансового ключа 73
Подчеркнем, что никакие свойства блока подстановки K на осуществимость процесса расшифрования не влияют.
5.2.2. Возможность ослабления шифра за счет структуры сеансового ключа
Заметим, что выбор K с равновероятным распределением битов в колонках, строго говоря, не обеспечивает качественную псевдогамму L||R, т.к. для каждого K существуют блок B и сеансовый ключ X, такой, что GA(B) = B.
~
Действительно, рассмотрим четырехцикловой алгоритм GA с
~ |
−1 |
(T )= B . Если выход после |
последовательностью t(i)= (0,1,2,3) и пусть GA |
|
|
|
~ |
|
|
|
|
|
|
|
четвертого цикла GA(B) имеет вид T=U||U, то дополнительное преобразование |
|||||||||
его не |
меняет. |
Заметим, что |
|
~−1 |
t(i)= (3,2,1,0). Поэтому |
для |
|||
для GA |
|||||||||
|
|
~ |
|
|
|
t(i)= (0,1,2,3,3,2,1,0) получим |
|||
восьмициклового GA с последовательностью |
|||||||||
GA(B)= B . |
|
|
|
|
|
|
|
|
|
То |
же |
будет |
верно |
для |
тридцати |
двух |
циклов, |
при |
|
t(i)= (0,1,2,3,3,2,1,0,K,0,1,2,3,3,2,1,0), |
что |
при стандартном значении |
t(i) |
эквивалентно использованию сеансового ключа вида
X = X0 , X1, X2 , X3 , X3 , X2 , X1, X0 .
Таким образом, из сказанного ранее следует, что для алгоритма ГОСТ в режиме простой замены виртуальные таблицы замены могут отличаться по качеству в зависимости от ключей.
Наибольшее влияние на качество виртуальных таблиц оказывает долговременный ключ – блок подстановки K. Некорректный выбор ключа K может привести к ослаблению шифра, независимо от сеансовых ключей.
5.3. Замечания о режимах шифрования и имитовставки
Рассмотрим процесс формирования 64-х битовых блоков для входа в блочный шифр при режимах шифрования.
74 Глава 5. ОСОБЕННОСТИ ПРИМЕНЕНИЯ АЛГОРИТМА ГОСТ 28147-89
Врежиме гаммирования для тактов шифрования k =1,2,K
последовательность 64-битовых блоков гаммы имеет вид: γk |
=GA(f (σk −1 )), |
|||||||||||
где |
σk = f (σk −1 ), |
блок σ0 выражается через синхропосылку: |
σ0 =GA(S ), а |
|||||||||
функция |
f (σ ) |
использует |
две несекретные |
константы |
c1,c2 , |
т.е. |
||||||
f (σ )= f (σ,c1,c2 ). |
|
|
|
|
|
|
|
|
||||
|
Для блока σ , состоящего из двух подблоков σ = s1 || s2 , |
блок |
f (σ ) |
|||||||||
состоит из подблоков вида: s1 oc1 , s2 + c2 . |
|
|
|
|
|
|
||||||
|
Здесь |
сложение |
производится |
по |
модулю |
232, |
а |
|||||
s oc |
= s |
+ c mod(232 −1), |
за |
исключением |
случая s |
+c |
= 232 −1, |
когда |
||||
1 |
1 |
1 |
1 |
|
|
|
|
1 |
1 |
|
|
|
результат принимается равным 232-1. |
|
|
|
|
|
|
||||||
|
В режиме гаммирования с обратной связью очередной блок гаммы для |
|||||||||||
такта |
k = 1, 2,… |
получается |
в |
результате зашифрования в режиме простой |
замены блока шифрованного текста, полученного на такте с номером k-1. Под блоком шифртекста для k=0 понимается синхропосылка S.
Легко видеть, что неравновероятность гаммы, вызванная слабым долговременным ключом, проявляется в режиме гаммирования в той же мере, что и в режиме простой замены.
Также очевидно, что блок подстановки, у которого каждый узел замены Ki содержит лишь одинаковые тетрады, полностью ослабляет режим гаммирования с обратной связью. Действительно, в этом случае гамма отличается от соответствующего блока на входе в режим простой замены лишь перестановкой полублоков. При этом сам входной блок известен, т.к. является предыдущим блоком шифртекста.
Итак, слабые для режима простой замены ключи снижают стойкость основных режимов шифрования.
Замечания о режимах шифрования и имитовставки 75
Необходимо также учитывать, что выбор блока подстановки наугад не является наилучшим способом, т.к. можно убедиться, что в этом случае вероятность получения равного числа нулей и единиц в одном столбце ключа K менее 0,2.
Следовательно, построение долговременных ключей для алгоритма ГОСТ необходимо проводить специальным образом.
Отметим, что кроме режимов шифрования, в стандарте ГОСТ 28147-89 предусмотрен т.н. режим выработки имитовставки. Этот режим служит для защиты от несанкционированной модификации открытого текста после его зашифрования.
Обеспечение имитозащиты открытого текста является необходимым, поскольку для криптограмм модульного гаммирования открытый текст можно модифицировать, не изменяя гаммы.
Действительно, пусть c = t +γ(n) - знак шифртекста при модульном гаммировании знака открытого t текста гаммой γ. Пусть знак t известен и его необходимо заменить на знак s.
Очевидно, c + (s −t)= t + (s −t)+γ(n), поэтому, если в криптограмме заменить знак c на знак c + (s −t), открытый текст новой криптограммы после расшифрования будет соответствующим образом изменен.