Популярный алгоритм шифрования RSA, применяемый в интернет-коммерции, строится на предположении, что когда простые числа — те, что делятся без остатка только на себя и на единицу — достаточно велики, их почти невозможно подобрать. Для создания ключей шифрования RSA использует два длинных простых числа и с их помощью получает еще большеее простое число. Затем производится проверка, доказывающая, что оно действительно простое. Современные алгоритмы, применяемые в таких тестах простых чисел, работают достаточно быстро, но допускают небольшую вероятность ошибки.
Новый алгоритм, разработанный в Индийском технологическом институте в Канпуре Маниндрой Агравалом (Manindra Agrawal) и его студентами (Neeraj Kayal и Nitin Saxena), как утверждается, генерирует абсолютно точные результаты. “Самый большой недостаток современного криптографического ПО — невозможность на 100% гарантировать, что число является простым, — комментирует профессор вычислительной техники Университета штата Нью-Джерси Эрик Аллендер (Eric Allender). — Этот новый алгоритм решает фундаментальную проблему, стоящую уже несколько веков, над которой ученые интенсивно работали последние десятилетия”.
Работа Агравала, посвященная этому вопросу, еще не опубликована, но оригинальный способ, которым решена задача, сформулированная еще математиками древнего Китая и Греции, уже вызвала переполох среди специалистов. Ряд светил математики и вычислительной техники изучает этот труд. “Подготовительная работа была достаточно сложной, но в результате получился блестящий, очень красивый и элегантный алгоритм”, — говорит Аллендер.Правда, авторы признают, что до практического применения их открытия еще далеко. “Наш метод медленнее, чем самые быстрые из известных алгоритмов тестирования простых чисел, — сказал Агравал. — Его преимущество в том, что он полностью детерминистический, в отличие от его предшествующих, которые могут приводить к ошибкам, хотя и редко”.
Специалисты отмечают, что во многих случаях люди предпочитают мириться с такими маловероятными ошибками. Однако растущая важность шифрования для таких сфер деятельности, как банковское обслуживание и защищенная связь, вызывает все большую потребность в повышении надежности криптозащиты. “Самое важное в этом (алгоритме) — теоретический результат, и это только первый шаг, — говорит Аллендер. —
За ним последуют уточнения и усовершенствования с целью практического применения метода”.Сэндип Джуннаркар
(Sandeep Junnarkar)12 августа, 2002, 12:57
Источник: Crypto scientists crack prime problem (9.08.2002)
Ссылки по теме:
Открытая спецификация RSA вызовет бум на рынке средств шифрования
Самый крутой в мире шифр взломан!
Правительство США приняло новый стандарт шифрования
© http://zdnet.ru/, 12.08.2002
Меню по безопасности