RSA
RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом.
Информация
RSA стал первым алгоритмом такого типа, пригодным и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений. В телефонах Motorola является цифровой подписью длиной в 1024 бита.
На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера ключа в 1024 бита.
Группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит.[6] По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года.
Как следует из описания работы, вычисление значений ключа осуществлялось общим методом решета числового поля.
На первый шаг (выбор пары полиномов степени 6 и 1) было потрачено около полугода вычислений на 80 процессорах, что составило около 3% времени, потраченного на главный этап алгоритма (просеивание), который выполнялся на сотнях компьютеров в течении почти двух лет. Если интерполировать это время на работу одного процессора AMD Opteron 2.2ГГц с 2Гб памяти, то получилось бы порядка 1500 лет. Обработка данных после просеивания для следующего ресурсоёмкого шага (линейной алгебры) потребовалось несколько недель на малом количестве процессоров. Заключительный шаг после нахождения нетривиальных решений ОСЛУ занял не более 12 часов.
Решение ОСЛУ проводилось с помощью метода Видемана на нескольких раздельных кластерах и длилось чуть менее 4 месяцев. При этом размер разреженной матрицы составил 192 796 550х192 795 550 при наличии 27 795 115 920 ненулевых элементов (т.е. в среднем 144 ненулевых элементов на строку). Для хранении матрицы на жёстком диске понадобилось около 105 гигабайт. В то же время понадобилось около 5 терабайт сжатых данных для построения данной матрицы.
В итоге группе удалось вычислить 232-цифровой ключ, открывающий доступ к зашифрованным данным.
Исследователи уверены, что используя их метод факторизации, взломать 1024-битный RSA-ключ будет возможно в течении следующей декады.
RSA в Мotorola
В телефонах Motorola используется ключ длиной в 1024 бита. Подбирание этого ключа даёт полный доступ к буту, что делает возможность заменить прошивку на свою (к примеру, symbian).
В 2006-2007 годах на мотофане был проект по подбору ключа. Сейчас этим никто не занимается, так как довольствуются методом обхода. Нужно это теперь только владельцам телефонов с IROM4 (L9/W510 etc.).