Xreferat.com » Рефераты по информатике и программированию » Проблема аутентификации данных и блочные шифры

Проблема аутентификации данных и блочные шифры

height="22" />Проблема аутентификации данных и блочные шифрыПроблема аутентификации данных и блочные шифрыПроблема аутентификации данных и блочные шифрыПроблема аутентификации данных и блочные шифрыПроблема аутентификации данных и блочные шифры       1:         C0(1)                C1(1)                C2(1)                C3(1)        0:    C0(0)    C1(0)   C2(0)    C3(0)    C4(0)    C5(0)    C6(0)   C7(0) Рис. 3. Схема попарного хеширования проверочных             комбинаций при выработке общего ключа             проверки подписи.

Схема попарного хеширова­ния проверочных комбинаций при выработке общего ключа проверки подписи на восемь сообщений при­ведена на рисунке 3.  Так, в схеме на 8 сообщений при передаче сообще­ния №5 (контрольная комбинация выделена рамкой) вместе с его под­писью должны быть переданы кон­трольная комбинация сообщения №4 (C4(0)), общая для сообщений №№6–7 (C3(1)) и общая для сообще­ний №№0–3 (C0(2)), все они выделе­ны на рисунке другим фоном.  При проверке подписи значение  C5(0)  будет вычислено из сообщения и его подписи, а итоговая контрольная комбинация, подлежащая сравнению с эталонной, по следующей формуле:

C=C0(3)=H(C0(2)||H(H(C4(0)||C5(0))||C3(1))).

Номера контрольных комбинаций каждого уровня, которые должны быть переданы вместе с подписью сообщения с номером  i  (0£i<2L), вычисляются по следующей формуле:  Cë (il/)2lûÅ1, l=0,...,L–1, где  xÅ1  означает число, получающееся в результате инвертирования младшего бита в числе  x.

Необходимость отправлять вместе с подписью сообщения дополнительную информацию, нужную для проверки подписи, на самом деле не очень обременительна.  Действительно, в системе на  1024=210  подписей вместе с сообщением и его подписью необходимо дополнительно передавать 10 контрольных комбинаций, а в системе на 1048576=220  подписей – всего  20  комбинаций.  Однако при большом числе подписей, на которые рассчитана система, возникает другая проблема – хранение дополнительных комбинаций, если они рассчитаны предварительно, или их выработка в момент формирования подписи.

Дополнительные контрольные комбинации, которые передаются вместе с подписью и используются при ее проверке, вырабатываются при формировании ключа проверки по ключу подписи и могут храниться в системе и использоваться в момент формирования подписи, либо вычисляться заново в этот момент.  Первый подход предполагает затраты дисковой памяти, так как необходимо хранить  2L+1–2  хэш-комбинаций всех уровней, а второй требует большого объема вычислений в момент формирования подписи.  Можно использовать и компромиссный подход – хранить все хэш-комбинации начиная с некоторого уровня  l*, а комбинации меньшего уровня вычислять при формировании подписи.  В рассмотренной выше схеме подписи на 8 сообщений можно хранить все 14 контрольных комбинаций, используемых при проверки (всего их 15, но самая верхняя не используется), тогда при проверке подписи их не надо будет вычислять заново.  Можно хранить  6  комбинаций начиная с уровня 1 (C0(1), C1(1), C2(1), C3(1), C0(2), C1(2)), тогда при проверке подписи сообщения №5 необходимо будет заново вычислить комбинацию  C4(0), а остальные  (C0(2),C3(1))  взять из «хранилища», и т.д..  Указанный подход позволяет достичь компромисса между быстродействием и требованиям к занимаемому количеству дискового пространства.  Надо отметить, что отказ от хранения комбинаций одного уровня приводит к экономии памяти и росту вычислительных затрат примерно вдвое, то есть зависимость носит экспоненциальный характер.

3.4. Схема цифровой подписи на основе блочного шифра.

Ниже приведены числовые параметры и используемые вспомогательные алгоритмы рассматриваемой схемы цифровой подписи:

EK – алгоритм зашифрования с размером блока данных и ключа  n  и  nK  битов соответственно;

Гm(s,K) – алгоритм выработки  m  битов криптостойкой гаммы с использованием  n-битового вектора начальных параметров (синхропосылки)  s  и  nK–битового ключа  K, представляет собой рекуррентный алгоритм выработки  n-битовых  блоков данных и их последующего зашифрования по алгоритму  EK;

Pm®nK – набор функций расширения  m-битовых блоков данных до  nK-битовых для различных  m  (типично – для кратных  n, меньших  nK);

L – фактор количества подписей (система рассчитана на  N=2L  подписей);

nT – число битов в подписываемых битовых группах, тогда число групп равно .

Ниже изложены алгоритмы схемы подписи:

1. Алгоритм формирования ключей подписи и проверки подписи.

(a) Формирования ключа подписи.

Ключ подписи формируется как  nK-битовый блок данных с помощью аппаратного генератора случайных кодов или криптостойкого программного генератора псевдослучайных кодов  KS=GnT(...).  Биты ключа должны быть независимы и с равной вероятностью принимать оба возможных значения – 0 и 1.

(b) Формирования ключа проверки подписи.  Схема алгоритма формирования ключа проверки подписи изображена на рисунке 4.

Шаг 0. Исходные данные алгоритма –  nK–битовый массив данных  KS – ключ подписи.

Шаг 1. Вычисляем  nG  – количество  nT-битовых групп в подписываемых блоках.

Следующие шаги 2–9 выполняются столько раз, на сколько подписей рассчитана схема, т.е. для каждого номера подписи системы.

Проблема аутентификации данных и блочные шифры      Рис. 4.  Алгоритм выработки      ключа проверки подписи.

Шаг 2. Выработать блок гаммы размером  2nnG  бит с помощью генератора криптостойкой гаммы на ключе  KS  с начальным заполнением  i  (номером подписи) и поместить его в 2nnG–битовый массив X.

Шаг 3. 2nnG–битовый массив  X  интерпретируется как массив из  2nG  n-битовых элементов Xj, X=(X1,X2,...,X2nG),  |Xj|=n,

затем для каждого элемента этого массива вычисляется результат его «односторонней прокрутки»  2nT–1  раз.

Шаг 4. Для массива  X  вычисляется и записывается в блок данных  S  его хэш-код, который является индивидуальной проверочной комбинацией для подписи номер  i.

Следующие шаги 5,6 выполняются количество раз, равное фактору количества подписей  L.

Шаг 5. Если  l  младших бит номера подписи – единицы, переход к шагу 6, иначе – выполнение цикла прекращается и управление передается на шаг 7.

Шаг 6. Текущая хэш-комбинация  S  объединяется c текущей хэш-комбинацией  Dl  уровня  l, и для полученного массива вычисляется хэш–значение, которое становится новой текущей хэш–комбинацией.

Шаг 7. Текущая хэш-комбинация  S  заменяет хэш-комбинацию  Dl  уровня  l.

Шаг 8. Последняя вычисленная при выполнении алгоритма текущая хэш-комбинация  S  и будет являться результатом работы алгоритма – ключом проверки подписи.  Кроме того, в ходе выполнения алгоритма будут последовательно выработаны хэш-комбинации всех уровней от  0  до  L  , 0£l£L, 0£i<2L–l, которые могут храниться в системе и использоваться при формировании подписи.

2. Алгоритм подписи хэш-блока массива данных.

Схема алгоритма подписи хэш-блока массива данных изображена на рисунке 5.

Шаг 0. Исходные данные алгоритма:

T – подписываемый – n-битовый хэш-блок массива данных;

KS – ключ подписи – nK-битовый массив данных;

i – порядковый номер подписи.

Шаг 1. Вычисляем  nG – число  nT-битовых групп в подписываемом n-битном хэш-блоке.

Шаг 2. Выработать блок гаммы размером  2nnG  бит с помощью генератора криптостойкой гаммы на ключе  KS  с начальным заполнением  i  (номером подписи) и поместить его в  2nnG-битовый массив  X.

Шаг 3. 2nnG-битовый массив  X  интерпретируется как массив из  nG  пар  n-битовых элементов X=((X1,X2),...,(X2nG–1,X2nG)),  |Xj|=n,

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

Проблема аутентификации данных и блочные шифры      Рис. 5.  Алгоритм подписи      хэш-кода сообщения.

Шаг 4. К индивидуальной проверочной комбинации последовательно добавляется попарные хэш-комбинации, по одной комбинации с каждого уровня от  0  до  L–1,  которые необходимы при вычислении проверочной комбинации самого верхнего уровня  (L), общей для всех сообщений.  Номер добавляемой комбинации каждого уровня определяется отбрасыванием количества последних бит в номере подписи, равного номеру уровня,  и в инвертировании младшего бита полученного числа.

Шаг 5. В результате получаем цифровую подпись хэш-блока сообщения  S=(X,D), состоящую из массива подписей битовых групп блока  X=(X1,X2,...,X2nG)  и из массива дополнительных проверочных комбинаций  D=(D0,D1,...,DL–1), необходимых для выполнения процедуры проверки подписи и используемых при вычислении попарных проверочных комбинаций.

3. Алгоритм проверки подписи хэш-блока массива данных.

Схема алгоритма проверки подписи хэш-блока массива данных изображена на рисунке 6.

Проблема аутентификации данных и блочные шифры     Рис. 6. Алгоритм проверки      подписи.

Шаг 0. Исходные данные алгоритма:

T – подписанный – n-битовый хэш-блок массива данных;

s – подпись хэш–блока, состоит из массива  X, содержащего  2nG  n-битовых элементов подписи битовых групп, и массива  D, содержащего  L  n-битовых хэш–комбинаций;

i – порядковый номер подписи.

Шаг 1. Вычисляем  nG – число  nT–битовых групп в подписываемом хэш–блоке, имеющем размер  n  бит.

Шаг 2. В соответствии с правилами проверки подписи производится «односторонняя прокрутка» элементов подписи битовых групп, содержащихся в массиве  X, по два элемента на каждую группу.

Шаг 3. Для массива  X  вычисляется и записывается в  S  его хэш-код, который должен быть равен индивидуальной проверочной комбинацией для  i-той подписи.

Следующие шаги 4–6 выполняются количество раз, равное фактору количества подписей  L.

Шаг 4. Производится выбор по значению  l-того бита (нумерация с 0 со стороны младшего бита) номера подписи.

Шаг 5. Если значение бита равно 0, то к коду справа добавляется очередная хэш-комбинация, содержащаяся в подписи, для полученного блока вычисляется хэш-функция, которая замещает предыдущее содержимое  S.

Шаг 6. Если значение бита равно 1, то выполняется то же самое, только хэш-комбинация добавляется к коду слева.

Шаг 7. В конце выполнения алгоритма в  S  содержится код, который должен быть сравнен с ключом проверки подписи, если коды одинаковы, подпись считается верной, иначе – неверной.

Заключение.

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

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

Литература.

1. А.Ю.Винокуров.  ГОСТ не прост...,а очень прост, М., Монитор.–1995.–N1.

2. А.Ю.Винокуров.  Еще раз про ГОСТ., М., Монитор.–1995.–N5.

3. А.Ю.Винокуров.  Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86., Рукопись, 1997.

4. А.Ю.Винокуров.  Как устроен блочный шифр?, Рукопись, 1995.

5. М.Э.Смид, Д.К.Бранстед.  Стандарт шифрования данных: прошлое и будущее. /пер. с англ./ М., Мир, ТИИЭР.–1988.–т.76.–N5.

6. Системы обработки информации.  Защита криптографическая.  Алгоритм криптографического преобразования ГОСТ 28147–89, М., Госстандарт, 1989.

7. Б.В.Березин, П.В.Дорошкевич. Цифровая подпись на основе традиционной криптографии//Защита информации, вып.2.,М.: МП "Ирбис-II",1992.

8. W.Diffie,M.E.Hellman. New Directions in cryptography// IEEE Trans. Inform. Theory, IT-22, vol 6 (Nov. 1976), pp. 644-654.

9. У.Диффи.  Первые десять лет криптографии с открытым ключом. /пер. с англ./ М., Мир, ТИИЭР.–1988.–т.76.–N5.


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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

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

Похожие рефераты: