Приведем сначала классическое описание схемы, чтобы потом увидеть, в каком направлении происходили ее модификации.

Для функционирования схемы выбирается большое простое число р и примитивный корень по модулю р. Числа эти несекретные и должны быть известны как подписывающему сообщение (пользователь A), так и проверяющим подпись под этим сообщением (пользователь B).

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

1. - долговременный секретный ключ подписи, выбирается случайно из указанного интервала и хранится в секрете.

2. - разовый секретный ключ подписи, конкретного сообщения, НОД .

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

1. - открытый ключ подписи, вычисляется и сообщается всем проверяющим подпись пользователя а.

2. - составляет правую из двух частей (r,s) подписи.

Подписываемое сообщение должно быть представлено числом M из интервала [0,р-1]. (Далее в качестве M будет также рассматриваться значение функции хэширования Н от сообщения.)

Процедура подписи сообщения M следующая.

1. Пользователь а выбирает случайное число из интервала таким образом, чтобы выполнялось условие НОД

2. Вычисляет, то есть число, удовлетворяющее сравнению . Именно для разрешимости этого сравнения при выборе наложено ограничение его временной простоты C(p-l).

3. Вычисляет первую часть подписи .

4. Вычисляет вторую часть подписи по формуле

.

На этом процедура выработки подписи (r,s) к сообщению M заканчивается, и эти данные сообщаются всем проверяющим подпись.

Процедура проверки данных , , такова (черта над буквами поставлена потому, что поступившие на проверку данные могут не совпадать с оригинальными).

1. По полученным данным ,, и имеющемуся у проверяющего открытому ключу подписывающего вычисляются величины и .

2. В случае выполнения равенства =, считается, что , , и подпись верная.

Для объяснения схемы подписи рассмотрим проверяемое сравнение , решением которого и являются числа r и s. После подстановки значений и r оно примет вид

По свойствам сравнений (*) последнее сравнение эквивалентно сравнению по модулю (p-l) вида

).

Именно из этого сравнения подписывающий вычисляет величину .

Стойкость метода зависит во многом от сложности вычисления дискретных алгоритмов в GF(р). Так, с этой задачей злоумышленник сталкивается при определении секретного ключа из наблюдаемых данных M, r и s, так как из известного ему соотношения следует или . В случае, если ему удастся найти , то это будет полное вскрытие схемы цифровой подписи, и злоумышленник может выдавать себя за пользователя A. Отсюда следует, что нужно очень осторожно выбирать простое число р, чтобы не выбрать такое, для которого разработаны противником или известны быстрые методы вычисления дискретных логарифмов. (Например, в силу метода Полига-Хеллмана, когда (p-l) имеет только "маленькие" делители [35].)

В случае, если злоумышленник получил в свое распоряжение N наборов данных , (), то он сталкивается с решением системы из N сравнений от N+1 неизвестного , ,…,, которая является неопределенной и имеет экспоненциальное число решений. Но в случае повторения какого-нибудь разового ключа , долговременный ключ может быть определен из этой системы однозначно.

Может оказаться более простым, чем нахождение дискретных логарифмов, способ нахождения злоумышленником пары (r,s) из соотношения, но пока такого способа не известно.

В [115] показано, что схема Эль Гамаля допускает возможность выработки ложных сообщений и подписей к ним, удовлетворяющих соотношению (Existential forgery), но получаемые при этом сообщения являются неосмысленными. Показано, что если злоумышленник имеет истинную тройку, тo он может получить подпись () из соотношений,

,

к сообщению вида

где а, B, C выбираются произвольно, но так, чтобы существовал обратный эксперимент к (). Правильные подписи могут быть получены и без знания истинных данных , что следует при а = 0. В этом случае имеют вид

,, .

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

Представление сообщения M через числа r и s подписи неоднозначно. Например [82], при р=7, k=5, x=5 и M=3 сравнению удовлетворяют пары вида (r,s) вида (2.1) и (1.2). Число возможных подписей (r,s) равно р², а число возможных сообщений М только р. Таким образом, каждое сообщение имеет много подписей, но любая подпись подписывает только одно сообщение.

2 9 Управление ключами

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

- генерация ключей (key generation);

- распределение ключей (key distribution);

- хранение ключей (key storage);

- уничтожение ключей (key deiition);

- регистрация пользователей (user registration).

Рассмотрим последовательно некоторые из них.

Генерация. Стойкость криптографических алгоритмов, описание которых, согласно принципу Керкхоффcа может быть известно и злоумышленнику, основывается на безопасности ключей. Поэтому, как подчеркивается в [85], если вы используете слабый алгоритм для генерации ключей, то и вся система становится не безопасной. Противнику достаточно анализировать не саму криптосистему, а алгоритм генерации ключей.

Первое, от чего стоит предостеречь, это от сокращения возможных значений ключей, путем выбора в качестве них, например, осмоленных, легко запоминающихся слов и выражений, сокращения алфавита знаков ключей и т.д. Это приводит к возможности полного перебора ключей с помощью современной вычислительной техники, производительность которой постоянно растет (См. www.top500.org ). Конечно, все зависит от модели предполагаемого злоумышленника и необходимого уровня стойкости системы. Можно использовать метод преобразования (key crunching) легко запоминающихся фраз в псевдослучайный ключ с помощью каких-нибудь процедур (хэш-функций).

Хорошие ключи - это случайные равновероятные строки в некотором алфавите, поэтому для их получения используются различные генераторы случайных и псевдослучайных последовательностей. Это целая тема в криптографии, требующая отдельного рассмотрения [23,40]. В качестве примера можно привести метод генерации ключей, содержащийся в американском стандарте ANSI X.9.17.

Если обозначить через преобразование зашифрования блока открытого текста M на ключе k (в стандарте, то генерация ключей определяется по следующему правилу

, i = 0, 1,…,

, i = 0, 1,…,

где - начальный секретный вектор, а - время выработки i-го ключа в двоичном представлении.

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

Следует также учитывать, что некоторые криптоалгоритмы могут иметь «слабые» ключи, которые менее безопасны, чем другие. Например, алгоритм des имеет 16 таких ключей. Поэтому нужно при генерации ключей предусмотреть контроль за появлением слабых ключей.

Распределение ключей. Это центральная проблема при управлении ключами.

В случае симметричных криптосистем эта проблема решается следующими способами. Наиболее известным способом является создание секретного канала передачи ключей удаленным пользователям с помощью курьерской службы. Недостатками такого способа являются его высокая цена, невысокая скорость. Особенно это проявляется при большом числе пользователей. Например, число различных парных ключей для секретной связи n пользователей равно N(N-1)/2. К тому же передачу секретной информации с помощью курьера трудно назвать полностью безопасной. Всегда остаются сомнения, не были ли ключи украдены (списаны) или подменены во время доставки. Можно использовать при этом некоторые аппаратные средства для исключения доступа курьера к данным.

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

Существует целый ряд способов распределения ключей, использующих центр(ы) доверия (или центр распределения ключей -ЦРК). Это дает возможность сократить число необходимых ключей, так как не каждому из пользователей сети надо секретно взаимодействовать с каждым, что приводит к необходимости установления секретной связи между каждым пользователем и центром. Однако центр доверия становится основной мишенью для злоумышленника, так как имеет доступ ко всем ключам пользователей системы. Иногда на практике трудно найти третью, незаинтересованную сторону, пользующуюся доверием всех пользователей. Недостатком включения центров доверия является также то, что возникают колоссальные нагрузки на эти центры по генерации ключей и взаимодействию со многими пользователями одновременно, что снижает надежность и оперативность секретной связи.

Приведем пример протокола распределения ключей с использованием симметричной криптосистемы и центра распределения ключей из работы [56].

1. ЦРК вырабатывает и передает по защищенному каналу долговременные ключи каждому пользователю системы для связи с ЦРК.

2. Когда пользователь а желает установить секретную связь с пользователем B, он посылает запрос в ЦРК с требованием секретного сеансового ключа для связи с пользователем B.

3. ЦРК вырабатывает сеансовый ключ , зашифровывает его два раза на долговременных ключах и вместе с идентифицирующей пользователей информацией и случайно выбранными добавками, чтобы исключить совпадения обоих открытых текстов и рассылает соответствующие шифртексты пользователям A и B.

4. Пользователи A и B расшифровывают поступившие шифртексты и получают сеансовый ключ.

Для полноты приведем трехэтапный протокол Шамира с коммутативным преобразованием зашифрования, для которого

,

при любом открытом тексте M.

При этом предполагается, что канал связи не позволяет осуществить злоумышленнику имитацию или подмену сообщения. В качестве шифрсистемы для реализации этого протокола Месси (Massey), и независимо Омура (Omura d.), предложил систему, где преобразование зашифрования и расшифрования имело вид

,

где p - простое число, e и d - секретные ключи зашифрования и расшифрования, положительные целые числа, такие, что , НОД(e, p-1)=1, .

Итак, если пользователь A желает послать секретную информацию M (ключ или открытое сообщение) пользователю B, то необходимо сделать следующее:

1. Пользователь A посылает пользователю B сообщение.

Это сообщение ничего не дает для B, так как он не знает ключ расшифрования пользователя A. Для нахождения злоумышленник, наблюдающий должен в лучшем для него случае определить , решая задачу нахождения дискретного логарифма в предположении, что ему известен открытый текст M. Отсюда дополнительные требования к числу p-1 , оно, например, должно содержать большой простой делитель.

2. Пользователь B вычисляет и посылает пользователю A. На этом этапе злоумышленник может попытаться найти как .

3. Наконец, пользователь A вычисляет (по теореме Ферма) и посылает пользователю .

4. Пользователь B находит секретную информацию M с помощью возведения . Заметим что, получив сообщение M пользователь B также может попытаться найти секретный ключ из , но это для него вычислительно трудная задача. Аналогично A не может найти .

Если канал связи не обладает приведенными выше свойствами, обеспечивающими подлинность передаваемых сообщений, то злоумышленник G может выдать себя за пользователя B и послать вместо сообщение и определить далее сообщение M из сообщения .

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

Протокол обмена сеансовых ключей между A и B может быть следующим.

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

2. Пользователь B расшифровывает полученное от а сообщение с помощью своего секретного ключа и получает сеансовый ключ .

Ключ может быть ключом для симметричной криптосистемы, скорость работы которой выше, чем у криптосистем с открытым ключом (гибридные системы).

В этом протоколе открытый ключ должен быть защищен от подмены, иначе злоумышленник может заменить его на свой ключ , и пользователь а передает сеансовый ключ в сообщении ему (man-in-the-middle attack). В работе [114] предложен протокол, не позволяющий противнику, контролирующему открытый канал между A и B, получить доступ к ключу .

1. Пользователи A и B обмениваются своими открытыми ключами и

2. Пользователь а зашифровывает вое сообщение на открытом ключе , . Посылает половину зашифрованного сообщения (1) пользователю B.

3. Пользователь B зашифровывает свое сообщение на ключе и посылает половину (1) пользователю а.

4. A посылает другую половину (2) пользователю B.

5. Пользователь B расшифровывает обе части (1) и (2) на своем секретном ключе . В случае получения осмысленного значения он посылает другую половину своего зашифрованного сообщения (2) пользователю A.

6. а расшифровывает обе части (1) и (2) на своем секретном ключе .

Пользователи A и B не могут прочитать направленные им сообщения соответственно до шага 5 и 6. Злоумышленник может подставить свои открытые ключи на шаге I. Но теперь, получив половину сообщения (1) на шаге 2, он не может в силу этого получить с помощью своего секретного ключа и перешифровать его с помощью открытого ключа . Он вынужден создавать новое сообщение , шифровать его с помощью и посылать половину его B. Аналогично обстоит для противника дело с половиной сообщения от B. Наконец, он получает вторые половины реальных сообщений на шаге 4 и 5, но это слишком поздно, чтобы заменить новые сообщения на те, которые он желает.

Ранее был рассмотрен протокол ключевого обмена Диффи и Хеллмана, требующий также подтверждения подлинности передаваемых сообщений. Для него также справедливо все сказанное выше по поводу возможной подмены злоумышленником этих сообщений и противодействия этому [114].

В целом ряде работ [47,48] содержатся протоколы обмена ключами с подтверждением подлинности отправителя.

2.10 Криптографические хэш-функции. Аутентификация.

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

Криптографические хэш-функции подразделяются на два класса: с ключом и без ключа. Значение хэш-функции с ключом может вычислить лишь тот, кто знает некоторый секретный параметр - ключ. Часто в литературе [102] они называются кодами аутентификации сообщений (MAC - Message Authentication Code), видимо, по широко известному примеру такой функции, описанному в стандарте FIPS PUB 113-1985[39]. Российским аналогом этого американского стандарта может служить режим имитовставки в стандарте ГОСТ 28147-89.

Хэш-функцией с ключом (зависящей от ключа) называется функция, имеющая следующие свойства.

1. Описание функции H(k,x) должно быть открыто, а секретная информация должна содержаться только в выборе ключа k (правило Керкхоффса).

2. Аргумент х функции H(k,x) может быть строкой чисел произвольной длины, а значение функции должно быть строкой чисел фиксированной длины.

3. При любых данных k и х вычисление H(k,x) должно быть быстрым (за полиномиальное время).

4. По любому данному х должно быть трудно угадать значение H(k,x) с вероятностью большей, чем 1/2:^n, где n - число бит в выходной строке. Должно быть трудно определить ключ k даже по большому числу известных пар при выбранных криптоаналитиком входах (adaptive chosen text attack) или вычислить по этой информации H(k,x') для любого .

В стандарте FIPS PUB 113-1985 хэш-функция с ключом построена на основе блочного стандарта шифрования des с ключом из 56 бит. В качестве аргумента функции выступает открытый текст и , разбитый на 64 битовых блока, которые преобразуются по правилу (cfb)

, ,

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

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

В работе [103] предложена хэш-функция на основе поточной криптосистемы, двоичная гамма которой управляет поступлением битов открытого текста как входного воздействия на два неавтономных регистра сдвига. Значение функции определяется конечным состоянием регистров сдвига. Это очень быстрый способ вычисления хэш-функции.

Хэш-функция без ключа, иногда называется кодом определения манипуляции (MDC - Manipulation Detection Code). Такие функции в свою очередь подразделяются на два подкласса: слабые(weak) односторонние хэш-функции и сильные (strong) односторонние хэш-функции. Дадим их определение.

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

1. Аргумент х функции может быть строкой чисел произвольного размера.

2. Значение функции H(х) представляет собой строку чисел фиксированного размера.

3. Значение функции H(х) легко вычисляется (в полиномиальное время).

4. Почти для всех у вычислительно невозможно найти такое х, что Н(х) = у .

5. Для любого фиксированного х вычислительно невозможно найти другое х х', такое, что H(х') = H(х). Такое событие называется коллизией (collision).

Свойства (3) и (4) утверждают, что H является однонаправленной функцией. Последнее свойство (5) сильнее, чем (4). Заметим также, что по свойствам (I) и (2) коллизии должны существовать, однако свойство (5) требует, чтобы найти их было вычислительно невозможно.

Однонаправленной сильной хэш-функцией называется функция H(х), удовлетворяющая свойствам (1)-(4) предыдущего определения, а свойство (5) имеет вид:

5. Вычислительно невозможно найти любую пару аргументов функции х х', такую, что H(х') = H(х).

Оба определения предполагают, что описание функции H(х) открыто (правило Керкхоффса).

Хотя последние два определения похожи друг на друга, но с вычислительной точки зрения они разные. Для пояснения этого приведем пример из работы [82]. Пусть H - является хэш-функцией с n-битовым выходом. И пусть криптоаналитик желает найти для фиксированного сообщения M другое сообщение M', такое, что H(M) = H(M'). Предполагая, что возможных выходов функции H появляются случайно при опробовании входа, то любой кандидат м' имеет вероятность только дать тот же выход H(М). Если опробовано N кандидатов, то вероятность того, что хотя бы один вариант даст равенство H(M) = H(M'), есть .

При n = 80, N = 2⁶⁰= 10¹⁸, коллизия найдется с вероятностью 10¹⁶. То есть H(х) безопасная хэш-функция в смысле свойства (5). Опробование n вариантов входа функции H можно сравнить со случайным бросанием дробинок в = m ящиков, соответствующих возможным значениям функции H. Общее число способов размещения N дробинок в m ящиков равно (каждая из m дробинок может попасть в любой из N ящиков). Чтобы ни одна пара дробинок не попала в один ящик, первая может быть помещена в любой ящик, вторая может попасть в любой из (m-1) оставшихся ящиков, третья в любой из (m-2) ящиков, … и так далее. Вероятность отсутствия коллизий есть

m(m-1)... , а вероятность, по крайней мере, одной коллизии есть

.

Можно показать, что при m >N > (2 с m)^l/2 вероятность

Р (m,n) > . Откуда при вероятность p(m,N)>1/2.

При n = 80, вычисление вариантов хода даст, по крайней мере, одну коллизию с вероятностью > 1/2 и H не является безопасной в смысле свойства (5').

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

Применение криптографических хэш-функций исключительно разнообразно.

Одно из основных применений они находят в реализациях схем цифровой подписи. Впервые идея такого применения была высказана в работе [19] (Davies, Price). Это значительно ускоряет процесс подписи документа, когда его данные сжимаются в короткий отрезок с помощью односторонней хэш-функций (как правило, без ключа) и только к этому отрезку применяется преобразование цифровой подписи. К тому же, сам процесс подписи и проверки подписи значительно медленнее, чем процесс симметричного шифрования или хэширования. Размеры входа алгоритма цифровой подписи и выхода алгоритма вычисления функции хэширования должны быть, естественно, согласованы. Кроме того, сами эти алгоритмы также должны быть проанализированы совместно, чтобы не ослабить друг друга[59], как это было со схемой цифровой подписи rsa и алгоритмом хэширования, также использующим модульное экспоненцирование. Так. к существующим стандартам цифровой подписи DSS, ГОСТ P 34.10-94, ГОСТ Р 34.10-2001 разработаны соответствующие стандарты на функцию хэширования shs (secure Hash Standard) [108] и ГОСТ Р 34.11-94. В отличие от схем цифровой подписи, эти функции хэширования DSS и ГОСТ отличаются друг от друга существенным образом, поэтому будут рассмотрены далее отдельно.

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

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

Если используется хэш-функция с ключом (MAC), то простейший способ защиты подлинности сообщения - это вычисление значений этой функции и добавление его к сообщению. Подлинность информации здесь зависит теперь от секретности и подлинности ключа аутентификации и может быть проверена каждым, кто знает этот ключ. Значения хэш-функций на практике часто передаются по медленным, но обеспечивающим аутентичность и/или секретность каналам, таким как телефонная линия или почтовая связь (с узнаванием голоса или с обычной рукописной подписью). Участники связи должны полностью доверять друг другу. Даже если ключи не попадут к какому-нибудь стороннему злоумышленнику, все равно есть возможность кому-то из законных участников отказаться от посланного сообщения или заявить, что не получал другого сообщения. Лучший способ преодолеть это - использование цифровой подписи.

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

Есть отличие в выборе слабой или сильной хэш-функций в зависимости от модели предполагаемого противника. Если это один из законных пользователей, то он может попытаться найти пару сообщений M M' и H(M) = H(M'), послать сначала M и H(M), но позднее извлекать преимущества из знания м'. Поэтому, чтобы избежать этой атаки, хэш-функция должна быть сильной. Если злоумышленник не является законным пользователем системы связи, и он может только наблюдать значения M и H(M), то его задача найти M' такое, что H(M) = H(M'). Чтобы противостоять этой атаке, достаточно слабой хэш-функции. Разработка слабых хэш-функций проще, да и значений таких хэш-функций может быть меньше.

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

Наиболее простой способ обеспечения подлинности и секретности - это вычисление , добавление его к открытому тексту и зашифрование всей информации:

.

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

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

Раздел 3. Стандартизация криптографических методов

3.1 Организации, разрабатывающие стандарты по криптологии

В мире существует достаточно много организаций по стандартизации методов защиты информации или их использования в информационных технологиях.

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

США

ANSI (American National Standards Institute) - Американский

национальный институт стандартов. (В скобках указывается точный английский эквивалент, чтобы не зависеть от перевода.) Занимается вопросами по электронному обмену данных (EDI

Electronic Date Interchange), банковскому делу, безопасности

взаимосвязи открытых систем (OSI - Open systems interconnection). Все стандарты этой организации имеют номера, начинающиеся с буквы X.

IEEE (Institute of Electrical and Electronic Engineers),

Институт инженеров по электронике и радиоэлектронике. Занимается безопасностью локальных сетей связи (LAN - Loca/AreaMetwork) и другими вопросами.

NIST (National Institute for Standards and Technology), Национальный институт по стандартам и вычислительной технике. До 1988 года ОН назывался NBS (National Bureau of Standards)

Национальное бюро стандартов. Это подразделение Министерства торговли США. В 1987 году Конгресс принял Закон о защите ЭВМ (computer security Act), согласно которому ответственность за стандарты, касающиеся ЭВМ и соответствующих систем связи, возлагались на nbs-nist. Институт выпустил целый ряд стандартов (Federal Information Processing Standards - FIPS), включая известный DES (Data Encryption Standard).

US/Pod (Department of Defense) - Министерство oбороны США также занимается разработкой своих стандартов.

NCSC (US National Computer Security Center) - Национальный институт компьютерной безопасности США (отделение nsa. см. далее). Под эгидой этой организации выпущены стандарты по оценке безопасности компьютерных систем:

- TCSEC (Trusted Computer System Evaluation Criteria), лучше известный как Оранжевая книга (Orange Book);

TNI (Trusted Network Interpretation) - Красная Книга, интерпретирует Оранжевую книгу для компьютерных сетей;

- TDI (Trusted Database Interpretation) - Gray Book, интерпретирует Оранжевую книгу для баз данных.

NSA (US National Security Agency) - Агентство национальной безопасности США (АНБ). Создано в 1940г. в соответствии с секретной директивой президента Трумэна, по которой в обязанности АНБ вменялись задачи по "разведке в области средств связи" (т.е. перехват, дешифрование криптограмм иностранных государств) и "обеспечению безопасности национальных приемопередающих систем". АНБ находится на передовой научных поисков и разработок в области электронно-вычислительной техники, криптологии. АНБ субсидирует многочисленные исследования по интересующей его тематике, проводит активную политику и в разработке и принятии стандартов. Этому способствует и меморандум о взаимопонимании (Memorandum of Understanding) между NSA и NIST. Именно NSA влияло на выбор параметров для des, на разработку принципов стандарта контролируемого шифрования.

АВА (American Bankers Assot1 at ion) - Американская ассоциация банкиров, разрабатывает стандарты использования криптографических методов применительно к банковской практике.

Европа

CEM/CEHELEC (European Comrltte for Standardization), Европейский комитет по стандартизации (Аналог ISO и IES, см. далее).

ETSI (European Telecommunications Standard Institute)

Европейский институт стандартов в телекоммуникациях.

ITAEGV (Information Technology Advisory Expert Group for

Information security). Разрабатывает требования для будущих стандартов.

EUOS (European Workshop for Open Systems) - Европейский симпозиум по открытым системам.

ЕСМА (European Computer Manufactures Association)

Европейская ассоциация производителей компьютерной техники. Работает над безопасностью систем баз данных, безопасностью открытых систем.

UM/EDIFACT Security Joint Working Group (United Nations/Economic and Social Council) - объединенная рабочая группа по безопасности электронного обмена данными (edi -Electronic Date Interchange).

CCITT (International Telegraphy and Telephone Consultative

Committee) - Международный консультативный комитет по телеграфии и телефонии. Занимается вопросами обмена данными, является частью международного союза телекоммуникации (international Telecommunication Union - itu) в ООН. Стандарты, разработанные комитетом, носят рекомендательной характер и пересматриваются каждые 4 года. Работа проводится в 17 группах, вопросы безопасности изучаются ГРУППОЙ SG VII (Data Networks).

IEC (International Electronical Commission) - Международная электротехническая комиссия.

ISO (International Standards Organization) - Международная организация по стандартизации. Включает организации стандартизации около ста стран мира. Работа внутри ISO ведется техническими комитетами (Technical committee - TC), которые учреждают подкомитеты (Subcomm. Hees - SC). Подкомитеты в свою очередь разбиты на рабочие группы (Working Groups - hg), некоторые из которых - специальные рабочие группы (Special working group - swg) находятся на уровне подкомитетов. Документ проходит следующие стадии разработки.

- NP (Hew Work item proposal) - Предложение по новой теме работы;

- wd (Working Draft) - Проект рабочей группы;

- CD (Committee Draft) - Проект комитета;

DIS (Draft International Standard) - Проект международного стандарта;

- ISC (International Standard) - Международный Стандарт.

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

ISO и IES объединяют свою работу в рамках Объединенного технического комитета YTC1 - "Информационная технология" ("information Technology"). Этот комитет подразделяется на несколько подкомитетов (SC) и рабочих групп (WG), среди которых можно выделить SC610SI Lower Layers), SC17 (Identification Cards), SC18 (Text and Office Systems), SC21 (OSI Architecture, Management, and Upper Layers), SC22 (Languages) и SC27 (Security Techniques).

Работа в SC27 сосредоточена в трех рабочих группах.

UG1 (Requirements, Security Services and Guidelines),

VG2 (Techniques and Mechanisms),

MG3 (Security Evaluation Criteria).

Особо можно выделить технический комитет ISO/TC68 - "Банковское дело и связанные с этим финансовые услуги". (Banking and Related Financial Services).

3.2 Первые варианты стандартов цифровой подписи США и России

Американский стандарт цифровой подписи DSS (Digital signature standard - FIPS 186 и российский его аналог ГОСТ 50 34.10-94 приняты в 1994 году и являются фактически модернизациями схемы цифровой подписи Эль Гамаля. Рассмотрим поэтапно внесенные изменения.

Хотя к настоящему времени были приняты и используются другие стандарты (FIPS 186-3, ГОСТ Р 34.10-2001), но актуальность их не потеряна. Во-первых, надо проверять сейчас ранее подписанные по этим стандартам документы. Во-вторых, эти стандарты лежат в основе новых стандартов, а отличие лишь в лежащих в их основе алгебраических группах.

Быстродействие процедуры подписи и проверки подписи в схеме Эль Гамаля определяется числом операций возведения в степень, которая является наиболее трудоемкой. В классическом варианте схемы необходимо выполнить соответственно одно и три возведения в степень по модулю простого числа р. Схему можно модернизировать так, что при проверке вместо трех возведений будут выполняться два, используя при этом данное проверяющему число , полученное при подписи.

Для этого в сравнении нужно поменять один знак и рассмотреть сравнение , из которого следует, что при подписывании величина S будет вычисляться по формуле , асравнение будет определять проверочное соотношение

,

для вычисления правой части которого требуются только два возведения.

Однако теперь появилось новое дополнительное требование, необходимо существование обратного элемента по модулю (p-1), т.е. чтобы S и (p-1) были бы взаимно просты. Конечно, это можно учитывать в процедуре подписи и выбирать k так, чтобы помимо требования (k, p-1) = 1, выполнялось бы .Но это приводило бы к дополнительным пробам и увеличивало бы, хотя и незначительно, время подписи.

Как уже отмечалось выше, для усложнения методов логарифмирования и увеличения стойкости схемы, число (p-1) должно иметь хотя бы один большой простой делитель. Обозначим его через q, а сравнение рассмотрим именно по модулю q. Тогда требование существования обратных элементов k и s отпадает, так как они всегда существуют по модулю простого числа q (если k 0, s 0). При этом величины k и х можно рассматривать по модулю q, а не р.

Существенным в схеме Эль Гамаля является то, что элементы данных (M.r.s), передаваемых проверяющему, связаны линейно, то есть соотношением вида

,

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

Знаки выбраны так, чтобы в проверочных соотношениях не было отрицательных степеней, и они соответственно имели бы вид:

Отсюда видно, как изменятся процедура подписи и проверки при вычислении r и s одним из приведенных шести способов. Так, при (1 и 2 случай) или (3 и 4 случай) при подписи приходится вычислять соответственно или . В случае (5 и 6 случай) этого делать не надо. Вычисление можно также отнести к предварительной работе, когда вырабатывается ключ подписи х. Соответственно, при проверке надо вычислять (1 и 2 случай), (3 и 6 случай) и (4 и 5 случай).

Стандарты США и России соответствуют I и 5 из приведенных случаев соответственно.

Помимо необходимости вычислять , , и необходимо само существование этих обратимых элементов, что гарантируется их взаимной простотой с модулем (p-l) . Проверка взаимной простоты также требует дополнительного времени на подписывание, поэтому естественно гарантировать существование этих обратных элементов за счет выбора в качестве модуля простого числа q, являющегося делителем числа (p-l). В качестве q надо взять наибольший простой делитель числа (p-l), который должен существовать по требованию усложнения методов логарифмирования и увеличения стойкости схемы. При этом произойдет и уменьшение показателя степени, в которую надо возводить числа при проверке подписи, а также уменьшится размер самой подписи, что важно для экономии памяти.

Наконец, в качестве надо взять элемент g порядка q, степени которого {} пробегают все множество чисел {1,...,q-1}, и все проверочное соотношение привести по модулю q, так как левая его часть нам тоже нужна в виде.

Для сравнения американского и российского стандартов цифровой подписи выпишем их параллельно друг другу.

FIPS PUB 186	ГОСТ Р 50 34.10-94
,	или
, имеет порядок q	имеет порядок q
Процедура	подписи
(предварительно найти )

Процедура проверки подписи по

Для полного соответствия предыдущим рассуждениям надо в них вместо сообщения М иметь в виду значение H(M) функции хэширования H. Кроме того, в приведенной таблице опущены для сокращения изложения проверки неравенство , , а также замена Н(М) на 1 в случае в российском стандарте, что необходимо для существования обратного элемента к H(M) по модулю q.

Если проверка неравенств не производится (например, из-за ошибки программиста при реализации проверки), то это позволяет подделать подпись методом из работы [].

Приведенный материал дает возможность показать этапы становления этих стандартов из классической цифровой подписи Эль Гамаля.

3.3 Развитие американских стандартов хэш-функции

Первый американский стандарт хэш-функции (Secure Hash Standard) принят в 1993г. Это был первый стандарт, позже были приняты и другие. Стандарт был разработан на основе алгоритма хэш-функции MD4, предложенного Райвестом [104]. Стандарт содержит описание односторонней функции хэширования без ключа (MDC), преобразующий двоичное сообщение длины меньшей в строку длины 160 бит, называемую хэш-кодом или дайджестом сообщения (message digest). Размер хэш-кода согласован с размером входа алгоритма цифровой подписи DSS (FIPS PUB 186-94).

Приведем основные используемые обозначения и понятия. Словом (word) называется 32-битовая строка, которая может представлять собой и целое число из множества 0,. Наряду с этим рассматриваются и шестнадцатеричные цифры (hex digit) - элементы множества {0,1,...,9,A,...,F}, которые представляют 4-битовые строки (7 = 0111, A = 1010). Наконец, блок (block) - это 512-битовая строка =16 слов.

Символ "⁺" обозначает сложение слов, как чисел по модулю 2³², символы "", "", "", "-", обозначают соответственно побитовое умножение, логическое сложение, сложение по модулю два, логическое отрицание. Через (или х«n) обозначен оператор циклического сдвига слова х на n позиций влево.

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

Сначала производится расширение сообщения (message palling) так, что его длина становится кратна 512. Расширенное сообщение имеет вид:

();.

Последние 64 бита последнего блока содержат значение длины исходного сообщения (отсюда ограничение на длину ).

Размер (a-l) нулевой строки равен минимальному целому числу, при котором 512 делит b + а + 64.

Обозначим через разбиение этого расширенного сообщения на блоки по 512 бит. Для получения значения функции хэширования используются два регистра и Q из 5 разрядов каждый. Разряды содержат 32-битовые слова.

Если обозначить через - состояние

первого регистра H в момент времени i, то оно будет меняться по следующему рекуррентному правилу

,

Начальное состояние имеет вид

Последовательное соединение (конкатенация) заполнении

конечного состояния и является значением хэш-функции. В последнем соотношении "*" обозначает поразрядное сложение по модулю 2³² состояния и вектор-функции , описание которой будет дано далее. Таким образом, получение дайджеста сообщения можно реализовать следующей схемой неавтономного регистра сдвига

Наконец, опишем функцию . Для получения ее значений используется 5-разрядный регистр Q и 16-разрядный регистр W, каждая ячейка памяти которого также содержит слово. Значение функции представляет собой состояние регистра Q после его изменения по следующему рекуррентному правилу за 80 тактов работы.

Здесь

a W(t) получается по линейному рекуррентному соотношению из блока сообщения следующим образом

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

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

К настоящему моменту принят целый ряд американских стандартов хэш - функции с разными размерами хэш-кода от 224 до 512.

SHA-256

Алгоритм SHA-256 работает наподобие алгоритма SHA-1. Функция сжатия алгоритма работает на 512-bit блоке сообщения и 256-bit промежуточном хэш - значении (переменная связи). На самом деле функция сжатия представляет собой алгоритм 256-битного блочного шифра, который шифрует промежуточное значение хэш-функции, используя для этого блок сообщения в качестве ключа.

Обозначения

Все эти операторы действуют на 32-битные слова.

Начальное хэш значение является следующей последовательностью 32-bit слов (которые получаются путем взятия дробных частей квадратных корней первых восьми простых чисел):

Предварительная обработка

Вычисление значения хэш - кода сообщения начинается с подготовки сообщения:

1) Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512. Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Добавление состоит из единицы, за которой следует необходимое количество нулей. К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое и содержит длину исходного сообщения до добавления. Для примера (8bit- ASCII) сообщение “abc” имеет длину 8*3=24 ,тогда дополняя его единичным битом, а затем 448-(24+1)=423 нулевыми битами его длина становится дополненной до 512-битного сообщения

2) Разбиваем сообщение на N 512-битовых блоков M⁽¹⁾, M⁽²⁾,…, M^(N). Первый 32-битовый блок сообщения обозначим как M⁽¹⁾₀, следующий 32-bit блок через M⁽¹⁾₁ и так далее включительно до M⁽¹⁾₁₅ блока. Далее мы используем представление big-endian, так чтобы крайний левый бит являлся старшим.

Основной цикл.

Вычисление хэш - кода продолжается следующим образом:

For i=1 to N (где N=число блоков добавленных в сообщение)

{

Устанавливаем регистры a

Размещено на http://www.allbest.ru/

,b,c,d,e,f,g,h с промежуточным значением хэш-функции (оно равно первоначальному значению хэш-кода, если i=1)



Применяем функцию сжатия

Размещено на http://www.allbest.ru/

алгоритма SHA-256 для обновления регистров a,..,h

For j=0 to 63

{

Основой алгоритма является модуль, состоящий из 64 циклических обработок каждого блока M{i}.

Вычисляем Ch(e,f,g),Maj(a,b,c),?₀(a), ?₁(e),W_j (смотри описание ниже)

}

Вычисляем i

Размещено на http://www.allbest.ru/

-ое промежуточное хэш значение

}

является хэш - кодом М-ого блока.

Описание

Алгоритм SHA-256 использует шесть логических функций, каждая из которых выполняется над 32-битными словами (обозначенные как x,y,z). Результатом каждой функции является 32-битное слово.

Каждая функция определяется следующим образом:

Расширенные блоки сообщения вычисляются как следует ниже через расписание сообщения алгоритма SHA-256:

Последовательность постоянных слов (констант), , используемых в SHA-256 в шестнадцатеричном виде:



Каждая из этих констант является первыми 32-мя битами дробной части кубических корней первых 64-х простых чисел.

Схема работы

Функция сжатия алгоритма SHA-256 приведена ниже

Рис : внутренний шаг функции сжатия C алгоритма SHA-256 где символ означает сложение по .

Усложнение сообщения может быть описано следующим образом:

Рис. регистр для усложнения сообщения SHA-256

Регистры здесь загружены с соответствующими 32-bit блоками

SHA-512

Алгоритм SHA-512 является вариантом SHA-256 который оперирует на восьми 64-битных словах. Сообщение в начале хешируется следующим образом:

1) его длина дополняется таким образом, чтобы длина результата являлась кратной

1024-битам, затем

2) сообщение разбивается на 1024-битные, блоки

Блоки сообщения обрабатываются по одному за раз: Начиная с фиксированного начального значения , последовательно вычисляем где C является функцией сжатия SHA-512,а + означает сложение по . является значением хэш функции для M-ого блока.

Описание алгоритма SHA-512

Функция сжатия алгоритма SHA-512 работает на 1024-битном блоке сообщения и

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

Начальное хэш значение является следующей последовательностью 64-битных слов (которые получаются путем взятия дробной части квадратных корней первых восьми простых чисел):



Предварительная обработка

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

1) Дополняем сообщение обычным способом: Предполагаем, что длина сообщения M в битах есть L. Конец сообщения дополняем единичным битом, и затем k-тыми нулевыми битами, где k является наименьшим неотрицательным решением уравнения L+1+k =896 mod 1024. К полученному добавляем 128-битный блок который равен числу L в двоичном представлении. Для примера (8bit- ASCII) сообщение “abc” имеет длину 8*3=24, тогда дополняя его единичным битом, затем 896-(24+1)=871 нулевыми битами, получим, что его длина станет добавленной до 1024-битного сообщения

Длина добавленного сообщения должна быть кратной 1024 битам.

2) Разбиваем сообщение на N 1024-битных, блоков

Первый 64-битный блок сообщения обозначим как , следующий 64-битный блок через и так далее включительно до блока. Далее мы используем представление big-endian, так чтобы в каждом 64-битном слове крайний левый бит являлся старшим.

Основной цикл

Вычисление хэша продолжается следующим образом:

For i=1 to N (где N=число блоков добавленных в сообщение)

{

Устанавливаем регистры a,b,c,d,e,f,g,h с промежуточным значением хэш функции (оно равно первоначальному значению хэша в тех случаях когда i=1)

Применяем функцию сжатия

Размещено на http://www.allbest.ru/

алгоритма SHA-512 для обновления регистров a,..,h

For j=0 to 79

{

Основой алгоритма является модуль, состоящий из 80 циклических обработок каждого блока M:

Вычисляем Ch(e,f,g),Maj(a,b,c),?₀(a), ?₁(e),W_j (смотри описание ниже)



где Kj-восемьдесят 64-битных констант, каждая из которых является первыми 64-мя битами дробной части кубических корней первых восьмидесяти простых чисел

}

Вычисляем i

Размещено на http://www.allbest.ru/

-ое промежуточное хэш-значение

}

H^(N)=( H^(N)₁, H^(N)₂,…, H^(N)₈) является хэш-кодом М-ого блока.

Описание

Алгоритм SHA-512 использует шесть логических функций, каждая из которых выполняется над 64-битными словами, обозначенными как x,y,z. Результатом каждой функции является 64-битное слово.

Каждая функция определяется следующим образом:



Расширенные блоки сообщения W₀, W₁,…, W₇₉ вычисляются, как следует ниже через расписание сообщения алгоритма SHA-512:

Последовательность постоянных слов (констант), K₀, K₁,…, K₇₉, используемых в SHA-512 в шестнадцатеричном виде:



Каждая из этих констант является первыми 64-мя битами дробной части кубических корней первых 80-ти простых чисел.

Схема работы

Функция сжатия алгоритма SHA-512 провидена ниже

Рис №16: внутренний шаг функции сжатия C алгоритма SHA-512 где символ означает сложение по .

Расписание сообщения может быть описано следующим образом:

Рис : расписание сообщения SHA-512

Регистры здесь загружены с соответствующими блоками W₀, W₁,…, W₁₅.

SHA-384

SHA-384 в точности работает также как и SHA-512 за исключением двух следующих особенностей:

1) начальное значение хэш-функции H⁽⁰⁾ базируется на дробной части квадратных корней первых шестнадцати простых чисел:

2) 384-битный хэш-код получается из левых 384 битов окончательного хэш-кода H(N): H₀^(N) || H₁^(N) || H₂^(N) || H₃^(N) || H₄^(N) || H₅^(N).

3.4 Российский стандарт хэш-функции ГОСТ Р 34.11-94

Стандарт разработан в 1994 году, введен в действие Постановлением Комитета РФ по стандартизации, метрологии и сертификации (Ростехрегулирование - 2008). Описанная в нем хэш-функция h отображает любую последовательность двоичных символов в 256-битовый вектор в зависимости от стартового вектора хэширования Н (тоже вектор размера 256) и таблиц замены П₁,П₂,…,П₈ , используемого алгоритма шифрования по ГОСТ 28147-89 в режиме простой замены [76]. Поэтому в зависимости от протокола использования эта функция хэширования может как зависеть от ключа, так и не зависеть, если указанные ключевые параметры зафиксировать и сделать открытыми (число возможных вариантов (1б¹⁶)⁸). Размер выхода согласуется с входом алгоритма стандарта цифровой подписи ГОСТ Р 34.10-94.

...