Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Вµтся с помощью нотации О большого, то есть описывается порядком величины вычислительной сложности. О большое - член разложения функции сложности, быстрее всего растущий с ростом п, в результате чего все члены низшего порядка игнорируются. Например, если временная сложность заданного алгоритма составляет , то вычислительная сложность, равная порядку , записывается в виде .
Использование нотации большого О позволяет выявить зависимость требований к времени и объёму памяти от объёма входных данных. Например, если , то удвоение входных данных также удвоит и время выполнения алгоритма. Если , то добавление одного бита к входным данным удвоит время алгоритма.
Согласно теории сложности алгоритмы классифицируют в соответствии с их временной или пространственной сложностью следующим образом. Алгоритм называется постоянным (constant algorithm), если сложность его выполнения не зависит от объёма входных данных n: . Алгоритм является линейным (linear algorithm), если его сложность его выполнения линейно зависит от объёма входных данных: . По аналогии с линейным алгоритмом различают квадратичные , кубические и т.п. в зависимости от константы m в . Алгоритмы, сложность которых определяется как , называются полиномиальными (polynomial algorithm), а алгоритмы с полиномиальной временной сложностью - алгоритмами с полиномиальным временем (polynomial time).
Алгоритмы со сложностью , где - константа, а - некоторая полиномиальная функция от п, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность выполнения которых составляет , где с - константа, а возрастает быстрее, чем постоянная функция, но медленнее, чем линейная, является суперполиномиальным.
Как мы можем наблюдать, с ростом п временная сложность может возрасти настолько, что это повлияет на практическую реализуемость алгоритма. В таблице 2.1 приведены данные о времени выполнения различных классов алгоритмов для .
Таблица 2.1 - Время выполнения различных классов алгоритмов
КлассСложностьКоличество операций для Время при операций в секундуПостоянные11 мксЛинейный1061 сКвадратичные101211,6 дняКубические101832000 летЭкспоненциальные10301030В 10301006 раз больше, чем время существования вселенной
Что касается временной сложности вскрытия грубой силой алгоритмов различных классов, то она прямо пропорциональна количеству возможных ключей, которое в свою очередь экспоненциально зависит от длины ключа. Для ключа длиной n сложность вскрытия алгоритма грубой силой равна . Обычно в зависимости от этого значения определяется нижняя граница длины ключа. Например, для 56-битового ключа временная сродность взлома грубой силой алгоритма DES равна 256, а для 112-битового - 2112, причем в первом случае вскрытие возможно, а вот втором - уже нет.
Поразрядные оценки сложности основных операций в кольце вычетов, необходимые нам для оценки эффектинвости вычислекния разрабатываемой и существующиз псевдослучаемых функций приведены в таблице 2.2.
Таблица 2.2 - Поразрядные оценки сложности основных операций в кольце вычетов (29)
Операция над Сложность медленно быстро медленно быстро
Помимо сложности конкретных алгоритмов решения проблемы теория сложности также классифицирует и сложность самих проблем. Теория рассматривает минимальное время и объём памяти, необходимые для решения самого трудного варианта проблемы на теоретическом компьютере, известном как машина Тьюринга. Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения/записи и является реалистичной моделью вычислений.
Проблемы, решение которых возможно при помощи алгоритмов с полиномиальным временем, называются решаемыми, так как для разумных входных данных обычно могут быть решены за разумное время. Проблемы, которые невозможно решить за полиномиальное время, называются неразрешимыми (трудноразрешимыми, трудными) по причине того, что вычисление их решений быстро становится невозможным. Проблемы, которые могут быть решены только с помощью суперполиномиальных алгоритмов, вычислительно нерешаемы, даже при относительно малых значениях п. Кроме того, Алан Тьюринг доказал, что некоторые проблемы принципиально неразрешимы - даже если отвлечься от временной сложности алгоритма, невозможно построить алгоритм решения таких проблем.
Существует множество хорошо известных трудноразрешимых задач, которые часто используются в современной криптографии. Например, к неразрешимым задачам относятся задача факторизации целых чисел (integer factorization problem), задача дискретного логарифмирования (discrete logarithm problem), задача Диффи-Хеллмана (Diffie-Hellman problem) и некоторые родственные задачи. Эти задачи можно рассматривать в качестве эталонов, поскольку они имеют долгую историю и в настоящее время продолжают считаться трудноразрешимыми.
Поэтому криптографические алгоритмы и протоколы считаются хорошими, если формально доказана их практическая стойкость к адаптивным разновидностям атак с одной стороны, а с другой - практическая эффективность по отношению к ресурсам пользователя.
Проблемы можно разбить на классы в соответствии со сложностью их решения. Самые важные классы и их предполагаемые соотношения представлены на рисунке 2.2.
Рисунок 2.2 - Классы сложности проблем
Класс Р состоит из всех проблем, которые можно решить за полиномиальное время. Класс NP составляют проблемы, которые можно решить за полиномиальное время только на недетермированной (вероятностной) машине Тьюринга