Стойкость RSA и систем с открытым ключом — HackZona.Ru
Стойкость RSA и систем с открытым ключом
Стойкость RSA и систем с открытым ключом
Тип статьи:
Со старой ХакЗоны.
Источник:
Я не являюсь специалистом в области теории чисел. Поэтому я излагаю свои мысли в виде гипотезы, а не строгого доказательства. Я ведь тоже могу ошибаться. Для начала рассмотрим систему шифрования с открытым ключем. Предполагается, что если злоумышленнику о системе с открытым ключем известно все, кроме исходного сообщения 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 (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
Учитывая приведенное выше описание свойств системы с открытым ключем, следует заметить, что модуль m при использовании алгоритма RSA в системе шифрования с открытым ключем является составной частью функций E, D, G. Именно поэтому, рассмотривать m в контексте системы шифрования с открытым ключем, основанной на алгоритме RSA, как нечто самостоятельное не имеет смысла. Это мы как раз сейчас и увидели.
Для вычисления функции f: x -> xe (mod m) достаточно знать лишь числа e и m. Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число d, оно и является «секретом», о котором идет речь. Казалось бы, ничего не стоит, зная число m, разложить его на простые сомножители, вычислить затем с помощью известных правил ф(m) и, наконец, с помощью de = 1 (mod ф(m)), (0
Давайте заметим в этом фрагменте текста еще одну странную особенность: ф(m) является модулем для операций в сравнении de є 1 (mod ф(m)), (0
Попробуйте пересечь наполненный водой бассейн с привязанными к ногам пудовыми гирями. Думаю, что не смотря на то, что это было продемонстрировано в разделе «слабо» телевизионной передачи «сам себе режиссер», вероятность утонуть все-таки выше. Математики тоже иногда привязывают себе «гири» в виде ограничений. Вероятность совершить ошибку в рассуждениях становится значительно выше. Но, вместе с тем, правильные рассуждения становятся более весомыми. Кстати, по поводу ограничений надо бы заметить, что алгоритм RSA основан на операциях по модулю m, т.е. в качестве окончательного результата берется остаток от деления на m результата операции с числами натурального ряда. Интересно, а откуда у деления растут уши, если от его использования изначально отказались?
Вспомним, что только практика является критерием истины и попробуем выполнить вычитание по модулю. Ура! Получилось! И самое интересное, что вычитание имеет единственный результат. Вот с делением не все так очевидно. Хотя и для деления можно показать, что результат деления так же существует и имеет единственное значение. Это следует хотя бы из того, что деление определено, как операция, обратная умножению. А при умножении сомножители и результат определены.
Что нас ожидает
Если моя гипотеза верна, то нам всем придется навсегда забыть о цифровой подписи. По крайней мере до тех пор, пока не будет придумана какая-то новая схема, аналогичная системам с открытым ключем, принципиально отличающаяся от рассмотренной. Иначе в скором времени может наступить крах мировой банковской системы. Или другие катаклизмы. Это не Y2K. Это гораздо круче.
Не все так плохо
Сам по себе алгоритм RSA на самом деле обладает хорошей стойкостью. Но при одном условии, что публиковать можно только один ключ из тройки: e, d или m. Лучше m. А еще лучше — не публиковать вообще.
P.S. В качестве примера использованы фрагменты текста из книги «Введение в криптографию» (Под об.ред.В.В.Ященко — М.: МЦНМО, «ЧеРо», 1998).
Для начала формализуем постановку задачи шифрования с открытым ключем. Пусть имеем 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 (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
Учитывая приведенное выше описание свойств системы с открытым ключем, следует заметить, что модуль m при использовании алгоритма RSA в системе шифрования с открытым ключем является составной частью функций E, D, G. Именно поэтому, рассмотривать m в контексте системы шифрования с открытым ключем, основанной на алгоритме RSA, как нечто самостоятельное не имеет смысла. Это мы как раз сейчас и увидели.
Для вычисления функции f: x -> xe (mod m) достаточно знать лишь числа e и m. Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число d, оно и является «секретом», о котором идет речь. Казалось бы, ничего не стоит, зная число m, разложить его на простые сомножители, вычислить затем с помощью известных правил ф(m) и, наконец, с помощью de = 1 (mod ф(m)), (0
Давайте заметим в этом фрагменте текста еще одну странную особенность: ф(m) является модулем для операций в сравнении de є 1 (mod ф(m)), (0
Попробуйте пересечь наполненный водой бассейн с привязанными к ногам пудовыми гирями. Думаю, что не смотря на то, что это было продемонстрировано в разделе «слабо» телевизионной передачи «сам себе режиссер», вероятность утонуть все-таки выше. Математики тоже иногда привязывают себе «гири» в виде ограничений. Вероятность совершить ошибку в рассуждениях становится значительно выше. Но, вместе с тем, правильные рассуждения становятся более весомыми. Кстати, по поводу ограничений надо бы заметить, что алгоритм RSA основан на операциях по модулю m, т.е. в качестве окончательного результата берется остаток от деления на m результата операции с числами натурального ряда. Интересно, а откуда у деления растут уши, если от его использования изначально отказались?
Вспомним, что только практика является критерием истины и попробуем выполнить вычитание по модулю. Ура! Получилось! И самое интересное, что вычитание имеет единственный результат. Вот с делением не все так очевидно. Хотя и для деления можно показать, что результат деления так же существует и имеет единственное значение. Это следует хотя бы из того, что деление определено, как операция, обратная умножению. А при умножении сомножители и результат определены.
Что нас ожидает
Если моя гипотеза верна, то нам всем придется навсегда забыть о цифровой подписи. По крайней мере до тех пор, пока не будет придумана какая-то новая схема, аналогичная системам с открытым ключем, принципиально отличающаяся от рассмотренной. Иначе в скором времени может наступить крах мировой банковской системы. Или другие катаклизмы. Это не Y2K. Это гораздо круче.
Не все так плохо
Сам по себе алгоритм RSA на самом деле обладает хорошей стойкостью. Но при одном условии, что публиковать можно только один ключ из тройки: e, d или m. Лучше m. А еще лучше — не публиковать вообще.
P.S. В качестве примера использованы фрагменты текста из книги «Введение в криптографию» (Под об.ред.В.В.Ященко — М.: МЦНМО, «ЧеРо», 1998).
1 комментарий
Я тоже, к сожалению, пока не являюсь специалистом в теории чисел, но я и не собираюсь говорить чего-то сверхумного...
ЗАМЕЧАНИЕ:
Для того, чтобы дешифровать текст нужно знать d так? Но само решение уравнения (4) не является сложным! Уравнение это, кстати имеет немного другой вид и знание n недостаточно. Нужно знать его разложение на простые множители n=gh, именно эта задача и является NP-полной. Так вот отправителю необязательно разлагать n. Его и можно найти, перемножая g и h, причем эта задача посильная. Обратная(разложение) - нет. Так что все в порядке, господа, не волнуйтесь...
Хотя прочитать сообщение можно, но это уже совсем другая история. При соблюдении некоторых правил поведения RSA на данный момент достаточно надежная криптосистема.