Крупные события в мире криптографии случаются сравнительно редко. При этом чаще всего они представляют собой банальные баги в программах или проблемы производителей. Гораздо реже мы слышим о взломе очередного ключа объединёнными усилиями тысяч энтузиастов. И уж совсем редко доводится узнать о фундаментальных достижениях математиков, сумевших совершить очередной рывок в разработке алгоритмов для взлома. Именно к последней категории следует отнести письмо, появившееся три дня назад в известной конференции Bugtraq на не менее известном в компьютерном мире сайте SecurityFocus. Автор письма сообщает об отзыве своих публичных PGP-ключей длиной 1024 бит. Причина - очевидная опасность их взлома с использованием вычислительной машины, построенной по архитектуре, предложенной недавно математиком Дэном Бернштейном (D.J.Bernstein). Насколько реальна опасность?

Собственно, свою работу, посвящённую целочисленной факторизации, Бернштейн опубликовал ещё осенью. В частности, она описывает узлы машины специализированной параллельной архитектуры, предназначенной для факторизации чисел длиною примерно в три раза больших при неизменных материальных затратах по сравнению с нынешними параллельными суперкомпьютерами. Чтобы разобраться в хитросплетениях математических формул, с помощью которых Бернштейн описывает свою архитектуру, требуется быть математиком, либо, как минимум, специалистом в криптографии. За неимением соответствующих навыков и наличием необходимости оценить происходящее, я предлагаю пойти иным путём: обратить внимание на две различных точки зрения, одна из которых принадлежит Брюсу Шнайеру, а вторая представлена в уже упомянутом письме в Bugtraq, составленном на основе мнений участников конференции Financial Cryptography.

Говоря упрощённо, асимметричная криптография (протоколы открытых ключей - RSA, DSS/DH) строится на нахождении двух больших простых чисел с последующей передачей только их произведения. Соответственно, лобовая атака на системы, использующие этот механизм, основана на разложении произведения на простые множители. На сегодняшний день есть лишь четыре реальных способа ускорить этот процесс - повышая скорость работы процессора, уменьшая его стоимость, оптимизируя алгоритмы и, наконец, создавая принципиально новые математические теории. Работа Бернштейна относится Шнайером к третьей категории - что означает, что даже в случае её полной эффективности, конечному пользователю достаточно увеличить длину ключа вдвое, гарантированно защитив свои данные от успешной атаки. Но изюминка в том (и это понимает сам Бернштейн), что эффективность использования новой архитектуры доказана лишь для чисел лишь очень большой длины - оценить, насколько полезной она окажется для атаки на практически используемые ключи (длиною до 4096 бит) очень сложно. Для Шнайера это повод заявить о том, что беспокоиться в ближайшие годы не о чем. Иначе говоря, даже пользователи 1024-битных ключей пока могут продолжать работать с ними.

Оценки, приведённые в письме в Bugtraq, более тревожны. Несмотря на высокую сложность, построить практически полезную машину по архитектуре Бернштейна уже реально, затратив на это сумму в пределах милиарда долларов. В случае же, если заинтересованное в постройке лицо владеет ещё и своими производственными мощностями, и может спроектировать и изготовить в нужных количествах специализированные схемы, цена значительно уменьшиться. Как минимум несколько организаций в мире (пример: АНБ в США) обладают таким потенциалом. Результат - теоретическая возможность (помните: эффективность архитектуры Бернштейна для сравнительно малых ключей пока не доказана) взлома 1024-битных ключей в секунды и минуты. Вывод пусть каждый сделает сам для себя.