Пример. В шифровке

$$ \begin{array}{l} 1163219079\ 4668046830\ 0011216732\ 0309650467\ 3267065033\ \underline{1192514275}\\ 1212489158\ 5058346454\ 4345793196\ \underline{\underline{4397102669}}\ 5368937727\ 0949088697 \\ 5120945088\ \underline{1192514275}\ 1921390549\ 0896888534\ 2535878443\ \underline{\underline{4397102669}}, \end{array} $$ зашифрованной ключом $ M=5694996163, {\mathbf E}=2676573121 $, можно обнаружить одинаковые блоки. Этот факт свидетельствует о том, что и соответствующие блоки открытого текста должны быть одинаковыми. Так оно и есть — открытым текстом здесь является (в кодировке, приведенной ☞ ЗДЕСЬ ) отрывок из стихотворения Ф.И.Тютчева:

Наличие рифмы и обеспечивает повторяемость блоков¹⁾. Разумеется, содержание соответствующих блоков открытого текста можно узнать, только дешифровав шифровку. Однако противник может подменить блок исходного текста на свой собственный, исказив тем самым смысл. Попробуйте заменить в приведенном выше тексте ДАТЬ на ЕСТЬ. И рифма сохранится, и текст — с некоторой натяжкой — осмыслен, но только смысл совсем не тот, что предполагал автор. ♦

Даже сам факт наличия дополнительной информации о сообщении, может оказать существенную помощь противнику.

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

ПОЛУЧАТЕЛЬ ПЛАТЕЖА , РАСЧЕТНЫЙ СЧЕТ , СУММА В РУБЛЯХ , ФИЛИАЛ СБЕРБАНКА РФ

и прочие будут кочевать из одного сообщения в другое. Зная открытый ключ шифрования $ ({\mathbf E},M) $ (а он доступен!), противник может заранее найти выражения $ x^{\mathbf E} \pmod{M} $ для тех $ x_{} $, что составляют кодировку упомянутых словосочетаний. После этого, перехватив очередное платежное поручение, посланное в банк в электронном виде, и заблокировав его пересылку законному адресату, он попытается найти куски шифровки, совпадающие с его образцами. Если ему повезет и он обнаружит блок соответствующий тексту «РАСЧЕТНЫЙ СЧЕТ», то следующим его действием может стать замена идущего за отгаданным блока шифровки — номера расчетного счета — на тот, что более подходит ему… После этого искаженная шифровка отправляется в банк. Итак, исходное сообщение не дешифруется, но подменяется, искажается.

Атака на шифровку называется пассивной, если она имеет целью только ознакомление с содержанием (т.е. нарушение конфидециальности), и активной, если она направлена на изменение содержания.

Как обеспечить контроль за сохранностью содержания сообщения?

Опытный разведчик, закрывая ящик своего письменного стола, оставит метку — определенным образом закрепленный волосок. Не задев его, невозможно открыть ящик. Ту же идею можно реализовать и для блоков шифровки. В открытом тексте выберем из каждого блока по букве, например, первой. Составим из них новое слово (для сообщения из приведенного примера это будет ТBЗE_В_Р_ДО_МВ_НБД , поставим его в конец открытого текста, закодируем и зашифруем открытым ключом.

«Метка» поставлена. По получении шифровки законный адресат дешифрует ее и первым делом обращает внимание на соответствие первых букв блоков дешифрованного текста и соответствующих букв «метки». В случае несовпадения включается сигнал тревоги: канал связи стал ненадежным! Можно сразу же обнаружить и место «испорченного» блока и принимать соответствующие меры. Если метки совпадают, то, разумеется, есть вероятность, что противнику повезло настолько, что «испорченный» блок имеет ту же начальную букву, что и истинный. Но вероятность этого не очень большая (кстати, какая?).

Сам процесс выделения из исходного текста некоторой его «выжимки» называется хешированием²⁾. Хеширование используется для решения разных задач, связанных с обработкой информации, в том числе для ее поиска, сортировки или контроля за целостностью при пересылке. Каждый человек, переводивший с иностранного языка, применял хеширование при поиске в словаре значения незнакомого слова: $$ anxiety = an - xie - ty , $$ сначала запоминая первые две буквы и отыскивая в словаре соответствующие страницы, затем уже пробегая взглядом эти страницы, находя слова, соответствующие следующим буквам, и, наконец, добравшись до однокоренных слов, выявляя нужное ему значение. Такая организация поиска позволяет сэкономить «оперативную» и, тем более, не засорять «долговременную» память, предназначенные для гораздо более серьезных целей, чем запоминание иностранных слов…

Поскольку описание всех операций с текстами мы перевели на язык цифр, то и хеширование имеет смысл определять как функцию на множестве целых чисел.

Функцией хеширования или хеш-функцией называется функция $ h_{}(x) $, удовлетворяющая как минимум двум требованиям:
а) сжатия: $ h(x) $ отображает произвольное число $ x_{} $ в число, не превышающее некоторого заданного $ \tilde M $;
б) простоты вычисления.

Пример. Только что предложенный способ контроля целостности передаваемой информации по первой букве блока описывается хеш-функцией

$$h(x): \ x=\underline{{\mathfrak x}_1{\mathfrak x}_2{\mathfrak x}_3 \dots {\mathfrak x}_{\ell}} \mapsto \underline{{\mathfrak x}_1{\mathfrak x}_2} \ . $$ Здесь число $ x_{} $ задано в десятичной системе счисления и, следовательно, $ \tilde M=99 $.

Хорошо известно хеширование методом вычисления контрольной суммы: $$ h(x): \ x=[x_1\big|x_2\big| \dots \big| x_k] \mapsto x_1+x_2+\dots+x_k \pmod{ \tilde M} \ . $$ Здесь число $ x_{} $ сначала разбивается на блоки $ x_{j} $ — числа фиксированной длины, которые затем суммируются по модулю некоторого заданного числа $ \tilde M $. ♦

По самой цели ее введения хеш-функция будет заведомо необратимой в обычном понимании: если $ h(x)=y $ для некоторого $ x_{} $, то, как правило, существует $ \tilde x \ne x $ такое, что $ h(\tilde x)=y $, т.е. для одного образа существует по крайней мере два прообраза. Поэтому в дальнейшем, говоря об обратимости хеш-функции, будем иметь в виду задачу определения всех прообразов данного значения этой функции.

Будем говорить о наличии коллизии³⁾, если $$ h(x)=h(\tilde x) \quad npu \ x \ne \tilde x \ . $$ В начале пункта КРИПТОАНАЛИЗ мы предположили, что противнику известны методы контроля за целостностью пересылаемого сообщения. Иначе говоря, следует предполагать, что и алгоритм вычисления значений функции хеширования ему известен; допустим, однако, что он не в состоянии изменить значение функции хеширования, вычисленное для истинного сообщения и сопровождающее это истинное сообщение⁴⁾. Последнее условие ограничивает «свободу действий» при подлоге: подменить $ x_{} $ на $ \tilde x_{} $ можно только в том случае, когда выполнено условие коллизии $ h(x)=h(\tilde x) $. Затруднить же работу злоумышленника можно, усилив требования при выборе $ h(x) $ так, чтобы усложнить задачу нахождения коллизий. Пусть в дополнение к свойствам a) и б) функция хеширования обладает еще и следующими:

в) трудной обратимостью: по заданному образу $ y_{} $ нахождение любого его прообраза $ x, \tilde x , \dots $ очень трудоемко;
г) трудностью «повторения успеха»: по известной паре $ (x,h(x)) $ трудно восстановить другой прообраз $ \tilde x \ne x $ такой, что $ h(x)=h(\tilde x) $;
д) трудностью «попадания двух снарядов в одну воронку»: очень трудоемко обнаружить вообще любые коллизии.

Поясним смысл двух последних ограничений. Предположим для простоты, что содержание открытого текста не скрывается (т.е. не требуется конфиденциальность) и проблема заключается исключительно только в сохранении целостности информации в ходе ее передаче. Тогда смысл условия г) очевиден из предыдущего абзаца: никто посторонний не должен иметь возможности незаметно исказить содержание.

В чем смысл условия д)? Для объяснения этого нам придется отказаться от «презумпции⁵⁾ невиновности» самого автора сообщения. Предположим, что этот автор хочет сжульничать: отправить такое сообщение, чтобы в дальнейшем иметь возможность отказаться подтвердить (т.е. отвечать за) его содержание. Для этого в сообщение им вставляется блок $ x_{} $, который, возможно, не несет никакой информации — нейтрален в смысле истинности или ложности, да и вообще может представлять бессмысленный набор букв; но для этого блока автору известна коллизия $ \tilde x_{} $, т.е. пара $ x_{} $ и $ \tilde x_{} $ удовлетворяет условию $ h(x)=h(\tilde x) $. Когда после отсылки сообщения наступит «час расплаты», жулик-отправитель может формально отречься подтвердить его содержание — например, оплатить счет за заказанную в Интернете покупку, — обосновав свой отказ тем, что его истинным было сообщение, содержавшее именно блок $ \tilde x_{} $, который якобы и был подменен на $ x_{} $ неким злоумышленником. Легко сообразить, что схема подлога может зеркально развернуться — и тот же покупатель может стать жертвой нечестного продавца. Для иллюстрации сошлемся на сцену судебного разбирательства из комедии Бомарше «Безумный день, или Женитьба Фигаро»:

Как выбрать подходящего кандидата $ h_{}(x) $, удовлетворяющего всем перечисленным требованиям? Заметим, что все эти требования можно объединить в одном: значение $ h_{}(x) $ должно легко вычисляться, но быть заранее непредсказуемым по виду $ x_{} $. Иными словами, надо подобрать такое аналитическое выражение для $ h_{}(x) $, которое бы имитировало случайный, хаотический разброс значений этой функции во множестве $$\left\{0,1, \dots , {\tilde M}-1 \right\} \ .$$ В этом отношении хеш-функции похожи на функции шифрования, т.е. должны быть односторонними. Следовательно, подходящих кандидатов можно искать в одних и тех же классах, например, среди функций вида $$ x^n \pmod{\tilde M} \ npu \ n\in \mathbb N . $$ Однако эти функции, во-первых, надо слегка «испортить», чтобы предотвратить возможность их обращения любым участником переписки, и, во-вторых, сделать применимыми к сообщениям любой длины. Одновременное достижение обеих целей возможно, если определить хеш-функцию рекурсивно. В качестве примера приведем хеш-функцию Дэвиса—Мейера. Исходный открытый текст снова разбивается на блоки одинаковой длины (меньшей $ \tilde M $) $$x=[x_1\big|x_2\big| \dots \big| x_k] $$ и значение хеш-функции вычисляется по правилу $$ h(x)= H_k, \quad \mbox{ где } \ H_j= H_{j-1} \oplus \left[ H_{j-1}^{x_j} \pmod{\tilde M} \right] \quad \mbox{ для } \ j\in \{1,\dots,k \}\ . $$ Здесь значение $ H_0\in \{2,\dots, \tilde M -1\} $ берется произвольным фиксированным, а $ \oplus $ означает операцию побитного сложения по модулю $ 2_{} $ чисел, представленных в двоичной системе счисления: если $ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $ и $ B=\underline{{\mathfrak b}_1{\mathfrak b}_2 \dots {\mathfrak b}_s {\mathfrak b}_{s+1}} $ два числа, представленных в такой системе, то $$A\oplus B = \underline{{\mathfrak c}_1{\mathfrak c}_2 \dots {\mathfrak c}_s {\mathfrak c}_{s+1}} \ , npu \ {\mathfrak c}_j = {\mathfrak a}_j + {\mathfrak b}_j \pmod{2} \ . $$ Следует отметить, что для всех используемых в настоящее время хеш-функций не доказана их «абсолютная случайность» и их использование основывается на достаточно длительном опыте их безотказного применения. Предполагаемое число коллизий для функции Дэвиса—Мейера при $ \tilde M=2^K $ равно $ 2^{K/2} $.

При «абсолютно случайной» функции $ h_{}(x) $ злоумышленнику придется искать коллизии в последовательности значений $$h(x_1),h(x_2), \dots , h(x_k), \dots \ ,$$ практически равновероятно распределенных в этом множестве. Если число $ \tilde M $ очень велико, то и встречи коллизии следует ожидать лишь при больших значениях $ k_{} $, что и составляет кажущееся непреодолимым препятствие для подделки. Однако помощь злоумышленнику неожиданно окажет обстоятельство, известное под названием парадокса дней рождения: в общем случае, для достаточно большого множества $ N_{} $ элементов следует ожидать появления «дубля» при выборке (с возвращением) спустя $ \sqrt{\pi N\, \big/\, 2} \approx 1.3 \sqrt{N} $ испытаний.

Идея атаки, основанной на парадоксе дней рождения, заключается в следующем. Пусть имеется истинное сообщение $ x_{} $, содержание которого должно дойти до адресата. Пусть имеется сообщение $ \hat x $, которое жулик впоследствии хочет выдать за $ x_{} $. Жулик генерирует $$L= \left\lfloor 1.3 \sqrt{\tilde M} \right\rfloor $$ сообщений $ X_1,\dots,X_L $, слегка отличающихся от истинного $ x_{} $ либо наличием в открытом тексте орфографических или смысловых ошибок⁶⁾, либо же — если для кодирования открытого текста применяются коды, исправляющие ошибки, — изменяя биты этой кодировки, как бы имитируя действие технических помех на канале связи. Для всех этих модификаций вычисляются значения хеш-функции: $$ \mathbb H = \{h(X_1), \dots, h(X_L) \} \ ,$$ и эти значения сортируются для облегчения последующего анализа. Далее, жулик начинает генерировать сообщения $ \hat X_1, \hat X_2,\dots $, слегка отличающиеся от $ \hat x $ и вычислять значения хеш-функции, проверяя их на принадлежность множеству $ \mathbb H $. Ожидаемое количество генераций до встречи с коллизией равно $ L_{} $. Если $ h(X_j)=h(\hat X_k) $, то вместо истинного сообщения $ x_{} $ жулик может послать сообщение $ X_{j} $, отличающееся от $ x_{} $ незаметным на первый взгляд дефектом, однако впоследствии утверждать, что на самом деле он переслал сообщение $ \hat X_k $ слегка отличающееся от $ \hat x $.

В настоящее время безопасными для подобной атаки считаются хеш-функции с $ \tilde M>2^{80} $.

Как установить автора присланного сообщения?

Иначе: как удостовериться, что полученное сообщение действительно принадлежит тому, за кого пославший выдает себя, т.е. аутентифицировать корреспондента? В идеологии криптографии открытых ключей это можно попытаться сделать, отождествив корреспондента с созданным им и официально зарегистрированным ключом.

На этом пути, однако, могут возникнуть трудности технического характера.

Как, например, узнать, что данный ключ RSA $ ({\mathbf E},M) $ принадлежит именно банку, клиентом которого Вы собираетесь стать?

Предположим, что этот ключ выложен на всем известном сайте банка и любой желающий может воспользоваться им для своей корреспонденции с банком, рассчитывая при этом на конфиденциальность. Вообразим, однако, ситуацию, когда контроль над сайтом на какое-то время банком утерян — скажем, в результате хакерской атаки. Перехвативший управление злоумышленник может изменить истинный ключ $ ({\mathbf E},M) $ на свой собственный $ ({\mathbf E}_1,M_1) $. Он даже может подобрать множители числа $ M_1 $ так, чтобы оно, на первый взгляд, было очень похожим на истинное, да еще, вдобавок, так, чтобы и ключ шифрования остался бы тем же: $ {\mathbf E}_1={\mathbf E} $.

Клиент банка, заглянувший на сайт в этот момент, примет $ ({\mathbf E},M_1) $ за ключ, которым следует пользоваться для корреспонденции. В результате вся присланная им в банк корреспонденция, зашифрованная этим ключом будет спокойно прочитываться хакером, поскольку этот ключ создан им самим! Более того, после прочтения он может расстараться и вновь зашифровать открытый текст — теперь уже истинным, т.е. банковским, ключом шифрования $ ({\mathbf E},M) $ и оставить в ящике входящих писем банка после окончания своей атаки. Банку придется затратить уйму времени и средств для установления факта нарушения конфиденциальности.

Мы не касаемся способов решения этой проблемы и будем в дальнейшем считать идентификацию ключ $ \longleftrightarrow $ владелец произведенной.

Фактически владельца ключа RSA можно аутентифицировать парой $ \left(\mathbf D,\mathbf E \right) $, т.е. секретной и открытой частями ключа. И он обладает уникальной возможностью выполнения двух операций с любым открытым текстом $ x $, закодированным числом из множества $ \{0,1,\dots,M-1\} $. Первая из этих операций — шифрование $ x^{\mathbf E} \pmod M $ для него имеет смысл если только он хочет скрыть $ x $ от чужих глаз. А вот обратная операция $ x^{\mathbf D} \pmod M $ позволяет получить число, из которого любой желающий может восстановить исходный открытый текcт $ x $: $$ \left(x^{\mathbf D} \right)^{\mathbf E} \equiv x \pmod M \, . $$

На этом и основана идея цифровой подписи. Любой открытый текст $ x_{} $ владелец ключа может преобразовать в число $ s_{} $ по формуле $$ s= x^{\mathbf D} \pmod{M} $$ и закон этого преобразования $ x \mapsto s $ будет известен только ему. Если $ x<M $, то существует и обратное преобразование $ s \mapsto x $, которое может быть установлено любым желающим, поскольку задается открытым ключом $$ x= s^{\mathbf E} \pmod{M} $$ в виду справедливости $ \left(x^{\mathbf D} \right)^{\mathbf E} \equiv x \pmod{M} $ для $ \forall x\in \left\{1,2,\dots,M-1 \right\} $.

Итак, владелец ключа хочет передать сообщение, содержание которого не составляет тайны (например, объявление о продаже), но хочет, чтобы целостность сообщения не была нарушена и было установлено его — отправителя — авторство. Для достижения этих целей он отправляет вместо открытого текста $ x_{} $ его образ $ s_{} $, получившийся в результате действия секретного преобразования $ x^{\mathbf D} \pmod{M} $.

Число $ s_{} $ называется цифровой подписью⁷⁾ сообщения $ x_{} $. (В конце пункта это определение будет модифицировано.)

Получив сообщение $ \widetilde s $, получатель применяет к нему открытый ключ шифрования $$ \widetilde x= \widetilde s^{\mathbf E} \pmod{M} \ . $$ Если $ \widetilde x $ декодируется в осмысленное сообщение, то оно принимается за сообщение, пришедшее от владельца ключа и считается дошедшим до получателя в неизмененном виде.

Противник, разумеется, может предпринять активную атаку, пробуя подобрать число $ \widetilde s $ так, чтобы число $ \widetilde s^{\mathbf E} \pmod{M} $ декодировалось в осмысленный текст. Однако маловероятно достичь этой цели случайным перебором. Дополнительным препятствием для такой атаки послужит и то обстоятельство, что в большинстве случаев получатель заранее имеет представление о возможном содержании сообщения (финансовая информация при переписке с банком, ключевые моменты при частной переписке и пр.) и поэтому откровенную бессмыслицу не воспримет за истинное сообщение.

Пример. Для доказательства того, что шифровка примера $ 4 $ из ☞ ПУНКТА действительно принадлежит авторам алгоритма RSA, они сопроводили [1] шифровку цифровой подписью

$$ s={\scriptstyle 1671786115038084424601527138916839824543690103235831121783503844692906265544879223711449050957860865566224965779748400040570220373} \ . $$ Любой желающий мог восстановить число $ x_{} $ по формуле $ x= s^{\mathbf E} \pmod{M} $ с помощью открытого ключа шифрования $ {\mathbf E}=9007 $ , $$M= {\scriptstyle 114381625757888867669325779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541} \ : $$

С другой стороны, поскольку ключ дешифрования $ {\mathbf D} $ был известен только разработчикам, то никто другой не смог бы создать тот же эффект: при выборе числа $ s_{} $ наобум, результатом $ s^{\mathbf E} \pmod{M} $ практически всегда будет абракадабра⁸⁾. ♦

Можно, наконец, «продублировать» подпись $ s_{} $, сопроводив ее при пересылке открытым текстом $ x_{} $ (содержание которого, по предположению, не составляет тайны); тогда подтверждение авторства будет заключаться в простом сравнении $ s^{\mathbf E} \pmod{M} $ и $ x_{} $. Напомним, однако, что во всех предшествующих рассуждениях открытый текст $ x_{} $ предполагался достаточно коротким для того, чтобы формула $ s^{\mathbf E} \pmod{M} $ восстанавливала его однозначно. Что делать в случае, когда $ x\ge M $ ? Во-первых, можно разбить открытый текст $ x_{} $ на блоки длины меньшей $ M_{} $: $$x=\left[x_1\big| x_2\big| \dots \big| x_k \right], \ npu \ x_j<M, \ j\in \{ 1,\dots, k \} , $$ и сгенерировать цифровые подписи для каждого блока: $$s= \left[s_1\big| s_2 \big|\dots \big| s_k \right], \ npu \ s_j= x_j^{\mathbf D} \pmod{M} \ . $$ На этом пути нас, однако, подстерегает опасность подмены блока, аналогичная той, что обсуждалась в предыдущем ПУНКТЕ. Из того же пункта можно позаимствовать и способ разрешения этой трудности, а именно хеширование. Действительно, поскольку содержание сообщения не требуется сохранять в тайне, а необходимо только лишь обеспечить его сохранность и позаботиться о подтверждении авторства, то можно отсылать открытый текст, не шифруя его, но сопроводив «припиской», которая одновременно будет контролировать целостность текста и выполнять роль цифровой подписи.

Пусть $ h_{}(x) $ — хеш-функция такая, что $ h(x)<M $ для всех $ x\in \{0,1,\dots,M-1 \} $. Число $$\widehat s = \left(h(x) \right)^{\mathbf D} \pmod{M}$$ называется цифровой подписью сообщения $ x_{} $.

Это определение очевидно обобщает предыдущее, получающееся из него в частном случае $ h(x)=x $. Принципиальным отличием первого определения от второго является то, что в первом случае по самой цифровой подписи открытый текст $ x_{} $ восстанавливается однозначно, а во втором — нет, и, следовательно, его присутствие в письме обязательно.

По получении сообщения — открытого текста $ x_{} $, сопровождающегося цифровой подписью $ \widehat s $, — получатель вычисляет $ \widehat s^{\mathbf E} \pmod{M} $ и значение хеш-функции $ h_{}(x) $ (предполагается, что ему известен алгоритм хеширования). В случае совпадения значений, сообщение $ x_{} $ принимается за сообщение, исходящее от владельца ключа и считается дошедшим до получателя в неизмененном виде.

Проиллюстрируем теперь возможности использования открытых ключей шифрования для одновременного обеспечения как секретности содержания, так и контроля за его целостностью, а также для подтверждения авторства. Пусть два участника переписки $ {\mathcal A} $ и $ {\mathcal B}_{} $ имеют ключи, в которых модулями, открытыми и секретными составляющими, являются соответственно числа $ M_{\mathcal A},{\mathbf E}_{\mathcal A},{\mathbf D}_{\mathcal A} $ и $ M_{\mathcal B},{\mathbf E}_{\mathcal B},{\mathbf D}_{\mathcal B} $. Пусть $ {\mathcal A} $ хочет переслать $ {\mathcal B}_{} $ открытый текст $ x_{} $, зашифровав его так, чтобы прочитать его мог только $ {\mathcal B}_{} $ и чтобы было подтверждено авторство $ {\mathcal A}_{} $. Алгоритм шифрования RSA обеспечит секретность пересылки с помощью открытого ключа шифрования $ ({\mathbf E}_{\mathcal B},M_{\mathcal B}) $; алгоритм получения цифровой подписи с помощью ключа дешифрования $ ({\mathbf D}_{\mathcal A},M_{\mathcal A}) $ позволит установить авторство $ {\mathcal A}_{} $. Для одновременного достижения обеих целей имеет смысл объединить алгоритмы в следующую схему: Действия $ {\mathcal B}_{} $ по получении шифровки $ c^{} $: Если в результате получается число $ x_{} $, декодируемое в осмысленный текст, то получатель считает его истинным текстом, исходящим именно от $ {\mathcal A}_{} $.

Во всех предшествующих рассуждениях имеется, однако, один изъян, который проиллюстрируем на следующем примере.

Пример. Резидент разведки из примера 1, приведенного ☞ ЗДЕСЬ, хочет отправить Центру в зашифрованном виде цифровую подпись сообщения «ДА». Что получит Центр, если модуль ключа резидента равен $ 3953 $, а ключ шифрования равен $ 157 $?

Решение. Для согласования с приведенной выше схемой будем считать, что резидент — это $ {\mathcal A}_{} $, а Центр — $ {\mathcal B}_{} $. Имеем, следовательно : $ x=0501=501 $, а $$ \begin{array}{lll} M_{\mathcal A}=3953,\ & {\mathbf D}_{\mathcal A}=829,\ & {\mathbf E}_{\mathcal A}=157 \ ; \\ M_{\mathcal B}=3233,\ & {\mathbf D}_{\mathcal B}=2299,\ & {\mathbf E}_{\mathcal B}=19 \ . \end{array} $$ По приведенной выше схеме резидент выполняет действия: $$x=501 \mapsto s=x^{{\mathbf D}_{\mathcal A}} \pmod{M_{\mathcal A}} =3860 \mapsto c=s^{{\mathbf E}_{\mathcal B}} \pmod{M_{\mathcal B}}=1759 \ , $$ т.е. в Центр поступит шифровка $ c=1759 $. Дешифрование этого сообщения и восстановление открытого текста из цифровой подписи, проводятся Центром по схеме: $$c=1759 \mapsto \tilde s= c^{{\mathbf D}_{\mathcal B}} \pmod{M_{\mathcal B}} = 627 \mapsto \tilde x= {\tilde s}^{{\mathbf E}_{\mathcal A}} \pmod{M_{\mathcal A}}= 3841 \ ,$$ дают, однако, вовсе не истинное значение $ x_{} $…

В чем дело? Попробуем действовать в обратном порядке: пусть сообщение идет от $ {\mathcal B}_{} $ к $ {\mathcal A}_{} $. $$x=501 \mapsto s_1=x^{{\mathbf D}_{\mathcal B}} \pmod{M_{\mathcal B}}=2453 \mapsto c_1=s_1^{{\mathbf E}_{\mathcal A}} \pmod{M_{\mathcal A}}= 2980 \ . $$ Резиденту приходит шифровка $ a_1=2980 $, дешифровав которую и извлекая из цифровой подписи открытый текст: $$2980 \mapsto \tilde s_1= c_1^{{\mathbf D}_{\mathcal A}} \pmod{M_{\mathcal A}} = 2453 \mapsto \tilde x_1= {\tilde s_1}^{{\mathbf E}_{\mathcal B}} \pmod{M_{\mathcal B}}= 501 \ , $$ то есть, на этот раз сообщение доставляется нормально!

Объяснение этой асимметрии скрыто в следующем. Дело в том, что поскольку $ M_{\mathcal A}>M_{\mathcal B} $, то в первом случае (письмо от $ {\mathcal A}_{} $ к $ {\mathcal B}_{} $) цифровая подпись $ s=3860 $ оказывается бóльшей $ M_{\mathcal B} $. Следовательно, действие алгоритма шифрования этой подписи $ c=s^{{\mathbf E}_{\mathcal B}} \pmod{M_{\mathcal B}} $ приводит сначала к «усечению» $ s_{} $ до величины меньшей $ M_{\mathcal B} $, т.е. до $$ \hat s=s \pmod{M_{\mathcal B}}=s-M_{\mathcal B}=627 \ , $$ а уже потом к вычислению $$c=\hat s^{{\mathbf E}_{\mathcal B}} \pmod{M_{\mathcal B}}=1759 \ . $$ Иными словами, у истинного значения цифровой подписи сразу же происходит потеря значимых битов. При дешифровании получатель $ {\mathcal B}_{} $ и восстанавливает как раз это усеченное значение $ \hat s $.

Если бы цифровая подпись $ s_{} $ удовлетворяла условию $ s<M_{\mathcal B} $, то этой проблемы не возникло. Это условие очевидно будет удовлетворено — для любого сообщения — при выполнении ограничения $$ {.} \mbox{модуль отправителя } \ < \ \mbox{ модуль получателя } \ , $$ что и проиллюстрировал пример обратной пересылки (письмо от $ {\mathcal B}_{} $ к $ {\mathcal A}_{} $).

Можно предложить несколько способов разрешения этой проблемы. Во-первых, из двух процедур — подписания сообщения и его шифрования — первой выполнять ту, которая связана с меньшим модулем. Таким образом, в приведенном только что примере, при пересылке сообщения Центру, резидент мог бы действовать по схеме $$x=501 \mapsto \hat{c}=x^{{\mathbf E}_{\mathcal B}} \pmod{M_{\mathcal B}}=2148 \ \mapsto \ \hat{s}=\hat{c}^{{\mathbf D}_{\mathcal A}} \pmod{M_{\mathcal A}}= 55 \ . $$ По получении $ \hat{s} $ Центр тоже должен поменять последовательность действий: $$\hat{s}=55 \ \mapsto \ \hat{a} = \hat{s}^{{\mathbf E}_{\mathcal A}} \pmod{M_{\mathcal A}} =2148 \ \mapsto \ x= \hat{a}^{{\mathbf D}_{\mathcal B}} \pmod{M_{\mathcal B}}=501 \ . $$ ♦

[1]. Gardner M. A new kind of cipher that would take millions of years to break. Scientific American. 1977. Vol. 237. N 2. P. 120-124.

[2]. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM. 1978. Vol. 21. N 2. P. 120-126.

[3]. Утешев А.Ю., Черкасов Т.М., Шапошников А.А. Цифры и шифры.СПб.: Изд-во СПбГУ, 2001.