kiev-security.org.ua-Криптография.Цифровые подписи

IEEE Communication Magazine, May 1990 Omura J.K. Novel Applications of Cryptography in Digital Communications. 1976 г. Диффи и Хеллман [1] сделали революционный шаг в развитии открытых исследований в криптографии, дав определение криптографии с открытым ключом [2]. Сейчас существует много новых применений криптографии с открытым ключом. Большинство из них основаны на цифровых подписях. В этой статье впервые представлены обобщгнные сведения по цифровым подписям (ЦП), а затем обсуждаются некоторые применения, включая управление ключами для аппаратуры последовательного шифрования, электронную почту и обмен данными, управление доступом и регистрацию, проверку программного обеспечения и обнаружение вирусов, защиту банкнот от подделки, датчики обнаружения ядерных взрывов и системы формирования ответа на запрос типа "свой-чужой" в авиации. ЦИФРОВЫЕ ПОДПИСИ При быстром развитии вычислительной техники и цифровых сетей связи мы близки к достижению безбумажного электронного обмена, который давно предсказывался. Сегодня чрезвычайно возросли объгмы передаваемой и хранимой бумажной корреспонденции, и мы по-прежнему полагаемся на архивы и почту, по каналам которой передаются подписанные документы в опечатанных конвертах. В общем случае обычную подпись легко подделать и тяжело проверить. При существующем уровне технологии относительно легко сделать фотокопию подписи и нанести ег на документ, который данное лицо не подписывало. В то же время проверить подпись тяжело, не имея копии хорошо известной подписи. Для безбумажного обмена необходимо заменить ручные подписи цифровыми подписями, а конверты - шифрованием. Такие ЦП могут использоваться для подписи платгжных документов, контрактов и электронных сообщений всех видов. Желательно, чтобы ЦП имели следующие свойства: * подпись тяжело подделать * подпись легко проверить ЦП состоит из строки символов. Если бы чья-то ЦП всегда была одинаковой для каждого сообщения, ег было бы легко подделать, копируя строку символов. Следовательно, ЦП должна различаться при каждом использовании. Это достигается, если каждая ЦП является функцией подписываемого сообщения и временной метки. Для того чтобы быть уникальной для каждого подписывающего и защищгнной от подделки, ЦП должна также зависеть от некоторого секретного числа, уникального для подписывающего. Таким образом, защищгнная от подделки ЦП должна зависеть от сообщения и уникального секретного числа подписывающего. Лицо, проверяющее подпись, может и не знать этого числа. Механизм открытых ключей является единственным известным, обеспечивающий заданные свойства ЦП. Хорошо известны два способа, предложенные Ривестом, Шамиром и Адельманом (RSA) [3] и Эль Гамалем [4]. Эль Гамаль добавил механизм подписи к методу Диффи-Хеллмана, изобретателей криптографии с открытым ключом. Мы опишем основные идеи криптографии с открытым ключом и ЦП. Криптография с открытым ключом К.Шеннон в своей глубокой статье (1949) "Теория связи в секре тных системах" [5] высказал мысль, что "задача создания хорошего шифра заключается в отыскании сложных задач, зависящих от ряда других условий. Мы можем построить наш шифр таким образом, что его раскрытие эквивалентно решению некоторой трудогмкой задачи". Безопасность всех криптографических методов с открытыми ключами базируется на хорошо известных труднорешаемых задачах. Система обмена ключами Диффи-Хеллмана [1] и подписи Эль Гамаля [4] базируются на сложной задаче вычисления дискретных логарифмов в конечных полях, а RSA [3] - на сложности нахождения простых делителей больших целых чисел. В этой статье опущены технические подробности, и описаны основные идеи криптографии с открытым ключом. Особое внимание уделено новым применениям. Любой обычный алгоритм шифрования использует один ключ для шифрования и дешифрования. В обычной криптографической системе отправитель и предполагаемый получатель зашифрованных данных разделяют один и тот же ключ. Ключ является секретным и известен только тем пользователем, которые имеют доступ к зашифрованным данным. Алгоритмы с открытым ключом используют два ключа: один для шифрования, другой для дешифрования. Хотя оба ключа однозначно связаны друг с другом теоретически, на практике их можно рассматривать как "почти независимые", поскольку знание одного из ключей не приводит к раскрытию другого. Это означает, что вычислительно сложно найти один ключ из другого. В алгоритмах с открытым ключом можно зашифровать сообщение и не иметь возможности его расшифровать, и, наоборот, можно расшифровать принятое сообщение, но не знать, как оно было зашифровано. В данной статье переменные шифрования и дешифрования обозначаются заглавными буквами, а индексы обозначают владельца ключей. Например, пользователь А выработал ключи шифрования и дешифрования Еа и Da. Шифрование сообщения "DATA" на ключе Ea показывается так: Ea(DATA)=ENDATA, а дешифрование на ключе Da - Da(ENDATA)=DATA. Предполагается, что знание Da не раскрывает Ea и наоборот. Если опубликовать ключ шифрования, то любой пользователь может зашифровать сообщение на этом ключе, но только пользователи, обладающие соответствующим ключом дешифрования могут расшифровать эти сообщения. С другой стороны, если пользователь сохраняет в тайне ключ шифрования и публикует соответствующий ключ дешифрования, то любое лицо с помощью этого ключа может не только дешифровать сообщения, зашифрованные пользователем, но и убедиться в том, что сообщение не было изменено. Только пользователь, имеющий ключ шифрования, мог создать это сообщение. Это свойство, однозначно определяющее источник сообщения, позволяет пользователю, имеющему секретный ключ шифрования, посылать "подписанные" сообщения. Создание цифровых подписей Предположим, некто, скажем, Алиса, создагт свой собственный ключ шифрования Ea и соответствующий ключ дешифрования Da. Пусть Алиса держит в секрете Ea и публикует Da. Несекретный ключ дешифрования Алисы можно поместить в справочник, содержащий все несекретные (открытые) числа, доступные всем. Если Алиса хочет послать подписанное сообщение Бобу, она вычисляет известную хэш-функцию [6,7] сообщения, называемую иногда код MDC [8]. Сообщение М может быть произвольным, а хэш-функция сообщения, обозначаемая Н, имеет фиксированную длину, обычно около 512 бит. Любая хорошая хэш-функция обладает таким свойством, что нельзя найти два сообщения, преобразуемые в одну и ту же вычисленную хэш-функцию. Функция несекретна и известна всем. Подпись Алисы для сообщения М - это зашифрованная хэш-функция: S=Ea(H). зддддддддддддддддддддддддј ° сообщение ° юдддддддддддддддддддддддды H=хэш-функция сообщения S= подпись Алисы H - известная хэш-функция сообщения S - подпись Алисы (шифрование хэш-функции сообщения на секретном ключе шифрования Алисы Ea - секретная функция шифрования Алисы Da - открытая функция дешифрования Алисы, опубликованная в справочнике Рис.1а. Создание подписи Алисы Проверка цифровых подписей Когда Боб получает подписанное сообщение Алисы, он может проверить аутентичность подписи Алисы и целостность сообщения (рис.2). Боб вычисляет хэш-функцию полученного сообщения H'. Затем он бергт из справочника несекретный ключ дешифрования Алисы Da для получения хэш-функции Н, вычисленной Алисой: H=Da(S), и сравнивает H и Н'. Если обе функции совпадают, он делает выводы: - сообщение подписала Алиса; - сообщение не было изменено после того, как его подписала Алиса. Таким образом, не зная никаких секретных данных Алисы, Боб может проверить аутентичность ег продписи и целостность сообщения. Более того, он не может подделать подпись Алисы. зддддддддддддддддддддддддј ° сообщение ° юдддддддддддддддддддбддддѓ Проверка Бобом ° S ° юдддды 1. Вычислить хэш-функцию Н' сообщения. 2. Взять несекретную функцию дешифрования Алисы Da из справочника. 3. Дешифровать подпись Алисы, Da(S)=H, для получения хэш-функции сообщения, вычисленной Алисой. 4. Если Н'=Н, то проверяющий знает: - сообщение подписала Алиса; - сообщение не было изменено после того, как его подписала Алиса. Предполагается, что Боб может взять несекретную функцию дешифрования Алисы из справочника. Рис.1b. Проверка с помощью справочника Сертификационный центр Использование справочника можно заменить сертификационным центром (СС), который действует как нотариальная служба, заверяющая все открытые ключи дешифрования. Пусть СС имеет собственный секре тный ключ шифрования Eo и соответствующий несекретный ключ Do, известный всем. Do может быть опубликован в газете, телефонном справочнике или заложен в аппаратуре, проверяющей подписи. Алиса получает сертификат своего открытого ключа дешифрования Da, как показано на рис.1с. Сперва она идентифицирует себя СС (без обмана). Затем СС шифрует открытый ключ дешифрования Алисы для получения сертификата Ca=Eo(Da), который выдагтся Алисе. Поскольку каждый имеет ключ дешифрования СС Do, то из сертификата Са можно получить несекретный ключ дешифрования Алисы Da=Do(Ca). Более того, это лицо будет уверено в том, что ключ дешифрования принадлежит Алисе, поскольку только СС мог создать сертификат. зддддддддддддддддддддддддј ° сертификационный центр ° юдддддддддддддддддддддддды Da Ca=Eo(Da) Eo - секретная функция шифрования СС Do - открытая функция дешифрования СС, известная всем в системе Da - открытая функция дешифрования Алисы Ca - сертификат Алисы Примечание: при известном Са можно выполнить следующие операции Do(Ca)=Do(Eo(Da))=Da. Рис.1c. Создание сертификата Алисы Хотя здесь и не показано, предполагается, что имя Алисы также включается в сертификат, поэтому дешифрованное открытое число отождествляется с Алисой. Если Алиса имеет сертификат, она может добавить его к своим подписанным сообщениям. Это позволит Бобу (или кому-либо) проверить подпись Алисы без обращения к справочнику. Сертификат содержит открытую функцию дешифрования Алисы в защищгнном виде. В этом случае подписанное сообщение Алисы состоит из сообщения М, подписи S и сертификата Алисы Са. Проверка Бобом сообщения показана на рис. 1d. Она такая же как и на рис.1b, но открытый ключ дешифрования Da Боб получает из сертификата. зддддддддддддддддддддддддј ° сообщение ° юдддддддддддддддддддбддддѓ Проверка Бобом ° S ° цддддѓ ° Ca ° юдддды 1. Вычислить хэш-функцию Н' сообщения. 2. Вычислить несекретную функцию дешифрования Алисы Do(Ca)=Da. 3. Дешифровать подпись Алисы, Da(S)=H, для получения хэш-функции сообщения, вычисленной Алисой. 4. Если Н'=Н, то проверяющий знает: - сообщение подписала Алиса; - сообщение не было изменено. Рис.1d. Проверка с помощью сертификата