Александр Цихилов - Блокчейн. Принципы и основы

к более сложным. Алгоритм Диффи–Хеллмана, появившийся первым среди

методов асимметричной криптографии, не решал задачу аутентификации

сторон, которые совместно генерировали секретный ключ. Однако уже в 1977

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

шифрования, но и был пригоден для создания аутентификации субъекта

системы посредством цифровой электронной подписи. Данный алгоритм

базировался на задаче так называемой «факторизации» больших целых чисел

и получил название в виде аббревиатуры RSA — по фамилиям ученых, его

создавших — Рональда Ривеста, Ади Шамира и Леонарда Адлемана.

Факторизацией называется процесс разложения натурального числа на

произведение простых множителей. В алгоритме RSA секретный ключ

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

произведение этих двух чисел. Использование этого метода в криптографии

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

нескольких чисел является достаточно легкой, в том числе и для весьма

больших значений. В то же время обратное разложение полученного числа на

исходные множители является задачей исключительной вычислительной

сложности.

Поясним на примере. Допустим, у нас есть три простых числа — 3, 5 и 7.

Простые числа — это те, которые без остатка делятся лишь на себя самих и на

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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