Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
. Машина предполагает решение проблемы путем удачного угадывания либо перебором всех предположений параллельно, каждое за полиномиальное время. Таким образом, многие симметричные и асимметричные алгоритмы могут быть взломаны за недетерминированное полиномиальное время. Для данного шифротекста C противник выбирает наугад открытый текст Х и ключ k, а затем за полиномиальное время осуществляет его шифрование и сверяет с данным шифротекстом.
Класс NP включает в себя класс Р, так как любая проблема, решаемая за полиномиальное время на детерминированной машине Тьюринга, будет также решена за полиномиальное время на детерминированной машине Тьюринга. Если все NP проблемы решаются за полиномиальное время на детерминированной машине, то P = NP. Несмотря на то, что интуитивно чувствуется разная сложность различных NP-проблем, еще не было доказано, что , впрочем, как и обратное.полные проблемы входят в класс NP и так же сложны, как и любая проблема класса NP. Если NP-полная проблема решается за полиномиальное время, то P = NP, и наоборот: если для любой проблемы класса NP возможно доказательство отсутствия существования детерминированного алгоритма с полиномиальным временем выполнения, то и для NP-полной проблемы не существует детерминированного алгоритма с полиномиальным временем решения. Таким образом, доказательство решаемости NP-полных проблем за детерминированное полиномиальное время, очевидно, разрешит вопрос о равенстве классов P и NP и будет означать возможность взлома многих шифров слабыми, детерминированными алгоритмами.
Следующим в иерархии сложности стоит класс PSPACE. Проблемы этого класса могут быть решены в полиномиальном пространстве, но не обязательно за полиномиальное время. PSPACE включает в себя класс NP при видимой сложности некоторых проблем класса PSPACE перед NP. Их равенство также пока не доказано. Кроме того, существует также класс PSPACE-полных проблем, для которых справедливо следующее условие: если любая из них является NP-проблемой, то PSPACE = NP, и если любая из них является P-проблемой, то PSPACE = P.
И, наконец, существует класс проблем EXPTIME, которые решаются за экспоненциальное время. EXPTIME не равно Р.
Опишем основополагающие теоретико-числовые проблемы в криптографии: проблему принятии решения Дифии-Хеллмана и вычислительную проблему Диффи-Хеллмана.
Пусть даны простое число р и g - порождающий элемент по модулю р. Существует полиномиальный алгоритм возведения числа в степень по любому модулю, поэтому задача вычисления значения считается легкой задачей. Вычисление же обратной функции считают сложной задачей, поскольку на данный момент не найдено полиномиальных алгоритмов ее решения. Впрочем, не доказано и принципиальная невозможность построить такой алгоритм.
Проблема Диффи-Хеллмана формализует проблему дискретного логарифмирования. Предположение о сложности решения проблемы принятия решения Диффи-Хеллмана лежит в основе многих криптографических протоколов, среди которых наиболее известны криптосистемы Эль Гамаля и Крамера-Шоупа.
Рассмотрим мультипликативную циклическую группу (cyclic group) ? порядка p с порождающим элементом g. Предположение о сложности решения DDH проблемы заключается в том, что для данных ga и gb со случайно выбранными элементами значение gab выглядит совершенно неотличимым от случайно выбранного элемента из ?.
Формально говоря, два нижеприведенных распределения вероятностей вычислительно не различимы для параметра безопасности p:
-, где a и b случайно и независимо выбраны из .
-, где a, b, c случайно и независимо выбраны из .
Строка вида в отечественной и зарубежной литературе часто называется кортежем, строкой или тройкой Диффи-Хеллмана (DDH triples, DDH tuples).проблема тесно связана с предположением о сложности решения проблемы дискретного логарифмирования. Поскольку на данный момент задача дискретного логарифмирования не относится к числу решаемых за полиномиальное время, то проблема Диффи-Хеллмана считается сложной. Таким образом, любая криптосистема, взлом которой вычислительно эквивалентен решению данной проблемы, является условно стойкой.
В случае существования эффективного алгоритма вычисления дискретного логарифма в ? взлом DDH в группе ? представляет собой тривиальною задачу. Тогда для данных определение, является ли , заключается в вычисление дискретного логарифма , а затем в сравнении значений z и .
По этой причине решение DDH проблемы считают сложнее вычисления дискретного логарифма в следующем смысле: существуют группы, в которых определение кортежей DDH является легкой задачей, но вычисление дискретного логарифма остается сложным. По этой причине требование о предполагаемой сложности DDH в группе является более ограниченным.
Сложность DDH также связана со сложностью решения вычислительной проблемы Диффи-Хеллмана (computational Diffie-Hellman assumption, CDH). Она заключается в утверждении о том, что если возможно эффективно вычислить при данных , тогда легко различить описанные выше вероятностные распределения. Поэтому предположение и DDH считается более строгим, чем CDH.
Проблема распознавания DDH строки является саморедуцируемой (random self-reducible). Грубо говоря, это понятие означает, что если что-то является сложной задачей даже для небольшого фрагмента, то это будет сложно практически для любого объема входных данных, и если что-то легко решить для небольшого фрагмента входных данных, то это можно считать легкой задачей для почти любого объема входных данных.
2.4 Модель случайного ор