Все новости от 20 января 1999 г.

Специалисты по криптографии анализируют «прорыв» школьницы

К такому заключению пришли эксперты по криптографии, собравшиеся на конференции RSA Data Security в Сан-Хосе (штат Калифорния). Они согласны, что 16-летняя Сара Фланнери (Sarah Flannery) из Бларнея (Ирландия) разбирается в теории шифрования, но недоумевают, почему СМИ поспешили объявить ее метод быстрейшим и лучшим по сравнению с общепринятыми алгоритмами.

«Она знает, о чем говорит, — сказал профессор по электро- и вычислительной технике Массачусетсского технологического института (MIT) Рональд Райвест (Ronald Rivest). — Однако для оценки ее работы у нас недостаточно информации». Райвест беседовал с Фланнери после появления первых сообщений в прессе, где утверждалось, будто изобретенный школьницей метод работает быстрее общепринятой технологии RSA, не уступая ей в надежности. Он называет ее «милой» и признает, что она «знает толк в теории чисел» — учитывая, в каком кругу произносились эти слова, их нужно расценивать как высшую похвалу. Тем не менее, детали алгоритма Фланнери пока неизвестны.

«Должно пройти лет пять, прежде чем мы сможем убедиться, что теория выдержала проверку временем», — полагает Пэдди Холаган (Paddy Holahan), вице-президент по маркетингу британской фирмы Baltimore Technology, где Сара проходила двухнедельную практику и познакомилась с доктором Майклом Персером (Michael Purser), который подал ей эту идею. Доказать эффективность любого алгоритма шифрования чрезвычайно трудно. В большинстве случаев формальные математические доказательства здесь неприменимы. Обычно такие алгоритмы публикуются, а затем проходят широкую проверку в рамках сообщества криптографов; этот процесс может занять несколько лет.

Кто сказал «мяу»?
«Кто тот авторитет, который назвал это „прорывом”? — вопрошал президент компании RSA Data Security Джеймс Бидзос (James Bidzos), имея в виду газетные публикации, где утверждается, что метод ирландской школьницы работает в 10–30 раз быстрее, чем алгоритм RSA. Даже сама Фланнери согласна с ним. «Конечно, мой метод не проходил сравнительных испытаний и не подвергался анализу», — сказала она в телефонном интервью. По словам Бидзоса, даже работы самых талантливых криптографов редко получают признание сразу. «Этому алгоритму вряд ли удастся выйти из процесса проверки невредимым, — сказал он. — Но похоже, что девушка знает предмет, и у нас появилась еще одна яркая личность, интересующаяся криптографией».

Предварительная оценка эффективности
Другой специалист из Baltimore Technologies, который работал вместе с Фланнери, Уильям Уайт (William Whyte), рассказал, что алгоритм использует комбинации из четырех чисел — матрицы 2х2. Каждое число ограничено определенным размером, или модулем. Ранее в сообщении в Usenet Уайт утверждал, что надежность метода Фланнери должна быть такой же, как у ключа RSA с модулем того же размера, но с крупными сообщениями он работает быстрее. Анализ Фланнери показывает, что шифрование с 700-битным ключом будет осуществляться в 22 раза быстрее, чем по алгоритму RSA. «К недостаткам метода, — пишет Уайт, — следует отнести то, что как ключ, так и зашифрованный текст получаются примерно в восемь раз длиннее модуля, тогда как в алгоритме RSA их длина примерно равна длине модуля». Иными словами, выигрыш алгоритма Фланнери в быстродействии компенсируется проигрышем в объеме данных. Тем не менее, в определенных приложениях это может оказаться выгодным.

Что же дальше? Сара отказалась патентовать свой алгоритм, решив вместо этого представить его на конференции Crypto 99, если успеет к тому времени оформить работу. До поступления в колледж девушке еще два года, но внимание со стороны Райвеста может означать для нее стипендию в MIT. «Меня уже пригласили несколько институтов, — сказала она. — Конечно, теперь у меня очень широкие перспективы».

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

	Nerd - cenbradian.ru 29 Mar 2000 4:57 PM
Вопрос, конечно, интересный! И в современном мире очень много людей занимаются самыми различными областями знаний, поэтому не удивительно, что кто-то достигнет замечательных результатов. Я,кстати, учась на 2-ом курсе института, тоже мечтал открыть что-нибудь новое в криптографии, поэтому любой новый метод требует тщательной проверки, так как легко открытый шифр может быть также легко и вскрыт. Но о времени для вкрытия я схожусь к периоду в два-два с половиной года. Сергей
	Ruagh - sevabssys.com 15 Jun 2000 3:41 PM
Ну, насколько я помню что-то из теории алгоритмов, они всегда балансировали между скоростью и памятью... В принципе ничего особо удивительного нет в том, что этот алгоритм работает настолько быстрее. Ведь и памяти ему гораздо больше нужно. Сева.