9. Сетевые ИТ
1. Разложение больших чисел на простые множители (алгоритм RSA, авторы – Райвест, Шамир и Адлеман – Rivest, Shamir, Adleman).
2. Вычисление логарифма или возведение в степень (алгоритм DH, авторы – Диффи и Хелман).
3. Вычисление корней алгебраических уравнений.
Рассмотрим простейший пример необратимых функций. Легко в уме найти произведение двух простых чисел 11 и 13. Но попробуйте быстро в уме найти два простых числа, произведение которых равно 437. Такие же трудности возникают и при использовании вычислительной техники для отыскания двух простых сомножителей для очень большого числа: найти сомножители можно, но потребуется много времени.
Таким образом, в системе кодирования, основанной на разложении на множители, используются два разных ключа: один для шифрования сообщения, а второй – отличный от первого, но связанный с ним – для дешифрования. Ключ шифрования основан на произведении двух огромных простых чисел, а ключ дешифрования – на самих простых числах.
Термин «необратимые» функции неудачен. Правильнее было бы их назвать быстро (или просто) необратимые функции. Однако этот термин устоявшийся, и с неточностью приходится мириться.
В 40-х годах XX в. американский инженер и математик Клод Шеннон предложил разрабатывать шифр таким образом, чтобы его раскрытие было эквивалентно решению сложной математической задачи. Сложность задачи должна быть такой, чтобы объем необходимых вычислений превосходил бы возможности современных ЭВМ.
В асимметричных системах приходится применять длинные ключи (1024 бита и больше). К сожалению, длинный ключ резко увеличивает время шифрования открытого сообщения. Кроме того, генерация ключей становится весьма длительной. Зато пересылать ключи можно по незащищенным (незасекреченным, открытым) каналам связи. Это особенно удобно, например, для коммерческих партнеров, разделенных большими расстояниями.
В симметричных алгоритмах используют более короткие ключи, поэтому шифрование и дешифрование происходят быстрее. Но в таких системах распределение (рассылка) ключей является сложной процедурой из-за необходимости держать в тайне информацию о секретном ключе.