Все новости от 12 августа 2002 г.

Решена фундаментальная проблема криптографии

Популярный алгоритм шифрования RSA, применяемый в интернет-коммерции, строится на предположении, что когда простые числа — те, что делятся без остатка только на себя и на единицу — достаточно велики, их почти невозможно подобрать. Для создания ключей шифрования RSA использует два длинных простых числа и с их помощью получает еще большеее простое число. Затем производится проверка, доказывающая, что оно действительно простое. Современные алгоритмы, применяемые в таких тестах простых чисел, работают достаточно быстро, но допускают небольшую вероятность ошибки.

Новый алгоритм, разработанный в Индийском технологическом институте в Канпуре Маниндрой Агравалом (Manindra Agrawal) и его студентами (Neeraj Kayal и Nitin Saxena), как утверждается, генерирует абсолютно точные результаты. «Самый большой недостаток современного криптографического ПО — невозможность на 100% гарантировать, что число является простым, — комментирует профессор вычислительной техники Университета штата Нью-Джерси Эрик Аллендер (Eric Allender). — Этот новый алгоритм решает фундаментальную проблему, стоящую уже несколько веков, над которой ученые интенсивно работали последние десятилетия». Работа Агравала, посвященная этому вопросу, еще не опубликована, но оригинальный способ, которым решена задача, сформулированная еще математиками древнего Китая и Греции, уже вызвала переполох среди специалистов. Ряд светил математики и вычислительной техники изучает этот труд. «Подготовительная работа была достаточно сложной, но в результате получился блестящий, очень красивый и элегантный алгоритм», — говорит Аллендер.

Правда, авторы признают, что до практического применения их открытия еще далеко. «Наш метод медленнее, чем самые быстрые из известных алгоритмов тестирования простых чисел, — сказал Агравал. — Его преимущество в том, что он полностью детерминистический, в отличие от его предшествующих, которые могут приводить к ошибкам, хотя и редко».

Специалисты отмечают, что во многих случаях люди предпочитают мириться с такими маловероятными ошибками. Однако растущая важность шифрования для таких сфер деятельности, как банковское обслуживание и защищенная связь, вызывает все большую потребность в повышении надежности криптозащиты. «Самое важное в этом (алгоритме) — теоретический результат, и это только первый шаг, — говорит Аллендер. — За ним последуют уточнения и усовершенствования с целью практического применения метода». 

 Предыдущие публикации:

 В продолжение темы:

Обсуждение и комментарии

	al - aliac.spb.ru 12 Aug 2002 3:08 PM
Вдумайтесь в то, что вы написали: "Для создания ключей шифрования RSA использует два гигантских простых числа, перемножая их для получения еще большего числа. Затем производится проверка, доказывающая, что это действительно простое число." Перемножением 2 чисел никак не может получиться простое число.
	...мимо проходящий 12 Aug 2002 3:34 PM
...а это у них переводчик хреновый. Там и думать нечего.
	Nob - sudakovbgumail.bgu.ac.il 12 Aug 2002 3:38 PM
Алгоритм описанный в этой статье только дает ответ на вопрос "простое число или нет", а не решает проблему факторизации, на которой как раз основаны все алгоритмы криптографии. Так что это не "фундаментальная проблема криптографии" а всего лишь хороший алгоритм, который за полиномиальное время скажет если число простое с 100% уверенностью. До этого были алгоритмы которые за меньшее время давали вероятность 99.9999999999%. Так что не уверен, что с этим решением задачи что-либо изменится, поскольку погрешность не столь велика, а время работы алгоритма намного более критично.
	Ирина 13 Aug 2002 6:03 AM
Мимо проходящему. Не-а. Я вчера эту статью читала в оригинале, там именно так и написано. Перемножаем два простых (prime) числа и получаем простое (prime опять же). Проблема глыбже где-то.
	Sergey - sergey_a_sablinrambler.ru 13 Aug 2002 7:28 AM
В RSA, если внимательно вчитаться есть два исходных простых числа p и q (закрытый ключ), открытый ключ n = p * q, и это, естественно, не разу не простое число, и не должно быть простое, потому как вся сложность RSA в том и заключается, чтобы разложить это известное всем n на два простых p и q. А тут лажу какую-то написали, вот. Относительно, индийцев: если все подтвердиться, то они большие молодцы, т.к. красивого теоретического решения на этот вопрос со времен Ферма никто не придумал, хотелось бы посмотреть.
	Chkaloff 13 Aug 2002 2:04 PM
2 Nob: Квантовый компьютер как раз и должен вроде решать эту задачу за полиномиальное время.
	DemonZla 16 Aug 2002 12:36 PM
Хм... Всё равно расшифруем... Людской фактор угробит любую криптографию...
	Max 17 Aug 2002 12:18 PM
2 Chkaloff: kakaya razhnitsa kakoy komputer? "Polinomial'noe vremya" eto effectivnost' algoritma, a ne bystrota komputera.
	Костя - mkostyatechunix.technion.ac.il 30 Nov 2002 12:36 AM
2 Max: Квантовый компьютер способен за полиномиальное время решить задачу, которую обычный решает за экспоненциальное.
	GhostII 18 Apr 2003 7:28 PM
Может быть они имели в виду следующее: с помощью перемножения двух простых числел и некоторых других простых операций можно найти хорошее начальное приближение для поиска еще более большого простого числа. Это проще, чем полный перебор, начиная с некоторого значения.