Нажмите CTRL-D чтобы добавить нас в закладки
Внимание! Вы находитесь в незащищенном режиме (HTTP). Для перехода в защищенный режим SSL, нажмите здесь
HackZone.RU - Гипотеза о стойкости RSA и систем с открытым ключом Актуальные базы 2GIS в форматах CSV,Excel,SQL
Войти / Регистрация / Участники
Определение даты выпуска iPhone по серийному номеру
-
Поиск по сайту
Форумы



Реклама

Поиск ТОП Добавить публикацию

Гипотеза о стойкости RSA и систем с открытым ключом

16.06.2008

Обращаем внимание, что данная публикация взята из архива.
Возможно, что информация, изложенная здесь, частично устарела

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

Открытый ключ

Для начала рассмотрим систему шифрования с открытым ключем. Предполагается, что если злоумышленнику о системе с открытым ключем известно все, кроме исходного сообщения A и секретного ключа d, то он либо не может вычислить исходное сообщение A, либо это вычисление крайне трудоемко. Этого можно добиться, например, если процесс передачи сообщения будет описываться одним уравнением с двумя неизвестными. Идея систем с открытым ключем шифрования очень простая, красивая и очень заманчивая. Эта простота и настораживает. Вспомните - "простота хуже воровства". Уж слишком все просто. Фантастически просто. Вот фантастикой и займемся.

Для начала формализуем постановку задачи шифрования с открытым ключем. Пусть имеем A - исходное сообщение, a - зашифрованное сообщение, E - функцию шифрования, e - открытый ключ шифрования, D - функцию дешифрования и d - секретный ключ дешифрования. Опишем процесс передачи сообщения:

1. a = E ( A , e )
2. A = D ( a , d )

Подставив в (2) значение a из (1) мы получаем следующее выражение, описывающее процесс передачи сообщения в системе с открытым ключем:

3. A = D ( E ( A , e ), d )

С помошью системы с открытым ключем передача сообщений возможна тогда и только тогда, когда выбранные функции E и D такие, что для некоторых значений e и d независимо от исходного сообщения A выражение (3) обращается в тождество. Введем функцию G (генератор ключей) такую, что при заранее заданном ключе e из уравнения (4) получается ключ d, обращающий (3) в тождество для любого значения A.

4. G ( e , d ) = 0

Разрешив уравнение (4) относительно неизвестного ключа и подставив его значение в (3), получаем тождество. По условию злоумышленнику неизвестны только A и d, поэтому функция G ему также известна.

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

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

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

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

Алгоритм RSA

 

Пусть m и e натуральные числа. Функция f, реализующая схему RSA, устроена следующим образом:

f : x -> xe (mod m)

Для дешифрования сообщения a = f(x) достаточно решить сравнение:

xe = a (mod m)

При некоторых условиях на m и e это сравнение имеет единственное решение x.

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

Давайте заметим одну странную особенность в приведенном фрагменте текста: исследование свойств функции f, реализующей схему RSA, выполняется в области чисел натурального ряда и заданных над ними операций. Если присмотреться повнимательнее, в правой части каждого выражения можно видеть (mod m). В принципе, нет ничего предосудительного в том, что исследование операций по модулю выполняется на множестве чисел натурального ряда. Лишь бы все рассуждения были корректными, без ошибок.

В работах, посвященных исследованию RSA, часто можно встретить примерно такую фразу: Даны два числа X и Y,... Вспомним, что все операции выполняются по модулю m, т.е. каждое из этих чисел - остаток от деления некоторого числа натурального ряда на m. Следовательно, речь идет не о каком-то одном конкретном числе X, а о множестве чисел, которое задается следующим образом: x=A*m+X. Следовательно, если исследование производится в области чисел натурального ряда, эта фраза должна звучать так: Даны два набора чисел i*m+X и j*m+Y,... Иначе рискуем доказать, что 2 * 2 = 5.

Сразу же возникает вопрос: можно ли пользоваться функцией Эйлера? Может оказаться так, что всегда найдутся такие i и j, что числа натурального ряда i*m+X и j*m+Y ( 0 < X,Y < m ) не будут взаимно простыми. Естественно, что речь идет обо всех возможных парах чисел, а только об одной из всех комбинацияй пар чисел из двух наборов. Похоже, что понятие простого числа для операций по модулю теряет смысл и функцию Эйлера в данном случае применять нельзя. Следовательно, все остальные рассуждения, основанные на применении функции Эйлера, могут оказаться неверными. Поэтому, для определенности будем полагать, что ф(m) = m.

Учитывая приведенное выше описание свойств системы с открытым ключем, следует заметить, что модуль m при использовании алгоритма RSA в системе шифрования с открытым ключем является составной частью функций E, D, G. Именно поэтому, рассмотривать m в контексте системы шифрования с открытым ключем, основанной на алгоритме RSA, как нечто самостоятельное не имеет смысла. Это мы как раз сейчас и увидели.  

Для вычисления функции f : x -> xe (mod m) достаточно знать лишь числа e и m. Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число d, оно и является "секретом", о котором идет речь. Казалось бы, ничего не стоит, зная число m, разложить его на простые сомножители, вычислить затем с помощью известных правил ф(m) и, наконец, с помощью de = 1 (mod ф(m)), (0 < d < ф(m)) определить нужное число d. Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа m на простые сомножители и составляет наиболее трудоемкую часть вычислений.

Давайте заметим в этом фрагменте текста еще одну странную особенность: ф(m) является модулем для операций в сравнении de ╨ 1 (mod ф(m)), (0 < d < ф(m)). Заменим ф(m) на m. В результате получим: de = 1 (mod m), (0 < d < m). Операции производятся по модулю, поэтому вместо d и e подставим их эквиваленты из области чисел натурального ряда: (i*m+d)*(j*m+e)=k*m+1. Получилось Диофантово уравнение, которое необходимо разрешить относительно i, j, k, где i, j, k - любые числа натурального ряда. Надеюсь, что это уравнение разрешимо. Косвенно на это указывают некоторые факты. Один из них - это то, что RSA все-таки работает уже лет 15. Второй, - это прямое указание на легкость вычисления d из приведенного сравнения в выделенном фрагменте текста. Третий - это то, что в исследованиях стойкости RSA нигде не рассматривается операция обратная умножению, т.е. аналог деления для чисел натурального ряда.

Попробуйте пересечь наполненный водой бассейн с привязанными к ногам пудовыми гирями. Думаю, что не смотря на то, что это было продемонстрировано в разделе "слабо" телевизионной передачи "сам себе режиссер", вероятность утонуть все-таки выше. Математики тоже иногда привязывают себе "гири" в виде ограничений. Вероятность совершить ошибку в рассуждениях становится значительно выше. Но, вместе с тем, правильные рассуждения становятся более весомыми. Кстати, по поводу ограничений надо бы заметить, что алгоритм RSA основан на операциях по модулю m, т.е. в качестве окончательного результата берется остаток от деления на m результата операции с числами натурального ряда. Интересно, а откуда у деления растут уши, если от его использования изначально отказались?

Вспомним, что только практика является критерием истины и попробуем выполнить вычитание по модулю. Ура! Получилось! И самое интересное, что вычитание имеет единственный результат. Вот с делением не все так очевидно. Хотя и для деления можно показать, что результат деления так же существует и имеет единственное значение. Это следует хотя бы из того, что деление определено, как операция, обратная умножению. А при умножении сомножители и результат определены.

Что нас ожидает

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

Не все так плохо

Сам по себе алгоритм RSA на самом деле обладает хорошей стойкостью. Но при одном условии, что публиковать можно только один ключ из тройки: e, d или m. Лучше m. А еще лучше - не публиковать вообще.


27-30 ноября 1999 года
Urix


P.S. В качестве примера использованы фрагменты текста из книги "Введение в криптографию" (Под об.ред.В.В.Ященко - М.:МЦНМО, "ЧеРо", 1998).

P.P.S. Возможно, что следующее ниже мне следовало сказать в самом начале. Я сознательно не рассматривал, хотя именно так это и реализуется на практике, функцию M(m), генерирующую пару ключей e и d. Стойкость метода в этом случае определяется сложностью решения обратной задачи для этой функции, т.е. сложностью нахождения неизвестного ключа по известному. Введение такой функции хотя и служит хорошей иллюстрацией тому, что стойкость систем шифрования с открытым ключем основывается на сложности решения обратной задачи, но только усложняет и запутывает рассуждения. Доказано, что для алгоритма RSA решение обратной задачи является НП-полной задачей, т.е. задачей, теоретически неразрешимой в известном смысле. Для этого класса задач невозможно теоретически ни подтвердить, ни опровергнуть существование решения. Решение, если таковое имеется, можно найти только практически. Но если решение еще не найдено, то это совсем не означает, что оно не существует. Просто ПОКА оно еще не найдено. Вот этот факт я и отобразил, введя функцию G и уравнение (4). Тем самым я рассмотрел гипотетическую ситуацию, когда решение обратной задачи найдено. И обнаружил для этого случая порок, присущий системам с открытым ключем: несмотря на то, что сами алгоритмы несимметричны, как корреспондент, так и злоумышленник несут совершенно одинаковые (симметричные) затраты. Следовательно, системой шифрования с открытым ключем на основе несимметричного алгоритма шифрования, стойкость которого основывается на теоретической неразрешимости НП-полной задачи (в частности RSA), можно пользоваться только до тех пор, пока не найдено и/или не ОПУБЛИКОВАНО практическое решение обратной задачи для этого алгоритма. Нет никаких гарантий, что кому-то это решение уже не стало известным. Стойкость системы шифрования с открытым ключем определяется, как наименьшее время из времени, затраченного на нахождение практического решения обратной задачи или из времени, необходимого на перебор вариантов. В этом смысле система шифрования с открытым ключем является "условно стойкой". Следовательно, в особо критичных, в особо ответственных случаях пользоваться следует исключительно алгоритмами шифрования, обладающими "безусловной стойкостью", т.е. алгоритмами, стойкость которых определяется только затратами на перебор вариантов, как для алгоритмов DES и ГОСТ. Но эти алгоритмы имеют симметричные ключи, следовательно, в системах с открытым ключем неприменимы. Рано или поздно с алгоритмом RSA может произойти то же, что произошло с алгоритмом "укладки ранца" и с некоторыми другими алгоритмами, стойкость которых как раз и была основана на теоретической неразрешимости НП-полной задачи. Дай Бог, чтобы это решение было НЕМЕДЛЕННО ОПУБЛИКОВАНО. Для некоторых алгоритмов уже НАЙДЕНО РЕШЕНИЕ. Если мои экзерсисы относительно RSA Вам не нравятся, можете их рассматривать, как дурную шутку. Это в принципе ничего не меняет. И последнее, если Вы ВНИМАТЕЛЬНО прочитали весь текст и ПОНЯЛИ ВСЕ, что я сказал или хотел сказать, то Вы сами легко сформулируете ту единственную задачу, от решения которой зависит реальная стойкость RSA и систем шифрования с открытым ключем. Может быть именно Вы найдете ее решение. Успехов.

При копировании материалов ссылка на HackZone.RU обязательна

Добавить страницу в закладки

 Детали
Категория: Архив
Опубликовал: DiMan
Просмотров: 9848
Проголосовало через SMS: 0
Ключевые слова: rsa, (найти похожие документы)
  Разместить у себя на сайте
Прямая ссылка
HTML
BBCode ссылка
BBCode ссылка с текстом

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

Зарегистрироваться *** Авторизоваться


 Последние новости и статьи  Последние сообщения с форумов
  • Самозащита от вируса Petya
  • Google Pixel взломали за 60 секунд
  • В CMS Joomla обнаружена критическая 0-day уязвимость
  • ФБР не смогло взломать протокол шифрования переписки террористов ...
  • Полиция обыскала дом предполагаемого создателя платежной системы ...
  • Google: квантовый ПК будет в 100 млн раз быстрее стандартных чипо...
  • "Лаборатория Касперского" констатирует усиление атак кибергруппир...
  • Microsoft Edge откроет исходные коды ChakraCore
  • Anonymous объявили 11 декабря «днём троллинга» ИГИЛ
  • Миллионы телевизоров, смартфонов и маршрутизаторов оказались уязв...

    Все новости... Все статьи... Прислать новость RSS
  • Взлом и безопасность / Разное » есть кто реально взламывает вотсап? достали разводилы!
  • Взлом и безопасность / Новичкам » Re: Услуги взлома ВКонтакте,Вотсап,Вайбер,Взлом ПОЧТЫ [ГАРАН...
  • Взлом и безопасность / Новичкам » Re: Услуги взлома ВКонтакте,Вотсап,Вайбер,Взлом ПОЧТЫ [ГАРАН...
  • Взлом и безопасность / Новичкам » Re: УСЛУГИ ВЗЛОМА МЕССЕНДЖЕРОВ, СОЦ СЕТЕЙ, ПОЧТЫ, САЙТОВ И Т...
  • Взлом и безопасность / Новичкам » Услуги легального взлома ВКонтакте,Вайбер,Вотсапп!Анонимно!
  • Взлом и безопасность / Новичкам » Re: УСЛУГИ ВЗЛОМА МЕССЕНДЖЕРОВ, СОЦ СЕТЕЙ, ПОЧТЫ, САЙТОВ И Т...
  • Взлом и безопасность / Новичкам » Re: Профессиональные услуги по взлому
  • Взлом и безопасность / Новичкам » Услуги легального взлома ВКонтакте,Вайбер,Вотсапп!Анонимно!
  • Взлом и безопасность / Новичкам » Re: Взлом Whatsapp.Viber.Instagram. facebook.Узнаем взломаем...
  • Сети / Общее » Услуги взлома ,переписка whats app/viber

    Все форумы... RSS


  • Разместить рекламу
    © HackZone Ltd. 2007-2012. Все права зарегистрированы.
    Перепечатка материалов без согласования и указания источника будет преследоваться по Закону

    О проекте | История проекта | Размещение рекламы | Обратная связь | Правила поведения на портале
    Ya-Cyt службы мониторинга серверов

    #{title}

    #{text}

    x

    #{title}

    #{text}