Читаем 1c2b9509b53cb0837976a7dc6c8bcd37 полностью

единицу. Перемножим эти три числа между собой и получим результат — 105.

А теперь представим, что у нас имеется только конечный результат 105 и нам

необходимо разложить его обратно на простые множители, то есть получить

исходные числа 3, 5 и 7. При решении задачи даже для такого небольшого

трехразрядного числа человек столкнется с трудностями. А задача о

факторизации чисел, имеющих разрядность в десятки позиций, и для

современного компьютера может стать весьма нетривиальной. Безусловно, существуют алгоритмы, которые позволяют осуществлять факторизацию

несколько эффективнее, чем простым перебором делителей, но однозначно

оптимального алгоритма, позволяющего быстро решить эту задачу для

больших чисел, пока не изобрели.

Проблема факторизации чисел занимала умы ученых еще сотни лет назад.

Одним из первых, кто занялся этой задачей, стал французский математик Пьер

де Ферма. Еще в 1643 году он предложил свой метод факторизации, который

используется для криптоанализа шифров RSA и в наши дни. Понятно, что для

любого алгоритма шифрования всегда найдутся люди, которые будут искать

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

то в научных — чтобы исследовать криптостойкость алгоритма и защитить

проекты, базирующиеся на данном решении. Еще в середине 2000-х гг. стали

появляться сообщения о том, что группа ученых того или иного университета

взломала сначала 512-битный, а затем и 1024-битный ключ RSA. При этом они

не задействовали какую-то исключительную вычислительную мощность, а для

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

не справится, поэтому для решения подобных задач компьютеры обычно

объединяют в специальные вычислительные кластеры.

За последние десять лет вычислительная мощность компьютеров заметно

выросла. Согласно закону Мура, производительность компьютерных

процессоров удваивается каждые 18 месяцев, поэтому для поддержания

криптостойкости алгоритма RSA в различных технологических решениях

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

бесконечности этот процесс продолжаться не может, от данного алгоритма

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

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

разрядностью — в пределах 256–1024 бит. Одним из таких стал алгоритм

формирования цифровой подписи DSA, построенный на модели дискретного

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

модульная арифметика, которая представляет собой задачу поиска степени, в

которую необходимо возвести заданное число, чтобы, разделив результат по

модулю на другое заданное число, получить желаемый остаток от деления.

Чтобы стало понятнее, рассмотрим следующий пример: Деление по модулю — это обычное деление целых чисел друг на друга с

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

классах школы, непосредственно перед изучением дробей. После чего про

деление с остатком благополучно забывают и не вспоминают до

университетского курса высшей математики. Где неожиданно выясняется, что

деление с остатком на самом деле играет довольно важную роль в теории

чисел и алгебре. В нашем примере мы должны определить, в какую степень

нам надо возвести тройку, чтобы потом, разделив полученный результат по

модулю на 17, получить число 13 в качестве остатка от деления. Правильный

ответ: x = 4. То есть 34 = 81, 81/17 = 4 + остаток 13 (проверка: 4 x 17 = 68 + 13 =

81). Довольно просто, не правда ли? Возводя тройку в различные степени x от

единицы и более, а затем деля по модулю полученный результат на 17, мы

будем каждый раз получать различные остатки от деления. Однако у них будет

одно общее свойство — все эти остатки будут находиться в диапазоне от 1 до

16 включительно, но выстраиваться отнюдь не по порядку (по мере

последовательного возрастания степени x). Множество этих чисел называется

кольцом вычетов. Кольцом, потому что остатки будут постоянно повторяться

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

теперь представим, что мы оперируем не одно-двухразрядными, а очень

большими числами. В этих случаях, если степень заданного числа нам заранее

неизвестна, то задача ее нахождения для конкретных величин остатков

становится очень и очень сложной. Именно эта сложность и лежит в основе

алгоритма DSA.

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

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

просто, а в обратную — исключительно сложно. И алгоритм DSA — не

исключение. Если мы будем решать задачу для больших чисел путем простого

перебора различных значений, то данный метод будет работать очень

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

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