Автор: Андрей Винокуров

Данная статья является продолжением серии статей автора о реализациях и использовании Российского стандарта шифрования [1,2,3] и об архитектуре и режимах использования блочных шифров [4], и посвящена проблемам подтверждения подлинности и авторства сообщений. Статья была написана осенью 1995 года – почти три года назад, и подготовлена для публикации в журнале «Монитор», где у автора вышли 2 статьи по криптографии. Однако по разным причинам статья тогда не была опубликована – сначала из-за нехватки времени на ее окончательную доводку и подготовку кодов–примеров к статье, а затем из-за закрытия «Монитора».

Введение

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

Так как информация имеет нематериальный характер, массивы данных не несут на себе никаких отпечатков, по которым можно было бы судить об их прошлом – о том, кто является автором, о времени создания, о фактах, времени и авторах вносимых изменений. Модификация информационного массива не оставляет осязаемых следов на нем и не может быть обнаружена обычными методами. «Следы модификации» в той или иной форме могут присутствовать только на материальных носителях информации – так, специальная экспертиза вполне способна установить, что сектор X на некоей дискете был записан позже всех остальных секторов с данными на этой же дорожке дискеты, и эта запись производилась на другом дисководе. Указанный факт, будучи установленным, может, например, означать, что в данные, хранимые на дискете, были внесены изменения. Но после того, как эти данные будут переписаны на другой носитель, их копии уже не будут содержать никаких следов модификации. Реальные компьютерные данные за время своей жизни многократно меняют физическ ую основу представления и постоянно кочуют с носителя на носитель, в силу чего их не обнаружимое искажение не представляет серьезных проблем. Поскольку создание и использование информационных массивов практически всегда разделены во времени и/или в пространстве, у потребителя всегда могут возникнуть обоснованные сомнения в том, что полученный им массив данных создан нужным источником и притом в точности таким, каким он дошел до него.

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

• подлинность – он пришел к потребителю именно таким, каким был создан источником и не претерпел на своем жизненном пути несанкционированных изменений;
• авторство – он был создан именно тем источником, каким предполагает потребитель.

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

1. Задача аутентификации данных.

На первый взгляд может показаться, что данная задача решается простым шифрованием. Действительно, если массив данных зашифрован с использованием стойкого шифра, такого, например, как ГОСТ 28147–89, то для него практически всегда будет справедливо следующее:

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

Тем не менее, использование шифрования в системах обработки данных само по себе неспособно обеспечить их аутентичности по следующим причинам:

1. Изменения, внесенные в зашифрованные данные, становятся очевидными после расшифрования только в случае большой избыточности исходных данных. Эта избыточность имеет место, например, если массив информации является текстом на каком-либо человеческом языке. Однако в общем случае это требование может не выполняться – если случайная модификация данных не делает их недопустимым для интерпретации со сколько-нибудь значительной долей вероятности, то шифрование массива не обеспечивает его подлинности. Говоря языком криптологии, аутентичность и секретность суть различные свойства криптосистем. Или, более просто: свойства систем обработки информации обеспечивать секретность и подлинность обрабатываемых данных в общем случае могут не совпадать.

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

Таким образом, существование проблемы подтверждения подлинности и авторства массивов данных, отдельной от задачи обеспечения их секретности, не вызывает сомнения. В последующих разделах настоящей статьи излагаются подходы к ее решению, базирующиеся на использовании классических блочных шифров. В разделе 2 рассматриваются подходы к решению задачи подтверждения подлинности данных, а в разделе 3 – к задаче подтверждения их авторства. В принципе, для решения указанных задач может быть использован любой традиционный блочный криптографический алгоритм. В компьютерных кодах, прилагаемых к настоящей статье, автор использует наиболее знакомый и близкий ему шифр – криптоалгоритм ГОСТ 28147–89.

2. Контроль неизменности массивов данных.

2.1. Задача имитозащиты данных.

Под имитозащитой данных в системах их обработки понимают защиту от навязывания ложных данных. Как мы уже выяснили, практически всегда на некоторых этапах своего жизненного цикла информация оказывается вне зоны непосредственного контроля за ней. Это случается, например, при передаче данных по каналам связи или при их хранении на магнитных носителях ЭВМ, физический доступ к которым посторонних лиц исключить почти никогда не представляется возможным. Только если целиком заключить линию связи в кожух из твердого металла, внутрь кожуха закачать газ под давлением и высылать роту автоматчиков прочесывать местность каждый раз, когда в секции такой системы будут зафиксированы малейшие изменения давления, как это, по слухам, делают Российские спецслужбы, ответственные за правительственную связь, будет хоть какая-то гарантия неприкосновенности передаваемых данных, не всегда, впрочем, достаточная. Но подобный подход многократно удорожает стоимость каналов связи, ведь стоимость кожуха, защищенных помещений для обработки сигнала и услуг вооруженных людей на много порядков превышает стоимость проложенной витой пары проводов. И как в этом случае быть с электромагнитным сигналом? – ведь не до всех мест можно дотянуть провод, а такой сигнал, даже если это узконаправленный лазерный пучок, не говоря об обычном радиосигнале, не спрячешь в кожух.

Таким образом, физически предотвратить внесение несанкционированных изменений в данные в подавляющем большинстве реальных систем их обработки, передачи и хранения не представляется возможным. Поэтому крайне важно своевременно обнаружить сам факт таких изменений – если подобные случайные или преднамеренные искажения будут вовремя выявлены, потери пользователей системы будут минимальны и ограничатся лишь стоимостью «пустой» передачи или хранения ложных данных, что, конечно, во всех реальных ситуациях неизмеримо меньше возможного ущерба от их использования. Целью злоумышленника, навязывающего системе ложную информацию, является выдача ее за подлинную, а это возможно только в том случае, если сам факт такого навязывания не будет вовремя обнаружен, поэтому простая фиксация этого факта сводит на нет все усилия злоумышленника. Подведем итог – под защитой данных от несанкционированных изменений в криптографии понимают не исключение самой возможности таких изменений, а набор методов, позволяющих надежно зафиксировать их факты, если они имели место.

Попытаемся найти универсальные подходы к построению такой защиты. Прежде всего, в распоряжении получателя информации должна быть процедура проверки или аутентификации A(T), позволяющая проверить подлинность полученного массива данных T. На выходе указанная процедура должна выдавать одно из двух возможных булевых значений – массив данных опознается как подлинный, либо как ложный: A(T)[]{0,1} для любого допустимого T. Условимся, что значение 1 соответствует подлинному массиву данных, а значение 0 – ложному. Процедура аутентификации должна обладать следующими свойствами, ограничивающими возможность злоумышленника подобрать массив данных T1, отличающийся от подлинного массива T (T[]T1), который бы тем не менее был бы этой процедурой опознан как подлинный (A(T1)=1):

• у злоумышленника не должно быть возможности найти такое сообщение иначе как путем перебора по множеству допустимых сообщений – последняя возможность есть в его распоряжении всегда;
• вероятность успешно пройти проверку на подлинность у случайно выбранного сообщения T* не должна превышать заранее установленного значения p.

Теперь вспомним про универсальность конструируемой схемы защиты, которая, в частности, означает, что схема должна быть пригодной для защиты любого массива данных T из достаточно широкого класса. Однако, если реализовать схему буквально, т.е. использовать для проверки в точности то сообщение, которое отправитель должен передать получателю, принцип универсальности может придти в противоречие со вторым требованием к процедуре проверки. Действительно, исходя из этого принципа мы можем потребовать, чтобы все возможные сообщения T были допустимыми, что совершенно явно нарушит второе требование к функции проверки. Для того, чтобы их примирить, в схему необходимо ввести дополнительные шаги – преобразование данных отправителем и обратное преобразование получателем. Отправитель выполняет преобразование данных с использованием некоторого алгоритма F: T'=F(T). Тогда, помимо процедуры аутентификации, в распоряжении получателя должна быть процедура G восстановления исходных данных: T=G(T'). Весь смысл этих преобразований заключается в том, чтобы множество преобразованных сообщений {T'}, взаимно однозначно отображающееся на множество допустимых исходных сообщений {T}, было неизвестно злоумышленнику, и вероятность случайно угадать элемент из этого множества была достаточно мала для того, чтобы ее можно было не принимать во внимание.

Последнее требование в сочетанием с принципом универсальности однозначно приводит к необходимости внесения определенной избыточности в сообщение, что означает попросту тот факт, что размер преобразованного сообщения должен быть больше размера исходного сообщения на некоторую величину, как раз и составляющую степень избыточности: |T'|–|T|=[]. Очевидно, что чем больше эта величина, тем меньше вероятность принять случайно взятое сообщение за подлинное – эта вероятность равна 2–[]. Если бы не требование внесения избыточности, в качестве функций преобразования F и G данных могли бы использоваться функции зашифрования и расшифрования данных на некотором ключе K: F(T)=EK(T), G(T')=DK(T'). Однако при их использовании размер массива зашифрованных данных T' равен размеру массива исходных данных T: |T'|=|T|, поэтому метод здесь не подходит.

Наиболее естественно реализовать алгоритм преобразования с внесением избыточности простым добавлением к исходным данным контрольной комбинации фиксированного размера, вычисляемой как некоторая функция от этих данных: T'=F(T)=(T,C), C=f(T), |C|=[]. В этом случае выделение исходных данных из преобразованного массива заключается в простом отбрасывании добавленной контрольной комбинации C: T=G(T')=G(T,C)=T. Проверка на подлинность заключается в вычислении для содержательной части T полученного массива данных T' значения контрольной комбинации C'=f(T) и сравнении его с переданным значением контрольной комбинацией C. Если они совпадают, сообщение считается подлинным, иначе – ложным:

Теперь рассмотрим свойства, которым должна удовлетворять функция выработки контрольной комбинации f:

1. Эта функция должна быть вычислительно необратимой, то есть не должно существовать способа подобрать массив данных T под заданную контрольную комбинацию C иначе как перебором по пространству возможных значений T.
2. Эта функция не должна быть известна злоумышленнику – у него не должно быть способа вычислить контрольную комбинацию C ни для какого массива данных T. Это требование по сути означает, что функция f должна быть секретной, рассмотрим его подробнее:
   • во-первых, в соответствии с общепризнанным в криптографии принципом Кирхгоффа требование секретности функции выработки контрольной комбинации следует заменить на применение открытой функции, использующей вектор секретных параметров (ключ) – точно так же, как это делается при построении шифров: C=f(T)=fK(T).
   • во-вторых, оказывается, что в отдельных случаях это требование можно существенно ослабить. Дело в том, что истинная цель этого пункта – исключить для злоумышленника возможность отправить ложное сообщение T1, снабдив его корректно вычисленной контрольной комбинацией C1=f(T1). Этого можно достичь двумя следующими способами:
     1. с помощью использованного выше требования секретности функции вычисления контрольной комбинации или зависимости ее от вектора секретных параметров (ключа);
     2. с помощью организации такого протокола использования средств защиты, который бы исключал возможность подобного навязывания ложных данных.

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

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

2.2 Подходы к контролю неизменности данных.

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

1. Выработка MAC – Message Authentification Code – кода аутентификации сообщений. Этот подход заключается в том, что контрольная комбинация вычисляется с использованием секретного ключа с помощью некоторого блочного шифра. Важно, что на основе любого такого шифра можно создать алгоритм вычисления MAC для массивов данных произвольного размера. В литературе МАС иногда не вполне корректно называется криптографической контрольной суммой, или, что более точно, криптографической контрольной комбинацией. Данный подход к аутентификации данных общепризнан и закреплен практически во всех криптографических стандартах - имитовставка, формируемая согласно ГОСТ 28147-89 является типичным образцом MAC.
2. Выработка MDC – Маnipulation Detection Code – кода обнаружения манипуляций (с данными). Для вычисления MDC для блока данных используется так называемая необратимая функция сжатия информации, в литературе также называемая односторонней функцией, функцией одностороннего сжатия (преобразования) информации, криптографической хэш–функцией, или просто хэш–функцией. Понятно, что ее необратимость должна носить вычислительный характер:
   • вычисление прямой функции Y=f(X) легко осуществимо вычислительно;
   • вычисление обратной функции X=f–1(Y) неосуществимо вычислительно, то есть не может быть выполнено более эффективным путем, чем перебором по множеству возможных значений X;

Оба способа вычисления контрольной комбинации – MDC и MAC принимают в качестве аргумента блок данных произвольного размера и выдают в качестве результата блок данных фиксированного размера.

В следующей ниже таблице 1 приведены сравнительные характеристики обоих подходов:

Таблица 1. Сравнительные характеристики подходов к решению задачи контроля неизменности массивов данных.

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

Казалось бы, преимущества первого подхода настолько очевидны, что второй подход не сможет найти себе применения. Однако это не так – использование MAC требует, чтобы предварительно между участниками информационного обмена были распределены ключи. Если же этого не произошло, для его реализации необходим специальный канал, обеспечивающий секретность и подлинность передаваемой информации, по которому параллельно с передачей данных по незащищенному каналу будут передаваться ключи. Для передачи же MDC требуется канал, обеспечивающий только подлинность передаваемых данных, требование секретности отсутствует, и это делает данный метод предпочтительным при одноразовой передаче данных: основная информация передается по обычному незащищенному каналу, а MDC сообщается отправителем получателю по каналу, который может прослушиваться но не может быть использован для навязывания ложных данных – например, голосом по телефону – если участники обмена лично знакомы и хорошо знают голоса друг друга. Кроме того, подход на осн

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

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

2.2. Выработка кода аутентификации сообщений.

Выработка кода аутентификации сообщений с использованием процедуры криптографического преобразования данных официально или полуофициально закреплена во многих стандартах на алгоритмы шифрования. Так, например, в различных комментариях к стандарту шифрования США рекомендуется использовать DES для выработки контрольной комбинации [5]. Российский стандарт шифрования ГОСТ 28147 89 [6] явным образом предусматривает режим выработки имитовставки, которая является не чем иным, как образцом MAC.

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

третьего свойства не требуется, так как при этом преобразование всегда выполняется в одну сторону. Кроме того криптостойкость алгоритма преобразования может быть несколько ниже, чем при шифровании, и это не приведет к снижению надежности всей схемы. Действительно, при выработке MAC в распоряжении криптоаналитика есть только один блок данных – MAC, который является функцией сразу всех блоков исходного текста, а при зашифровании в его распоряжении есть набор блоков шифротекста, каждый из которых зависит только от одного блока исходного текста. Очевидно, в первом случае его задача существенно сложнее. Именно по этой причине в ГОСТе 28147–89 для выработки имитовставки используется упрощенный 16-раундовый цикл преобразования, тогда как для шифрования – полный 32-раундовый.

2.3. Выработка кода обнаружения манипуляций.

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

Существует большое количество возможных подходов к построению вычислительно необратимых функций, практически всегда самым трудным является обоснование свойства необратимости предложенной функции. Однако есть класс способов, где такое свойство не нуждается в доказательстве, оно просто следует из характеристик примененного метода – это построение функций одностороннего преобразования на основе классических блочных шифров. Данный подход известен достаточно давно и изложен в ряде работ, из русскоязычных отметим [7], в его основе лежит тот факт, что уравнение зашифрования блока данных по циклу простой замены Y=EK(X) вычислительно неразрешимо относительно ключа K – это является неотъемлемым свойством любого действительно стойкого шифра. Даже при известных открытом (X) и зашифрованном (Y) блоках ключ K не может быть определен иначе как перебором по множеству возможных значений. Алгоритм выработки контрольной комбинации для массива данных T следующий:

ключи также в общем случае различны – вероятность встретить пару ключей, переводящих одновременно несколько пар одинаковых блоков открытых текстов в пары одинаковых блоков шифротекстов стремительно убывает с ростом числа этих пар. Поэтому обнаружение побочного ключа криптоаналитиком при дешифровании сообщения не является его особым успехом, так как с вероятностью, незначительно отличающейся от 1, на этом найденном ключе он не сможет правильно расшифровать никаких других блоков шифротекста. Совершенно иное дело в алгоритме выработки MDC – здесь обнаружение побочного ключа означает, что злоумышленник подобрал такой ложный, то есть отсутствующий в сообщении блок данных, использование которого приводит к истинному MDC исходного массива данных.

Для того, чтобы уменьшить вероятность навязывания ложных данных через нахождение побочных ключей, в шагах криптографического преобразования применяются не сами блоки исходного сообщения, а результат их расширения по некоторой схеме. Под схемой расширениея здесь понимается процедура построения блоков данных большего размера из блоков данных меньшего размера. Примером может служить, например, функция расширения, в которой выходной блок строится из байтов (или 2-,4-,... и т.д. -байтовых слов) исходного блока, перечисляемых в различном порядке. Указанное расширение стоит применять, если размер ключа использованного шифра в несколько раз превышает размер его блока данных. Так, для алгоритма DES, с размером блока данных 64 бита и ключа 56 бит в расширении нет необходимости. Если в схеме используется алгоритм ГОСТ 28147–89 с размером блока 64 бита и размером ключа 256 бит, стоит использовать 64- или 128-битные блоки исходного текста и расширять их до размеров 256 бит. Пример функции расширения 128-битового блока в 256-битовый может быть, например, следующим:

3 Цифровая подпись на основе традиционных блочных шифров.

На первый взгляд, сама эта идея может показаться абсурдом. Действительно, общеизвестно, что так называемая «современная», она же двухключевая криптография возникла и стала быстро развиваться в последние десятилетия именно потому, что ряд новых криптографических протоколов типа протокола цифровой подписи, в которых возникла острая необходимость в связи с проникновением электронных технологий в новые сферы, не удалось реализовать на базе традиционных криптоалгоритмов, широко известных и хорошо изученных к тому времени. Тем не менее, это возможно. И первые, кто обратил внимание на такую возможность, были … родоначальники криптографии с открытым ключом У.Диффи (W.Diffie) и М.Е.Хеллман (M.E.Hellman). В своей работе [8] они опубликовали описание подхода, позволяющего выполнять процедуру цифровой подписи одного бита с помощью блочного шифра. Прежде чем изложить эту изящную идею, сделаем несколько замечаний о сути и реализациях цифровой подписи.

2.4. Что такое цифровая подпись.

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

Собственно говоря, указанных трех алгоритмов достаточно для реализации схемы цифровой подписи, однако на практике в схемы добавляют еще один алгоритм – функцию выработки хэш–блока для подписываемого массива данных T. Большинство криптографических алгоритмов оперируют блоками данных фиксированного размера, а массивы большего размера обрабатывают по частям, что необходимо для обеспечения эффективности и надежности этих схем. Если такой же подход использовался при выработке цифровой подписи, блоки массивов информации подписывались бы отдельно друг от друга, и размер подписи оказался бы сравнимым с размером подписываемого массива данных, что по вполне понятным причинам не удобно. Поэтому в практических схемах ЭЦП подписывается не само сообщение, а его хэш–код, то есть результат вычисления функции необратимого сжатия для этого массива, который имеет фиксированный размер. Таким образом, в схему ЭЦП добавляется четвертый алгоритм:

4. Алгоритм H вычисления необратимой хэш–функции для подписываемых массивов:
h=H(T).

Алгоритм вычисления хэш–функции и прочие алгоритмы схемы не зависят друг от друга и согласуются только по размеру блоков, которыми они оперируют. Это позволяет при необходимости менять в схеме подписи способ вычисления хэш–значений.

Для работоспособной схемы электронно-цифровой подписи необходимо выполнение следующих условий:

• никто, кроме лица, обладающего секретным ключом подписи KS, не может корректно подписать заданное сообщение T;
  Поскольку сторона, проверяющая подпись, обладает открытым ключом KC проверки подписи, из указанного свойства следует, что не должно существовать вычислительно эффективного алгоритма вычисления секретного ключа KS по открытому KC.
• никто, включая лицо, обладающее ключом подписи, не в состоянии построить сообщение T', подходящее под наперед заданную подпись s.

При предложении какой-либо схемы подписи оба эти свойства необходимо доказывать, что делается обычно доказательством равносильности соответствующей задачи вскрытия схемы какой-либо другой, о которой известно, что она вычислительно неразрешима. Практически все современные алгоритмы цифровой подписи и прочие схемы «современной криптографии» основаны на так называемых «сложных математических задачах» типа факторизации больших чисел или логарифмирования в дискретных полях. Однако доказательство невозможности эффективного вычислительного решения этих задач отсутствует, и нет никаких гарантий, что они не будут решены в ближайшем будущем, а соответствующие схемы взломаны – как это произошло с «ранцевой» схемой цифровой подписи [9]. Более того, с бурным прогрессом средств вычислительных техники «границы надежности» методов отодвигаются в область все больших размеров блока. Всего пару десятилетий назад, на заре криптографии с открытым ключом считалось, что для реализации схемы подписи RSA достаточно 128- или даже битовых чисел. Сейчас эта граница отодвинута до 1024-битовых чисел – практически на порядок, – и это далеко еще не предел. Надо ли объяснять, что с каждой такой «подвижкой» приходится перепроектировать аппаратуру и переписывать программы, реализующие схему. Ничего подобного нет в области классических блочных шифров, если не считать изначально ущербного и непонятного решения комитета по стандартам США ограничить размер ключа алгоритма DES 56-ю битами, тогда как еще во время обсуждения алгоритма предлагалось использовать ключ большего размера [5]. Схемы подписи, основанные на классических блочных шифрах, свободны от указанных недостатков:

• во-первых, их стойкость к попыткам взлома вытекает из стойкости использованного блочного шифра;
  Надо ли говорить, что классические методы шифрования изучены гораздо больше, а их надежность обоснована неизмеримо лучше, чем надежность методов «современной криптографии».
• во-вторых, даже если стойкость использованного в схеме подписи шифра окажется недостаточной в свете прогресса вычислительной техники, его легко можно будет заменить на другой, более устойчивый, с тем же размером блока данных и ключа, без необходимости менять основные характеристики всей схемы – это потребует только минимальной модификации программного обеспечения;