рейтинг блогов

Взломан самый длинный ключ RSA

топ 100 блогов rumyano4ka25.01.2020

Взломан самый длинный ключ 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 становится возможен в разумные сроки. Границу «безопасной» разрядности пора отодвигать.


Оставить комментарий



Архив записей в блогах:
Обнаружилось, что отсутствие возможности комментировать прямо у меня в журнале доставляет невыносимые страдания для некоторой части ЖЖ-публики. Но у каждого есть возможность зарегистрировать хоть сотню ЖЖ и высказывать там свое особоценное мнение хоть по сто раз. При чем, в случае если вы ...
У вас есть такая категория писем, которые вы получаете, и вас начинает как-то корёжить? У меня это - рассылка от моих прошлых работодателей, у которых я почему-то все еще там нахожусь в их списках, и которые мне ежедневно присылают несколько ...
Выдался чудесный и солнечнечный денек на днях! Cобаку в ошейник, на себя расслабленный look и гулять) Делюсь с вами:  На мне: бойфренды levi's куртка Mango ботинки ALDO толстовка Bershka шапку ZARA одолжила у ...
Шла вот в аптеку за чем-то там да и позырить время-то рабочее . А там - новые незнакомые баночки да флакончики! Вот не удержалась и прихватила гель для душа -вроде самое безобидное что может быть. Какая-то французская, как тут поправляют, марка ...
Долгожданная новость: второй пилот жив и находится на нашей базе. Операция по спасению длилась 12 часов. «Операция завершилась успешно. Штурман доставлен на нашу базу. Жив, здоров», — сообщил Сергей Шойгу на коллегии Минобороны. Реджеп Тайип Эрдоган вынес вердикт: «Кратковре ...