768-битный ключ RSA успешно взломан
Суббота, 09 Янв 2010 6:42
Инженеры из Японии, Швейцарии, Нидерландов и США успешно вычислили данные, зашифрованные с помощью криптографического ключа RSA длиной 768 бит. По словам исследователей, после их опыта в качестве надежной системы шифрования рекомендуется использовать только криптографические ключи длиной 1024 бита и более. Все лючи имеющие длину менее 768 бит уже сейчас можно взломать, правда с определёнными усилиями.
Взломать криптосистему команде учённых удалось в начале декабря, однако доклад на эту тему они представили только сегодня. Сами авторы метода взлома говорят, что их работы могут быть восприняты как незаконные в некоторых странах, в виду того что алгоритм RSA много где используется в государственных и военных нуждах, однако исследователи поясняют, что их работа — это чисто академический опыт и ни одного реального ключа, находящегося в использовании они не взломали. Хотя сделать это возможно.
Из описания работы, вычисление значений криптоключа инженеры проводили методом факторизации модульных чисел. Метод основан на сравнительно простых арифметических действиях, объединенных в сложные формулы.
Как пояснил Андрей Тимофеев из института CWI в Амстердаме, для своих расчетов они использовали самое обычное оборудование, доступное в продаже. Самым первым шагом во взломе системы служило вычисление подходящих простых множителей. Если бы эта процедура проводилась основным методом перебора, то на процессоре AMD Opteron 2.2 ГГц он бы занял примерно 1500 лет и около 5 терабайт данных. Но, исследователи решили использовать многомерные математические матрицы.
Создание кластера матриц заняло около 12 часов. На основе матриц размерностью 2200 на 2200 исследователи обнаружили множители, последующие процессы вычисления шли значительно быстрее и уже на базе современных многоядерных процессоров. В результате группе удалось вычислить 232-цифровой ключ, который открыл доступ к зашифрованным данным.
Учёные уверены, что если использовать их метод факторизации, взломать 512-битный RSA-ключ можно было еще лет 5-10 назад.
Данные о работе исследователей можно просмотреть по адресу http://eprint.iacr.org/2010/006.pdf
