Решена новая задача факторинга RSA

1 min


Насколько сложно учитывать большие числа? И насколько безопасны методы шифрования, основанные на сложности факторизации больших чисел?

Проблемы факторинга RSA были созданы для решения этих вопросов. В прошлом году RSA-230 был учтен, и На этой неделе RSA-240 был учтен. Это число из 240 цифр (795 бит), произведение двух простых чисел.

Исследователи решили две связанные проблемы одновременно, с учетом RSA-240 и решения дискретный логарифм проблема. Вместе эти проблемы заняли около 4000 лет. Из объявления не ясно, сколько времени потребовалось бы только для того, чтобы учесть только RSA-240.

Если бы вы арендовали используемую вычислительную мощность, я думаю, что стоимость будет где-то в шести цифрах.

Это делает 2048-битные и 3072-битные ключи RSA очень консервативными. Однако самым слабым звеном в шифровании RSA является недостатки реализации, а не способность учитывать большие числа.

Предположим на мгновение, что для взлома шифрования RSA требуются ключи факторинга. (Это может быть неверно в теории или на практике.) Сколько времени потребуется, чтобы получить 2048 или 3072 битный ключ?

Время, необходимое для факторизации числа N с помощью числового поля сита пропорционально

 exp  left ( left ( sqrt (3) { frac {64} {9}} + o (1)  right) ( ln n) ^ { frac {1} {3}} ( ln  ln n) ^ { frac {2} {3}}  right)

Вот о(1) грубо означает термины, которые уходят как N становится больше. (Подробнее об обозначениях Вот.) Для простоты предположим, что мы можем игнорировать эти термины.

Это говорит о том, что факторизация 2048-битного ключа на 12 порядков сложнее, чем факторинга RSA-240, а факторизация 3072-битного ключа на 18 порядков сложнее.

Однако я не думаю, что кто-то считает, что для взлома RSA с помощью 2048-битных ключей потребуется квадриллион ядерных лет. Если бы АНБ поверило в это, они бы не рекомендуя что все переходят на 3072-битные ключи.

Почему такое большое расхождение? Вот несколько причин. Как упомянуто выше, шифрование RSA часто имеет уязвимые недостатки реализации. И даже если все реализовано идеально, нет никаких доказательств того, что взломать RSA-шифрование так же сложно, как факторинг. И могут быть прорывы в алгоритмах факторинга. И масштабный квантовые компьютеры может стать практичным, и в этом случае факторинг станет намного проще.


0 Comments

Ваш e-mail не будет опубликован. Обязательные поля помечены *