Алгоритм опередил развитие процессоров: взломан самый длинный ключ RSA
Программистам удалось посрамить электронщиков. Без улучшения аппаратной платформы? фактически с опережением того самого пресловутого закона Мура? группе исследователей по безопасности удалось поставить новый рекорд по взлому ключа RSA, который до сих пор удавалось вычислить. Подчеркнем еще раз, рекорд поставлен не на росте голой производительности компьютерного "железа", а благодаря усовершенствованным алгоритмам для разложения большого числа на простые множители и с использованием улучшенной методики вычисления дискретного логарифма.
Многие алгоритмы шифрования с открытым ключом опираются на чрезвычайно большие числа, которые, в свою очередь, получаются путем перемножения двух или более простых чисел. Простые числа в данном случае служат секретными ключами, которые позволяют получить нужный ключ и расшифровать сообщение. Аналогичным образом используется сложность в нахождении дискретного логарифма. Разложение достаточно больших чисел на простые множители и вычисление дискретного логарифма? это задачи, которые не подлежат взлому, а только вычислению. Все большие числа, которые можно разложить на простые в разумное время, являются скомпрометированными и для повышения защиты шифрования их разрядность необходимо увеличивать.
Новый рекорд, поставленный специалистами, позволил разложить на простые числа ключ RSA-240 длиной 240 десятичных разрядов или 795 бит. Эта же самая команда исследователей смогла вычислить дискретный логарифм такой же длины. Предыдущий рекорд разложения на простые множители был поставлен в 2010 году. Тогда удалось взломать ключ RSA с разрядностью 768 бит или с 232 десятичными разрядами. Простой дискретный логарифм для этой разрядности смогли вычислить в 2016 году. Похоже, ключ RSA 1024 бит в опасности и для надежного шифрования данных необходимо переходить на 2048-разрядные ключи.
Важнейшим моментом исследования стал факт ускорения вычислений на той же самой аппаратной платформе, которая использовалась в 2016 году. По идее этого не должно было произойти. Растущая сложность вычисления дискретного логарифма длиной 795 бит должна была потребовать в 2,5 раза больших аппаратных ресурсов, чем для вычисления 768-битного числа. Фактически расчеты оказались в 1,33 раза быстрее, что говорит о 3-кратном превосходстве предсказания. Ускорение расчетов исследователи связали с обновлениями в программном обеспечении с открытым исходным кодом, которое опирается на вычисления с использованием метода решета числового поля (Number Field Sieving). Такой пакет как CADO-NFS содержит 300 тыс. строк кода, написанного на C и C ++.
Сумма времени для обоих новых рекордов составляет около 4000 ядро-лет. Аппаратная платформа для решения этой задачи состояла из процессоров Intel Xeon Gold 6130 с тактовой частотой 2,1 ГГц. На вычисление RSA-240 методом NFS ушло 800 ядро-лет, а матричным методом? 100 ядро-лет. Вычисление логарифма DLP-240 методом NFS потребовало 2400 ядро-лет, а матричным? 700 ядро-лет. Если не скупиться на ядра, взлом достаточно больших чисел в ключах RSA становится возможен в разумные сроки. Границу "безопасной" разрядности пора отодвигать.
