|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[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 = т/г. Тогда |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||