УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу КРИПТОГРАФИЯ


ЦИФРОВАЯ ПОДПИСЬ

Активная атака: подмена открытого текста

П

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

\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, можно обнаружить одинаковые блоки. Этот факт свидетельствует о том, что и соответствующие блоки открытого текста должны быть одинаковыми. Так оно и есть — открытым текстом здесь является (в кодировке, приведенной ЗДЕСЬ ) отрывок из стихотворения Ф.И.Тютчева:

Т а к в ж и з н и е с т ь м г н о в е н и я
19 01 11 00 00 03 00 00 07 09 08 14 09 00 00 06 18 19 29 00 00 13 04 14 15 03 06 14 09 32
И х т р у д н о п е р е д а т ь
00 09 22 00 19 17 20 05 14 15 00 16 06 17 06 05 01 19 29 00
О н и с а м о з а б в е н и я
15 14 09 00 00 00 00 00 18 01 13 15 08 01 02 03 06 14 09 32

З е м н о г о б л а г о д а т ь
00 00 08 06 13 14 15 04 15 00 02 12 01 04 15 05 01 19 29 00

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

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

«Мюллер не спал. Он только что получил сообщение из центра дешифровки: шифр русской радистки совпадал с шифром, который пришел в Берн. Таким образом, предположил Мюллер, русский резидент начал искать новую связь…

… И он показал шифровку, отправленную с Плейшнером в Берн.

А вот это — провал, — понял Штирлиц. — Это — крах. Я оказался идиотом. Плейшнер или трус, или растяпа, или провокатор.»

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

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

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

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

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

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

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

Сам процесс выделения из исходного текста некоторой его «выжимки» называется хешированием2). Хеширование используется для решения разных задач, связанных с обработкой информации, в том числе для ее поиска, сортировки или контроля за целостностью при пересылке. Каждый человек, переводивший с иностранного языка, применял хеширование при поиске в словаре значения незнакомого слова:

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, т.е. для одного образа существует по крайней мере два прообраза. Поэтому в дальнейшем, говоря об обратимости хеш-функции, будем иметь в виду задачу определения всех прообразов данного значения этой функции.

Будем говорить о наличии коллизии3), если

h(x)=h(\tilde x) \quad npu \ x \ne \tilde x \ .

В начале пункта об атаках мы предположили, что противнику известны методы контроля за целостностью пересылаемого сообщения. Иначе говоря, следует предполагать, что и алгоритм вычисления значений функции хеширования ему известен; допустим, однако, что он не в состоянии изменить значение функции хеширования, вычисленное для истинного сообщения и сопровождающее это истинное сообщение4). Последнее условие ограничивает «свободу действий» при подлоге: подменить 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);
д) трудностью «попадания двух снарядов в одну воронку»: очень трудоемко обнаружить вообще любые коллизии.

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

В чем смысл условия д)? Для объяснения этого нам придется отказаться от «презумпции5) невиновности» самого автора сообщения. Предположим, что этот автор хочет сжульничать: отправить такое сообщение, чтобы в дальнейшем иметь возможность отказаться подтвердить (т.е. отвечать за) его содержание. Для этого в сообщение им вставляется блок 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 где \ H_j= H_{j-1} \oplus \left[ H_{j-1}^{x_j} \pmod{\tilde M} \right] \quad для \ 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_{} либо наличием в открытом тексте орфографических или смысловых ошибок6), либо же — если для кодирования открытого текста применяются коды, исправляющие ошибки, — изменяя биты этой кодировки, как бы имитируя действие технических помех на канале связи. Для всех этих модификаций вычисляются значения хеш-функции:

\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_{} владелец ключа может преобразовать в число 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_{} называется цифровой подписью7) сообщения x_{}. (В конце пункта это определение будет модифицировано.)

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

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

П

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

s={\scriptstyle 1671786115038084424601527138916839824543690103235831121783503844692906265544879223711449050957860865566224965779748400040570220373} \ .

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

M= {\scriptstyle 114381625757888867669325779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541} \ :

06 09 18 19 20 00 19 15 12 22 05 18 00 23 09 14 19 00 15 14 05 00 08 21 14 04 18 05 04 00 04 15 12 12 01 18 19
f i r s t s o l v e r w i n s o n e h u n d r e d d o l l a r s

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

Можно, наконец, «продублировать» подпись 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 \}. Число

\tilde s = \left(h(x) \right)^{\mathbf D} \pmod{M}

называется цифровой подписью сообщения x_{}.

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

По получении сообщения — открытого текста x_{}, сопровождающегося цифровой подписью \tilde s, — получатель вычисляет \tilde 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}, то этой проблемы не возникло. Это условие очевидно будет удовлетворено — для любого сообщения — при выполнении ограничения

{.}модуль отправителя \ < модуль получателя \ ,

что и проиллюстрировал пример обратной пересылки (письмо от {\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.

1) Чтобы добиться такого эффекта, при кодировании пришлось вставить несколько дополнительных пробелов.
2) hash (англ.) — рубить, крошить; беспорядочная путаница.
3) collisio (лат.) — столкновение.
4) Обеспечить такое препятствие можно с помощью алгоритма, рассмотренного в следующем ПУНКТЕ.
5) præsumptio (лат.) — предположение.
6) меняя и на или как это показано у Бомарше…
7) digital signature (англ.).
8) Бессмыслица, непонятный набор слов; происходит от abracadabra (лат.) — магического слова, употреблявшегося в древнем Риме как заклинание против лихорадки.

2017/10/17 10:12 редактировал au