Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 3. Теория вероятностей и теория информации 117
3.5. Четверть чисел в некотором множестве являются квадратами целых чисел. Извлечем из этого множества пять случайных чисел. Определите вероятность того, что большинство из них окажется квадратами целых чисел. Подсказка: аналогично примеру 3.8.3 просуммируйте количество вариантов, в которых количество квадратов целых чисел превышает три.
3.6. Дайте определение левого и правого хвостов биномиального распределения.
3.7. Докажите верхнюю оценку (3.5.8) для левого хвоста биномиального распределения.
3.8. Почему определение 3.2 считается теоремой, которую можно доказать с помощью закона больших чисел?
3.9. Пусть п = pq, где р и q — разные простые числа приблизительно одинаковой длины. Известно, что для любого а < п и gcd(a, п) = 1 выполняется равенство ap+q = an+1(modn). Докажите, что число п можно факторизовать за п1/4 шагов.
3.10. В протоколе "Подбрасывание монеты по телефону" Алиса извлекает из равномерно распределенной совокупности большое целое число. Чему равна энтропия Алисы, измеренная со стороны Алисы и Боба соответственно?
3.11. В примере 3.11 мы измерили избыточность четырех очень длинных названий атак, описанных в главе 14, по сравнению с сокращениями аО, а1, а2 и аЗ. Используя сведения, изложенные в главе, оцените избыточность следующих четырех сокращенных названий атак.
• Passive IND-attack
• IND-CPA
• IND-CCA
• IND-CCA2
Глава 4
Вычислительная сложность
4.1 Введение
Если случайная величина имеет равномерное распределение и не зависит от какой-либо известной информации, то не существует способа связать эту величину с какой-либо другой информацией с помощью "вычислений". Именно это обстоятельство лежит в основе безусловно стойкой (или теоретико-информационной) схемы шифрования: одноразового блокнота (one-time pad). Суть этой схемы шифрования заключается в побитовом смешивании строки, состоящей из равномерно распределенных символов (так называемой ключевой строки), и строки сообщения (см. раздел 7.3.3). Для обеспечения независимости между ключевой строкой и строкой сообщения необходимо, чтобы они имели одинаковую длину. К сожалению, на практике эти ограничения почти невыполнимы.
Несмотря на это, ситуация не является безнадежной. Во время записи сообщения шифровальщики широко используют не слишком мощные вычислительные устройства и методы. (Заметим, что эти методы доступны и взломщикам шифров.) На сегодняшний день еще не существует удачных вычислительных средств, позволяющих установить связь между двумя обрывками информации, если один из них "выглядит случайным", несмотря на то, что оба текста полностью зависят друг от друга (например, открытый и зашифрованный тексты в большинстве криптосистем). В результате безопасность современных криптографических систем основывается на так называемой теории вычислительной сложности (complexity-theoretic model). Эта безопасность зависит от предположения, что некоторые задачи являются трудноразрешимыми (intractable problems). Здесь термин "трудноразрешимые задачи" означает, что широкодоступные вычислительные методы не в состоянии эффективно их решать.
Следует заметить, что описанная выше ситуация может оказаться временной. В настоящее время возникли новые, более мощные модели вычислений — квантовые (quantum information processing — QIP). В рамках этих моделей гигантское количество вычислений можно выполнять параллельно, манипулируя так называемыми "суперпозициями" квантовых состояний. В результате многие трудноразрешимые задачи, обеспечивающие стойкость криптосистем, будут решены и, следовательно, станут бесполезными. Например, с помощью квантового
Глава 4. Вычислительная сложность
119
компьютера факторизация и умножение целых чисел одинакового размера будут выполняться за одинаковое время, и, следовательно, такие известные криптосистемы с открытым ключом, как система RSA (Rivest, Shamir and Adelman [246]), описанная в разделе 8.5, сойдут со сцены. Однако пока квантовые вычисления остаются лишь на бумаге. Текущий рекорд факторизации составного числа равен 15 [300]. Это наименьшее нечетное составное целое число, не являющееся квадратом.
Итак, пока еще можно не слишком бояться применения квантовых вычислений. В остальной части главы мы будем использовать обычную вычислительную модель и подходы, основанные на применении теории вычислительной сложности.
4.1.1 Структурная схема главы
В разделе 4.2 описывается модель вычислений Тьюринга (Turing). В разделе 4.3 рассматриваются классы детерминированных полиномиальных алгоритмов и способы измерения сложности. В разделах 4.4 и 4.5 изучаются два подкласса недетерминированных полиномиальных задач (NP-задачи). Первый подкласс (раздел 4.4) состоит из вероятностных полиномиальных задач, которые в свою очередь разделяются на четыре подкласса эффективно решаемых задач (разделы 4.4.2-4.4.5). Второй подкласс (раздел 4.5) включает задачи, которые эффективно решаются только, если известна дополнительная информация. Эти задачи играют важную роль в современной криптографии, основанной на теории вычислительной сложности. В разделе 4.6 вводится понятие сложности, не связанное с полиномами. Раздел 4.7 посвящен неполиномиальным задачам, в частности, решению проблемы неразличимости при полиномиальной оценке временных затрат работы алгоритма (polynomial-time indistinguishability). В заключительном разделе 4.8 обсуждается связь между теорией вычислительной сложности и современной криптографией.
