Max Home IndustryЭто странная история, особенно потому, что она восходит к статье 2012 года. Шифрование RSA важно, потому что это основа криптографической структуры с открытым ключом, которую мы все используем. Так он треснул или нет?
Сейчас это попало в заголовки из-за публикации Уильяма Кузмауля в его блоге Algorithm Soup — настоятельно рекомендуется. В нем подробно объясняются идеи, поэтому здесь я сконцентрируюсь на более общих идеях и выводах.
Давно известно, что даже лучшую систему шифрования легче взломать, если ее пользователи плохо справляются со своей работой. Иногда бывает сложно понять, что представляет собой хорошая работа. Во время Второй мировой войны взлом немецкого кода Enigma был упрощен тем, что сообщения всегда начинались одинаково — предоставляя некоторый известный простой текст для сравнения с зашифрованным текстом. То же самое и с RSA, и в этом случае неожиданной проблемой является то, что слишком много людей и устройств используют одни и те же методы генерации случайных простых чисел.
Шифр RSA использует два больших случайных простых числа p и q, и пользователь делает доступным свой продукт в Интернете pk = p * q для всеобщего обозрения и использования. Значение pk — это открытый ключ, который используется для шифрования отправляемого сообщения. Чтобы расшифровать сообщение, вам нужно знать p и q, а факторизация pk затруднена. На недавнюю попытку разложить ключ из 232 десятичных цифр потребовалось 1500 лет вычислений. Ключи размером 512 бит можно разложить на множители за несколько недель, но мы используем 1024-битные и 4096-битные ключи, и хотя некоторые предполагают, что факторизация 1024-битных ключей возможна, 4096-битные ключи по-прежнему считаются очень безопасными.
Итак, RSA безопасно? Ну, если мы все будем использовать одни и те же простые числа, это не так. Вы можете подумать, что мы вряд ли будем использовать одни и те же числа, но при этом игнорируется способ генерации этих больших простых чисел. Обычно генератор случайных чисел используется для создания значения, которое затем проверяется на простоту, и это можно сделать достаточно быстро. Проблема в том, что генераторы случайных чисел, которые мы используем, как правило, одинаковы, и они не такие случайные, как нам хотелось бы. Чтобы улучшить случайность, вы должны запустить генератор, используя выбранное начальное число, и часто одно и то же начальное число используется повторно. Другими словами, очень многие открытые ключи имеют одно простое число.
Почему это слабость?
Вот где сюрприз ждет любого эксперта, не занимающегося теорией чисел. Если два открытых ключа имеют общее простое число, то это простое число является общим делителем, и, что удивительно, легче найти наибольший общий знаменатель двух чисел, чем разложить число на множители. На поиск общего делителя требуется время, пропорциональное количеству цифр. Когда у вас есть общий делитель, вы можете читать сообщения, отправленные любым из открытых ключей.
Добавьте к этому тот факт, что исследователи Арьен К. Ленстра, Джеймс П. Хьюз, Максим Ожье, Йоппе В. Бос, Торстен Кляйнджунг и Кристоф Вахтер реализовали быстрый алгоритм наибольшего общего делителя, и вы увидите, что плохо реализованный RSA может иметь проблему. Они собрали более 6 миллионов открытых ключей и сумели взломать 12 934 из них. Более того, вычисления производились на одноядерном процессоре за считанные часы. Интересно, что они не включили в статью детали своего быстрого алгоритма. Предположительно, они были обеспокоены тем, что он может быть использован для взлома ключей в злых целях. Однако похоже, что другая группа действительно опубликовала подробности своего быстрого алгоритма, который включал умножение всех ключей вместе, чтобы получить действительно большое число, а затем найти наибольший общий делитель. Это действительно быстрее! Также сообщалось, что большинство ключей, которые можно взломать, поступило из встроенных приложений, таких как маршрутизаторы, брандмауэры и так далее. Очевидно, производители использовали один и тот же генератор случайных чисел.
Итак, какое решение?
Легко — либо убедитесь, что ваш открытый ключ не разделяет простое число с какими-либо связанными ключами, либо, что еще лучше, используйте надежный генератор случайных чисел, в котором много энтропии. Хорошая новость в том, что RSA не взломан, но вы должны делать это правильно.
Интересно то, что кажется, что взломать один открытый ключ сложно, но при некотором совместном использовании простых чисел взломать несколько открытых ключей проще. Есть ли подобные лазейки?