Lecture 02

Вычислительная сложность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных

Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами

Одной из основных абстрактных моделей вычисления в теории сложности является Машина Тьюринга

В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы)

Классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче.

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

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

Класс NP включает в себя класс P. Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики.

Гэри М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи .

Издательство Мир 1982 г.

Монография американских ученых посвящена решению сложных (в том числе и NP-трудных) комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории

автоматов с примерами.

• Интуитивная (до начала XVI века )

1

• Формальная (конец XV века - начало XX века )

2

• Научная (30-е - 60-е годы XX века)

3

• Компьютерная (с 70-х годов XX века)

4

Криптосистема

Абонент Е (Ева) – противник, конкурент

Криптоаналитик

Симметричные ключи (также называемые секретными ключами (secret key) - имеет двойную функциональность и применяется для зашифрования и для расшифрования

Каждый из абонентов должен хранить ключ в секрете и надлежащим образом защищать его

Поскольку оба абонента используют один и тот же ключ, то симметричные криптосистемы могут обеспечить только конфиденциальность, но не аутентификацию или неотказуемость

Сообщение делится на блоки битов, которые передаются на обработку математическим функциям, по одному блоку за раз

Для обеспечения стойкости шифра, в нем должны в достаточной степени использоваться два основных метода: перемешивание (confusion) и рассеивание (diffusion). Перемешивание обычно выполняется с помощью замены, тогда как рассеивание – с помощью перестановки.

Поточные шифры (stream cipher) обрабатывают сообщение, как поток битов и выполняют математические функции над каждым битом отдельно

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