Зашифровать можно. Расшифровать нельзя!
Вычисление f(x) по схеме Диффи – Хеллмана – сравнительно быстрая операция, которую можно осуществить и на домашнем компьютере, даже если р огромное, скажем стозначное число. Тем не менее лучшие математики мира вот уже несколько десятилетий бьются над построением алгоритма, который, наоборот, по остатку от деления на р выдавал бы значение х. И ничего не получается!
Самые быстрые алгоритмы работают месяцы, даже будучи параллельно запущенными на тысячах мощных компьютеров по всему миру. Ниже мы расскажем о совсем недавней наиболее успешной попытке решения. Но, как мы увидим, этот метод тоже не «быстрый», а скорее «в принципе выполнимый» и сильно опирается на конкретную имплементацию шифра.
Конечно, это не значит, что по-настоящему быстрого алгоритма не существует. Но задача оказалась настолько сложной, что схема очень активно используется на практике, и если выбрать число р по-настоящему большим, то можно не бояться взлома шифра.
В нашем маленьком примере у Алисы и Боба после открытого обмена сообщениями появился общий секретный ключ, число 11. С его помощью Алиса и Боб могут спокойно зашифровывать и расшифровывать сообщения и передавать их друг другу. Но Еве этот ключ не заполучить, потому что она не сможет вычислить ни x, ни у.
Красота схемы в том, что Алиса и Боб обмениваются ключами через открытый канал. Ева может перехватить все сообщения до одного, но ей это ничего не даст!
Именно поэтому подобные схемы называются «открытым обменом ключами». Нет никакого секрета в том, как работают эти схемы. При этом несанкционированная расшифровка ваших сообщений – проблема посложнее «Энигмы». Секретность без секретов.
На практике часто используется еще одна схема открытого обмена ключами – алгоритм RSA, названный так по первым буквам имен своих авторов: Ривеста, Шамира, Адлемана (Rivest, Shamir, Adleman). Для интересующегося читателя ниже во врезке мы кратко объясняем основной принцип его работы. Если вы не хотите вдаваться в детали, можете пропустить этот текст.
Алгоритм RSA
Алиса может выбрать не одно число, а сразу пару чисел р, q. Можно считать, что p и q – простые. Возьмем очень простое преобразование
n = p × q.
Это довольно быстрая операция – обычное умножение. Однако если вам дано натуральное число n и даже известно, что n = p × q с некоторыми простыми р и q, которых вы не знаете, то восстановить эти простые числа вам не удастся! Вернее, на это уйдут годы, коль скоро п достаточно велико. Вот такие чудеса! Принцип здесь тот же самый. Для вычисления п используется простое умножение, это очень быстрая операция. А вот обратный процесс, операция разложения на множители, носит в математике красивое имя факторизация (от англ. factor – сомножитель) и представляет собой большую проблему с точки зрения вычислений.
Добавим, что операцию разложения на множители легко выполнить на квантовом компьютере. Но пока у таких компьютеров очень ограниченный регистр, то есть они могут работать только с относительно маленькими числами. Для шифрования на практике используются очень большие числа. Поэтому на данный момент квантовые компьютеры особой угрозы не представляют.
