Н. П. Варновский. Грабли для корифеев

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

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

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

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