- Специальный корреспондент
Ученые взломали ключ шифрования RSA-240, считающийся самым сложным во всем мире. Для этого они использовали усовершенствованные алгоритмы разложения большого числа на простые множители и новые методики вычисления дискретного логарифма.
Шифрование данных по угрозой
Группе французских ученых во главе с Эммануэлем Томе (Emmanuel Thome) из Национального института исследований в информатике и автоматике удалось взломать ключ шифрования RSA-240 длиной 240 десятичных разрядов или 795 бит. Его называли сложнейшим в мире, считалось, что на его расшифровку требуется 35 млн вычислительных лет (core years). Эта же группа ученых сумела вычислить дискретный логарифм такой же длины.
Специалистам удалось прийти к цели за существенно меньшее количество времени – 4000 вычислительных лет. По их словам, они смогли этот рекорд вовсе не за счет того, что за прошедшее с предыдущего рекорда (взлом RSA-232) время производительность компьютеров хоть немного, но возросла. Вместо этого они сделали ставку на улучшенные алгоритмы разложения большого числа на простые множители и усовершенствованные методики вычисления дискретного логарифма.
Взлом ключа RSA-240 доказал, что идеальной защиты не существует
В пользу правильности сделанного выбора говорит тот факт, что дискретный логарифм для ключа ключ RSA с разрядностью 768 бит (232 десятичных разряда) был вычислен в лишь 2016 г., хотя сам ключ был взломан в 2010 г.
Что такое RSA
RSA – это алгоритм шифрования, созданный в 1977 г. Роном Ривестом (Ron Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адельманом (Leonard Adleman). В 1982 г. они основали компанию RSA Security, существующую до сих пор. Несмотря на практически 43-летний возраст, по состоянию на декабрь 2019 г. он по-прежнему считается одной из наиболее распространенных и востребованных форм шифрования, использующей умножение для получения очень большого числа из нескольких простых.
Данный алгоритм, получивший свое название от первых букв фамилий своих создателей, применяется в ряде криптографических программ и протоколов, в том числе PGP, TLS и SSL.
Секрет успеха
Для выполнения поставленной задачи французские ученые задействовали несколько одновременно работающих кластеров компьютеров. Аппаратные платформы для решения этой задачи состояли из процессоров Intel Xeon Gold 6130 с тактовой частотой до 3,7 ГГц двухлетней давности. Данный чип Intel выпустила в III квартале 2017 г, он содержит 16 ядер (32 потока) и 22 МБ кэш-памяти третьего уровня. Это серверный процессор, производимый по 14-нанометровой технологии.
Ускорение расчетов сами специалисты соотносят с обновлениями в программном обеспечении с открытым исходным кодом, опирающееся на вычисления с использованием метода решета числового поля (Number Field Sieving, NFS). К примеру, ПО CADO-NFS содержит 300 тыс. строк исходного кода, написанного на языках C и C++.
Следует отметить, что 4000 вычислительных лет – это суммарное количество затраченного времени на четыре расчета – вычисление ключа методом NFS затребовало 800 из них, а на матричный метод ушло еще 100. Вычисление логарифма DLP-240 по NFS-методу заняло 2400 вычислительных лет, а по матричному методу – 700.
Другие примеры взлома RSA
Взлом алгоритма RSA – это своего рода хобби для многих ученых. Своей цели они достигали разными методами – кто-то делал ставку на самое современное и мощное компьютерное железо, объединенное в кластеры, кто-то, как команда Эммануэля Томе, уповал на программное обеспечение.
Но существуют и другие способы взлома этого алгоритма. К примеру, в самом начале XXI века, в 2001 г., филиппинский математик-энтузиаст Лео де Велез (Leo de Velez) метод декодирования алгоритма шифрования RSA, основанный всего лишь на трех простых формулах. Сами формулы ученый не публиковал, однако RSA Security знает об их существовании. Сразу после распространения информации об этих «супер-формулах» представители компании заявили, что филиппинский математик явно переоценил свои способности, и что его формулы едва ли смогут взломать длинные ключи шифрования.
В 2013 г. Троим исследователям из Института Вейцмана в Израиле удалось ключи алгоритма шифрования RSA после того, как они проанализировали шум, который компьютер издает во время работы. «Многие компьютеры во время своей работы издают высокочастотный шум, обусловленный вибрацией некоторых электронных компонентов. Эти звуковые колебания могут содержать информацию о запущенном программном обеспечении и, в частности, важную информацию о математических вычислениях, связанных с шифрованием информации», – содержится в докладе исследователей.
Примечательно, что среди авторов работы был сам Ади Шамир (Adi Shamir), один из разработчиков алгоритма RSA.
