Современная прикладная криптография

Другим примером задачи, которая имеет экспоненциальную временную сложность, является "задача выполнимости". ("Satisfiability problem"), заключающаяся в проверке существования выполняющего набора булевых переменных для набора дизъюнкций над этим множеством переменных.

Класс NP включает класс P, так как любая задача, полиномиально решаемая на детерминированной машине Тьюринга, полиномиально решаема и на недетерминированной. Если бы все задачи из np-класса полиномиально решались бы на детерминированной машине, то было бы верно равенство P=NP. Хотя многие задачи из NP-класса кажутся более сложными, чем задачи из P (например, задача о рюкзаке, задача о выполнимости), но никто еще не доказал, что P NP.

Основной метод, используемый для доказательства близости задач, состоит в "сведении" их друг к другу с помощью конструктивного преобразования, которое позволяет превратить любой алгоритм решения одной задачи в алгоритм решения другой. Известно много примеров подобной сводимости [26]. В 1971 г. Кук (Cook) показал, что задача о выполнимости имеет свойство, что каждая другая задача из np может быть сведена к ней за полиномиальное время. Далее Карп (Каrр) доказал, что многие хорошо известные комбинаторные задачи, включая "задачу о коммивояжере" [15], столь же трудны, как задача о выполнимости.

Класс эквивалентности, состоящий из всех "самых трудных" задач 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]. В частности, возведение в квадрат просто, а извлечение квадратного корня сложно.

В качестве возможной односторонней функции Гилл Дж. [Gill] предложил показательную функцию f(x) = modn, где а (основание) принадлежит интервалу (l,n-1), а умножение ведется по модулю числа n. Значение modn вычисляется достаточно эффективно, даже при больших числах х из (l.n) за операций, с помощью схемы Горнера "слева-направо" или "справа-налево").

Если двоичное разложение числа х имеет вид, то

(вариант "слева-направо")/(вариант "справа-налево")

Операция, обратная к этой операции, известна как операция вычисления дискретного логарифма: по данным а и у найти такое целое т. что modn = у. До настоящего времени не найдено достаточно эффективных алгоритмов решения этой задачи. Более подробно об этом сказано в [32,34,35].

С помощью показательной функции Диффи и Хеллман разработали так называемую схему открытого распределения ключей [4]. В этой же работе Диффи и Хеллман предложили для построения однонаправленных функций использовать классические криптосистемы с одним ключом, стойкие к методам вскрытия по известному открытому и шифрованному текстам (known plaintext attack). Если зафиксировать какой-нибудь открытый текст и рассмотреть отображение пространства ключей в пространство шифртекстов, определяемое в виде f(x) = = с, то нахождение по f(x) эквивалентно задаче нахождения ключа по известному открытому и соответствующему шифрованному текстам.

Для шифрования информации однонаправленная функция не применима, так как никто, даже законный адресат, не сможет расшифровать шифртекст C = f(M), полученный с ее помощью. В [85] найдено хорошее сравнение преобразования однонаправленоой функции с разбиением тарелки: восстановить рисунок по мелким кусочкам разбитой тарелки достаточно трудная задача. Однако именно эти свойства однонаправленных функций, как уже было сказано, нашли применение в парольной аутентификации пользователей ЭВМ.

Понятие однонаправленной функции оказалось также связанным с понятием широко используемых в криптографии генераторов псевдослучайных последовательностей [21], а также с понятием так называемой функции хэширования информации [164]. Кроме того, это понятие послужило толчком к определению однонаправленной функции с секретом (trap-door one-way function)

2.3 Открытое распределение ключей. Схема Диффи-Хеллмана

Одной из проблем криптографии, решенной в работе Диффи и Хеллмана [4], стала проблема распределения (рассылки) ключей для секретной связи. Использование криптосистем с секретным ключом предполагает заблаговременные до сеансов связи договоренности между абонентами о сеансовых секретных ключах или их предварительную пересылку по защищенному каналу связи. Разработанные в [4] принципы так называемого открытого распределения ключей (ОРК) и открытого шифрования (ОШ) и явились "новыми направлениями в криптографии", давшими начало криптографии с открытым ключом. Несмотря на то, что идеи ОРК и ОШ были сформулированы одновременно, удалось сразу предложить конкретную реализацию только для схемы ОРК, на основе показательной односторонней функции. Эта схема получила название экспоненциального ключевого обмена Диффи - Хеллмана.

Рассмотрим схему в ее оригинальном изложении. В протоколе обмена секретными ключами предполагается, что все пользователи знают некоторое большое простое число р и примитивный элемент (1<<p) конечного поля GF(р) (то есть элемент, степени которого а^t дают все ненулевые элементы поля {l,2,...,p-1}). Такие элементы всегда существуют, их число равно , где - функция Эйлера [66]. Для выработки общей секретной информации k пользователи A и B должны сделать следующее.

1. Пользователи а и в независимо выбирают случайные числа и из интервала {l,...,p-1}, называемые секретными ключами пользователей.

2. Вычисляют с использованием известных р и величины

и ,

которые являются открытыми ключами пользователей.

3. Обмениваются ключами и по открытому каналу связи (с подтверждением их авторства, чтобы избежать замены их кем-то другим).

4. По полученным ключам и каждый из пользователей независимо вычисляет секретный параметр K, который и будет их общим сеансовым секретным ключом.

Еще раз следует подчеркнуть, что в схеме не устраняется необходимость аутентификации открытых ключей в п.3, то есть подтверждения того факта, что и действительно выработаны пользователями A и B.

Безопасность (секретность) изложенной схемы зависит от (не превышает) сложности вычисления дискретных логарифмов в мультипликативной группе конечного поля GF(p). Пока не найдено удовлетворительных быстрых алгоритмов нахождения К из ,, без вычисления из , и из ,.

В настоящее время наиболее интересны с точки зрения реализации следующие алгебраические группы:

-мультипликативная группа конечного поля: GF(p)^*, р - простое число > 2 ;

-мультипликативная группа конечного поля характеристики 2: GF;

-группа точек эллиптической кривой над конечным полем f: ес(F);

Некоторые последние результаты по проблеме дискретного логарифмирования

Общие методы для произвольной группы:

Метод Шенкса (Daniel Shanks) или ”baby steps, giant steps”.

Pollard ro-method.(рандомизированный алгоритм)

- метод Полларда.

Аддитивная группа кольца вычетов целых чисел (Z, +) по модулю m.

Найти x из a х=b (mod m). Очень просто решается.

Мультипликативная группа целых чисел по модулю простого числа p.

Метод Шенкса (baby steps, giant steps)).

Pollard ro-method.(рандомизированный алгоритм).

Сложность методов решения DLP - О(), где q наибольший простой делитель числа

(p-1), хотя метод Полларда почти не использует память.

1993. Van Oorschot - Wiener предложили способ распараллеливания метода Полларда на t процессоров. Это дало сложность в t раз меньшую.

Обычно число q выбирают сравнимым с числом p, например берут p=2q+1.

Использование дополнительных свойств группы.

Методы исчисления индексов (Index calculus methods)

Обычно состоят из трех этапов. Двух предварительных вычислительных этапов: генерации соотношений, решение уравнений и оперативного, рабочего этапа: вычисление доступных логарифмов с использованием результатов предыдущих этапов.

Субэкспоненциальная сложность. L[1/2, c], где с - некоторая константа с > 0.

Метод линейного решета (Lenear sieve method) и Gaussian integer method достигли с=1.

L[t,c] = exp((с+0(1))((lnp)(lnlnp))

Улучшить оценку сложности позволило ускорение предварительных вычислительных этапов. Решение разреженных систем линейных уравнений за O(n) шагов (метод Wiedemann, Berlekamp-Massey algorithm).

См. Odliyzko, DLP in FFs and their crypto significance, Eurocrypt`84.

1988. Поллард нашел новый подход для факторизации целых чисел. H. Lenstra развил его для чисел специального вида. Далее рядом авторов он был распространен на произвольные числа со сложностью L_N [1/3, c], где с=(64/9) = 1,9229… .

Далее Копперсмит улучшил оценку с=1,9018… .(См. Modifications to the Number Field Sieve, J.Cryptology 6(1993),169-180)

1992 Gordon D. адаптировал метод NFS для решения DLP при простом p со сложностью L[1/3, c], где с=2,0800.

1993. Shirokaurer O. снизил оценку с до с=1,9229. Алгоритм Широкауера был реализован Вебером, и в работе [Weber D. Eurocrypt`95, 95-105] описано логарифмирование по модулю p порядка 10^40, а в работе 1996г.[Schirokauer O., Weber D., Denny T., ANTS II, 337-362] p порядка 10^65.

Жу и Лерсье [Joux A., Lercier R. ]в апреле 2001 года провели логарифмирование по модулю 10^120. Это рекорд для модуля не специального вида (2003).

2003. Матюхин Д.В. довел константу с до с=1,9018 (См. Дискретная математика и ее приложения, 13(2003), №1, 17-50)

Это на сегодня лучшая оценка трудоемкости.

Группа точек эллиптической кривой над конечным полем

ECDLP - дискретное логарифмирование на эллиптической кривой.

Число точек на кривой по теореме Хассе

#E(F) = q+1 - t при -2 t2

Наилучшие методы решения ECDLP - это ро-метод и лямбда метод Полларда.

Для группы из N элементов, Ро-метод Полларда дает сложность О(), а - метод Полларда) дает О(). Методы Полларда работают в любой абелевой группе.

Оба метода эффективно распараллеливаются.

До сих пор не предложено субъэкспоненциальных алгоритмов для произвольных кривых.

Однако, существуют субъэкспоненциальные алгоритмы для специфических кривых: суперсингулярных (t= 0, q, 2q, 3q, или 4q) и аномальных (кривая над Z с p точками).

В отчете проекта NESSIE (2003) , после анализа сложности основных теоретко-числовых задач, предложена таблица эквивалентных по стойкости размеров ключей

Размер симметричного ключа	56	64	80	112	128	160
Размер модуля (pq)	512	768	1536	4096	6000	10000
Размер характеристики поля эллиптической кривой	112	128	160	224	256	320

Заметим, что в отечественном ГОСТ 34.10-2001 минимальный характеристики простого поля p> 2, в то время как размер ключа в ГОСТ 28147-89 равен 256.

P-174 - 06

An Algorithm to Solve the Discrete Logarithm Problem with the Number Field Sieve

An Commeine, Igor Semaev

(Алгоритм решения задачи дискретного логарифмирования с помощью метода решета числового поля)

В работе предложен новый алгоритм для решения DLP в поле GF(p), отличный от алгоритма Матюхина Д.В., но с той же сложностью L[1/3, 1,9018]. Достоинством нового метода является лучшая трудоемкость последнего рабочего этапа за L[1/3, 3] = L [1/3, 1,44225]

E-254-06

The Function Field Sieve in the Medium Prime Case

(Решето поля функций в случае простого числа среднего размера)

Antoine Joux, Reynald Lercier

В работе рассматривается применение так называемого алгоритма решета поля функций для вычисления дискретных логарифмов в полях вида Fпри q - среднего размера степень простого числа. Авторы показывают, что при q не слишком большом, для решения DLP может быть использован вариант решета поля функций с хорошей сложностью L[1/3]. Условие для q: logq<O(log n). Как всегда

L[t,c] = exp((c+0(1))((logN))(loglogN)).

Для двух крайних случаев, простого поля F и поля F, решето числового поля и решето поля функций дают сложность

L[1/3, (64/9)] и L[1/3, (32/9)] соответственно.

Этот новый алгоритм имеет важное значение при оценке стойкости некоторых известных криптосистем, таких как основанных на торе Т схемах, схемах короткой подписи с характеристикой 3, криптосистемах на основе суперсингулярных абелевых переменных.

Решето поля функций было предложено Адлеманом (ANTS-I, 1994, 108-121) как обобщение алгоритма Копперсмита(1984, Fast evaluation of logarithms in fields of char two).

Далее Адлеман и Хунг улучшили его сложность.(1999 )

Joux - Lercier в 2002 году показали, что он практически применим для поля характеристики 2. В 2004 Granger R., Holt A. он был применен для характеристики 3.

Интересно то, что предложенный метод позволяет решать DLP в случае, когда оба числа q и p среднего размера, быстрее, чем в поле сопоставимого размера вида F (p-простое) и F (n-простое).

В момент передачи статьи для публикации авторы добавили в нее результат препринта, который появился в трудах CRYPTO`06 (C-326)

C-326 - 06

The Number Field Sieve in the Medium Prime Case

(Решето числового поля в случае простого числа среднего размера)

Antoine Joux, Reynald Lercier, Nigel Smart, Frederik Vercauteren

В этой статье авторы изучают несколько вариантов NFS для вычисления дискретных логарифмов в конечных полях вида F, где p от среднего до большого простое число. Показано, что когда n не слишком большое число, то сложность решения задачи аналогична сложности задачи NFS для простых полей и составляет L[1/3]. Этот р результат дополняет последний результат Joux - Lercier на Eврокрипте`06 и по методу решета поля функций. Таким образом, для решения DLP достигнута сложность L [1/3] для любого конечного поля.

Для иллюстрации метода вычисляется логарифм в поле 120-разрядных чисел из конечного поля F.

eP-2006/253-06

Hard Instances of the Constrained Discrete Logarithm Problem

(Трудные примеры ограниченной DLP)

Ilya Mironov, Anton Mityagin, Kobbi Nissim

Это скорректированная версия статьи, представленной на симпозиуме (7th Algorithmic Number Theory Symposium -ANTS VII), LNCS 4076, pp. 582-598, 2006..

Проблема DLP обобщается до «ограниченной DLP», когда секретная экспонента принадлежит некоторому множеству, известному противнику. Сложность общего алгоритма для решения ограниченной DLP зависит от выбора этого множества. Авторы изучали множества, для которых решение ограниченной DLP трудно.

eP-2006/333-06

Discrete Logarithms in Generalized lacobians

S. D. Galbraith, B. A. Smith

Показано, что обобщенные якобианы (Dechene) как источник групп для криптосистем с открытым ключом менее предпочтительны, чем стандартные якобианы.

Задача Диффи-Хеллмана

Протоколы транспортировки ключей и протоколы согласования ключей.

Протокол согласования ключей Диффи-Хеллмана для произвольной группы

Дано: G = (g) - циклическая группа порядка p с генератором g, в которой DLP трудно решаема. Это открытая информация.

Сторона А: выбирает секретный ключ а из {1,…,p} и вычисляет открытый ключ g*g*…*g=Y(a раз), передает Y стороне B по открытому каналу с аутентификацией.

Сторона B: выбирает секретный ключ b из {1,…,p} и вычисляет открытый ключ g*g*…*g=Y_B (b раз), передает Y стороне A по открытому каналу с аутентификацией.

Сторона А: вычисляет К= Y*…* Y (a раз) = g*…*g(ab раз)

Сторона B: вычисляет К= Y*…* Y (b раз) = g*…*g(ba раз)

Вычислительная задача Диффи-Хеллмана (The computational DH problem - CDH)

Дано: G = (g), g, g, g.

Найти: g.

Задача принятия решения Диффи-Хеллмана (The decisional HH problem - DDH)

Дано: G = (g), g, g, g, g.

Найти: g^ab = g^c или не равно.

(The Gap DH problem)

Дано: G = (g), g, g, g, и оракул, который корректно решает задачу принятия решений Диффи-Хеллмана.

Найти: g.

Очевидно, что если задача DDH является трудно решаемой в группе (g), то тогда трудно решаемы задачи CDH и DLP.

Сильная задача Диффи-Хеллмана и ее варианты(SDH - strong Diffie-Hellman problem)

t-слабая задача Диффи-Хеллмана(t-weak Diffie-Hellman(t-wDH) problem

Дано: G = (g), g, g) для i = 1,2,…,t.

Найти: g.

(задача была сформулирована Mitsunari-Sakai-Kasahara в 2002 году)

t-сильная задача Диффи-Хеллмана(t-weak Diffie-Hellman(t-wDH) problem

Дано: G = (g), g, g) для i = 1,2,…,t.

Найти: g

(задача является ослабленной версией t-wDH задачи. Она была введена Boneh и Boyen (eurocrypt 2004) для построения схем коротких подписей)

Задача SDH обощается на так называемые билинейные группы.

The `-Bilinear Diffie-Hellman Inversion (`-BDHI) Problem.

E-1 -06

Security Analysis of the Strong Diffie-Hellman Problem

(Анализ безопасности сильной задачи Диффи-Хеллмана)

Jung Hee Cheon

В работе показано, что если g - элемент простого порядка p в абелевой группе и а из Z, то если известны элементы g, g, и g для некоторого положительного делителя d числа (p - 1), то секрет а можно найти за O(log p·(+)) групповых операций, используя память объема O(max{,}). Если g (i = 0, 1, 2, . . . , d) известны для положительного делителя d числа (p + 1), то секрет а может быть найден за O(log p·(+d)) групповых операций, используя память объема O(max{, }). Это означает, что SDH задача имеет вычислительную сложность в O() меньшую, чем DLP для таких простых чисел.

Далее автор применяет предложенный алгоритм к криптосхемам, основанным на DLP в абелевых группах простого порядка. Это понижает сложность нахождения ключа с О() до О() для подписи вслепую Болдыревой и схемы шифрования Эль Гамаля, когда (p-1) (соответственно (p+1)) имеет делитель d (соответственно d) .

2.4 Односторонняя функция с секретом

Диффи У. и Хеллман развили понятие однонаправленной (односторонней) функции, позволившее приспособить его для целей шифрования и давшее начало всей новой области криптографии - криптографии с открытым ключом [4].

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

Один из первых предложенных примеров таких функций основан на степенной функции f(x) = mod n, вычисление которой при известных m и n производится одним из методов быстрого экспоненцирования не более чем за ^3 операций умножения. Преобразование, обратное к преобразованию возведения в степень mod n называется вычислением корня m-й степени по модулю n. В настоящее время эффективный алгоритм вычисления такого x , что mod n = у при известных числах m, n и у требует знания разложения числа n по степеням простых чисел. Таким образом, эта информация может служить как секретный параметр k.

Именно эта односторонняя функция с секретом используется в криптосистеме с открытым ключом RSA [9]. Другие широко известные примеры односторонних функций с секретом легли в основу криптосистемы на основе задачи о рюкзаке (knapsack function) [24], и криптосистемы Мак Элайса [57], и другие. Выбор систем и функций для изучения должен определяться их распространенностью применения и объемом необходимого для их объяснения нового материала.

2.5 Открытое шифрование, криптосистема с открытым ключом

На основе введенного понятия односторонней функции с секретом Диффи и Хеллман предложили новый принцип так называемого открытого шифрования, который вместе с открытым распределением ключей составил новое направление в криптографии, когда для организации секретной связи не требуется снабжения абонентов секретной информацией(ключами).

Действительно, если получатель секретного сообщения выберет одностороннюю функцию с секретом и сообщит по открытому каналу отправителю эффективный алгоритм ее вычисления, то отправитель может вычислить значение функции от сообщения M и передать это значение получателю также в открытом виде. Только знающий секретный параметр k знает алгоритм вычисления обратной функции и может определить M.

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

Итак, криптосистема с открытым ключом представляет собой систему, включающую следующие компоненты:

- пространство открытых текстов ;

- пространство шифрованных текстов ;

- пространство секретных ключей ;

- множество преобразований зашифрования ,

, где ;

- множество преобразований расшифрования .

При этом преобразования и должны удовлетворять следующим свойствам.

1. Для каждого преобразование является обратным к преобразованию , то есть при всех .

2. По каждому выбранному легко найти пару обратимых преобразований и .

3. Для всех ,, величины и легко вычисляются (в полиномиальное время).

4. Для почти всех вычислительно невозможно из вывести какое-либо легко вычисляемое преобразование, эквивалентное преобразованию .

Свойство 4 отличает эти системы от криптосистем с секретным ключом, рассмотренным ранее, в которых преобразования и также зависят от параметра к, но знание преобразования дает знание k и или наоборот, знание позволяет определить k и , так что преобразования и либо оба известны, либо оба неизвестны. Это свойство 4 позволяет не засекречивать преобразование , а сделать его открытым, общедоступным для всех, кто хочет послать секретное сообщение.

Так как злоумышленник имеет доступ к преобразованию зашифрования , то он может всегда выбрать любой открытый текст и получить соответствующий ему шифрованный текст. Поэтому криптосистемы с открытым ключом должны быть всегда устойчивы к методам по выбранному открытому тексту (chosen-plaintext attacks).

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

В ряде учебников по криптографии [24] секретное преобразование называют секретным ключом (private key), a открытое преобразования - открытым ключом (public key), а сами системы называют также двухключевыми криптосистемами (two key cryptosystem). Другим синонимом этих систем является понятие асимметричной криптосистемы (asymmetric cryptosystem), в то время как обычные криптосистемы с секретным ключом называются симметричными (symmetric cryptosystem).

Криптосистемы с открытым ключом обеспечивают только практическую стойкость.

Интересно, что авторы идеи и понятия о системах открытого шифрования не смогли сразу предложить такую систему для реализации (в отличие от схемы открытого распределения ключей). Первыми из таких систем являются ранцевая криптосистема Меркля-Хеллмана [24] и криптосистема Райвеста-Шамира-Адлемана (RSA) [9].

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

Название криптосистемы образовано от первых букв фамилий предложивших ее авторов (Rivest Н., Shamir A., Adleman L.) [9].

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

,

где (е, n) - ключ преобразования зашифрования.

При расшифровании блок открытого текста M восстанавливается также экспоненцированием, но с другой степенью d в качестве ключа расшифрования

Зашифрование и расшифрование могут быть выполнены с использованием быстрых алгоритмов экспоненцирования не более чем за операций.

В основе приводимых выше преобразований лежит теорема Эйлера (Euler), согласно которой для каждого числа M, взаимно простого с модулем n, выполнено соотношение , где - функция Эйлера, то есть число целых положительных чисел, не превосходящих n и взаимно простых с n.

Теорема. Если числа e и d удовлетворяют соотношению , a взаимно просто с n, то . (Это и означает, что d(e(m)) = M.)

Действительно, . Условие означает, что для некоторого целого t. Таким образом,

,

где .

Значит, .

(Можно показать, что для n=pq (произведение простых чисел) соотношение также верно для любого М).

При наличии можно легко найти пару чисел е и d удовлетворяющих соотношению . Для этого выбирается число е взаимно простое с , что проверяется с помощью алгоритма Евклида. Взаимная простота нужна для разрешимости сравнения относительно неизвестного х. Число d находится с помощью расширенного алгоритма Евклида, определяющего числа d и t, удовлетворяющих соотношению ed+t fi(n)= 1, которое и означает, что . Сложность алгоритма Евклида не превосходит 0(log n)^3 операций.

Все сказанное справедливо для произвольного модуля n. Но системе RSA модуль n есть произведение двух больших простых чисел р и q, . Поэтому=(p-1)(q-1) (В общем случае … для ).

При любое простое число будет взаимно просто с , и при выработке ключа е можно просто воспользоваться быстрыми тестами проверки чисел на простоту [64] и не применять алгоритм Евклида.

Без знания простых сомножителей р и q значение функции определить очень трудно и, если сделать открытыми числа е и n, а число d держать в секрете, то нахождение числа M из C сводится к трудной задаче извлечения корня степени е из числа C по модулю m. Это и означает, что предложенная система может быть использована как система открытого шифрования, когда преобразование зашифрования открыто, а преобразование расшифрования держится в секрете. В этом случае открытым ключом является пара (е,n), а закрытым - (d,n).

Напомним, что по теореме Эйлера числа M и n =pq должны быть взаимно простыми. Именно в этом предположении была показана справедливость преобразований зашифрования - расшифрования. Но оказывается, что вероятность этого близка к единице при больших значениях р и q. Действительно, число чисел M, не взаимно простых с n, равно , а их доля в интервале [0,1] близка к нулю в силу соотношения

при больших значениях р и q.

Для полноты картины можно отметить, что есть небольшая вероятность того, что шифрование числа M возведением в степень е по модулю n не изменяет открытый текст M. Так, в [16] показано, что для каждого значения е существует, по крайней мере, девять значений M таких, что . Так как е взаимно просто c , то е является нечетным числом, и поэтому два сравнения и имеют три решения. x=0, 1, -1. Комбинируя их в условиях китайской теоремы об остатках, получаем искомые 9 сообщений M.

Например, для n=4759=2773 это: 0, 1, 2772, 2537, 2303, 235, 2538, 471, 236.

В криптосистеме RSA вместо функции Эйлера можно рассмотреть функцию Кармайкла (Carmichael) - , определяемую для произвольного целого числа следующим образом:

Значение функции Эйлера совпадает с порядком мультипликативной группы целых чисел по модулю n, а значение функции Кармайкла совпадает с экспонентой этой группы.

В теореме Кармайкла, обобщающей теорему Эйлера, утверждается, что для любого целого числа M, взаимно простого с числом n, верно сравнение .

Далее в приведенных рассуждениях можно заменить на . При n = pq имеем = Н.О.К. [p-1, q-1] = /нод (p-1, q-1), где в знаменателе стоит наибольший общий делитель чисел (p-1) и (q-1), который больше 2 в силу четности p-1 и q-1.

Описанная блочная криптосистема может использоваться и как обычная криптосистема с секретным ключом. Так, в [10] было предложено в качестве n выбирать большое простое число р. Оно может быть и несекретным (в соответствии с правилом Керкхоффcа), так как возможно его нахождение по размерам блоков шифртекста. В этом случае числа e и d являются секретными ключами . Это так называемая криптосистема Полига-Хеллмана (Pohllg-Hellman).

Стойкость этой криптосистемы зависит от сложности вычисления дискретных логарифмов в конечном поле GF(р), так как при атаке с известным открытым текстом криптоаналитик решает задачу нахождения числа , где C и M - шифрованный и открытый тексты соответственно.

При реализации системы RSA применяется китайская теорема об остатках, позволяющая сводить вычисление по большому модулю n=pq к вычислениям по меньшим модулям р и q. Покажем это на примере расшифрования, когда вычисляется . Введем обозначения , . Разделив d на (p-1) и (q-i) с остатком получим d = k(p-l)+ r =J(q-l)+s или r = d mod (р-1), s = d mod(q-1). По теореме Эйлера находим

Для восстановления M из вычисленных таким образом чисел а и b найдем и, 0<u<p, из условия . Тогда, как показано в [28], м находится одним из двух способов.

Легко видеть, что сложность операции расшифрования составляет ^3 операций.

Стойкость системы RSA можно оценить сверху сложностью разложения большого числа n на множители р и q с последующим определением и d. Именно потребности криптографии дали толчок в развитии методов факторизации целых чисел. Обзор по этим методам можно найти в [82]. Именно они влияют существенным образом на выбор ключевых параметров р и q.

В работе [46] можно найти доказательство того факта, что если для системы RSA удалось найти такое число , что для всех M взаимно простых с модулем n, тогда это дает возможность разложить число n на множители. Изложенный там алгоритм является примером так называемого вероятностного алгоритма (probabilistic algorithm), которые используются в криптографии.

То, что определить открытый текст в системе RSA можно без разложения числа n на множители, показывает следующий метод итерации преобразования зашифрования, предложенный в [30]. В этом методе криптоаналитик пытается найти целое число j, такое, что

, где - шифртекст, полученный из M на ключе (n,e).

Если такое число j найдено, то M получается следующим образом

,

так как справедливо соотношение .

В [30] приводится пример для p = 983, q = 563, е = 49, М = 123456.

Тогда , , , (число j делит порядок числа е по модулю ). В примере j = 10.

В работе [30] приведенная идея бесключевого чтения была обобщена, и криптоаналитик старается найти многочлен р(е) вида р(е) = еф(е), такой, что . Тогда открытый текст M находится вычислением

.

Некоторые последние результаты по труднорешаемым задачам

Задача факторизации

Решето числового поля(NFS), May 2005 RSA200 (665 бит).

Метод эллиптических кривых (ECM), April 2005 (220 битовый делитель).

Формула года Y, когда будет факторизовано целое число из D десятичных знаков приведено в трудах CRYPTO`00 и имеет вид

Y = 1928,6 + 13,24 D.

Например,

D=231(768 бит) , Y = 2010;

D=309(1024 бит), Y = 2018.

При Y=2006 получается D=200 (665 бит).

1988. Поллард нашел новый подход для факторизации целых чисел. H. Lenstra развил его для чисел специального вида. Далее рядом авторов он был распространен на произвольные числа со сложностью L[1/3, c], где с=(64/9) = 1,9229… .

L[t,c] = exp((c+0(1))((logN))(loglogN)).

Далее Копперсмит улучшил оценку для с=1,9018… .(См. Modifications to the Number Field Sieve, J.Cryptology 6(1993),169-180)

Задача RSA

Дано: модуль N=pq, открытая экспонента e, шифрованный текст C=M(mod N).

Найти: открытый текст M.

Гибкая (flexible)задача RSA. Сильная задача RSA (пер. книги В.Мао)

Дано: модуль N=pq, шифрованный текст C=M(mod N), полученный при некоторой неизвестной открытой экспоненте e.

Найти: пару e` и M`, удовлетворяющую соотношению (M`)(mod N) = C.

Задача RSA с малой открытой экспонентой (low-exponent RSA problem)

On the Equivalence of RSA and Factoring Regarding Generic Ring Algorithms(Об эквивалентности задачи RSA и факторизации в классе общих кольцевых алгоритмов)

Gregor Leander, Andy Rupp

Статья посвящена известной достаточно старой проблеме вычислительной эквивалентности задачи вскрытия схемы RSA (задача RSA) и задачи факторизации (разложения) больших целых чисел (модуля схемы RSA).

Показано, что любой эффективный общий (generic) алгоритм, учитывающий структуру кольца Z, который решает гибкую (flexible) задачу RSA с малой открытой экспонентой может быть преобразован в эффективный алгоритм факторизации модуля N=pq.

Таким образом, задача RSA c малой экспонентой e трудно решаема в классе указанных алгоритмов, при условии, что такой является задача факторизации.

New Attacks on RSA with Small Secret CRT-Exponents

(Новые атаки на схему RSA с малыми секретными CRT-экспонентами)

Daniel Bleichenbacher, Alexander May

Известно, что существует эффективный метод для расшифрования/подписи по схеме RSA, если секретная экспонента d является малой величиной по модулю

(p-1) и (q-1). Такие d называются малыми CRT-экспонентами.

Неизвестно полиномиальных атак на малые CRT-экспоненты, то есть результатов аналогичных атаке Wiener или Boneh-Durfee. На CRYPTO 2002 дано частичное решение задачи, когда простые делители p и q не сбалансированы (A.May), именно при q< N, где N=pq - модуль схемы.

В данной работе улучшена эта оценка для q< N. Это близко к сбалансированной схеме RSA.

Также в работе представлен второй результат при сбалансированных делителях p и q, но в случае, когда экспонента e значительно меньше модуля N. Более точно, установлено существование полиномиальной атаки в случае, когда

d, d < min {(N/e), N}.

Для доказательства используется метод Копперсмита (Coppersmith) нахождения малых корней сравнений.

Метод атаки может быть применен к двум быстрым вариантам схемы RSA, недавно предложенных Galbraith, Heneghan, McKee (ACISP`2005) и Sun, Wu (ePrint Archiv 2005/053).

A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants (Стратегия нахождения корней многочленов от многих переменных и ее новые применения в атаках на варианты схемы RSA)Ellen Jochemsz, Alexander May

В работе описывается стратегия нахождения малых корней многочленов от многих переменных с использованием метода Копперсмита ( Eurocrypt`1996), основанного на алгебраических решетках.

Предложены новые полиномиальные атаки на 2 варианта схемы RSA.

2.7 Цифровая подпись

Одним из основных применений криптосистем с открытым ключом является их использование при создании так называемой цифровой подписи (digital signature). Впервые идея цифровой подписи была высказана все в той же известной работе Диффи и Хеллмана [4].

Для ее изложения потребуем, чтобы преобразования зашифрования и расшифрования из определения криптосистемы с открытым ключом действовали также соответственно на пространствах шифрованных и открытых текстов.

,

и к тому же преобразование было бы обратным преобразованием к , то есть выполнялось бы соотношение

для любого открытого текста .

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

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

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

M' =(C')

В силу же односторонней природы преобразования сделать это вычислительно невозможно.

В действительности, для сокращения времени подписывания и размера подписи (а также и для других целей) в процессе подписи используется общеизвестная функция H, действующая на пространстве открытых текстов и отображающая любое сообщение M в сообщения h(m) фиксированного малого размера, которое далее и преобразуется в подпись . Пользователь B, получив сообщение M и подпись к нему , может также вычислить H(M) и проверить выполнимость соотношения

Функция H называется функцией хэширования (hash function). Более подробно она будет рассмотрена отдельно.

Теперь будет понятно следующее определение [54] схемы (системы) цифровой подписи, которая включает следующие компоненты.

1. Пространство открытых сообщений , к которым применяется алгоритм цифровой подписи.

2. Пространство секретных параметров , которые выбираются пользователем.

3. Алгоритм G генерации за полиномиальное время пары - открытого и секретного ключей по выбранному параметру k. (Здесь, как и в ряде учебников, отождествляются открытое и секретные преобразования и с открытым и секретным ключами.)

4. Алгоритм подписи Q, который вырабатывает значение

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

5. Алгоритм проверки подписи, который проверяет правильность подписи к сообщению M с использованием открытого ключа .

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

По возможности доступа к информации о схеме выделяют три класса методов атаки.

1. Методы атаки только по открытому ключу (key-only attack). В этом случае предполагается, что злоумышленник знает только открытый ключ схемы подписи и имеет возможность проверки правильности подписей сообщений, которые у него окажутся.

2. Методы атаки по открытому ключу и сообщениям (message attacks). В этом случае злоумышленник знает открытый ключ подписывающего и может наблюдать случайные пары (сообщение/подпись).

3. Методы атаки по выбранным сообщениям (chosen-message attack. В этом случае злоумышленник может получить подписи к сообщениям выбранным им лично (как в случае с нотариусом). Выбор этих сообщений может зависеть от ранее полученных подписей.

Различают несколько уровней по степени раскрытия схемы подписей.

1. Эпизодическое подделывание (Existential forgery). Злоумышленник подделывает подпись одного сообщения, не обязательно им выбранного. Сообщение это может быть или случайным, или не имеющим смысла.

2. Выборочное подделывание (Selective forgery). Злоумышленник подделывает подпись некоторого сообщения, по своему выбору.

3. Универсальное подделывание (Universal forgery). Злоумышленник может подделывать подписи к любому сообщению, но без знания секретного ключа подписи. Он может найти функционально эквивалентный алгоритм подписи.

4. Полное раскрытие схемы подписи (Total break).

Злоумышленник может вычислить секретный ключ подписывающего.

2.8 Схема цифровой подписи Эль Гамаля

В 1985 г. Эль Гамаль (El Gamal) предложил схему цифровой подписи, основанную на сложности решения задачи дискретного логарифмирования [115]. В той же работе содержится и описание криптосистемы открытого шифрования.

...