получатель вычисляет и передаёт отправителю число B, определяемое последовательностью: D = C Kb mоd(P)
отправитель аннулирует свой шифр и отправляет полученную последовательность получателю E=D(X-1) mоd(P) E = D Fa mоd(P) где: Fa = Ka -1 получатель расшифровывает полученное сообщение M = E Fb mоd(P) где: Fb = Kb –1 Пример использования
Эта процедура ОШ может быть использована, например, для таких "экзотических" целей как игра в карты по телефону. Действительно, если игрок A желает "сдать" игроку B, скажем, 5 карт из 52 как при игре в покер, он зашифровывает обозначения всех карт и передает их игроку B: Ca = Ma Ka mоd(P) где I=1, 2, .. ,52
Игрок B выбирает из них 5, зашифровывает своим ключом 22 и возвращает игроку А: Da = Ca Kb mоd(P) где I=1, 2.... ,5
Игрок A снимает с этих 5 карт свой шифр и выдает их игроку B. Игрок B расшифровывает полученные карты: Ma = Ea Fb mоd (P)
При этом оставшаяся часть колоды C(6).... C(52) теперь находится у игрока B, но он не может раскрыть эти карты, т. к. они зашифрованы на ключе его партнера A. Остальные процедуры игры проделываются аналогично. Кpиптосистемы на основе эллиптических уpавнений
Эллиптические кpивые - математический объект, котоpый может опpеделен над любым полем (конечным, действительным, pациональным или комплексным). В кpиптогpафии обычно используются конечные поля. Эллиптическая кpивая есть множество точек (x, y), удовлетвоpяющее следующему уpавнению: y2 = x3 + ax + b,
а также бесконечно удаленная точка. Для точек на кpивой довольно легко вводится опеpация сложения, котоpая игpает ту же pоль, что и опеpация умножения в кpиптосистемах RSA и Эль-Гамаля. В pеальных кpиптосистемах на базе эллиптических уpавнений используется уpавнение y2 = x3 + ax + b mod p, где p - пpостое.
Пpоблема дискpетного логаpифма на эллиптической кpивой состоит в следующем: дана точка G на эллиптической кpивой поpядка r (количество точек на кpивой) и дpугая точка Y на этой же кpивой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G. Электронно-цифровая подпись Общие положения
При ведении деловой переписки, при заключении контрактов подпись ответственного лица является непременным аттрибутом документа, преследующим несколько целей:
Гарантирование истинности письма путем сличения подписи с имеющимся образцом; Гарантирование авторства документа ( с юридической точки зрения)
Выполнение данных требовани основывается на следующих свойствах подписи: подпись аутентична, то есть с ее помощью получателю документа можно доказать, что она принадлежит подписывающему; подпись неподделываема; то есть служит доказательством, что только тот человек, чей автограф стоит на документе, мог подписать данный документ, и никто иной. Подпись непереносима, то есть является частью документа и поэтому перенести ее на другой документ невозможно. Документ с подписью является неизменяемым. Подпись неоспорима.
Любое лицо, владеющее образцом подписи может удостоверится, что документ подписан вледельцем подписи.
Развитие современных средств безбумажного документооборота, средств электронных платежей немыслимо без развития средств доказательства подлинности и целостности документа. Таким средством является электронно-цифровая подпись (ЭЦП), которая сохранила основные свойства обычной подписи. Существует несколько методов посторения ЭЦП, а именно:
шифрование электронного документа (ЭД) на основе симметричных алгоритмов. Данная схема предусматривает наличие в системе третьего лица – арбитра, пользующегося доверием обеих сторон. Авторизацией документа в даной схеме является сам факт зашифрования ЭД секретным ключем и передача его арбитру. Использование ассиметричных алгоритмов шифрования. Фактом подписания документа является зашифрование его на секретном ключе отправителя. Развитием предыдущей идеи стала наиболее распространенныя схема ЭЦП – зашифрование окончательного результата обработки ЭД хеш-функцией при помощи ассиметричного алгоритма.
Кроме перечисленных, существуют и другие методы построения схем ЭЦП - групповая подпись, неоспариваемая подпись, доверенная подпись и др. Появление этих разновидностей обусловлено разнообразием задач, решаемых с помощью электронных технологий передачи и обработки электронных документов. Алгоритм DSA
В 1991 г. в США был опубликован проект федерального стандарта цифровой подписи - DSS (Digital Signature Standard, [DSS91], описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта была его патентная чистота. Предлагаемый алгоритм DSA, имеет, как и RSA, теоретико-числовой характер, и основан на криптографической системе Эль-Гамаля в варианте Шнорра . Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит. С момента опубликования проект получил много критических отзывов, многие из которых были учтены при его доработке. Одним из главных аргументов против DSA является то, что, в отличие от общей задачи вычисления дискретного логарифма, ее частный случай, использованный в данной схеме, мало изучен и, возможно, имеет существенно меньшую сложность вскрытия. Кроме того, стандарт не специфицирует способ получения псевдослучайных чисел, используемых при формировании цифровой подписи, и не указывает на то, что этот элемент алгоритма является одним из самых критичных по криптографической стойкости. Функции DSA ограничены только цифровой подписью, система принципиально не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно (в 10-40 раз) уступает ей при проверке подписи. Вместе с проектом DSS опубликован проект стандарта SHS (Secure Hash Standard), описывающий однонаправленную хэш-функцию SHA (Secure Hash Algorithm), рекомендованную для использования вместе с DSA. Хэш-функция SHA является модификацией алгоритма MD4, хорошо известного в криптографической литературе. Генерация ЭЦП При генерации ЭЦП используются параметры трех групп: общие параметры секретный ключ открытый ключ
Общие параметры необходимы для функционирования системы в целом. Секретный ключ используется для формирования ЭЦП, а открытый – для проверки ЭЦП. Общими параметрами системы являются простые целые числа p, q, g, удовлетворяющие следующим условиям: p: 2^511
q: простой делитель числа (p-1), который удовлетворяет условию 2^159 g: так называемый генератор, удовлетворяющий равенству g=h^((p-1)/q)mod p >1.
Парараметры p, q, g публикуются для всех участников обмена ЭД с ЭЦП. Секретный ключ x случайно выбирается из диапазона [1, q] и держится в секрете. Открытый ключ вычисляется: y=g^x mod p.
Также при описании данной схемы будут использоваться следующие обозначения и доролнительные параметры: m – входное сообщение пользователя для схемы с ЭЦП; k - случайное число, удовлетворяющее условию 0 Процесс генерации ЭЦП состоит из нескольких этапов: 1. Вычисляется хэш-код сообщения m h=H(m)
2. Из диапазона [1, q] случайным образом выбирается значение k и вычисляется r= (g^k mod p) mod q
3. Вычисляется S= (k^-1(h+xr)) mod q, где k^-1 удовлетворяет условию (k^-1*k) mod q =1
Значения r, s являются ЭЦП сообщения m и передаются вместе с ним по каналам связи. Проверка ЭЦП Пусть принято сообщение m1 и его подпись s1, r1. Проверка ЭЦП происходит следующим образом:
проверяется выполнений условий 0 w= s1^-1 mod q u1 = (H(m1)w) mod q u2 = ((r1/w) mod q v = (( g^u1y^u2) mod p ) mod q проверяется равенство v = r1
Если последнее равенство выполняется, то подпись принимается. В данном стандарте специфицируется также процедура генерации основных параметров системы и проводится доказательство того, что если v=r1, то m1=m, r1=r, s1=s. Стандарт на процедуры ЭЦП ГОСТ Р 34. 10-94
Отечественным стандартом на процедуры выработки и проверки ЭЦП является ГОСТ Р 34. 10-94. Схема ЭЦП, предложенная в данном стандарте, во многом напоминает подпись в DSA.
Цифровая подпись представляет собой два больших целых простых числа. Общедоступные параметры схемы ЭЦП (p, q, a) должны удовлетворять следующим условиям: p: 2^501 q: простой делитель числа (p-1), который удовлетворяет условию 2^254 a: 1
Секретный ключ x случайно выбирается из диапазона [1, q] и держится в секрете. Открытый ключ вычисляется: y=a^x mod p. Генерация ЭЦП Процесс генерации ЭЦП состоит из нескольких этапов: 1. Вычисляется хэш-код сообщения m h=H(m)
(хэш-функция, используемая в данном стандарте в соответствии с ГОСТ Р 34. 10-94), если h(m)(mod p) = 0, то h(m) присваевается значение 0…02551
2. Из диапазона [1, q] случайным образом выбирается значение k
3. вычисляется r= (a^k mod p) , r1=r(mod p); если r1=0, следует вернуться к предыдущему этапу и выработать другое значение k.
3. Вычисляется s= (xr1+kh(m))(mod p); если s=0, то необходимо выработать другое значение k.
Значения r1, s1 являются ЭЦП сообщения m и передаются вместе с ним по каналам связи. Проверка ЭЦП Проверка ЭЦП происходит следующим образом:
проверяется выполнений условий 0 Вычисляется значения z1=sv(mod p); z2=(q-r1)v(mod p). Вычисляется значение u=(a^z1y^z2(mod p))(mod q) проверяется равенство u = r1
Если последнее раенство выполняется, то подпись принимается.
Цифровые подписи, основанные на симметричных криптосистемах На первый взгляд, сама эта идея может показаться абсурдом. Действительно, общеизвестно, что так называемая “современная”, она же двухключевая криптография возникла и стала быстро развиваться в последние десятилетия именно потому, что ряд новых криптографических протоколов типа протокола цифровой подписи не удалось эффективно реализовать на базе традиционных криптографических алгоритмов, широко известных и хорошо изученных к тому времени. Тем не менее, это возможно. И первыми, кто обратил на это внимание, были родоначальники криптографии с открытым ключом У. Диффи и М. Хеллман, опубликовавшие описание подхода, позволяющего выполнять процедуру цифровой подписи одного бита с помощью блочного шифра. Прежде чем изложить эту идею, сделаем несколько замечаний о сути и реализациях цифровой подписи. Стойкость какой-либо схемы подписи доказывается обычно установлением равносильности соответствующей задачи вскрытия схемы какой-либо другой, о которой известно, что она вычислительно неразрешима. Практически все современные алгоритмы ЭЦП основаны на так называемых “сложных математических задачах” типа факторизации больших чисел или логарифмирования в дискретных полях. Однако, доказательство невозможности эффективного вычислительного решения этих задач отсутствует, и нет никаких гарантий, что они не будут решены в ближайшем будущем, а соответствующие схемы взломаны – как это произошло с “ранцевой” схемой цифровой подписи. Более того, с бурным прогрессом средств вычислительных техники “границы надежности” методов отодвигаются в область все больших размеров блока. Всего пару десятилетий назад, на заре криптографии с открытым ключом считалось, что для реализации схемы подписи RSA достаточно даже 128-битовых чисел. Сейчас эта граница отодвинута до 1024-битовых чисел – практически на порядок, – и это далеко еще не предел. Это приводит к необходимости переписывать реализующие схему программы, и зачастую перепроектировать аппаратуру. Ничего подобного не наблюдается в области классических блочных шифров, если не считать изначально ущербного и непонятного решения комитета по стандартам США ограничить размер ключа алгоритма DES 56-ю битами, тогда как еще во время обсуждения алгоритма предлагалось использовать ключ большего размера. Схемы подписи, основанные на классических блочных шифрах, свободны от указанных недостатков: во-первых, их стойкость к попыткам взлома вытекает из стойкости использованного блочного шифра, поскольку классические методы шифрования изучены гораздо больше, а их надежность обоснована намного лучше, чем надежность асимметричных криптографических систем; во-вторых, даже если стойкость использованного в схеме подписи шифра окажется недостаточной в свете прогресса вычислительной техники, его легко можно будет заменить на другой, более устойчивый, с тем же размером блока данных и ключа, без необходимости менять основные характеристики всей схемы – это потребует только минимальной модификации программного обеспечения; Итак, вернемся к схеме Диффи и Хеллмана подписи одного бита сообщения с помощью алгоритма, базирующегося на любом классическом блочном шифре. Предположим, в нашем распоряжении есть алгоритм зашифрования EK, оперирующий блоками данных X размера n и использующий ключ размером nK: |X|=n, |K|=nK. Структура ключевой информации в схеме следующая: секретный ключ подписи kS выбирается как произвольная (случайная) пара ключей k0, k1 используемого блочного шифра: kS=(k0, k1);
Страницы: 1, 2, 3, 4
