Грабли для корифеев

Грабли бывают разные. Одни выказывают свои зубья наружу настолько откровенно, что их видно за версту и только полный профан может не заметить такого подвоха. Другие прячутся в груде технических деталей, призывая всех желающих немного поиграть в саперов. Но есть одни грабли, которые стоят (или, точнее, лежат) в стороне от других. Их можно назвать изысканными, быть может даже элитарными. И все потому, что на них очень любят наступать специалисты самой высокой квалификации. Специалисты в математике, не в криптографии.

Математик, взявшийся за сочинение на криптографическую тему, всегда описывает криптосистему RSA. Это и понятно, ведь в основу конструкции RSA положена изящная математическая идея, а эстетическое начало всегда было одним из тех “китов”, на которых держится самая формализованная из наук. Однако, в нашем случае именно “эстетство” и подводит математика. Описав RSA, он, может быть, и хотел бы воскликнуть “красота-то какая!”, но что-то его смущает. Загвоздка вот в чем. В стандартном описании криптосистемы RSA говорится, что открытый текст $m$ должен быть взаимно прост с модулем $N$. Здесь $N=p\cdot q$, $p$ и $q$ – простые числа, $m\lt N$; $p$ и $q$ являются частью секретного ключа, а $N$ – открытого. С практической точки зрения это требование не ограничительно. Если, например, выбирать открытый текст $m$ равновероятным образом из всех чисел, меньших $N$, то вероятность того, что $(m,N)\ne 1$, будет пренебрежимо мала.

Но математики стремятся к завершенности во всем. В результате фактически общим местом всех описаний криптосистемы RSA стали рассуждения о возможности однозначного дешифрования криптограмм и в случае, когда $(m,N)\ne 1$. С математикой здесь, разумеется, все в порядке: корифеи не могут ошибаться в публикуемых ими небольших этюдах по элементарной теории чисел. Но с точки зрения криптографии эти рассуждения не имеют абсолютно никакого смысла. Представляется не слишком целесообразным беспокоиться о гармоничном сочетании оперения сидящего в клетке попугая с цветовой гаммой обоев, когда в доме пожар. Ведь если кому-либо удалось найти открытый текст $m$ такой, что $(m,N)\ne1$, то секретный ключ скомпрометирован! В самом деле, просто вычисляя наибольший общий делитель чисел $m$ и $N$, мы получим либо $p$, либо $q$.

Как говаривали классики, мораль сей басни такова. Хорошая математическая подготовка — необходимое условие для успешных занятий криптографией. Но это условие не является достаточным.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна