В рамках проекта Phuctor (The RSA Super Collider) развивается публичный сервис, позволяющий оценить надёжность используемых RSA-ключей и получить сведения о проблемных ключах, используемых в подписях PGP/GPG. Phuctor позволяет определить потенциальную возможность компрометации закрытого ключа на основании анализа открытого ключа.

Phuctor использует усовершенствованный алгоритм факторизации ключей, предложенный Дэниелем Бернштейном (Daniel J. Bernstein), позволяющий выявить проблемы с генерацией простых чисел, используемых при создании ключей. Система проверяет применение для начальных коэффициентов составных чисел и выявляет использование в разных ключах одинаковых цикличных коэффициентов (модуль), что может указывать на возможное наличие дубликатов закрытого ключа.

Как правило, проблемы с ключами возникают при использовании ненадёжных генераторов случайных чисел в момент создания ключа, выдающих предсказуемые повторяемые последовательности. В настоящее время в БД проекта уже занесена информация о 1.8 млн модулей. В 858 случаях выявлены дубликаты. Для 222 ключей удалось факторизировать начальные параметры генерации ключа.

Интересно, что среди владельцев скомпрометированных ключей встречаются достаточно известные деятели, например, в списке обладателей проблемных ключей присутствуют сотрудники NASA, Red Hat, Apple (product-security@apple.com!), Фонда СПО, IEEE, Intel, Debian (цифровая подпись для репозитория debian.sur5r.net) Отдельно выделяются проблемы с ключами PGP Corporation, используемыми в сервисе обновления ключей (update-key@pgp.com) и сервисе каталогов ("PGP Global Directory Verification Key").

Напомним, что в основе шифрования RSA лежит операция возведения в степень по модулю большого числа. В открытом ключе содержится модуль и степень. Модуль формируется на основании двух случайных простых чисел, которые известны только владельцу закрытого ключа. Таким образом наличие открытого ключа и знание одного из начальных простых чисел позволяет полностью восстановить закрытый ключ. В случае если в разных открытых ключах используется один и тот же модуль, то это свидетельствует либо о недостаточном размере энтропии при генерации случайных чисел, либо о наличии бэкдора в определённой реализации GPG. Использование составного начального числа указывает на возможность создания нескольких закрытых ключей для одного открытого ключа.

Источник: http://www.opennet.ru/opennews/art.shtml?num=44356