Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[0]

Алгоритмические проблемы теории чисел

Ю. В. Нестеренко

Эта статья посвящена алгоритмам теории чисел. Вопрос «как сосчитать?» всегда сопутствовал теоретико-числовым исследованиям. Труды Евклида и Диофанта. Ферма и Эйлера. Гаусса. Чебышева и Эрмита содержат остроумные и весьма эффективные алгоритмы решения диофанто-вых уравнений, выяснения разрешимости сравнений, построения больших по тем временам простых чисел, нахождения наилучших приближений и т.д. Без преувеличения можно сказать, что вся теория чисел пронизана алгоритмами. В последние два десятилетия, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ. исследования по алгоритмическим вопросам теории чисел переживают период бурного и весьма плодотворного развития. Мы кратко затронем здесь лишь те алгоритмические аспекты теории чисел, которые связаны с криптографическими применениями. За рамками статьи останутся проблемы нахождения решений диофантовых уравнений, вычислений в полях алгебраических чисел, вычислений с решётками, нахождения диофантовых приближений и ряд других вопросов.

Вычислительные машины и электронные средства связи проникли практически во все сферы человеческой деятельности. Немыслима без них и современная криптография. Шифрование и дешифрование текстов можно представлять себе как процессы переработки целых чисел при по-моши ЭВМ. а способы, которыми выполняются эти операции, как некоторые функции, определённые на множестве целых чисел. Всё это делает естественным появление в криптографии методов теории чисел. Кроме того, стойкость ряда современных криптосистем обосновывается только сложностью некоторых теоретико-числовых задач (см. [24]).

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

Математическое просвещение, сер. 3, вып. 2, 1998(87-114)


элементами кольца вычетов Z /toZ. Шифрующая функция при этом может рассматриваться как взаимнооднозначное отображение колен вычетов

/ : Z/toZ Z/toZ.

а число /(ж) представляет собой сообщение ж в зашифрованном виде.

Простейший шифр такого рода - шифр замены (см. [1]), соответствует отображению / : ж -> ж + k (mod то) при некотором фиксированном целом к. Подобный шифр использовал ешё Юлий Пезарь. Конечно, не каждое отображение / подходит для целей надежного сокрытия информации, см. [1].

В 1978 г.. см. [2]. американцы Р. Ривест. А. Шамир и Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman) предложили пример функции /, обладающей рядом замечательных достоинств. На её основе была построена реально используемая система шифрования, получившая название по первым буквам имен авторов - система RSA. Эта функция такова, что

а)существует достаточно быстрый алгоритм вычисления значений /(ж);

б)существует достаточно быстрый алгоритм вычисления значений обратной функции / 1(ж);

в)функция f(x) обладает некоторым «секретом», знание которого позволяет быстро вычислять значения / 1(ж); в противном же случае вычисление / 1(ж) становится трудно разрешимой в вычислительном отношении задачей, требующей для своего решения столь много времени, что по его прошествии зашифрованная информация перестает представлять интерес для лиц. использующих отображение / в качестве шифра.

Подробнее об отображениях такого сорта и возможностях их использования в криптографии рассказано в [1,9].

Еше до выхода из печати статьи [2] копия доклада в Массачусетском Технологическом институте, посвяшённого системе RSA. была послана известному популяризатору математики М. Гарднеру, который в 1977 г. в журнале Scientific American опубликовал статью [3]. посвяшённую этой системе шифрования. В русском переводе заглавие статьи Гарднера звучит так: Новый вид шифра, на расшифровку которого потребуются миллионы лет. Именно статья [3] сыграла важнейшую роль в распространении информации об RSA. привлекла к криптографии внимание широких кругов неспециалистов и фактически способствовала бурному прогрессу этой области, произошедшему в последовавшие 20 лет.


1. Система шифрования RSA

В дальнейшем мы будем предполагать, что читатель знаком с элементарными фактами теории чисел. Тех же. кто хотел бы ознакомиться с ними или напомнить себе эти факты, мы отсылаем к книге [4].

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

/ : х -?• хе (mod то).(1)

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

хе = a (mod то).(2)

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

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента то обозначается ср(тп) и равняется количеству целых чисел на отрезке от 1 до то. взаимно простых с то. Так (f(l) = 1 и p(pr) = рг~1(р - 1) для любого простого числа р и натурального г. Кроме того. ср(аЬ) = ср(а)ср(Ь) для любых натуральных взаимно простых а и Ь. Эти свойства позволяют легко вычислить значение <~р{т). если известно разложение числа то на простые сомножители.

Если показатель степени е в сравнении (2) взаимно прост с (т). то сравнение (2) имеет единственное решение. Для того, чтобы найти его. определим целое число d. удовлетворяюшее условиям

de = 1 (mod (р(т)), 1 d < (р(т).(3)

Такое число существует, поскольку (е.ср(т)) = 1, и притом единственно. Здесь и далее символом (а, Ъ) будет обозначаться наибольший обший делитель чисел а и Ь. Классическая теорема Эйлера, см. [4]. утверждает, что для каждого числа х. взаимно простого с то. выполняется сравнение х<р(т) = (mod то) и. следовательно.

ad = xde = х (mod то).(4)

Таким образом, в предположении (а. то) = 1, единственное решение сравнения (2) может быть найдено в виде

х = ad (mod то).(5)

Если дополнительно предположить, что число то состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения (а, то) = 1. Действительно, обозначим г = (а, то) и s = т/г. Тогда



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9]