Современная прикладная криптография (стр. 13 )

Класс эквивалентности, состоящий из всех "самых трудных" задач np, включающий задачу о выполнимости, получил название NP-полных задач (HP-complete). Если какая-нибудь из NP-полных задач окажется в Р, то будет доказано равенство NP=P.

Класс Co - NP состоит из всех задач, являющихся дополнительными некоторых задач из NP. Если задача в NP имеют вид "определить, существует ли решение", то задача из Co-NP имеет вид "показать, что решений нет". Неизвестно, верно ли равенство NP = Co-Np, но есть задачи, принадлежащие пересечению классов np и Co-NP. Примером такой задачи является "задача о разложении целых чисел": дано целое n, определить существуют ли делители р и q, такие, что n = pq. (Эта задача, нашла плодотворное применение в криптологии). Задача нахождения делителей однако сложнее, чем задача установления разложимости числа n.

Класс pspace состоит из задач, требующих полиномиальный объем машинной памяти, но не обязательно решаемых в полиномиальное время. Он включает классы np и Co-NP, но есть задачи в pspace, которые, по-видимому, труднее, чем задачи в np и Co-NP.

Класс PSPACE-полных задач (PSPACE-complete) состоит из задач, имеющих свойство, что если какая-нибудь из них окажется принадлежащей классу np, то pspace=np, или, если какая-нибудь из них окажется в р, то pspace=p.

Наконец, класс exp-time состоит из задач, решаемых в экспоненциальное время, и включает класс pspace.

В заключение уместно вспомнить слова К. Шеннона о том, что "проблема создания хорошего шифра является, по существу, проблемой нахождения наиболее сложных задач, удовлетворяющих определенным условиям. Можно составить наш шифр таким образом, чтобы раскрытие его было эквивалентно (или включало в себя) решению некоторой проблемы, про которую известно, что для ее решения требуется большой объем работы" [1].

1.5. Некоторые необходимые сведения из теории чисел

Следуя традиции ряда учебников по криптографии [24,46], можно было бы привести сведения из теории чисел, необходимые для понимания излагаемого материала. Для экономии объема отошлем за этими сведениями к указанным учебникам.

Раздел 2. Основные понятия и методы современной криптологии

2.1. Криптографические протоколы

Протокол - это точно определенная последовательность действий, посредством которых две или более стороны совместно решают (выполняют) некоторую задачу. Хотя это определение не достаточно строгое, и смысл понятия будет ясен из дальнейших примеров, следует обратить внимание на некоторые моменты, отмеченные в [85].

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

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

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

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

Протоколы с арбитром (Arbitrated Protocols).

Арбитр (arbitrator) – это не незаинтересованная, пользующаяся всеобщим доверием сторона, непосредственно участвующая в протоколе. Незаинтересованность означает, что арбитр не имеет своих личных предпочтений, как завершить протокол, и не имеет зависимости ни от одной из сторон. Доверительность означает, что все участники протокола признают, что любые утверждения или действия арбитра истинны и корректны. Арбитры могут помогать в завершении протоколов между взаимно недоверяющими сторонами.

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

Протоколы с третейским судьей (Adjudicated Protocols)

Эти протоколы не требуют больших затрат на арбитров, так как арбитр – третейский судья появляется только в исключительных случаях, когда возникают спорные ситуации между сторонами. Третейский судья также является незаинтересованной и пользующейся доверием стороной, но, в отличие от арбитра, он не участвует напрямую в протоколе. Участие третейского судьи не всегда необходимо. Существующие компьютерные протоколы исходят из того, что участвующие стороны действуют честно по правилам, но, если кто-нибудь обманывает, то существуют данные, по которым незаинтересованная третья сторона может определить, что кто-то обманывает. В хороших протоколах с третейским судьей он может также определить, кто именно обманывает.

Самодостаточные протоколы (Self Enforcing protocols). Это наилучший тип протоколов, когда сам протокол гарантирует соблюдение правил. Такой протокол построен так, что не может быть никакой спорной ситуации. И если одна из сторон попытается обмануть, то другая сторона немедленно определит это. К сожалению, не всегда удается построить такой протокол для каждой ситуации.

Атаки на протоколы могут быть направлены как против криптографических алгоритмов, используемых в протоколах, как против средств, использованных для реализации алгоритмов (например, генератора ключей), так и непосредственно против самих протоколов. Такие атаки делятся на пассивные и активные. Во время пассивной атаки злоумышленник только наблюдает за действиями сторон в протоколе и старается извлечь из этого полезную ему информацию, не вмешиваясь и не нарушая протокола. (Это соответствует атаке на криптосистему только по шифрованному тексту). При активной атаке на протокол злоумышленник старается видоизменить протокол в собственных интересах. Он может попытаться ввести новые сообщения в протокол, удалить присутствующие, заменить одно сообщение на другое, вывести из строя канал связи или изменить хранимую в компьютерах информацию.

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

2.2. Однонаправленная функция

Понятие это, как сказано в [56], первым ввел Нидхэм (Needham R. M.) в работе о защите входа в вычислительные системы.

Функция f(x) называется однонаправленной (one-way function - иногда переводят как односторонняя функция), если для всех х из ее области определения легко вычислить y=f(x), но почти для всех у из ее области значений, нахождение любого х, для которого y=f(x), вычислительно не осуществимо.

Заметим, что в определении фраза "почти для всех у" необходима, так как можно легко вычислить и запомнить, согласно первой части определения целую таблицу значений , ,…, и, если окажется, что выбранное значение у принадлежит этой таблице, то соответствующий х может быть легко определен. Фраза "вычислительно не осуществимо" означает с точки зрения теории сложности, что неосуществимо за полиномиальное время, которое характеризует "легко вычислимые задачи".

Может быть дано более строгое определение однонаправленной функции, но это лишь затруднит первое знакомство с такой функцией.

До сих пор строго не доказано, что однонаправленные функции существуют. Показано, что проблема существования однонаправленной функции эквивалентна известной нерешенной проблеме совпадения классов задач P и NP. Тем не менее, было предложено много функций, которые похожи на односторонние. в качестве односторонней функции предложил функцию на основе задачи об укладке ранца. высказал идею о том, что умножение двух простых чисел не составляет труда, а вот разложение полученного числа достаточно трудная задача [56]. В частности, возведение в квадрат просто, а извлечение квадратного корня сложно.