Дано: ,

где криптоаналитик может выбирать

Определить: либо , либо алгоритм восстановления из .

4. Атака на основе адаптивно подобранного открытого текста. Криптоаналитик может не только выбирать шифруемый текст, но также уточнять свой последующий выбор на основе полученных ранее результатов шифрования. Так при вскрытии с использованием подобранного открытого текста криптоаналитик может выбирать для шифрования только один крупный блок открытого текста. При адаптивном же вскрытии с использованием подобранного открытого текста он может выбирать следующий блок, используя результаты первого выбора и т.д.

Кроме перечисленных типов известны так же, по крайней мере, еще три типа криптоаналитических атак.

1) Атака на основе подобранного шифротекста. Криптоаналитик может выбирать различные шифротексты для расшифрования. А так же имеет доступ к расшифрованным открытым текстам. Например, у криптоаналитика есть доступ к «черному ящику», выполняющему автоматическое расшифровывание. Его задача состоит в раскрытии ключа.

Дано: .

Получить: .

Такой тип вскрытия применим, главным образом, к алгоритмам с открытым ключом. Кроме того, вскрытие с использованием подобранного шифротекста в некоторых случаях эффективно против симметрических алгоритмов.

2) Атака на основе подобранного ключа. Такой тип вскрытия не означает, что криптоаналитик может выбирать ключ - просто он кое-что знает о связях между различными ключами.

3) Бандитский криптоанализ. До получения ключа «криптоаналитик» прибегает к угрозам, шантажу или пыткам. Возможно также взяточничество, которое иногда называют «вскрытием с покупкой ключа». Это очень мощные и, зачастую, самые эффективные методы взлома алгоритма.

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

10.2 Взлом шифров с открытым ключом на основе подобранного шифротекста

СЦЕНАРИЙ №1. Еве, подслушивающей линии связи Алисы, удалось перехватить сообщение , зашифрованное с помощью RSA открытым ключом Алисы. Ева хочет прочитать сообщение , т.е. необходимо узнать .

(11.1)

Для вскрытия она сначала выбирает первое случайное число r, меньшее n и достает открытый ключ Алисы . Затем она вычисляет:

(11.2)

Если , то .

Далее Ева просит подписать Алису y её закрытым ключом, тем самым расшифровав y. (Алиса должна подписать сообщение, а не его хесл-значение). Алиса никогда раньше не видела y. Алиса посылает Еве:

(11.3)

После этого Ева вычисляет:

 (11.4)

Ева получает .

СЦЕНАРИЙ №2. Трент - компьютер-нотариус. Если Алиса хочет заверить документ, она посылает Тренту. Трент подписывает его цифровой подписью RSA и отправляет обратно. (Однонаправленные хеш-функции не используются, Трент шифрует своим закрытым ключом все сообщение). Ева хочет, чтобы Трент подписал такое сообщение, которое в обычном случае он никогда не подпишет. Это сообщение может содержать фальшивую временную метку, или же автором этого сообщения может являться другое лицо. Какой бы не была причина, Трент никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение . Сначала Ева выбирает произвольное значение x и вычисляет:

(11.5)

Значение - это открытый ключ Трента, который должен быть опубликован. Далее Ева вычисляет

(11.6)

и посылает Тренту на подпись. Трент возвращает . Теперь Ева вычисляет значение

(11.7)

которое и является подписью

СЦЕНАРИЙ №3. Ева хочет, чтобы Алиса подписала сообщение . Она создает два сообщения ,, такие, что:

(11.8)

Если Ева сможет заставить Алису подписать и , она сможет вычислить подпись для :

(11.9)

Вывод: Никогда не используйте алгоритм RSA для подписи случайных документов, подсунутых вас посторонними. Вначале всегда следует воспользоваться однонаправленной хеш-функцией. Формат блоков, предлагаемый ISO 9796, предотвращает описанное вскрытие.

10.3 Взлом шифров с открытым ключом при использовании общего модуля

Возможна реализация RSA, в которой всем пользователям раздается одинаковый модуль , но каждому передается отдельное значение степени и . Наиболее очевидная проблема такого подхода заключается в том, что тогда текст может быть раскрыт даже при отсутствии каких-либо сведений об одном из ключей шифрования. Рассмотрим эту проблему подробнее.

Пусть одно и то же сообщение когда-нибудь шифровалось разными показателями (с одним и тем же модулем), и эти два показателя - взаимно простые числа. Пусть - открытый текст сообщения, и - два ключа шифрования, а - общий модуль. Шифротекстами сообщения являются:

()

Криптоаналитик знает . Сообщение он находит по следующему алгоритму.

Так как и - взаимно простые числа, то с помощью расширенного алгоритма Евклида можно найти и , для которых

()

Считая отрицательным (здесь или , или должны быть отрицательными, положим, что отрицательным будет ), воспользуемся расшифрованным алгоритмом Евклида для вычисления .Затем

()

Из всего выше сказанного следует вывод, что нельзя делать общим для группы пользователей.

10.4 Методы повышения стойкости RSA

Знание одной пары секретного/открытого показателей для данного модуля позволяет взломщику разложить модуль на множители.

Знание одной пары секретного/открытого показателей для данного модуля позволяет взломщику вычислить другие пары показателей, не разлагая модуль на множители.

В протоколах сетей связи, применяющих RSA не должен использоваться общий модуль.

Для предотвращения вскрытия малого открытого показателя все сообщения должны быть дополнены случайными значениями.

Секретный показатель должен быть большим числом.

12. Квантовая криптография

Впервые идея шифрования с использованием квантового канала сформулирована в 1970 г. С.Уиснером и развита в 80-е г.г. Ч.Беннетом, Ж.Брассаром и С.Брейдбардом.

Для пересылки последовательности двоичных битов в квантовом канале связи используются специальным образом поляризованные фотоны. Фотон - элементарная квантовая система, которая характеризуется определенным направлением поляризации (рис.12.1)

Рис.12.1. Поляризация фотона.

Здесь r - единичный вектор, указывающий поляризацию фотона и направленный под углом ; где - проекции; f - направление поляризации фильтра-анализатора. Из законов квантовой механики следует, что при попадании в такой фильтр-анализатор с параметром фотон ведет себя «дихоматическим и совершенно непредсказуемым образом», проходя через фильтр без изменения с вероятностью и поглощаясь в нем с дополнительной вероятностью . Это квантово-механическое явление проявляется и на макроуровне для интенсивности пучка поляризованного света при прохождении через фильтр в виде закона Малюса, согласно которому интенсивность световой волны, прошедшей анализатор, пропорциональна квадрату косинуса угла между плотностью поляризации световой волны и плотностью пропускания анализатора. Отметим, что если разность угла поляризации и угла пропускания фильтра-анализатора принимает значение

то и фотон проходит фильтр или поглощается им с одной и той же вероятностью . Этот факт и используется при выборе осей поляризации для квантового шифрования.

Принято говорить, что имеет место диагональная поляризация фотона, если вектор его поляризации:

или ,

то говорят о диагоналях поляризации и обозначают её символом “x”.

Проиллюстрируем применение квантовых сигналов в криптографии на примере передачи секретного ключа по открытому квантовому каналу. Рассмотрим классическую схему криптографической передачи информации. Алиса, желающая передать Бобу секретный ключ, который в дальнейшем будет использоваться, например, для обмена информацией с помощью некоторой криптосистемы. Ева - криптоаналитик, которая хотела бы скрытно завладеть копией передаваемого ключа.

Алиса гарантирует случайную секретную двоичную ключевую последовательность длиной N:

и случайную секретную индексную последовательность той же длины:

Затем Алиса генерирует в квантовый канал связи последовательность N фотонов: i - му фотону Fi, несущему сигнал Ki, дается поляризация “+” (если Ji=0) и поляризация “x” (если Ji=1).

Боб, имея два приемника фотонов (с поляризациями “+” и “x”), принимает поток фотонов. Если бы он знал индексную последовательность J, то, переключая приемники, добился бы того, что то есть что последовательность фотонов была бы воспринята безошибочно, и, следовательно, получен ключ K. Так как Боб не знает J, он использует свою индексную последовательностьJ' VN. Очевидно, что в среднем совпадает N/2 символов у J и J'. Следовательно, лишь половина (в среднем) фотонов будет зарегистрирована безошибочно, а остальные фотоны не несут никакой информации о K:

,

Если Ева извлечет некоторые фотоны из последовательности измерения своими приемниками, то Боб сразу же обнаружит потерю фотонов.

Следующие шаги протокола выполняются в обычном канале связи. Прежде всего, через этот канал Алиса определяет посредством открытого обмена сообщениями, какие фотоны зарегистрированы и какие из них соответствуют истинной поляризации . Если Ева не нарушает квантовой передачи, то биты , значения которых не обсуждались по открытому каналу, становятся общим секретным ключом для Алисы и Боба:

.

Из-за возможных действий Евы (в том числе связанных со “вставкой ” фотонов) Алиса и Боб должны убедиться, что их получившиеся битовые строки идентичны. Простое решение состоит в том, чтобы Алиса и Боб открыто сравнили некоторые из битов , относительно которых, как они думают, необходимо прийти к соглашению. Позиции этих “открыто сверяемых” битов должны быть выбраны после того, как квантовая передача завершена, чтобы лишить Еву информации о том, какие фотоны она может измерять без опаски. Оставшиеся битов могут использоваться в качестве секретного ключа для последующей связи по открытому каналу с помощью одного из симметрических криптоалгоритмов. В таблице 13.1 приведен протокол выработки секретного ключа с помощью квантового канала связи при состоящий из следующих шагов:

1. Передача по квантовому каналу:

а) случайная бытовая строка посылаемая Алисой;

б) последовательность поляризаций, задаваемая ;

в) посланная Алисой последовательность фотонов;

г) последовательность поляризаций , использованная Бобом;

д) битовая строка, зарегистрированная Бобом;

2. Обсуждение по открытому каналу:

а) Боб сообщает поляризацию зарегистрированных фотонов;

б) Алиса отмечает, какие поляризации были угаданы правильно;

в) последовательность секретных битов, которую можно использовать в качестве секретного ключа (если не было нарушения квантовой передачи);

г) Боб указывает номера “открыто сверяемых” битов ключа;

3. Результат: оставшиеся секретных битов.

Табл. 13.1 Протокол выработки секретного ключа с помощью квантового канала связи.

Если же или ,

То говорят о прямоугольной поляризации и обозначают ее символом “+”.

Страницы: 1, 2, 3, 4, 5, 6